# Cryptoanalysis of RSA

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!

-
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