RSA Encryption

Date: 04/25/2002 at 21:38:25
From: Haz
Subject: Number theory RSA

The following message is ciphertext:  C=983830091

Its plaintext is a string of some English letters. The plaintext was 
first changed to an integer by the following scheme,

   a -> 01, b -> 02, c -> 03, z -> 26

Then it was encrypted to ciphertext C by using RSA encryption method 
with the public key(e,N) as follows:

   e = 7
   N = 2651733127

You are now asked to decrypt the encrpted message C. to find the 
original plaintext, a string of English letters.

Date: 04/26/2002 at 12:07:49
From: Doctor Paul
Subject: Re: Number theory RSA

You need to find the private exponent d.  This is very hard to do (and
explains why the algorithm is secure) if N is large.  But here, N can
easily be factored by a computer:

N = 71593 * 37039 = p*q

both of the factors are prime.

Then M = phi(N) = (p-1) * (q-1) = 2651624496

Now we want to find d such that

e*d = 1 mod M

that is,

7*d = 1 mod 2651624496

Use the regular Euclidean Algorithm to find gcd(7, 2651624496).  The
answer had better be one - otherwise we can't be sure that a solution
exists.

2651624496 = 7*378803499 + 3
7 = 3*2 + 1
3 = 1*3 + 0

The gcd is the last nonzero remainder, i.e. 1.

Now write this gcd (one) as a linear combination of 2651624496 and 7 
by working back up the tree that we just created:

1 = 7 - 2*3
  = 7 - 2*(2651624496 - 7*378803499)
  = 7*757606999 - 2*2651624496

Thus we have: 

7*757606999 - 2*2651624496 = 1

Now do "mod 2651624496" on both sides to obtain:

7*757606999 = 1 mod 2651624496

Thus d = 757606999

Now we compute:

C^d mod N = 

983830091^757606999 mod 2651733127

Of course, we use modular exponentiation so that the numbers don't 
get too large.

The answer is 211911, which becomes USK.

We check that this is the right answer by noting that if it is in fact 
correct, then 211911^e = C mod N

Computing 211911^e = C mod N gives 983830091 which is the right 
answer.

It seems as if the answer should be "USA" but then the plaintext would 
be

211901

and then C would be

(211901)^7 mod N = 1009910366

and this isn't the value of C that was given to us. So maybe the 
person who converted the phrase USA into a plaintext number made a 
mistake...

I hope this helps.  Please write back if you'd like to talk about this
some more.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/