Which of the following techniques was ultimately used as the basis of RSA encryption?
 Knapsackbased
 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 oneway 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 "knapsackbased" 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 bitlength 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