Part V Public-key cryptosystems, I. Key exchange, knapsack, RSA CHAPTER 5: Public-key cryptography I. RSA Rapidly increasing needs for flexible and secure transmission of information require to use new cryptographic methods. The main disadvantage of the classical (symmetric) cryptography is the need to send a (long) key through a super secure channel before sending the message itself. In the classical or secret-key (symmetric) cryptography both sender and receiver share the same secret key. In the public-key (assymetric) cryptography there are two different keys: a public encryption key (at the sender side) and a private (secret) decryption key (at the receiver side). prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 2/44 Basic idea - example Basic idea: If it is infeasible from the knowledge of an encryption algorithm ek to construct the corresponding description algorithm dk , then ek can be made public. Toy example: (Telephone directory encryption) Start: Each user U makes public a unique telephone directory tdU to encrypt messages for U and U is the only user to have an inverse telephone directory itdU . Encryption: Each letter X of a plaintext w is replaced, using the telephone directory tdU of the intended receiver U, by the telephone number of a person whose name starts with letter X. Decryption: easy for Uk , with the inverse telephone directory, infeasible for others. Analogy between secret and public-key cryptography: Secret-key cryptography 1. Put the message into a box, lock it with a padlock and send the box. 2. Send the key by a secure channel. Public-key cryptography Open padlocks, for each user different ones, are freely available. Only legitimate user has key from his padlocks. Transmission: Put the message into the box of the intended receiver, close the padlock and send the box. prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 3/44 Public Establishment of Secret Keys Main problem of the secret-key cryptography: a need to make a secure distribution (establishment) of secret keys ahead of transmissions. Diffie+Hellman solved this problem in 1976 by designing a protocol for secure key establishment (distribution) over public channels. Diffie-Helmann Protocol: If two parties, Alice and Bob, want to create a common secret key, then they first agree, somehow, on a large prime p and a q

n be publiclly known. Steps of the protocol: 1 Each user U in the network is assigned, by Trent, a unique public number rU < p. 2 Trent chooses three random numbers a, b and c, smaller than p. 3 For each user U, Trent calculates two numbers aU = (a + brU ) mod p, bU = (b + crU ) mod p and sends them via his secure channel to U. 4 Each user U creates the polynomial gU (x) = aU + bU (x). 5 If Alice (A) wants to send a message to Bob (B), then Alice computes her key KAB = gA(rB ) and Bob computes his key KBA = gB (rA). 6 It is easy to see that KAB = KBA and therefore Alice and Bob can now use their (identical) keys to communicate using some secret-key cryptosystem. prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 7/44 Secure communication with secret-key cryptosystems and without any need for secret key distribution (Shamir’s “no-key algorithm”) Basic assumption: Each user X has its own secret encryption function eX secret decryption function dX and all these functions commute (to form a commutative cryptosystem). Communication protocol with which Alice can send a message w to Bob. 1 Alice sends eA(w) to Bob 2 Bob sends eB (eA(w)) to Alice 3 Alice sends dA(eB (eA(w))) = eB (w) to Bob 4 Bob performs the decryption to get dB (eB (w)) = w. Disadvantage: 3 communications are needed (in such a context 3 is a much too large number). Advantage: A perfect protocol for distribution of secret keys. prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 8/44 Cryptography and Computational Complexity Modern cryptography uses such encryption methods that no “enemy” can have enough computational power and time to do decryption (even those capable to use thousands of supercomputers during tens of years for encryption). Modern cryptography is based on negative and positive results of complexity theory – on the fact that for some algorithm problems no efficient algorithm seem to exists, surprisingly, and for some “small” modifications of these problems, surprisingly, simple, fast and good (randomized) algorithms do exist. Examples: Integer factorization: Given n(= pq), it is, in general, unfeasible, to find p, q. There is a list of “most wanted to factor integers”. Top recent successes, using thousands of computers for months. (*) Factorization of 229 + 1 with 155 digits (1996) (**) Factorization of a “typical” 155-digits integer (1999) Primes recognition: Is a given n a prime? – fast randomized algorithms exist (1977). The existence of polynomial deterministic algorithms has been shown only in 2002 prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 9/44 Computationaly infeasible problems Discrete logarithm problem: Given x, y, n, determine integer a such that y ≡ xa (mod n) – infeasible in general. Discrete square root problem: Given integers y, n, compute an integer x such that y ≡ x2 (mod n) – infeasible in general, easy if factorization of n is known Knapsack problem: Given a ( knapsack - integer) vector X = (x1, . . . , xn) and a (integer capacity) c, find a binary vector (b1, . . . , bn) such that Pn i=1 bi xi = c. Problem is NP-hard in general, but easy if xi > Pi−1 j=1 xj , 1 < i ≤ n. prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 10/44 One-way functions Informally, a function F : N → N is said to be one-way function if it is easily computable - in polynomial time - but any computation of its inverse is infeasible. A one-way permutation is a 1-1 one-way function. easy computationaly infeasible x f(x) A more formal approach Definition A function f : {0, 1}∗ → {0, 1}∗ is called a strongly one-way function if the following conditions are satisfied: 1 f can be computed in polynomial time; 2 there are c, ε > 0 such that |x|ε ≤ |f (x)| ≤ |x|c ; 3 for every randomized polynomial time algorithm A, and any constant c > 0, there exists an nc such that for n > nc Pr (A(f (x)) ∈ f −1 (f (x))) < 1 nc . Candidates: Modular exponentiation: f (x) = ax mod n Modular squaring f (x) = x2 mod n, n − a Blum integer Prime number multiplication f (p, q) = pq. prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 11/44 Trapdoor One-way Functions The key concept for design of public-key cryptosystems is that of trapdoor one-way functions. A function f : X → Y is trapdoor one-way function if f and its inverse can be computed efficiently, yet even the complete knowledge of the algorithm to compute f does not make it feasible to determine a polynomial time algorithm to compute the inverse of f . A candidate: modular squaring with a fixed modulus. computation of discrete square roots is unfeasible in general, but quite easy if the decomposition of the modulus into primes is known. A way to design a trapdoor one-way function is to transform an easy case of a hard (one-way) function to a hard-looking case of such a function, that can be, however, solved easily by those knowing how the above transformation was performed. prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 12/44 Example – Computer passwords A naive solution is to keep in computer a file with entries as login CLINTON password BUSH, that is with logins and their passwords. This is not sufficiently safe. A more safe method is to keep in the computer a file with entries as login CLINTON password BUSH one-way function fc The idea is that BUSH is a “public” password and CLINTON is the only one that knows a “secret” password, say MADONA, such that fc (MADONA) = BUSH prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 13/44 LAMPORT’s ONE-TIME PASSWORDS One-way functions can be used to create a sequence of passwords: 1 Alice chooses a random w and computes, using a one-way function h, a sequence of passwords w, h(w), h(h(w)), . . . , hn (w) 2 Alice then transfers securely “the initial secret” w0 = hn (w) to Bob. 3 The i-th authentication, 0 < i < n + 1, is performed as follows: - - - - - - - Alice sends wi = hn−i (w) to Bob for I = 1, 2,. . . ,n-1 - - - - - - - Bob checks whether wi−1 = h(wi ). When the number of identifications reaches n, a new w has to be chosen. prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 14/44 General knapsack problem – unfeasible KNAPSACK PROBLEM: Given an integer-vector X = (x1, . . . , xn) and an integer c. Determine a binary vector B = (b1, . . . , bn) (if it exists) such that XBT = c. Knapsack problem with superincreasing vector – easy Problem Given a superincreasing integer-vector X = (x1, . . . , xn) (i.e. xi > Pi−1 j=1 xj , i > 1) and an integer c, determine a binary vector B = (b1, . . . , bn) (if it exists) such that XBT = c. Algorithm – to solve knapsack problems with superincreasing vectors: for i ← downto 2 do if c ≥ 2xi then terminate {no solution} else if c > xi then bi ← 1; c ← c − xi ; else bi = 0; if c = x1 then b1 ← 1 else if c = 0 then b1 ← 0; else terminate {no solution} Example X = (1,2,4,8,16,32,64,128,256,512) c = 999 X = (1,3,5,10,20,41,94,199) c = 242 prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 15/44 KNAPSACK ENCODING – BASIC IDEAS Let a (knapsack) vector A = (a1, . . . , an) be given. Encoding of a (binary) message B = (b1, b2, . . . , bn) by A is done by the vector/vector multiplication: ABT = c and results in the cryptotext c. Decoding of c requires to solve the knapsack problem for the instant given by the knapsack vector A and the cryptotext c. The problem is that decoding seems to be infeasible. Example If A = (74, 82, 94, 83, 39, 99, 56, 49, 73, 99) and B = (1100110101) then ABT = prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 16/44 Design of knapsack cryptosystems 1 Choose a superincreasing vector X = (x1, . . . , xn). 2 Choose m, u such that m > 2xn, gcd(m, u) = 1. 3 Compute u−1 mod m, X = (x1, . . . , xn), xi = uxi |{z} diffusion mod m. | {z } confusion Cryptosystem: X – public key X, u, m – trapdoor information Encryption: of a binary vector w of length n: c = X w Decryption: compute c = u−1 c mod m and solve the knapsack problem with X and c . Lemma Let X, m, u, X , c, c be as defined above. Then the knapsack problem instances (X, c ) and (X , c) have at most one solution, and if one of them has a solution, then the second one has the same solution. Proof Let X w = c. Then c ≡ u−1 c ≡ u−1 X w ≡ u−1 uXw ≡ Xw(mod m). Since X is superincreasing and m > 2xn we have (Xw) mod m = Xw c = Xw.and therefore prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 17/44 Design of knapsack cryptosystems – example Example X = (1,2,4,9,18,35,75,151,302,606) m = 1250, u = 41 X’ = (41,82,164,369,738,185,575,1191,1132,1096) In order to encrypt an English plaintext, we first encode its letters by 5-bit numbers - 00000, A - 00001, B - 00010,. . . and then divide the resulting binary strings into blocks of length 10. Plaintext: Encoding of AFRICA results in vectors w1 = (0000100110) w2 = (1001001001) w3 = (0001100001) Encryption: c1 = X w1 = 3061 c2 = X w2 = 2081 c3 = X w3 = 2203 Cryptotext: (3061,2081,2203) Decryption of cryptotexts: (2163, 2116, 1870, 3599) By multiplying with u–1 = 61 (mod 1250) we get new cryptotexts (several new c ) (693, 326, 320, 789) And, in the binary form, solutions B of equations XBT = c have the form (1101001001, 0110100010, 0000100010, 1011100101) Therefore, the resulting plaintext is: ZIMBABWE prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 18/44 Story of the Knapsack Invented: 1978 - Ralph C. Merkle, Martin Hellman Patented: in 10 countries Broken: 1982: Adi Shamir New idea: iterated knapsack cryptosystem using hyper-reachable vectors. Definition A knapsack vector X = (x1 , . . . , xn ) is obtained from a knapsack vector X = (x1, . . . , xn) by strong modular multiplication if Xi = uxi mod m, i = 1, . . . , n, m > 2 Pn i=1 xiwhere and gcd(u, m) = 1. A knapsack vector X is called hyper-reachable, if there is a sequence of knapsack vectors X = x0, x1, . . . , xk = X , where x0 is a super-increasing vector and for i = 1, . . . , k xi is obtained from xi−1 by a strong modular multiplication. Iterated knapsack cryptosystem was broken in 1985 - E. Brickell New ideas: dense knapsack cryptosystems. Density of a knapsack vector X = (x1, . . . , xn) is defined by d(x) = n log(max{xi |1≤i≤n}) Remark. Density of super-increasing vectors is ≤ n n−1 prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 19/44 KNAPSACK CRYPTOSYSTEM – COMMENTS The term “knapsack” in the name of the cryptosystem is quite misleading. By the Knapsack problem one usually understands the following problem: Given n items with weights w1, w2, . . . , wn and values v1, v2, . . . , vn and a knapsack limit c, the task is to find a bit vector (b1, b2, . . . , bn) such that Pn i=1 bi wi ≤ c and Pn i=1 bi vi is as large as possible. The term subset problem is usually used for the problem used in our construction of the knapsack cryptosystem. It is well-known that the decision version of this problem is NP-complete. Sometimes, for our main version of the knapsack problem the term Merkle-Hellmman (Knapsack) Cryptosystem is used. prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 20/44 McEliece Cryptosystem McEliece cryptosystem is based on a similar design principle as the Knapsack cryptosystem. McEliece cryptosystem is formed by transforming an easy to break cryptosystem into a cryptosystem that is hard to break because it seems to be based on a problem that is, in general, NP-hard. The underlying fact is that the decision version of the decryption problem for linear codes is in general NP-complete. However, for special types of linear codes polynomial-time decryption algorithms exist. One such a class of linear codes, the so-called Goppa codes, are used to design McEliece cryptosystem. Goppa codes are [2m , n − mt, 2t + 1]-codes, where n = 2m . (McEliece suggested to use m = 10, t = 50.) prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 21/44 McEliece Cryptosystem – DESIGN Goppa codes are [2m , n − mt, 2t + 1]-codes, where n = 2m . Design of McEliece cryptosystems. Let G be a generating matrix for an [n, k, d] Goppa code C; S be a k × k binary matrix invertible over Z2; P be an n × n permutation matrix; G = SGP. Plaintexts: P = (Z2)k ; cryptotexts: C = (Z2)n , key: K = (G, S, P, G ), message: w G is made public, G, S, P are kept secret. Encryption: eK (w, e) = wG + e, where e is any binary vector of length n & weight t. Decryption of a cryptotext c = wG + e ∈ (Z2)n . 1 Compute c1 = cP−1 = wSGPP−1 + eP−1 = wSG + eP−1 2 Decode c1 to get w1 = wS, 3 Compute w = w1S−1 prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 22/44 COMMENTS on McELIECE CRYPTOSYSTEM 1 Each irreducible polynomial over Zm 2 of degree t generates a Goppa code with distance at least 2t + 1. 2 In the design of McEliece cryptosystem the goal of matrices S and C is to modify a generator matrix G for an easy-to-decode Goppa code to get a matrix that looks as a general random matrix for a linear code for which decoding problem is NP-complete. 3 An important novel and unique trick is an introduction, in the encoding process, of a random vector e that represents an introduction of up to t errors – such a number of errors that are correctable using the given Goppa code and this is the basic trick of the decoding process. 4 Since P is a permutation matrix eP−1 has the same weight as e. 5 As already mentioned, McEliece suggested to use a Goppa code with m = 10 and t = 50. This provides a [1024, 524, 101]-code. Each plaintext is then a 524-bit string, each cryptotext is a 1024-bit string. The public key is an 524 × 1024 matrix. 6 Observe that the number of potential matrices S and P is so large that probability of guessing these matrices is smaller that probability of guessing correct plaintext!!! 7 It can be shown that it is not safe to encrypt twice the same plaintext with the same public key (and different error vectors). prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 23/44 FINAL COMMENTS 1 Public-key cryptosystems can never provide unconditional security. This is because an eavesdropper, on observing a cryptotext c can encrypt each possible plaintext by the encryption algorithm eA until he finds c such that eA(w) = c. 2 One-way functions exist if and only if P = UP, where UP is the class of languages accepted by unambiguous polynomial time bounded nondeterministic Turing machine. 3 There are actually two types of keys in practical use: A session key is used for sending a particular message (or few of them). A master key is usually used to generate several session keys. 4 Session keys are usually generated when actually required and discarded after their use. Session keys are usually keys of a secret-key cryptosystem. 5 Master keys are usually used for longer time and need therefore be carefully stored. Master keys are usually keys of a public-key cryptosystem. prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 24/44 SATELLITE VERSION of ONE-TIME PAD Suppose a satellite produces and broadcasts several random sequences of bits at a rate fast enough that no computer can store more than a small fraction of the output. If Alice wants to send a message to Bob they first agree, using a public key cryptography, on a method of sampling bits from the satellite outputs. Alice and Bob use this method to generate a random key and they use it with ONE-TIME PAD for encryption. By the time Eve decrypted their public key communications, random streams produced by the satellite and used by Alice and Bob to get the secret key have disappeared, and therefore there is no way for Eve to make decryption. The point is that satellites produce so large amount of date that Eve cannot store all of them prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 25/44 RSA cryptosystem The most important public-key cryptosystem is the RSA cryptosystem on which one can also illustrate a variety of important ideas of modern public-key cryptography. For example, we will discuss various possible attacks on the RSA cryptosystem and problems related to security of RSA. A special attention will be given in Chapter 7 to the problem of factorization of integers that play such an important role for security of RSA. In doing that we will illustrate modern distributed techniques to factorize very large integers. prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 26/44 DESIGN and USE of RSA CRYPTOSYSTEM Invented in 1978 by Rivest, Shamir, Adleman Basic idea: prime multiplication is very easy, integer factorization seems to be unfeasible. Design of RSA cryptosystems 1 Choose two large s-bit primes p,q, s in [512,1024], and denote n = pq, φ(n) = (p − 1)(q − 1) 2 Choose a large d such that gcd(d, φ(n)) = 1 and compute e = d−1 (mod φ(n)) Public key: n (modulus), e (encryption exponent) Trapdoor information: p, q, d (decryption exponent) Plaintext w Encryption: cryptotext c = we mod n Decryption: plaintext w = cd mod n Details: A plaintext is first encoded as a word over the alphabet {0, 1, . . . , 9}, then divided into blocks of length i − 1, where 10i−1 < n < 10i . Each block is taken as an integer and decrypted using modular exponentiation. prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 27/44 Correctness of RSA Let c = we mod n be the cryptotext for a plaintext w, in the cryptosystem with n = pq, ed ≡ 1 (mod φ(n)), gcd(d, φ(n)) = 1 In such a case w ≡ cd mod n and, if the decryption is unique, w = cd mod n. Proof Since ed ≡ 1 (mod φ(n)), there exist a j ∈ N such that ed = jφ(n) + 1. Case 1. Neither p nor q divides w. In such a case gcd(n, w) = 1 and by the Euler’s Totien Theorem we get that cd = wed = wjφ(n)+1 ≡ w (mod n) Case 2. Exactly one of p, q divides w – say p. In such a case wed ≡ w (mod p) and by Fermat’s Little theorem wq−1 ≡ 1 (mod q) ⇒ wq−1 ≡ 1 (mod q) ⇒ wφ(n) ≡ 1 (mod q) ⇒ wjφ(n) ≡ 1 (mod q) ⇒ wed ≡ w (mod q) Therefore: w ≡ wed ≡ cd (mod n) Case 3. Both p, q divide w. This cannot happen because, by our assumption, w < n. prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 28/44 DESIGN and USE of RSA CRYPTOSYSTEM Example of the design and of the use of RSA cryptosystems. By choosing p = 41, q = 61 we get n = 2501, φ(n) = 2400 By choosing d = 2087 we get e = 23 By choosing d = 2069 we get e = 29 By choosing other values of d we would get other values of e. Let us choose the first pair of encryption/decryption exponents (e = 23 and d = 2087). Plaintext: KARLSRUHE Encoding: 100017111817200704 Since 103 < n < 104, the numerical plaintext is divided into blocks of 3 digits ⇒ 6 plaintext integers are obtained 100, 017, 111, 817, 200, 704 Encryption: 10023 mod 2501, 1723 mod 2501, 11123 mod 2501 81723 mod 2501, 20023 mod 2501, 70423 mod 2501 provides cryptotexts: 2306, 1893, 621, 1380, 490, 313 Decryption: 23062087 mod 2501 = 100, 18932087 mod 2501 = 17 6212087 mod 2501 = 111, 13802087 mod 2501 = 817 4902087 mod 2501 = 200, 3132087 mod 2501 = 704 prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 29/44 RSA challenge One of the first descriptions of RSA was in the paper. Martin Gardner: Mathematical games, Scientific American, 1977 and in this paper RSA inventors presented the following challenge. Decrypt the cryptotext: 9686 9613 7546 2206 1477 1409 2225 4355 8829 0575 9991 1245 7431 9874 6951 2093 0816 2982 2514 5708 3569 3147 6622 8839 8962 8013 3919 9055 1829 9451 5781 5154 Encrypted using the RSA cryptosystem with 129 digit number, called also RSA129 n: 114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 513 958 705 058 989 075 147 599 290 026 879 543 541. and with e = 9007. The problem was solved in 1994 by first factorizing n into one 64-bit prime and one 65-bit prime, and then computing the plaintext THE MAGIC WORDS ARE SQUEMISH OSSIFRAGE prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 30/44 How to design a good RSA cryptosystem 1 How to choose large primes p, q? Choose randomly a large integer p, and verify, using a randomized algorithm, whether p is prime. If not, check p + 2, p + 4, . . . From the Prime Number Theorem it follows that there are approximately 2d log 2d − 2d−1 log 2d−1 d bit primes. (A probability that a 512-bit number is prime is 0.00562.) 2 What kind of relations should be between p and q? 2.1 Difference |p − q| should be neither too small nor too large. 2.2 gcd(p − 1, q − 1) should not be large. 2.3 Both p − 1 and q − 1 should contain large prime factors. 2.4 Quite ideal case: q, p should be safe primes - such that also (p–1)/2 and (q − 1)/2 are primes. (83, 107, 10100 − 166517 are examples of safe primes). 3 How to choose e and d? 3.1 Neither d nor e should be small. 3.2 d should not be smaller than n 1 4 . (For d < n 1 4 a polynomial time algorithm is known to determine d). prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 31/44 Prime recognition and factorization The key problems for the development of RSA cryptosystem are that of prime recognition and integer factorization. On August 2002, the first polynomial time algorithm was discovered that allows to determine whether a given m bit integer is a prime. Algorithm works in time O(m12 ). Fast randomized algorithms for prime recognition has been known since 1977. One of the simplest one is due to Rabin and will be presented later. For integer factorization situation is somehow different. No polynomial time classical algorithm is known. Simple, but not efficient factorization algorithms are known. Several sophisticated distributed factorization algorithms are known that allowed to factorize, using enormous computation power, surprisingly large integers. Progress in integer factorization, due to progress in algorithms and technology, has been recently enormous. Polynomial time quantum algorithms for integer factorization are known since 1994 (P. Shor). Several simple and some sophisticated factorization algorithms will be presented and illustrated in the following. prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 32/44 Rabin-Miller’s prime recognition Rabin-Miller’s Monte Carlo prime recognition algorithm is based on the following result from the number theory. Lemma Let n ∈ N. Denote, for 1 ≤ x ≤ n, by C(x) the condition: Either xn−1 = 1 (mod n), or there is an m = n−1 2i for some i, such that gcd(n, xm − 1) = 1 If C(x) holds for some 1 ≤ x ≤ n, then n is not a prime. If n is not a prime, then C(x) holds for at least half of x between 1 and n. Algorithm: Choose randomly integers x1, x2, . . . , xm such that 1 ≤ xi ≤ n. For each xi determine whether C(xi ) holds. Claim: If C(xi ) holds for some i, then n is not a prime for sure. Otherwise n is prime, with probability of error 2−m . prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 33/44 Factorization of 512-bits and 663-bits numbers On August 22, 1999, a team of scientists from 6 countries found, after 7 months of computing, using 300 very fast SGI and SUN workstations and Pentium II, factors of the so-called RSA-155 number with 512 bits (about 155 digits). RSA-155 was a number from a Challenge list issue by the US company RSA Data Security and “represented” 95% of 512-bit numbers used as the key to protect electronic commerce and financinal transmissions on Internet. Factorization of RSA-155 would require in total 37 years of computing time on a single computer. When in 1977 Rivest and his colleagues challenged the world to factor RSA-129, they estimated that, using knowledge of that time, factorization of RSA-129 would require 1016 years. In 2005 RSA-200, a 663-bits number, was factorized by a team of German Federal Agency for Information Technology Security, using CPU of 80 AMD Opterons. prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 34/44 LARGE NUMBERS Hindus named many large numbers - one having 153 digits. Romans initially had no terms for numbers larger than 104 . Greeks had a popular belief that no number is larger than the total count of sand grains needed to fill the universe. Large numbers with special names: duotrigintillion=googol−10100 googolplex−1010100 FACTORIZATION of very large NUMBERS W. Keller factorized F23471 which has 107000 digits. J. Harley factorized: 10101000 + 1. One factor: 316, 912, 650, 057, 350, 374, 175, 801, 344, 000, 001 1992 E. Crandal, Doenias proved, using a computer that F22, which has more than million of digits, is composite (but no factor of F22 is known). Number 10101034 was used to develop a theory of the distribution of prime numbers. prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 35/44 DESIGN OF GOOD RSA CRYPTOSYSTEMS Claim 1. Difference |p − q| should not be small. Indeed, if |p − q| is small, and p > q, then (p+q) 2 is only slightly larger than √ n because (p + q)2 4 − n = (p − q)2 4 In addition (p+q)2 4 − n is a square, say y2 . In order to factor n, it is then enough to test x > √ n until x is found such that x2 − n is a square, say y2 . In such a case p + q = 2x, p − q = 2y and therefore p = x + y, q = x − y. Claim 2. gcd(p − 1, q − 1) should not be large. Indeed, in the opposite case s = lcm(p − 1, q − 1) is much smaller than φ(n) If d e ≡ 1 mod s, then, for some integer k, cd ≡ wed ≡ wks+1 ≡ w mod n since p − 1|s, q − 1|s and therefore wks ≡ 1 mod p and wks+1 ≡ w mod q. Hence, d can serve as a decryption exponent. Moreover, in such a case s can be obtained by testing. Question Is there enough primes (to choose again and again new ones)? No problem, the number of primes of length 512 bit or less exceeds 10150 . prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 36/44 How important is factorization for breaking RSA? 1 If integer factorization is feasible, then RSA is breakable. 2 There is no proof that factorization is indeed needed to break RSA. 3 If a method of breaking RSA would provide an effective way to get a trapdoor information, then factorization could be done effectively. Theorem Any algorithm to compute φ(n) can be used to factor integers with the same complexity. Theorem Any algorithm for computing d can be converted into a break randomized algorithm for factoring integers with the same complexity. 4 There are setups in which RSA can be broken without factoring modulus n. Example An agency chooses p, q and computes a modulus n = pq that is publicized and common to all users U1, U2, . . . and also encryption exponents e1, e2, . . . are publicized. Each user Ui gets his decryption exponent di . In such a setting any user is able to find in deterministic quadratic time another user’s decryption exponent. prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 37/44 Security of RSA None of the numerous attempts to develop attacks on RSA has turned out to be successful. There are various results showing that it is impossible to obtain even only partial information about the plaintext from the cryptotext produced by the RSA cryptosystem. We will show that were the following two functions, that are computationally polynomially equivalent, be efficiently computable, then the RSA cryptosystem with the encryption (decryption) exponents ek (dk ) would be breakable. parityek (c) =the least significant bit of such an w that ek (w) = c; halfek (c) = 0 if 0 ≤ w < n 2 and halfek (c) = 1 if n 2 ≤ w ≤ n − 1 We show two important properties of the functions half and parity. 1 Polynomial time computational equivalence of the functions half and parity follows from the following identities halfek (c) = parityek ((c × ek (2)) mod n parityek (c) = halfek ((c × ek ( 1 2 )) mod n and the multiplicative rule ek (w1)ek (w2) = ek (w1w2). 2 There is an efficient algorithm to determine plaintexts w from the cryptotexts c obtained by RSA-decryption provided efficiently computable function half can be used as the oracle: prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 38/44 Security of RSA BREAKING RSA USING AN ORACLE Algorithm: for i = 0 to lgn do ci ← half (c); c ← (c × ek (2)) mod n l ← 0; u ← n for i = 0 to lgn do m ← (i + u)/2; if ci = 1 then i ← m else u ← m; output ← [u] Indeed, in the first cycle ci = half (c × (ek (2))i ) = half (ek (2i w)), is computed for 0 ≤ i ≤ lgn. In the second part of the algorithm binary search is used to determine interval in which w lies. For example, we have that half (ek (w)) = 0 ≡ w ∈ [0, n 2 ) half (ek (2w)) = 0 ≡ w ∈ [0, n 4 ) ∪ [ n 2 , 3n 4 ) half (ek (4w)) = 0 ≡ w ∈ prof. Jozef Gruska IV054 5. Public-key cryptosystems, I. Key exchange, knapsack, RSA 39/44 Security of RSA There are many results for RSA showing that certain parts are as hard as whole. For example any feasible algorithm to determine the last bit of the plaintext can be converted into a feasible algorithm to determine the whole plaintext. Example Assume that we have an algorithm H to determine whether a plaintext x designed in RSA with public key e, n is smaller than n 2 if the cryptotext y is given. We construct an algorithm A to determine in which of the intervals (jn 8 , (j+1)n 8 ), 0 ≤ j ≤ 7 the plaintext lies. Basic idea H can be used to decide whether the plaintexts for cryptotexts xe mod n, 2e xe mod n, 4e xe mod n are smaller than n 2 . Answers yes, yes, yes 0