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 d ≡ e−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 d⋅e ≡ 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.
0 comments:
Post a Comment