public key cryptography & rsa Algorithm

RSA:

The most common public key algorithm is RSA, named for its inventors Rivest, Shamir and Adleman(RSA). It uses two numbers, e and d, as the public and private keys.

RSA

Algorithm:

=> Each user generates a public/private key pair by: Selecting two large primes at random - p, q

=> Computing their system modulus N=p*q
=> Note ø(N)=(p-1)(q-1)
=>Selecting at random the encryption key e, where 1<e<ø(N), gcd(e,ø(N))=1
=> To find decryption key d :(e*d)=1 mod ø(N) and 0≤d≤N
=> Publish their public encryption key: KU={e,N}

=> Keep secret private decryption key: KR={d,p,q}

Algorithm with Example:

=> Choose p = 3 and q = 11

=> Compute n = p * q = 3 * 11 = 33

=> Compute k(n) = (p - 1) * (q - 1) = 2 * 10 = 20

=> Choose e, e and n are coprime. Let e = 7

=> Compute a value for d such that (d * e) % k(n) = 1.

One solution is d = 3 [(3 * 7) % 20 = 1]

=> Public key is (e, n) => (7, 33)

=> Private key is (d, n) => (3, 33)

=> The encryption of m = 2 is c = 27 % 33 = 29

=> The decryption of c = 29 is m = 293 % 33 = 2

 

 

 

 

PUBLIC KEY CRYPTOGRAPHY BY MRS.M.SHARMILA BANU & mE.R.JAYABHARATHI