RSA a milestone in cryptography, was first published by Ron Rivest, Adi Shamir and Leonard Adleman (MIT) in 1977. Their work based heavily on idea of asymmetric public-private key cryptosystem published in 1976 by Whitfield Diffie and Martin Hellman (Stanford).

Here I try to make simple explanation of that cipher (not to pretend I am an expert in subject more to remember myself):

1. Lets take primes  and .
2. Then calculate modulus .
3. Calculate Euler’s totient function – it is equal to amount of positive integers relatively prime to .
   , as there 6 co-prime numbers to 9 : [1, 2, 4, 5, 7, 8]. is kept private.
   – as p and q prime and amount of co-primes is p-1 and q-1.
4. Take such as and gcd( ) = 1. Which means are co-prime.  It will be our public key.
5. Our task at this point to use extended Euclidean algorithm (EEA) to calculate inversion by modulo . Such as :
   1.   mod   . From other side EEA calculates x and y such as
   2. .  Now lets say:
      and and (as they co-prime by definition). Then we have
   3. and after we take modulo on both side and we get:
   4. mod()This x we call d and it represent private key.
      f.e. =3120, =17 then by EEA =2753, 2753*17 mod 3120 = 1
6. –  Public Key.() – private key.
7. Main idea of RSA is   – if you know  or its very hard to find .
8. Encryption : where  and
9. Decryption : (mod n)

As you can see RSA can be used only for encryption of small messages. To encrypt big chunks of data used hybrid schemes. RSA used for encryption of key which will be used by symmetric cipher like IDEA/AES.

By Boris Ivanov