CS 4803 Computer and Network SecurityAlexandra (Sasha) BoldyrevaRSA function and encryption.1The RSA system. The basics.•Def. Let N,f ! 1 be integers. The RSA function associated to N,f is the function RSAN,f : ZN ' ZN defined by RSAN,f (w) = wf mod N for all w # ZN.•Claim. Let N ! 2 and e,d 󲰉 Z"(N) be integers such that ed $ 1 (mod "(N)). Then the RSA functions RSAN,e and RSAN,d are•both permutations on ZN and•inverses of each other, ie. RSAN,e = RSAN,d and RSAN,d = RSAN,e. •Proof. For any x󲰉ZN , modulo N:• RSAN,d(RSAN,e(x)) 󲰨 (xe)d 󲰨 xed 󲰨 xed mod φ(N) 󲰨 x1 󲰨 x•Similarly, RSAN,e(RSAN,d(y)) 󲰨 y&&&&&%1%1&2•The RSA function associated to N,f can be efficiently computed using MOD-EXP(!,f,N) algorithm.•Hence, RSAN,e(!) is efficiently computable given N,e•RSAN,e(!) = RSAN,d(!) is efficiently computable given N,d•But RSAN,e(!) = RSAN,d(!) is believed hard (without d) for a proper choice of parameters (good for crypto).•Let’s build algorithms that generate RSA parameters.•Claim. There is an O(k2) time algorithm that on inputs !(N), e where e 󲰉 Z"(N) and N < 2k, returns d # Z"(N) satisfying ed $ 1 (mod "(N)). %1%1& &3•The RSA modulus generator:(k)1Return (N, p, q)110 NUMBER-THEORETIC PRIMITIVESDefinition 10.9 A modulus generator with associated security parameter k (where k ≥ 2 is aninteger) is a randomized algorithm that takes no inputs and returns integers N, p, q satisfying:1. p, q are distinct, odd primes2. N = pq3. 2k−1≤ N < 2k(ie. N has bit-length k).An RSA generator with associated security parameter k is a randomized algorithm that takes noinputs and returns a pair ((N, e), (N, p, q, d)) such that the three conditions above are true, and, inaddition,4. e, d ∈ Z∗(p−1)(q−1)5. ed ≡ 1 (mod (p − 1)(q − 1))We call N an RSA modulus, or just modulus. We call e the encryption exponent and d the decryptionexponent.Note that (p − 1)(q − 1) = ϕ(N) is the size of the group Z∗N. So above, e, d are relatively prime tothe order of the group Z∗N. As the above indicates, we are going to restrict attention to numbersN that are the product of two distinct odd primes. Condition (4) for the RSA generator translatesto 1 ≤ e, d < (p − 1)(q − 1) and gcd(e, (p − 1)(q − 1)) = gcd(d, (p − 1)(q − 1)) = 1.For parameter generation to be feasible, the generation algorithm must be efficient. There aremany different possible efficient generators. We illustrate a few.In modulus generation, we usually pick the primes p, q at random, with each being about k/2bits long. The corresponding modulus generator K$modwith associated security parameter k worksas follows:Algorithm K$mod"1← 'k/2( ; "2← )k/2*Repeatp$← {2!1−1, . . . , 2!1− 1} ; q$← {2!2−1, . . . , 2!2− 1}Until the following conditions are all true:– TEST-PRIME(p) = 1 and TEST-PRIME(q) = 1– p += q– 2k−1≤ NN ← pqReturn (N, e), (N, p, q, d)Above, TEST-PRIME denotes an algorithm that takes input an integer and returns 1 or 0. It isdesigned so that, with high probability, the former happens when the input is prime and the latterwhen the input is composite.Sometimes, we may want modulii product of primes having a special form, for example primesp, q such that (p − 1)/2 and (q − 1)/2 are both prime. This corresponds to a different modulusgenerator, which works as above but simply adds, to the list of conditions tested to exit the loop, theconditions TEST-PRIME((p − 1)/2)) = 1 and TEST-PRIME((q − 1)/2)) = 1. There are numerousother possible modulus generators too.An RSA generator, in addition to N, p, q, needs to generate the exponents e, d. There are severaloptions for this. One is to first choose N, p, q, then pick e at random subject to gcd(N, ϕ(N)) =10 NUMBER-THEORETIC PRIMITIVESDefinition 10.9 A modulus generator with associated security parameter k (where k ≥ 2 is aninteger) is a randomized algorithm that takes no inputs and returns integers N, p, q satisfying:1. p, q are distinct, odd primes2. N = pq3. 2k−1≤ N < 2k(ie. N has bit-length k).An RSA generator with associated security parameter k is a randomized algorithm that takes noinputs and returns a pair ((N, e), (N, p, q, d)) such that the three conditions above are true, and, inaddition,4. e, d ∈ Z∗(p−1)(q−1)5. ed ≡ 1 (mod (p − 1)(q − 1))We call N an RSA modulus, or just modulus. We call e the encryption exponent and d the decryptionexponent.Note that (p − 1)(q − 1) = ϕ(N ) is the size of the group Z∗N. So above, e, d are relatively prime tothe order of the group Z∗N. As the above indicates, we are going to restrict attention to numbersN that are the product of two distinct odd primes. Condition (4) for the RSA generator translatesto 1 ≤ e, d < (p − 1)(q − 1) and gcd(e, (p − 1)(q − 1)) = gcd(d, (p − 1)(q − 1)) = 1.For parameter generation to be feasible, the generation algorithm must be efficient. There aremany different possible efficient generators. We illustrate a few.In modulus generation, we usually pick the primes p, q at random, with each being about k/2bits long. The corresponding modulus generator K$modwith associated security parameter k worksas follows:Algorithm K$mod"1← 'k/2( ; "2← )k/2*Repeatp$← {2!1−1, . . . , 2!1− 1} ; q$← {2!2−1, . . . , 2!2− 1}Until the following conditions are all true:– TEST-PRIME(p) = 1 and TEST-PRIME(q) = 1– p += q– 2k−1≤ NN ← pqReturn (N, e), (N, p, q, d)Above, TEST-PRIME denotes an algorithm that takes input an integer and returns 1 or 0. It isdesigned so that, with high probability, the former happens when the input is prime and the latterwhen the input is composite.Sometimes, we may want modulii product of primes having a special form, for example primesp, q such that (p − 1)/2 and (q − 1)/2 are both prime. This corresponds to a different modulusgenerator, which works as above but simply adds, to the list of conditions tested to exit the loop, theconditions TEST-PRIME((p − 1)/2)) = 1 and TEST-PRIME((q − 1)/2)) = 1. There are numerousother possible modulus generators too.An RSA generator, in addition to N, p, q, needs to generate the exponents e, d. There are severaloptions for this. One is to first choose N, p, q, then pick e at random subject to gcd(N, ϕ(N)) =10 NUMBER-THEORETIC PRIMITIVESDefinition 10.9 A modulus generator with associated security parameter k (where k ≥ 2 is aninteger) is a randomized algorithm that takes