RSA by Prof G.Samid (http://wesecure.net/)

The RSA team was quite impressed with Diffie and Hellman, and the clever idea:

Z = a^XYmod n= (a^X)^Ymod n= (a^Y)^Xmod n They then wondered what will happen if Z=a, namely:

Z = Z^XYmod n= (Z^X)^Ymod n Then one could use Z as a plaintext and designate Z^Xas ciphertext. By so doing X will serve as the encryption key, and Y as the decryption key -- and Diffie and Hellman have already shown that X and Y are not easily mutually derviable!
So now the RSA team needed find a proper n (which we have seen with Diffie and Hellman, should be a large number to insure intractability), and then they need to find two numbers X and Y that will insure that for every possible Z (every possible plaintext) it will hold that: 

Z = Z^XYmod n= (Z^X)^Ymod n.
So how can we find a pair (X,Y) to fit these requirement? Here comes the RSA ingenuity:
They said: let's pick two primes, p and q, and compute n=pq and n'=(p-1)(q-1). Let's pick X such that gcd(X,n')=1, and look for Y such that XY=1 mod n'. This will work because:

Z^XY= Z^kn'+1 because XY=1 mod n implies that for some k we have XY - 1 = kn' and hence:

Z^XY= Z^kn'+1= Z^kn'Z¹ But Z^kn'= 1 because of Euler's theorem since fi(n)=n', and hence:

Z^XY= Z and fi(n)=n' hence: where fi(n) is Euler's function.

Example:
Let us pick two primes: p=5, q=7. We now compute n=pq=35, and compute n`=(p-1)(q-1)=4*6=24. We now pick the encryption key e such that gcd(e,n`)=1. Let`s pick e=7 since gcd(7,24)=1

Next we need to find the decryption key, d. We look for a d such that 7d = 1 mod 24. While this is not very straight forward, there are computational short cuts available. At any rate, this computation has to be carried out once per a pair of keys. We can simply try d=1,2,3,.... and thereby find that for d=31 we have 7*31=217 = 24*9 + 1 = 1 mod 24.

Now we can check if this works. Let`s pick a plaintext M=17, and encrypt it to ciphertext C = 17⁷= 410,338,673 = 11,723,962*35+3 = 3 mod 35.

The recipient will decrypt the ciphertext 3 as follows M=3³¹= 3*(3⁵)⁶. We compute 3⁵= 243 = 33 mod 35 and continue: (33²)³= (1089)³. But 1089 = 4 mod 35, so M = 3*4²= 17 mod 35. So we have encrypted M=17 with encryption key 7 to ciphertext 3, and decrypted 3 back to 17 using decryption key d=31.

We can exchange between the two keys.