[Ghoser777]

This is a mathematics question really. I'm writing my own simple encryption procedures, and all is well except for performing digital signatures. Here's an example to illustrate my problem.

Let's say you have Alice and Bob (original) and they make the following simple choices for the public-private key encryption scheme:

Alice
mod = 3*17 = 51
phi = 2*16 = 32
public key = 7
private key = 23

Bob
mod = 5*11 = 55
phi = 4*10 = 40
public key = 13
private key = 37

Now, Bob wants to send the number 3 as a digitally signed message to Alice. So the order of steps is:
Bob encrypts with private key (37,55)
Bob encrypts with Alice's public key (7,51)
Send message
Alice decrypts with private key (23, 51)
Alice decrypts with Bob's public key (13,55)

Now here is the problem I'm running into:
When you encrypt 3 with Bob's private key, you get the number 53. When you encrypt with Alice's public key and then decrypt with Alice's private key, you will get a number that is less than 53 (as her modulus is 51). This is a problem! For the last step to work, decrypting with Bob's public key, the data that should be inputted has to be 53 or it won't work.

The issue as I see it is that the sender has a modulus that is bigger than the receiver... and I'm not sure how to work around it! Any good ideas?

[numero]

If your public key is e=7, n=51, then your message M must be less than n. If your n isn't large enough then you need to go back and select larger values for your p and q.

I think your example is also leading you down a wrong path. I'm no expert in RSA, but I don't think you want to be double encrypting the message. Single encryption is fine. If you need to verify the source of a message then do it through signing.

* * *
Taken from Wikipedia
RSA - Wikipedia, the free encyclopedia
Suppose Alice wishes to send a signed message to Bob. She produces a hash value of the message, raises it to the power of d mod n (as she does when decrypting a message), and attaches it as a "signature" to the message. When Bob receives the signed message, he raises the signature to the power of e mod n (as he does when encrypting a message), and compares the resulting hash value with the message's actual hash value. If the two agree, he knows that the author of the message was in possession of Alice's secret key, and that the message has not been tampered with since.
* * *
-numero

[Ghoser777]

The problem isn't really with p and q (you could use arbitrarily large values for p and q and have the same problem). My crypto program was having issues with data as small as 3 for p's and q's that were 24 bits long! The solution I found through a friend is to deal with the special case where the sender's modulus is bigger than the receiver's modulus by breaking the number into two smaller numbers that the sender can handle properly and then combine them at the end into the original number.

So in my example, the number 53 would need to be split into two separate numbers 1 and 2 (1*51 + 2 happens to equal 53), encrypt and decrypt with Alice's keys safely (as 1 and 2 are both below 51), then make sure Alice knows to interpret 1 and 2 as 1*51+2 = 53. Viola, transmission is successful.