RSA Encryption (number-theoretic algorithm)

Public-key encryption.  This means that you make the public key public.  Using your key, people can encrypt messages and send them to you.  You can decrypt the message with the private decryption key, known only to you.

If you want to reply to the message, you use the other guy's public encryption key.  And then the other guy uses their decryption key to decrypt your message.

There are other public key encryption algorithms now, but RSA is the one that started it all.

It's based on prime numbers.

How do you tell whether a number is prime?  Brute force is the common way.  There is presently an n^12 algorithm (on the number of digits in the number to determine whether a number is prime.)  Prior to the AKS algorithm, we had "probable prime" testing, where you can tell (quickly) whether a number is "probably prime" with 99.9% accuracy or whatever you needed.  You use this to discover very large prime numbers.  100 digits or more.  You need two of these very large primes.  (There are some heuristics there.  The primes should both be large (don't throw 97 in there), but the primes shouldn't be close together either.

You multiply these primes together to get an encryption number n = pq (p and q are the primes).  You know what p and q are because you found them first, but when you make n public, the public doesn't know what p and q are.  They would have to factor n to do this.

[Sucky way to do it.  (p-1)!+1 is divisible by p iff p is prime (or if p is 1).  4!+1 is 25, and divisible by 5.  6!+1 is 721, divisible by 7.  5!+1 is 121 and not divisible by 6.

And so far, prime factorization is still unknown to have a polynomial-time solution.  The best known way to factor a number is the tried-and-true trial and error algorithm.  Try primes up to the square root of n to see if you found a factor.  Should there ever be discovered an algorithm that efficiently factors a number, this would break RSA.

You also need to choose and e such that e and phi(n) are relatively prime.  So what is phi(n)?

phi(n) is the number of positive integers less than n that have no factors in common with n (other than 1) (numbers relatively prime to n).

So, phi(4) = 2, because 1 and 3 have no factor in common with 4.
Phi (10) = 4, because we have 1, 3, 7, and 9.
Phi(9) = 6:  1,2,4,5,7,8
Phi(7) = 6:  1,2,3,4,5,6
Phi(11) = 10
Phi(113) = 112.
Phi (p) = p-1, p is prime.
Phi(pq) = (p-1)(q-1), p and q are both prime.

Phi(p^n) = (p-1) *  p^(n-1), p prime
Phi(9) = phi(3^2) = 2 * 3^1 = 6.
Phi(81) = Phi(3^4) = 2 * 3^3 = 2*27 = 54.
If m and n are relatively prime,
Phi(mn) = phi(m) * phi (n).

Phi(100) = Phi(2^2) * phi(5^2).
= 1*2^1 * 4*5^1 = 2*20 = 40.

So, we have chosen two primes p, q, and we have n=pq.  Phi(n) = (p-1)(q-1).  Once again, the only real way we know to compute Phi(n) is to break n up into primes.

Here is a theorem from number theory.

If (e*d) % phi(n) = 1.  [provided that n is square-free, meaning that n is not divisible by the square of any prime]

Then  M^(e*d)%n = M.  [M < n, obviously].

We're using two variables because e is used for encryption and d is used for decryption.  You and you have the d value.  But you make n and e public.

So, if someone wants to send you a message, they break the message up (or interpret the message as) a sequence of numbers (possibly very large) less than n.

Then, for each number in the sequence, they compute M^e % n.  And they send you all those numbers.

Now, you have the d (and only you have the d).  You take all the numbers they send you and compute N^d % n.  Since N = M^e % n, you have just computed (M^e)^d % n = M^(e*d) % n = M, so you get the message back.

You find two large primes, p and q.  You multiply them together to get n.
You find e such that e and phi(n) relatively prime.  (You need to be able to compute phi(n) to do this).
You then find d so that (e*d) % phi(n) = 1.

YOU know what phi(n) is:  it's (p-1)*(q-1).  But nobody else knows what phi(n) is.  So, you can compute d easily.  But nobody else can, unless they first factor n to get p and q, and are then able to compute phi(n).

So, you alone have the decrypt key.

How do you compute M^e % n?  This is a surprisingly simple algorithm, even for very large numbers.  (I myself learned it in grade school.)

Computing M^e is ridiculous because the numbers are mondo huge, but computing M^e % n is surprisingly easy and the numbers never get too large.

Give me two primes:  101, 113, now 101*113= 11413.

42 96 83
+9  +8  + 6
23 %11 = 1.

4 2 9 6 8 3
  -1   1

20+8+54+12+24+3
6+1+5+5+3+3