Cryptography: RSA

•The RSA scheme is a block cipher in which the plaintext and ciphertext are integers between 0 and n - 1 for some n.

•A typical size for n is 1024 bits, or 309 decimal digits. That is, n is less than 21024.

•Where does the name come from?

Ron Rivest

Adi Shamir

Leonard Adleman

 
 Description of the Algorithm 

•RSA makes use of an expression with exponentials.

–Based on exponentiation in a finite field over integers modulo a prime

•Plaintext is encrypted in blocks, with each block having a binary value less than some number n.

•Block size must be less than or equal to log2(n) + 1; in practice, the block size is i bits, where

2i < n £ 2i+1.

•Encryption and decryption are of the following form, for some plaintext block M and ciphertext block C.

C = Me mod n

M=Cd mod n = (Me)d mod n = Med mod n

•Both sender and receiver must know the value of n.

•The sender knows the value of e, and only the receiver knows the value of d.

•Thus, this is a public-key encryption algorithm with a public key of PU = {e, n} and a private key of PR = {d, n}.

For this algorithm to be satisfactory for public-key encryption, the following requirements must be met.

1.It is possible to find values of e, d, n such that Med mod n = M for all M < n. 


2.It is relatively easy to calculate Me mod n and Cd mod n for all values of M < n. 


3.It is infeasible to determine d given e and n.

●

 

Med mod n = M

•This relationship holds if e and d are multiplicative inverses modulo  Ø (n), where  Ø (n) is the Euler totient function.

For p, q prime, Ø (pq) = (p - 1)(q - 1).

•The relationship between e and d: ed mod Ø (n) = 1

•This is equivalent to saying

ed ≡ 1 mod Ø (n)

d ≡ e-1 mod  Ø (n)

•That is, e and d are multiplicative inverses mod Ø (n).

Essentials Ingredients of RSA

•The private key consists of {d, n} and the public key consists of {e, n}.

•Suppose that user A has published its public key and that user B wishes to send the message M to A.

•Then B calculates C = Me mod n and transmits C.

•On receipt of this cipher-text, user A decrypts by calculating M = Cd mod n.