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

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...

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search