RSA - explained. Part 1.

Originally published 2016-12-28 · Boris Ivanov

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 Eulers 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