Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/