Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

I am having trouble with this problem:

Suppose that you would like to use the RSA system to send the secret message $P$ to a colleague across an insecure line of communication. Assume that you have made public your personal RSA modulus $n_1$, and encryption exponent $a_1$, while keeping your decryption exponent $b_1$ secret, and that your colleague has made public his or her personal RSA modulus $n_2$ and encryption exponent $a_2$, while keeping his decryption exponent $b_2$, secret. Assume also that $n_1>n_2$.

  1. Explain how your message could fail.

I know that $n_1>n_2$ has something to do with the message failing but I am not sure why.

After this, I am wondering how I could devise a method for signing a message that could not fail.

Thank you for your help!

share|improve this question
What do we know about $P$? Could it be larger than $n_2$? And how exactly is the message exchange supposed to be done? (It seems $n_1, a_1, b_1$ are irrelevant...) – TMM Mar 26 '12 at 18:00
My books says: Consider what would happen if P^b1 mod n1 was greater than n2 – John Mar 26 '12 at 18:14
Will you be signing your message? That would require you to first encrypt $P$ using your private key, $b_1$; then encrypt the result using your colleague's encryption exponent $a_1$. That is, you would send $(P^{b_1}\bmod n_1)^{a_2}\bmod n_2$. But if $P^{b_1}\bmod n_1$ is greater than $n_2$, then you "lose" information; your colleague cannot recover $P^{b_1}\bmod n_1$, so the message would "fail": the colleague cannot find out what you sent. – Arturo Magidin Mar 26 '12 at 18:30
Ah I see! Is there away around this? How can we make it no fail? Just make n2>n1? – John Mar 26 '12 at 18:38
@Ben: You have no control over $n_2$: that's your colleague's modulus. One possibility is to try to make sure that $P^{b_1}\bmod n_1\lt n_2$, by breaking up $P$ appropriately... – Arturo Magidin Mar 26 '12 at 19:09
show 5 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.