RSA – explained. Part 1.

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 p and q.
  2. Then calculate modulus n=p \cdot q.
  3. Calculate Euler’s totient function \phi(n) – it is equal to amount of positive integers relatively prime to n.
    \phi(9)=6 , as there 6 co-prime numbers to 9 : [1, 2, 4, 5, 7, 8]. \phi(n) is kept private.
    \phi(n)=\phi(p)\phi(q)=(p-1)(q-1) – as p and q prime and amount of co-primes is p-1 and q-1.
  4. Take e such as 1 < e < \phi(n) and gcd( e, \phi(n) ) = 1. Which means  e, \phi(n) 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 \phi(n). Such as :
    1.  ed\equiv1 mod   \phi(n) . From other side EEA calculates x and y such as
    2. ax + by=gcd(a,b).  Now lets say
      a=e and b=\phi(n) and gcd(e,\phi(n))=1 (as they co-prime by definition). Then we have
    3. ex+\phi(n)y=1 and after we take modulo \phi(n) on both side and we get
    4. ex \equiv 1 mod(\phi(n))This x we call d and it represent private key.
      f.e. \phi(n)=3120, e=17 then by EED d=2753, 2753*17 mod 3120 = 1
  6. (e,n) –  Public Key.(d) – private key.
  7. Main idea of RSA is (m^{e})^{d}\equiv m  mod(n) – if you know e,n or m its very hard to find d.
  8. Encryption : c\equiv m^{e} mod (n) where 0\leq m < n and gcd(m,n)=1
  9. Decryption : c^{d} \equiv (m^{e})^{d}\equiv m (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

Leave a Reply

Your email address will not be published. Required fields are marked *