rsa

Beckwith/Advanced Topics

Some of the Mathematics of RSA

RSA Encryption involves a complex process of selecting large prime numbers and, from them, deriving both public and private keys for encrypting and decrypting. Below is my version of an explanation of some of the mathematics involved:

1. Pick 2 Numbers:
Pick any 2 prime numbers u,v
Example: u = 5, v = 7 (in real RSA, these might be 200-digit numbers!)

2. Multiply:
Multiply u and v and call it r:
r = uv = 5*7 = 35 r = 35 (this number will be made public)

3. Finding Your p’s and q’s:
Find p, q, and s so that pq = s(u-1)(v-1)+1

There is a little dance you have to do here to find p and q:

We have u = 5 and v = 7, so:

pq = s(4)(6) + 1 = 24s + 1

This means, you need to find p and q, so that

pq = s * 24 + 1

(but also: p cannot equal q , p,q cannot equal 1)

Let’s try some s’s out:

s=2: pq = s*24 + 1
pq = 2*24 + 1
pq = 48 + 1
pq = 49
So we would have to have: p = 7, q = 7 ---No good, because p=q

s=3: pq = 3*24 + 1
pq = 72 + 1
pq = 73
So we would have to have: p = 73, q = 1 ---No good, q=1

s = 4: pq = 4*24 + 1
pq = 96 + 1
pq = 97
So we would have to have: p = 97, q = 1 ---No good, q=1

s=5: pq = 5*24 + 1
pq = 120 + 1
pq = 121
So we would have to have: p=121, q=1 ---No good, q=1

s=6: pq = 6*24 + 1
pq = 144 + 1
pq = 145
So we would have to have: p = 5, q = 29 ---Jackpot!!!

p IS THE PUBLIC KEY USED TO ENCODE MESSAGES and
q IS THE PRIVATE KEY USED TO DECODE MESSAGES

4. Change Letters to Numbers:
Convert your message using the chart below (these numbers have to have no common factors with R, which is 35, so 5, 7, 14, 15, 20, 21, 25, 28, 30 are out):

 2    3  4   6   8  9  11 12  13  16 17  18  19  22  23  24   ...

 A   B  C  D  E  F  G   H    I     J    K     L   M   N   O   P      ...

Message: HELP H = 11
E = 6
L = 17
P = 23 HELP = 11061723

5. Raise to the p power (this is the “public key” so anyone can do this part to a message):
Raise each 2-digit number to p (which = 5, in our case):

(actually, it would be done to the whole 8-digit number, but that would give a 36-digit number, so we’ll just pretend it gets done to the individual letters)

11⁵ = 161051
6⁵ = 7776
17⁵ = 1419857
23⁵ = 6436343

6. Divide and Make the Remainder the new Code:
Divide each number by r (which = 35, in our case)and take the remainder as the encrypted letter:
161051 / 35 gives a remainder of 16 = K
7776 / 35 “ “ “ “ 6 = E
1419857 / 35 “ “ “ “ 12 = I
6436343 / 35 “ “ “ “ 18 = M

7. To summarize: HELP = 11061723 becomes 16061218 = KEIM

8. To decode the message:
a) Raise each letter number to q:
16²⁹= 1.3937... x 10⁴²
6²⁹= 1.7190... x 10²⁷
12³²⁹= 5.906... x 10³⁷
18²⁹= 8.6007... x 10⁴³

b) Divide by 35 and take the remainder
1.3937... x 10⁴² / 35 gives a remainder of 11 = H
1.7190... x 10²⁷/ 35 gives a remainder of 6 = E
5.906... x 10³⁷/ 35 gives a remainder of 17 = L
8.6007... x 10⁴³/ 35 gives a remainder of 23 = P

9. In order to decrypt a message, someone would need to know the value of q.
But q comes from knowing the 2 prime factors of r (see the beginning of step 3).
For r=35, it is pretty easy to figure out that u=5 and v = 7 and then use (5-1)(7-1) =24 to get q.

But for r = 16,805,483 (a mere 8 digits), it is much more difficult to find that the prime
factors are u = 673 and v = 24,971 and so use 672x24,970=16,779,840 to get q.
*Imagine trying to factor R = 419,649,715,993 into it’s only two factors: 16,805,483 x 24,971
**Imagine trying to factor a number with over 400 digits into it’s only two factors.
***This is what makes RSA encryption so hard to crack and why mathematicians working to find larger prime numbers is essential to it’s working...

Easier RSA summary notes
1. Pick u and v
2. Get r, p, and q
r=uv
pq=s(u-1)(v-1)+1
r and p are made public
3. Raise message to p and divide by r to encrypt
4. Raise encrypted message to q and divide by r to decrypt
5. To find q, you must factor r into u and v
6. u and v will be 200-digit long (or more) prime numbers