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: