RSA Cryptosystem

Developed in 1977 by Ron Rivest, Adi Shamir, and Len Adleman at MIT
• Based on modular exponentiation and factorization of large numbers
• In RSA block cipher, plaintext (and ciphertext) are integers between 0 and n-1 for some n
• Typically |n| = 1024 bits
• Means, 𝑛 ≤ 2 1024 or 309 decimal digits
• Encryption:𝐶 = 𝑀𝑒 𝑚𝑜𝑑 𝑛 Decryption: = 𝐶𝑑 𝑚𝑜𝑑 𝑛 • Public Key: (e,n) Private Key: (d)

How to generate RSA parameters ?

Ans. Lets focus on values of e and d first
• Assume n is a composite number
• Means, n = pq where p and q are prime numbers
• ⇒ ∅ 𝑛 = ∅ 𝑝𝑞 = (𝑝 − 1)(𝑞 − 1) • We will show later why n should be composite
• We want M = 𝐶𝑑 𝑚𝑜𝑑 𝑛 or, M = 𝑀 ^ed 𝑚𝑜𝑑 𝑛 • We say above relationship holds, if
𝑒𝑑 𝑚𝑜𝑑 ∅ 𝑛 = 1 • This is equivalent to saying,
𝑒𝑑 ≡ 1 𝑚𝑜𝑑 𝜙 𝑛
or, 𝑑 ≡ 𝑒 ^-1 𝑚𝑜𝑑 𝜙 𝑛 • That is, e and d are multiplicative inverses with respect to 𝑚𝑜𝑑 𝜙 𝑛 • Remember, inverse of e only exists if e is relatively prime to 𝜙 𝑛