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. Basic idea - example Basic idea: If it is infeasible from the knowledge of an encryption algorithm e[k] to construct the corresponding description algorithm d[k], then e[k] can be made public. Toy example: (Telephone directory encryption) Start: Each user U makes public a unique telephone directory td[U] to encrypt messages for U and U is the only user to have an inverse telephone directory itd[U]. Encryption: Each letter X of a plaintext w is replaced, using the telephone directory td[U] of the intended receiver U, by the telephone number of a person whose name starts with letter X. Decryption: easy for U[k], with the inverse telephone directory, infeasible for others. 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. KEY DISTRIBUTION / AGREEMENT MAN-IN-THE-MIDDLE ATTACK The following attack, by a man-in-the-middle, is possible against the Diffie-Hellman key establishment protocol. Blom's key pre-distribution protocol allows to a trusted authority (Trent) to distributed secret keys to n (n - 1) / 2 pairs of n users. Let a large prime p > n be publiclly known. The protocol has the following steps: 1. Each user U in the network is assigned, by Trent, a unique public number r[U] < p. Secure communication with secret-key cryptosystems but without any need for secret key distribution (Shamir's ``no-key algorithm’’) Basic assumption: Each user X has its own secret encryption function e[X] secret decryption function d[X] and all these functions commute (to form a commutative cryptosystem). Cryptography and Computational Complexity Modern cryptography uses such encryption methods that no ``enemy'' can have enough computational power and time to do encryption (even those capable to use thousands of supercomputers for 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 of “small'' modifications of these problems, surprisingly, simple, fast and good enough (randomized) algorithms do exist. Computationaly infeasible problems 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 x f(x) computationaly infeasible[] 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. 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 corresponding passwords. This is not sufficiently safe. LAMPORT’s ONE-TIME PASSWORDS One-way functions can be used to create a sequence of passwords: • Alice chooses a random w and computes, using a one-way function h, a sequence of passwords w, h(w), h(h(w)),…,h^n(w) • Alice then transfers securely ``the initial secret’’ w[0]=h^n(w) to Bob. • The i-th authentication, 0 < i < n+1, is performed as follows: ------- Alice sends w[i]=h^n-i(w) to Bob ------- Bob checks whether w[i-1]=h(w[i]). When the number of identifications reaches n, a new w has to be chosen. General knapsack problem - unfeasible KNAPSACK PROBLEM: Given an integer-vector X = (x[1],…,x[n]) and an integer c. Determine a binary vector B = (b[1],…,b[n]) (if it exists) such that XB^T = c. KNAPSACK ENCODING - BASIC IDEAS Let a (knapsack) vector A = (a[1],…,a[n]) be given. Encoding of a (binary) message B = (b[1], b[2],…,b[n]) by A is done by the vector/vector multiplication: AB^T = c and results in the cryptotext c Design of knapsack cryptosystems 1. Choose a superincreasing vector X = (x[1],…,x[n]). 2. Choose m, u such that m > 2x[n], gcd(m, u) = 1. 3. Compute u ^-1 mod m, X '= (x[1]^’,…,x[n]^'), x[i]^’= ux [i] mod m. diffusion confusion Design of knapsack cryptosystems 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 w[1] = (0000100110) w[2] = (1001001001) w[3] = (0001100001) Encryption: c[1][’] = X'w[1] = 3061 c[2’] = X'w[2] = 2081 c[3’] = X‘w[3] = 2203 Cryptotext: (3061,2081,2203) Story of the Knapsack Invented: 1978 - Ralp 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 '= (x[1'],…,x[n][']) is obtained from a knapsack vector X=(x[1],…,x[n]) by strong modular multiplication if X’[i] = ux [i] mod m, i = 1,…,n, where and gcd(u, m) = 1. A knapsack vector X' is called hyper-reachable, if there is a sequence of knapsack vectors X = x[0], x[1],…,x[k] = X ‘, where x[0] is a super-increasing vector and for i = 1,…,k} and x[i] is obtained from x[i-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=(x[1],…,x[n]) is defined by Remark. Density of super-increasing vectors is 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 w[1], w[2],…, w[n] and values v[1], v[2],…, v[n] and a knapsack limit c, the task is to find a bit vector (b[1], b[2],…, b[n]) such that and is as large as possible. 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 [2^m, n - mt, 2t + 1]-codes, where n = 2^m. (McEliece suggested to use m = 10, t = 50.) McEliece Cryptosystem - DESIGN Goppa codes are [2^m, n - mt, 2t + 1]-codes, where n = 2^m. 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 Z[2]; • P be an n × n permutation matrix; • G‘ = SGP. Plaintexts: P = (Z[2])^k; cryptotexts: C = (Z[2])^n, key: K = (G, S, P, G‘), message: w G' is made public, G, S, P are kept secret. COMMENTS on McELIECE CRYPTOSYSTEM • Each irreducible polynomial over Z[2]^m of degree t generates a Goppa code with distance at least 2t + 1. FINAL COMMENTS • 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 e[A] until he finds an c such that e[A](w) = c. 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 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. 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. 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. Correctness of RSA Let c = w^e mod n be the cryptotext for a plaintext w, in the cryptosystem with In such a case and, if the decryption is unique, w = c^d mod n. 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, f(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 get other values of e. Let us choose the first pair of encryption/decryption exponents ( e=23 and d=2087). RSA challenge One of the first description 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 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 if follows that there are approximately d bit primes. (A probability that a 512-bit number is prime is 0.00562.) 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(m^12). 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. 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 , or there is an for some i, such that 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. Factorization of 512-bits and 663-bits numbers On August 22, 1999, a team of scientifists 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). LARGE NUMBERS Hindus named many large numbers - one having 153 digits. Romans initially had no terms for numbers larger than 10^4. 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 - 10^100 googolplex - 10^10^100 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 because In addition is a square, say y^2. In order to factor n, it is then enough to test x > until x is found such that x^2 - n is a square, say y^2. In such a case p + q = 2x, p – q = 2y and therefore p = x + y, q = x - y. How important is factorization for breaking RSA? • If integer factorization is feasible, then RSA is breakable. 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 produces 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) algorithm e[k] (d[k]) would be breakable. parity[ek](c) = the least significant bit of such an w that e[k](w) = c; Security of RSA BREAKING RSA USING AN ORACLE Algorithm: for i = 0 to [lg n] do c [i] ¬ half(c); c ¬ (c × e[k](2)) mod n l ¬ 0; u ¬ n for i = 0 to [lg n] do m ¬ (i+ u) / 2; if c [i] = 1 then i ¬ m else u ¬ m; output ¬ [u] Indeed, in the first cycle is computed for 0 £ i £ lg n. 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 x^e mod n, 2^ex^e mod n, 4^ex^e mod n are smaller than n / 2 . Answers yes, yes, yes 0 < x < n/8 no, yes, yes n/2 < x < 5n/8 yes, yes, no n/8 < x < n/4 no, yes, no 5n/8 < x < 3n/4 yes, no, yes n/4 < x < 3n/8 no, no, yes 3n/4 < x < 7n/8 yes, no, no 3n/8 < x < n/2 no, no, no 7n/8 < x < n RSA with a composite “to be a prime'' Let us explore what happens if some integer p used, as a prime, to design a RSA is actually not a prime. Let n = pq where q be a prime, but p = p[1]p[2], where p[1], p[2] are primes. In such a case but assume that the RSA-designer works with Let u = lcm(p[1][ ]- 1, p[2 ]- 1, q -1) and let gcd(w, n) = 1. In such a case and as a consequence In such a case u divides and let us assume that also u divides Then So if e[d] º 1 mod f[1](n), then encryption and decryption work as if p were prime. Two users should not use the same modulus Otherwise, users, say A and B, would be able to decrypt messages of each other using the following method. Decryption: B computes Since it holds: and therefore m and e[A] have no common divisor and therefore there exist integers u, v such that um + ve[A][ ]= 1 Since m is a multiple of f(n) we have and since e[A]d[A] º 1 mod f(n) we have and therefore is a decryption exponent of A. Indeed, for a cryptotext c: Private-key versus public-key cryptography • The prime advantage of public-key cryptography is increased security - the private keys do not ever need to be transmitted or revealed to anyone. KERBEROS We describe a popular key distribution protocol with trusted authority TA, where each user A shares a secrete K[A] with TA. • To communicate with the user B the user A asks TA a session key • TA chooses a random session key K, a time-stamp T, and a lifetime limit L. • TA computes and sends m[1], m[2] to A. •[ ]A decrypts m[1], recovers K, T, L, ID(B), computes m[3]=e[K](ID(B), T) and sends m[2][ ]and m[3][ ] to B. • B decrypts m[2][ ]and m[3], checks whether two values of T and of ID(B) are the same. If so, B computes m[4]=e[K](T+1) and sends it to A. • A decrypts m[4] and verifies that she got T+1.