RSA-Rivest-Shamir-Adleman:
Introduction
This algorithm is based on the difficulty of factorizing large numbers that have 2 and only 2 factors (Prime numbers). The system works on a public and private key system. The public key is made available to everyone. With this key a user can encrypt data but cannot decrypt it, the only person who can decrypt it is the one who possesses the private key. It is theoretically possible but extremely difficult to generate the private key from the public key, this makes the RSA algorithm a very popular choice in data encryption.
Algorithm
First of all, two large distinct prime numbers p and q must be generated. The product of these, we call n is a component of the public key. It must be large enough such that the numbers p and q cannot be extracted from it – 512 bits at least i.e. numbers greater than 10154. We then generate the encryption key e which must be co-prime to the number m = ϕ(n) = (p − 1)(q − 1).We then create the decryption key d such that de mod m = 1. We now have both the public and private keys.
STEPS:
1)Generate two large random primes, pp and qq, of approximately equal size such that their product n=pqn=pq is of the required bit length, e.g. 1024 bits.
2)Compute n=pqn=pq and ϕ=(p−1)(q−1)ϕ=(p−1)(q−1).
3)Choose an integer ee, 1<e<ϕ1<e<ϕ, such that gcd(e,ϕ)=1gcd(e,ϕ)=1.
4)Compute the secret exponent dd, 1<d<ϕ1<d<ϕ, such that ed≡1modϕed≡1modϕ.
5)The public key is (n,e)(n,e) and the private key (d,p,q)(d,p,q). Keep all the values d, p, q and ϕϕ secret. [Sometimes the private key is written as (n,d)(n,d) because you need the value of n when using d. Other times we might write the key pair as ((N,e),d)((N,e),d).]
- n is known as the modulus.
- e is known as the public exponent or encryption exponent or just the exponent.
- d is known as the secret exponent or decryption exponent.