##
RSA Crypto System

Posted in Cryptography by #care-crew

The RSA Crypto System was released 1978 by Ronald Rivest, Adi Shamir and Leonard Adleman. It is the most known and used public-key-crypto system, so you better learn how it works.

**Preparations**
1) Choose two huge prime numbers: p and q;
2) Calculate: m= p*q;
3) Calculate: w(m)=(p-1)(q-1);//Euler's Function
4) Choose a number e with: gcd(e,w(m)) = 1;
5) Calculate d with: e*d = 1; //in Z/w(m)Z
Fact: Any number x in Z will be: e*d=x*w(m)+1;//Fermat
the **public key pair** is (m,e)
the **private keys** are p,q and d
the alphabet of RSA is Z/mZ

**cipher plain text**
cipher a plain text "x" with: y=x^e in Z/mZ;
The person with knowledge of the private keys can decrypt y.

**decipher cipher text**
decipher y with: (x^e)^d => x^^{ed} in Z/mZ;
This works, because of the "Fact" above.

Published at 2011-10-25, Updated at 2011-10-25

next: Diffie Hellman Key Exchange
prev: Attacking Crypto Systems