# Quiz

## Which of the following techniques was ultimately used as the basis of RSA encryption?

### Which of the following techniques was ultimately used as the basis of RSA encryption?

• Knapsack-based
• Product of primes
• Permutation polynomials
• Group of unknown size

#### EXPLANATION

Ron Rivest, Adi Shamir, and Leonard Adleman ("R.S.A.") at the Massachusetts Institute of Technology made several attempts, over the course of a year, to create a one-way function that was hard to invert. Rivest and Shamir, as computer scientists, proposed many potential functions, while Adleman, as a mathematician, was responsible for finding their weaknesses. They tried many approaches including "knapsack-based" and "permutation polynomials".
The keys for the RSA algorithm are generated the following way:
• Choose two distinct prime numbers p and q.
• For security purposes, the integers p and q should be chosen at random, and should be similar in magnitude but 'differ in length by a few digits' to make factoring harder. Prime integers can be efficiently found using a primality test.
• Compute n = pq.
• n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.
• Compute λ(n) = lcm(λ(p), λ(q)) = lcm(p − 1, q − 1), where λ is Carmichael's totient function. This value is kept private.
• Choose an integer e such that 1 < e < λ(n) and gcd(e, λ(n)) = 1; i.e., e and λ(n) are coprime.
• Determine d as de−1 (mod λ(n)); i.e., d is the modular multiplicative inverse of e (modulo λ(n)).
• This is more clearly stated as: solve for d given de ≡ 1 (mod λ(n)).
• e having a short bit-length and small Hamming weight results in more efficient encryption – most commonly e = 216 + 1 = 65,537. However, much smaller values of e (such as 3) have been shown to be less secure in some settings.
• e is released as the public key exponent.
• d is kept as the private key exponent.
The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d, which must be kept secret. p, q, and λ(n) must also be kept secret because they can be used to calculate d.

#### SOURCE

https://people.csail.mit.edu/rivest/pubs/ARS03.rivest-slides.pdf

Share: