RSA (Rivest-Shamir-Adleman) Key

Each user generates the pair public/private key.

Randomly generates 2 large prime numbers - p, q.

Calculates the modulus of the system N=p.q.

• ø(N)=(p-1)(q-1)

Selects a random key e

• Where 1<e<ø(N), gcd(e,ø(N))=1 gcd = greatest common divisor.

Solves the equation to find the key and deciphers d.

• e.d=1 mod ø(N) and 0≤d≤N

Publishes the public key: KU={e,N}.

Maintains the private key to decipher: KR={d,p,q}.

Example RSA

1. Selects prime numbers: p=17 & q=11.

2. Calculates n = pq =17×11=187.

3. Calculates ø(n)=(p–1)(q-1)=16×10=160.

4. Selects e : gcd(e,160)=1; chooses e=7

5. Determines d: de=1 mod 160 and d < 160: value is d=23 because 23×7=161= 160+1

6. Publishes public key KU= {e,N}={7,187}.

7. Maintains secret key KR={d,p,q} = {23,17,11}

Use of RSA

To cipher the message M, the sender:

• Obtains a public key of the receiver KU={e,N}.

• Calculates: C=Me mod N, where 0≤M<N.

To decipher C:

• Uses its private key KR={d,p,q}.

• Calculates: M=Cd mod N.

Message M has to be lower than the modulus N

• Message M = 88 (88<N=187).

• Cipher: C = 887 mod 187 = 11 ; e=7.

• Decipher: M = 1123 mod 187 = 88 ; d=23.