ITP4103 Lab 2.3 RSA Calculation

RSA Public and Private Key Setup

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 j(N) = (p-1)(q-1)

•          Selecting at random the encryption key e

•          where 1 < e < j(N), gcd(e, j(N)) = 1

•          Solve following equation to find decryption key d

–         e * d = 1 mod j(N) and 0≤d≤N

–         Fast to do it using Euclid's Algorithm.

•          publish their public encryption key: Pu ={e,N}

•          keep secret private decryption key: Su ={d,p,q}

RSA Encryption and Descryption

•          Encrypt a message M by the sender:

–         Public key of recipient = {e, N}

–         computes: C = M^e mod N

•          Decrypt the ciphertext C by the owner:

–         Private key of recipient = {d, p, q}

–         compute: M = C^d mod N

•          Sign the message M by the owner :

–         Private key of recipient = {d, p, q}

–         compute: S = M^d mod N

•          Verify the signature S by the recipient:

–         Public key of recipient = {e, N}

–         compute: M = S^e mod N

•          Note that the message M must be smaller than the modulus N (block if needed)

Example

If p = 5, q = 11, public key e = 3

1.        What is the private key d?

p = 5 & q = 11
n = pq = 5 * 11 = 55
j(n) = (p-1)(q-1) = (5-1)(11-1) = 40
If e = 3, de = 1 mod 40
Therefore, 1= 3 * 27 mod 40

As a result, the private key d is (27, 5, 11)

2.        If the plaintext M=42, what is the ciphertext?

Therefore, the ciphertext is 3.

3.        What is the digital signature of M?

Therefore, the digital signature is 48.

Tutorial Questions