The RSA cryptosystem 1. The RSA cryptosystem 1.1 Description Def. A RSA modulus is an integer N of the form p.q, where p, q are two (usually large) prime numbers. In the sequel, we shall often make the abuse of notation that x mod N is the remainder of the Euclidean division of x by N. Setup of the RSA system. Alice : (a) Pick two prime numbers p, q; (b) Compute N = p.q (c) Pick an e such that gcd(e, (p-1)(q-1)) = 1 (d) Compute d = e^{-1} mod (p-1)(q-1) (e) sk_A = (N, d) ; pk_A = (N, e) ; publish pk_A. One RSA session. (a) Bob encodes his message under the form m_1, \dots, m_n, with each m_i a nonnegative integer < N, seen as an element of Z/NZ ; (b) for each i, Bob computes c_i := E(pk_A, m_i) := m_i^{e} \mod N and sends it to Alice (c) for each i, Alice computes m_i := D(sk_A, c_i) := c_i^{d} \mod N (d) Alice puts all the pieces together to get the whole message m. I won't go into too much detail on (a), (d) of the RSA session -- the simplest way (but not the most efficient) to do things would be to write the initial message as a huge integer, and decompose it in base N : M = 100101010010101001001101... => M is an integer M0 in base 2 i = 0 While M0 \neq 0 do m_i = M0 mod N M0 = (M0 - m_i)/N i = i+1 Return [m_0, ...] Getting the other way round uses the formula M0 = \sum_i m_i N^{t-1-i}, where t is the total number of message chunks. 2.2. Soundness and examples. Let's first check that everything is ok. Theorem. This cryptosystem is sound and gives back the message. Proof. Setup : d is defined, as we chose e coprime to (p-1)(q-1) Otherwise all the operations are obviously legitimate. Now, we need to check that D(sk, E(pk, m)) = m. We have D(sk, E(pk, m)) = D(sk, m^e mod N) = (m^e mod N)^d = m^{ed} mod N. As we know that m has to be smaller than N (the domain of E, D is Z/NZ), we just need to prove that m = m^{ed} mod N. We'll actually prove the slightly stronger Claim. Retaining the same notations, given c in Z/NZ, the congruence x^e = c mod N has the unique solution x = c^d mod N. Proof. Let us first prove this with p instead of N. Assume that x^e = c mod p. Then we must have x^{eu} = c^u mod p. Since we have ed = 1 + k(p-1)(q-1) = 1 + k'(p-1), we get x^{ed} = x . x^{k'(p-1)} = x.(x^{(p-1)})^{k'}. Now we split into two cases. * if x is prime to p (x nonzero mod p), then x^(p-1) = 1 mod p and we get x^{ed} = x mod p. * if x is divisible by p, then x = 0 mod p and obviously x^{ed} = x mod p. Overall, in all cases x^{ed} = x mod p and thus x^e = c mod p implies x = x^{ed} mod p = c^d mod p. By symmetry between (c, d) and (x, e), c^d mod p = x implies x^e = c mod p; hence the two statements are equivalent and we get existence + unicity of the solution. Remark. We only used the fact that e.d = 1 mod (p-1) in the proof. We now turn to the general case, which is going to be an easy consequence. x^e = c mod N <=> x^e = c mod p, which in turn <=> that x = c^d mod p. x^e = c mod N <=> x^e = c mod q, which in turn <=> that x = c^d mod q. The Chinese remainder theorem then allows us to combine those two identities to get that x^e = c mod N implies x = c^d mod N. QED. Exercise. The assumption that (e, (p-1)(q-1)) = 1 is key. Otherwise, the mapping x |-> x^e mod N is *not injective* -- we cannot decipher uniquely. Numerical examples. * a prime congruence : Consider the congruence x^{1583} = 4714 mod 7919 (is prime). We have e = 1583. Given the proof above we need to compute d such that ed = 1 mod 7918. Either using the Extended Euclidean algorithm we get d = 5277 mod 7918. Thus we compute x as 4714^5277 mod 7919 = 6059 mod 7919. It is readily checked that 6059^1583 = 4717 mod 7919 Exercise. Define Lambda(N) = lcm((p-1), (q-1)). Prove that if we take d' to be defined by d'.e = 1 mod Lambda(N), we retain all the same properties, with a possibly slightly smaller d'. * an RSA example Take p = 1223 and q = 1987. Then we get N to be 1223 * 1987, which is 2430101. Bob picks e randomly, e = 948047. We check that gcd(e, (p-1)(q-1)) = gcd(948047, 1222*1986) = 1. Bob publishes (N = 2430101, e = 948047) and computes d = 948047^(-1) mod 1222*1986 = 1051235 Alice wants to send the message m = 4289542452947; she computes m0 = m mod N = 1070777 m' = (m - m0)/N = 1765170 m1 = m' mod N = 1765170 m'' = (m' - m1)/N = 0, so she stops there. She computes c0 = m0^948047 mod 2430101 = 1473513 and c1 = m1^948047 mod 2430101 = 793756 and sends [c0, c1] to Bob. Bob computes m0 = c0^d mod N = 1070777, m1 = 1765170 and recovers M as m0 + N*m1 = 4289542452947. 1.2 Usage of RSA The main use of the public key world (including RSA) in practice is basically * as a basic block in advanced protocols; * to establish a "session key" - either Diffie-Hellman (interactive process => TLS, SSL, https), - or if you use GPG to encrypt a message (not interactive), GPG actually picks an Sessk for a private-key cryptosystem E', and sends to Alice E(pk_A, Sessk) || E'(Sessk, message). All further traffic is then encrypted with the fast, private key system. * for signature (overwhelmingly). Here, we use the fact that for RSA, D and E commute. A cryptographic signature is the equivalent of a handwritten one; it associates a message to a user; only this user can produce the signature but anyone should be able to check it. Alice will sign the message m \in Z/NZ by appending sigma_Alice(m) := D(sk_Alice, m) to it; Bob will verify the signature sigma by checking that E(pk_Alice, sigma(m)) = m. In this description the secret key is required to compute the signature, while any user may verify it (only the public key is required) and associate it to Alice (since the public key belongs to Alice). 1.3. Algorithmic issues -- decryption / encryption Let's start with the encryption / decryption issue. cost of (b) : O(log e) operations in Z/NZ (fast powering algorithm). cost of (c) : O(log d) operations in Z/NZ (dito). This analysis suggests an optimization : take e and/or d and/or N small. * e and d small: not possible, because e.d = 1 mod (p-1)(q-1) so that e.d has to be either 1 or >= (p-1)(q-1) ~= N at least -- unless e = d = 1 which is not a very good choice. * altruistic policy: e small => works, but some risks (see later). It is better (and a common choice is) to take e = 257 or 65537, whose binary expansion contains few 1s -- hence the powering algorithm is especially fast as the number of operations it makes is the number of binary digits of e plus the number of ones in the binary expansion. * selfish policy: d small => never do this, this is highly risky. As a rule of thumb, d should be at least N^{1/2}. Attacks are known for d < N^{0.282}. 2. Setup For the setup, we have left a difficult task: finding the primes p, q. We want p, q to be _both_ large -- if one is small, it is easily detected by trial division or another factoring algorithm (p-1, rho) that will be studied later on. Generating primes is thus a fundamental task in the setup of an RSA cryptosystem. As a rule of thumb in algorithmics, when trying to build an element with a given property in a set, we may choose between two approaches: * be smart and try to devise a construction which stumbles directly on an element with the required property; * be stupid, take an element at random until we have one which does the job. Surprisingly the second strategy is often (much) better. It has the further advantage to produce out of the box a _uniform_ element with the desired property (which is often hard to get by the first approach). However, we need two assumptions: (a) the elements are reasonably abundant; (b) we have an efficient way to test the property that we want to obtain. 2.1 The distribution of primes (a): let us model the situation by a box full of white and black balls. We draw a ball at each step; if the ball is black we put it back into the box, if the ball is while we stop and win. How many times are we going to draw a box if the proportion of white balls is alpha \in ]0, 1] ? Obviously Probability(we make one try) = alpha Probability(we make two tries) = (1-alpha).alpha (failure at step 1, success at step 2, the two being independent) Probability(we make three tries) = (1-alpha)^2.alpha (failure at step 1 & 2, success at step 3, the two being independent) etc. Overall, E[number of tries] = \sum_{k \geq 1} k (1 - alpha)^{k-1} alpha. = \alpha \sum_{k \geq 1} k (1 - alpha)^{k-1} Let S_k = -(1 - alpha)^k / alpha ; then (1 - alpha)^(k-1) = S_k - S_{k-1}. Now, \sum_{k \geq 1} k (S_k - S_{k-1}) = \sum_{k\geq 1} kS_k - \sum_{k\geq 1} kS_{k-1} = \sum_{k\geq 1} kS_k - \sum_{k\geq 0} (k+1)S_k = -\sum_{k\geq 0} S_k = 1/alpha (\sum_{k \geq 0} (1 - alpha)^k + 1) = 1/alpha^2 so, overall, E[number of tries] = 1/alpha. The same result could have been obtained (much faster) by using the fact that E(X) = \sum_{k >= 0} Pr(X > k) = \sum_{k >= 0} (1 - alpha)^k. So we want alpha to be not too small [(a)] and the time for each test to be small [(b)] This raises two issues: * we have to find a way to test for primality; * we need to understand, at least roughly, the number of primes <= n -- if it is too small we will fail to produce primes efficiently this way. For the second point, the best known answer is the following: Prime Number Theorem (Hadamard, de la Vallée Poussin, 1896) pi(n) \sim \int_2^n dt / log t \sim n / log n A corollary of this is the "fact" that a random integer n is prime with probability 1/log n -- a more formal statement being that a random integer n uniformly picked from [1, N] is prime with probability O(1/log N) as N -> infty. The proof is long, very difficult, and was a culmination for the time. The equivalent x / log x looks is more tractable but much less precise, as shows the following comparison: pi(n) n/log n \int_2^n dt / log t 10^6 78498 ~72382 ~78626 10^9 50847534 ~48254942 ~50849233 10^12 37607912018 ~36191206825 ~37607950279 10^15 29844570422669 ~28952965460216 ~29844571475286 10^16 279238341033925 ~271434051189532 ~279238344248555 We seem to have 1 digit right with n/log n, vs half the digits right with the integral equivalent. The fact that the error term in the prime number theorem is indeed O(n^{1/2 + epsilon}) for all epsilon is (one of the many forms of) the celebrated Riemann hypothesis, probably one of the most important open questions of number theory and mathematics as a whole. We shall not prove the Prime Number Theorem, but instead the weaker but sufficient: Chebyshev theorem. There is a constant C such that for all sufficiently large x, pi(x) >= C x/log x. Proof. (a) Lemma. Binomial(2m, m) >= 4^m / (2m + 1). Pf. Binomial(2m, k+1) = Binomial(2m, k) (2m - k) / (k+1). Hence Binomial(2m, k+1) > Binomial(2m, k) <=> 2m - k > k + 1 <=> k < m, which shows that the largest binomial coefficient is the middle one. As \sum Binomial(2m, m) = 4^m and there are 2m+1 coefficients, the lemma follows. (b) Lemma. v_p(x!) = \sum_{p\geq 2, k \geq 0} [x/p^k]. Pf. The number of j <= x such that p^t | j but p^{t+1} does not divide j is [x/p^t] - [x/p^{t+1}]. Now, v_p(x!) = \sum_{j <= x} v_p(j) = \sum_t \sum_{j <= x / v_p(j) = t} j Hence, v_p(x!) = \sum [x/p^t] - [x/p^{t+1}]. (c) If p | Binomial(2m, m), then p^{v_p(Binomial(2m, m))} <= 2m. Pf. v_p(Binomial(2m, m)) = \sum_{p, k} [2m / p^k] - 2 [m/p^k] <= log (2m) / log p as [2m / p^k] - 2 [m/p^k] \in {0, 1} and [2m/p^k] = [m / p^k] = 0 for k >= log(2m)/log p. Using (c), we have Binomial(2m, m) = \prod_{p <= 2m} p^v_p(Binomial(2m, m)) <= (2m)^pi(2m). As Binomial(2m, m) >= 4^m / (2m + 1), we deduce pi(2m) >= m log(4)/log(2m) - log(2m + 1)/log(2m) = 2m/log(2m) log 2 (1 + o(1)). Further, pi(2m+1) = pi(2m) + 1 = 1 + 2m/log(2m) log 2 (1 + o(1)). = (2m + 1)/log(2m+1) log 2 (1 + o(1)), from which the Theorem follows. Remark. Note that Binomial(2m, m) <= 4^m and \prod_{p <= 2m} p^v_p(Binomial(2m, m)) >= \prod_{m \leq p \leq 2m} p >= m^{pi(2m) - pi(m)} yields a quick upper bound on pi(2m) - pi(m), from which an upper bound on pi(m) is easily deduced. Replacing Binomial(2m, m) by a suitable mix of factorials yields improved constants. As a consequence of Chebyshev theorem, the average number of tries to produce a prime of k binary digits is of the order of log(2^k) (the box is [2^{k-1}, 2^k[, the white balls are the prime, in number pi(2^k - 1) - pi(2^{k-1} - 1). For typical RSA sizes (2^2048), this means a few thousands of tries before getting an actual prime. 2.2 Primality testing Two different philosophies: (a) compositeness testing: if, looking closely but quickly, it doesn't look like a composite then it ought to be a prime. (b) primality testing: do the hard job of actually proving that N is prime (and, often, loop forever if it is not). The general philosophy of (a) is : use a property of the kind : "if N is prime, then for all a <= N, P_a(N) holds"; thus if one can find some a such that P_a(N) does not hold, we have a proof that N is composite. We say that a is a _compositness witness_ for N. For the sake of completeness : Naive algorithm: trial division by all integers <= \sqrt{N}, yields O(\sqrt{N}) operations of integers <= N. a. The Fermat test. We'll first use "if N is prime, then for a <= N, we have a^N = a mod N". Example. N = 503, a = 2. Then 2^N = 2 mod 503. This is *** NOT A SUFFICIENT CONDITION *** Example: N = 561 : 2^561 = 2 mod 561... yet 3 | 561. Definition. For (a, N) = 1, if a^N \neq a mod N, then a is a compositeness witness (CW) for N for the Fermat test. Prop. If a is a CW for the FT for N, then N is composite. The algorithm is thus: pick a bunch of small or random a's, and if none of them is a CW, then declare that a is likely prime. How many a should we use ? It turns out that there is no good answer: An integer N is a Carmichael number if is has no CW for the FT. Thm. (Alford, Granville, Pomerance). There are infinitely many Carmichael numbers. The smallest is 561. For those numbers, there is very little chance to find randomly a suitable a, and exploring all possible a means an algorithm with complexity at least O(N)... worse than the naive method in O(sqrt(N)). Cost of the Fermat test: O(log N) operations mod N for each value of a. b. The strong pseudo-prime test This test is often credited to Miller and Rabin (mid 70s) in the literature, but this is strongly debatable. Selfridge seems to have at least proposed it earlier, and an old paper by Artjuhov (Acta Arithmetica, 1966, in Russian) describing it was rediscovered in the late 2000s. We are going to refine slightly the Fermat test, to get a much better test. Note that Fermat uses the condition a^N - a = 0 mod N, which is very close to a^{N-1} - 1 = 0 mod N -- actually equivalent if (a, N) = 1. But as N-1 is even, we can factor the latter as (a^{(N-1)/2} - 1)(a^{(N-1)/2} + 1) = 0 mod N ; since N is prime, this means that either a^{(N-1)/2} = 1 or a^{(N-1)/2} = -1 mod N. But we can go further. Assume that v_2(N-1) = k, so that N-1 = 2^s t for some odd t. Then, factoring over and over again gives : Definition. Let N be an odd integer with N-1 = 2^s t; for an a such that (a, N) = 1, we'll say that a is a compositeness witness for N for the SPPT if * a^t \neq \pm 1 mod N ; * a^{2^k t} \neq -1 mod N for all k \in [0, s-1]. Theorem. If a is a compositeness witness for N for the SPPT, then N is composite. Proof. (a^t - 1)(a^t + 1)(a^(2t) + 1)... (a^{2^(k-1)t} + 1) = 0 mod N, but none of the factors of the left hand side is zero. Cost: we start by computing a^t mod N, which costs O((log t)) operations mod N, and then have <= s squaring steps, which cost O(s) operations mod N. overall, O(log(2^s t)) = O((log N)) -- the SPPT is not more expensive than the Fermat test (=> you should only use this one). Theorem (Monier, 1980). Let n be an odd composite number. Then at least 3/4 of the integers between 1 and (n-1) are CW witnesses for the SPPT for n. Proof. Ugly combinatorics + arithmetic, but not conceptually hard. WARNING. This does not mean that if we pick a at random and N passes the SPPT, then N is prime with probability 3/4. Indeed, the event "N is prime" is deterministic once N has been chosen. The correct statement is : if N is composite and a is randomly chosen, the probability of incorrectly declaring N likely prime is <= 1/4. WARNING (2). It is a bit hard to combine such statements. One might get the feeling that if we pick k random values of a, the probability becomes <= (1/4)^k, but this is not exactly true, due to subtle interdependencies; still, this is a rough rule of thumb which is good to keep in mind. In practice, one uses a bunch (20, 50, 100 or so) of random values of a, and declares N prime if N passes the SPPT for all those a. Let's do the example N = 561 again. N - 1 = 560 = 2x280 = 2^2 x 140 = 2^3 x 70 = 2^4 x 35, thus s = 4, t = 35. Let us try a = 2. 2^t = 263 mod N 2^{2t} = 166 mod N 2^{4t} = 67 mod N 2^{8t} = 1 mod N which shows that N cannot be prime as 67 \neq -1 mod N. Example of the full "prime generation process": Let's look for a prime of size 6 digits. We first draw N = 390641. N-1 = 2^4 x 24415 2^24415 = 357928 2^(2*24415) = 174670 2^(4*24415) = 156159 2^(8*24415) = 259497 2^(16*24415) = 388070 => 2 is a CW for the SPPT (and for Fermat too), and N is composite. We draw N = 246165. Obviously 3 and 5 divide N, we shall not do complicated stuff to see that N is NOT PRIME. In practice one should test divisibility by small primes before going into SPPT. N = 176149; N-1 = 2^2 x 44037 2^44037 = 18543 2^(2*44037) = 1 2 is a CW for the SPPT, and N is composite. N = 726377; N-1 = 2^3 x 90797 2^90797 = 1 mod 726377 => pass. 3^90797 = 167932 mod N 3^(4*90797) = -1 mod N => pass 5^(4*90797) = -1 mod N => pass 7^90797 = -1 mod N => pass ... N really seems prime though we cannot be sure. Remark. One can get a conditional, but rigorous, result using the following Theorem (Miller, 1975). If a suitable generalization of the RH holds, then for all integer N, if N has no CW a for the SPPT test with a <= 2 (log^2 N), then N is prime. This gives, under the Extended Riemann Hypothesis (a slight generalization of the Riemann hypothesis mentioned earlier), a deterministic (no randomness is used) _primality test_ (we prove that the integer is prime) of cost O(log^3 N) operations mod N. The AKS theorem (Agrawal, Kayal, Saxena, 2002) is another such (unconditional) result, but useless in practice. In real life, the records are held by Atkin-Morain's ECPP test (using elliptic curves and deep ideas from number theory). 3. Security issues We shall study a number of security issues before moving to a general study of security. a. Man in the middle In real life, a public key interaction goes the following way: Bob -> Alice "send me your public key" Alice -> Bob "pk_Alice" Bob -> Alice E(pk_Alice, m). It is not, a priori, possible to distinguish between this situation and the following one : Bob -> Alice "send me your public key" -- intercepted by Charlie and forwarded to Alice. Alice -> Charlie "pk_Alice" Charlie -> Bob "pk_Charlie" -- which Bob naively takes for Alice's public key. Bob -> Charlie (but thinking that he's talking to Alice) E(pk_Charlie, m). Charlie computes m and forwards to Alice E(pk_Alice, m); he can thus eavesdrop on the whole conversation, unnoticed. Certificates were invented to avoid this situation. Someone who wants a certificate goes to a Certificate Authority (CA). The CA has a pair PK_CA, SK_CA and delivers a pair message m = "I the undersigned certify that I have checked the identity of Alice and that pk_Alice is indeed her public key", signature D(SK_CA, m) Anyone knowing PK_CA can verify the signature; if one trusts the CA to be serious and verify thoroughly the identity before delivering the certificate, one can then believe that one is indeed using the real Alice's public key. However, one must know the correct PK for the CA again... the PK's of the most common CAs are preloaded in the standard browsers. When a browser receives a certificate issued by a CA it doesn't know, one gets a popup warning about this fact -- this means that one might be subject to a man in the middle attack (though this is not, usually, the most likely explanation -- many people do not understand the concept of certificate and some people do, actually, sign their own certificates... which tends to make the concept meaningless). This problem is not restricted to RSA but is common to all public key cryptosystems. b. Broadcast attack Small value of e may have a huge drawback. Imagine I am to broadcast a message to 20 people with pk_i = (N_i, 3). If I format my message with the same chunks m's, I am going to send m^3 mod N_i for all i. The CRT then allows a pirate to get either a factor of some N_i, or m^3 mod (\prod N_i). As m has to be <= min(N_i), we have \prod N_i > m^3, which means that we have m^3 *over the integers* (not mod N). And extracting cube roots over the reals is easy (eg use dichotomy, or better Newton iteration). c. Shared modulus The idea was suggested long ago to avoid having to generate big primes by trusting a central authority to distribute keys. This authority would pick once and for all p, q, N and distribute distinct pairs (d, e) to various users. But this is unsecure: knowing d, e we can recover the factorisation of N. We shall use the very important following idea: if x \neq \pm 1 mod N but x^2 = 1 mod N, then gcd(x \pm 1, N) are two nontrivial factors of N (hence p, q). Indeed, (x - 1)(x + 1) = 0 mod N; so if gcd(x - 1, N) = 1, we have x + 1 = 0 mod N, contradition. If gcd(x - 1, N) = N, x = 1 mod N, contradiction again. By definition of RSA, we have de - 1 = k \varphi(N) for some k; hence for all a such that (a, N) = 1 we have a^{de - 1} = (a^\varphi(N))^k = 1 mod N (FLT). Now, write de - 1 = 2^s t, and pick a be a random integer \neq 0 mod N. (*) if (a, N) \neq 1, we have a factor of N ; (*) if a^t = 1 mod N, we pick another a ; hence we may assume that a^t \neq 1 mod N (*) We have a^{2^s t} = a^{de - 1} = 1 mod N. Hence, we can define j = max{k / a^{2^k t} \neq 1 mod N} < s. If a^{2^j t} = -1 mod N, we pick another a; otherwise, we take x = a^{2^j t} mod N and use the remark above. The question is thus, how many a shall we need before getting success ? This is again a matter of white/black balls. Proposition. The probability that a^t \neq 1 mod N and a^{2^j t} \neq -1 mod N is >= 1/4. The proof is not very difficult, but a bit long. This proposition means that we have 1/4 of white balls, hence on average 4 different a will be required to get a factorization of N (which is cheap). The cost of the algorithm is of the order of O(log N) operations mod N (as de - 1 <= N^2, so log t and s are O(log N)). d. Malleability of the signature The algebraic structure of RSA implies Signature(m)*Signature(m') = Signature(m m'). This is a weakness. Assumes that Bob wants Alice to sign m' \in Z/NZ which tells "I owe Bob 1M$"; instead, he asks for the signature of m meaning "the weather is nice today" and of m*m' which is meaningless (garbage). Assuming that Alice is tricked into signing those two messages, Bob can deduce the signature of m' and Alice owes him 1M$. The classical solution against this is to use padding: only sign messages with a given structure, as if m and m' have a certain structure most probably mm' won't have this same structure. A simple (and way too naive) example is to sign only messages repeating two times the same things as in m = "the weather is nice today the weather is nice today ". If m' = "I owe Bob 1M$ I owe Bob 1M$ " Alice will refuse to sign m*m' which will not have the right structure. The crypto guys actually often do much fancier stuff to get actual, strong, "proved" (under a lot of assumptions) notions of security -- check RSA-OAEP on the web or PKCS#1 if you want to get a hint of this. e. Small d -- not treated in class We have mentioned that the cryptosystem is weak of d < N^{0.282}. We present here a very simple attack which will disclose d, p, and q as soon as d < N^{1/4} (but we won't prove this fact). Do the extended Euclidean algorithm on e, N. We get identities u_i e + v_i N = r_i. Theorem. If 0 < d < N^{1/4}, there is an i such that |u_i| = d, |v_i| = k such that de = 1 + k \varphi(N). The proof is a consequence of the theory of continued fractions; roughly speaking, as N is close to \varphi(N), de - kN is small, thus |k / d - e / N| is very small -- it can be proved to be < 1/2d^2 as soon as d < N^{1/4}. The theory of continued fractions then implies that (k, d) have to appear in the EEA applied to (e, N), as claimed. Hence, for all i such that u_i < N^{1/4}, one should compute C_i = (u_i e - 1) / v_i; if this is an integer, a candidate value for phi(N) is N + 1 - (p + q); hence a candidate value for p + q is N + 1 - C_i. Now, if this is the right value of p + q, we recover p and q as the roots of x^2 - (N+1-C_i) x + N = 0. Example. e = 235, N = 391. Extended Euclidean algorith gives 1x391 - 1x235 = 156 gives C_i = 234 -391 + 2x235 = 79 gives C_i = 117 2x391 - 3x235 = 77 gives C_i = 352 for which we solve x^2 - 40x + 391 = 0, with roots 17, 23. Indeed 391 = 17 x 23. f. General evaluation of security -- not treated in class Attack against the message -------------------------- Attacking the message means : given pk and E(pk, m), find m. Here this means that we get access to c = m^e mod N and want to deduce m. * if we know how to factor N as p*q this is easy -- we just compute (p-1)(q-1), deduce d from e, and decrypt as c^d mod N. * otherwise, understanding how to solve this is a rather open question. The consensus in the community is that it is probably somewhat easier than integer factoring, but no one knows how to exploit this (except in very particular situations, eg we have a (big) hint on the message). * if we could take e = 2, then the attack on the message would be equivalent to factoring. However this is not RSA (as 2 is not coprime to (p-1)(q-1)), but Rabin's cryptosystem, and it raises some technicalities as decryption is no longer unique... Indeed, assume that we have access to a "black box computer" taking as an argument y \in Z/NZ and returning either "No" if y has no square root mod N, or x \in Z/NZ such that x^2 = y mod N, and let us show how one can factor N using this computer. Lemma. If N = pq, p, q odd, and (y, N) = 1, then y has either 0 or 4 square roots mod N. Proof. Z/pZ is a field; as y mod p is nonzero, either it has a nonzero square root x_p and a second one -x_p, or it has none. Similarly, y mod q has either two square roots x_q and -x_q, or none. By the CRT, (*) if y has no square root mod p or mod q, it has no square root mod N; because x^2 = y mod N would imply x^2 = y mod p and x^2 = y mod q. (*) if y has two square roots mod p and two square roots mod q, it has 4 (pairwise distinct) square roots mod N : x_0 such that x_0 = x_p mod p, x_0 = x_q mod q x_1 such that x_1 = -x_p mod p, x_1 = x_q mod q x_2 = -x_1 such that x_2 = x_p mod p, x_2 = -x_q mod q x_3 = -x_0 such that x_3 = -x_p mod p, x_3 = -x_q mod q all of which exist thanks to the CRT. Now, we pick a random z. If (z, N) > 1, we are done. Otherwise, we compute t = z^2 mod N, and submit t to the black box computer. As the computer does not know z, the square root of t it returns can only be one of the four square roots of t with the same probability for all 4. With probability 1/2, it thus returns neither z nor -z; then we have x/z \neq \pm 1 mod N, and (x/z)^2 = 1 mod N, which means that (x/z - 1 mod N, N) is a nontrivial factor of N. If this fails, we repeat the process; on average, in 2 steps, we'll get a factor of N. Attack against the key ---------------------- Attack against the key is : given (e, N), find d. We have seen above (shared modulus) that this is equivalent to integer factoring. To understand the security of RSA, one thus needs to make a thorough study of integer factoring. Today's state of the art is that one can factor 768 bits (232 decimal digits) RSA moduli; the common agreement is that one should use 2048 bit RSA moduli as keys, so p and q should be of the order of 10^310.