# I think this question is on congruences and RSA

• Mar 29th 2011, 11:26 AM
ironz
I think this question is on congruences and RSA
I missed a whole load of lectures as I was ill and now I am behind on some work. I am trying to catch up but I have come across this question which I haven't got a clue how to do:

A public key code has base n = 564146777 and encoding exponent a = 282044381.

i) Factorize n and calculate ϕ(n)
ii) Calculate the decoding exponent x (i.e a^(-1) mod ϕ(n) )
iii) Decode the following received message using the letter to number equivalents in the attached table (p4). Each block corresponds to a sequence of one or two letters; thus, since 10 corresponds to A and 11 to B, 1011 stands for AB, etc.

366514996 / 506479715 / 239338918 / 85377691

For part one, I assumed factorizing it meant in terms of its primes and I got n = (45691)(46777) and so I got ϕ(n) to be 564088740.

Then I am completely stuck for part 2. I looked over the lecture notes and I don't have a clue what is going on. Could someone please either show me, or give me a really push (not nudge lol) in the right direction because I am really struggling with this. I am assuming that I should be able to do part 3 if I can do part 2, but if you could give me a tiny hint on how to do that I would much appreciate it.

Thank you very much :)
• Apr 4th 2011, 12:35 AM
Haven
RSA uses Euler's theorem, and the fact that integer factorization generally takes a long time.

If I wish to send you a message, I pick two large primes p and q, and let $\displaystyle n= pq$. The fact that I have these two primes makes calculating $\displaystyle \phi(n)$ very easily. Then I pick an encoding exponent a, such that $\displaystyle (a,\phi(n))=1$. Then I numbers a and n public. You take your message M and send $\displaystyle M^a \pmod{n}$ to me.

Now since I am the only one with access to the prime factorization of n. I can easily calculate b such that $\displaystyle ab \equiv 1 \pmod{\phi(n)}$ which allows me to retrieve your message by performing the following
$\displaystyle (M^a)^b \equiv M^{ab} \equiv M^{k\phi(n)+1} \equiv M^{k\phi(n)}M \equiv M \pmod{n}$
This follows by Euler's theorem. So, calculating $\displaystyle a^{-1} \pmod{n}$. Will give you the "decoding exponent".

And to decode the message above. You just take each block, raise it to the power of $\displaystyle a^{-1}$ and reduce mod n.