Report

Lecture 8 Public-Key Encryption I Stefan Dziembowski www.dziembowski.net MIM UW 23.11.12 ver 1.0 Plan 1. Handbook RSA and its insecurity a. introduction b. algebraic properties of RSA 2. Security definitions 3. How to encrypt with RSA a. a practical construction b. a theoretical construction based on hardcore bits 4. Rabin encryption 5. Theoretical constructions Public-Key Encryption Use 2 keys (pk,sk), where pk is used for encryption, sk is used for decryption. m c := Enc(pk,m) Dec(sk,c) Alice Bob pk sk The RSA trap-door permutation from the last lecture N = pq - RSA modulus e is such that gcd(e, φ(N)) = 1, d is such that ed = 1 (mod φ(N)) Q: How to formalize this? f(x) = xe mod N A: “RSA assumption” easy ZN * • easy (if you know p,q) • believed to be hard (otherwise) Z N* A naïve idea • • pk = (N,e) is used for encryption, sk = (N,d) is used for decryption. m ZN* c := me mod N Alice (N,e) m = cd mod N Bob (N,d) The “handbook RSA encryption” N = pq - RSA modulus φ(N) = (p-1)(q-1) e is such that gcd(e, φ(N)) = 1, d is such that ed = 1 (mod φ(N)) RSA(e,N) (m) = me mod N, and RSA(d,N) (c) = cd mod N. = RSA-1(e,N) A game security parameter 1k adversary (x,e,N) oracle choose: • N = pq where p and q are random primes such that |p| = |q| = k • x – a random element of ZN* , • e – a random element of Zφ(N)* outputs y We say that the adversary wins if y = RSA-1(e,N) (x) mod N RSA assumption No poly-time adversary wins this game with a non-negligible probability. RSA assumption – more formally RSA assumption For any randomized polynomial time algorithm A we have: P(ye = x mod N : y := A(x,N,e)) is negligible in k where N = pq where p and q are random primes such that |p| = |q| = k, and x is a random element of ZN* , and e is random element of Zφ(N)* The ZN* group is a bit strange Some elements of ZN = {0,...,n-1} are not there but you don’t know which if you don’t know p and q. Is it a problem? No, for 2 reasons: • it is hard to find an element in ZN* \ ZN (other than 0), • RSA works also over ZN (“by accident”). Remember the Chinese Reminder Theorem? Example Zpq where p=5, q = 7 x mod 7 x mod 5 0 1 2 3 4 0 0 7 12 17 22 Z35 1 5 1 22 8 29 2 10 16 2 23 9 3 15 31 17 3 24 4 20 11 32 18 4 5 25 26 12 33 19 6 30 6 27 13 34 Z35* It is hard to find an element in ZN \ ZN* (other than 0) Why? ZN mod p Suppose we have found a non-zero element x Z N \ Z N* mod q ZN* For example: x mod q = 0 and x ≠ 0 Hence gcd(x,N) = q. So we can factor N. Example gcd(15,35) = 5 x mod 7 x mod 5 0 1 2 3 4 0 0 7 12 17 22 Z35 1 5 1 22 8 29 2 10 16 2 23 9 3 15 31 17 3 24 4 20 11 32 18 4 5 25 26 12 33 19 6 30 6 27 13 34 Z35* RSA works also over ZN Suppose x is such that x mod q = 0 and x mod p ≠ 0 We show that = xed RSA(N,d)(RSA(N,e)(x)) = x mod N By CRT it is enough to show that: this holds because both sides are divisible by q xed = x mod q xed = x mod p Recall that: (p-1)(q-1) | ed - 1 Hence: (p-1) | ed - 1 Therefore: xed-1 = 1 mod p This implies that xed = x mod p Question? Can we use this permutation for encryption? Answer: • yes, • but not directly... Problems RSApk is deterministic, so: if one encrypts twice the same message then the ciphertexts are the same Therefore if the message space M is small, the adversary can check all possible messages: given a ciphertext c do: for every m є M check if RSApk(m) = c for example if M={yes,no}, then the adversary can decrypt the message. RSA has some “algebraic properties”. Plan 1. Handbook RSA and its insecurity a. introduction b. algebraic properties of RSA 2. Security definitions 3. How to encrypt with RSA a. a practical construction b. a theoretical construction based on hardcore bits 4. Rabin encryption 5. Theoretical constructions Algebraic properties of RSA 1. RSA is homomorphic: RSA(e,N)(m0 · m1) = (m0 · m1)e = m0e · m1e = RSA(e,N )(m0) · RSA(e,N )(m1) why is it bad? By checking if c0 · c 1 = c the adversary can detect if RSA(d,N) (c0) · RSA(d,N)(c1) = RSA (d,N) (c) 2. The Jacobi symbol leaks. Jacobi Symbol +1 - 1 for N=pq define JN(x) := Jp(x) · Jq(x) for any prime p define Jp(x) := QR(p) QR(q) QR(n) mod p if x Є QRp otherwise JN(x) := +1 -1 -1 +1 mod q Jacobi symbol can be computed efficiently! (even if p and q are unknown) Fact: the RSA function “preserves” the Jacobi symbol N = pq - RSA modulus e is such that gcd(e, φ(N)) = 1 JN(x) = e JN(x mod N) Actually, something even stronger holds: RSA(N,e) is a permutation on each “quarter” of ZN* QRp QRq In other words: • m mod p QRp iff me mod p QRp • m mod p QRq iff me mod q QRq QRp Example Z35* Calculate RSA(23,35)(m) = m23 mod 35 QR7 mod 5 QR5 1 4 2 3 1 1 29 22 8 2 16 9 2 23 mod 7 4 11 4 32 18 3 31 24 17 3 5 26 19 12 33 6 6 34 27 13 1 4 3 2 1 1 29 8 22 4 11 4 18 32 2 16 9 23 2 5 26 19 33 12 3 31 24 3 17 6 6 34 13 27 How to prove it? By the CRT and by the fact that p and q are symmetric it is enough to show that m is a QRp iff me is a QRp Fact For an odd e: me mod p is a QRp iff m mod p is a QRp Proof. Let g be the generator of Zp*. Let y be such that m=gy. Recall that x is a QRp iff x is an even power of g It is easy to see that gye = gye mod (p-1) (remember that p and e are odd) (gy)e mod p is an even power of g iff gy mod p is an even power of g. Hence we are done. Conclusion The Jacobi symbol “leaks”, i.e.: from c one can compute JN(Dec(N,d)(c)) (without knowing the factorization of N) Is it a big problem? Depends on the application... Note The fact that the Jacobi symbol leaks does not contradict the RSA assumption. oracle adversary (x,e,N) choose: • N = pq where p and q are random primes such that |p| = |q| = k • x – a random element of ZN* , • e – is random element of Zφ(N)* cannot compute RSA-1(e,N) (x) mod N but can compute JN(RSA-1(e,N) (x) mod N) Question: Is RSA secure? Looks like it has some weaknesses... Plan: 1. Provide a formal security definition. 2. Modify RSA so that it is secure according to this definition. Plan 1. Handbook RSA and its insecurity a. introduction b. algebraic properties of RSA 2. Security definitions 3. How to encrypt with RSA a. a practical construction b. a theoretical construction based on hardcore bits 4. Rabin encryption 5. Theoretical constructions A mathematical view A public-key encryption (PKE) scheme is a triple (Gen, Enc, Dec) of poly-time algorithms, where Gen is a key-generation randomized algorithm that takes as input a security parameter 1n and outputs a key pair (pk,sk). Enc is an encryption algorithm that takes as input the public key pk and a message m, and outputs a ciphertext c, Dec is an decryption algorithm that takes as input the private key sk and the ciphertext c, and outputs a message m’. We will sometimes write Encpk(m) and Decsk(c) instead of Enc(pk,m) and Dec(sk,c). Correctness P(Decsk(Encpk(m)) ≠ m) is negligible in n The security definition Remember the symmetric-key case? We considered a chosen-plaintext attack. How would it look in the case of the public-key encryption? A chosen-plaintext attack (CPA) security parameter 1n 1. selects random (pk,sk) = Gen(1n) 2. chooses a random b = 0,1 pk chooses m’1 m’1 c1 = Enc(pk,m’1) ... chooses m’t challenge phase: chooses m0,m1 m’t ct = Enc(pk,m’t) m0,m1 c = Enc(pk,mb) has to guess b the interaction continues . . . oracle This is not needed. Why? Because if Eve knows pk she can compute all these ciphertexts herself! A simplified view security parameter 1n 1. selects random (pk,sk) = Gen(1n) 2. chooses a random b = 0,1 pk oracle challenge phase: chooses m0,m1 m0,m1 c = Enc(pk,mb) has to guess b CPA-security Alternative name: CPA-secure Security definition: We say that (Gen,Enc,Dec) has indistinguishable encryptions under a chosen-plaintext attack (CPA) if any randomized polynomial time adversary guesses b correctly with probability at most 0.5 + ε(n), where ε is negligible. Is the “handbook RSA” secure? the “handbook RSA” N = pq - RSA modulus e is such that gcd(e,d) = 1, d is such that ed = 1 (mod φ(N)) Enc(N,e)(m) = me mod N, and Dec(d,N)(c) = cd mod N. Not secure! In fact: No deterministic encryption scheme is secure. How can the adversary win the game? 1. he just chooses any m0,m1 , 2. computes c0=Enc(pk,m0) himself 3. compares the result. Moral: encryption has to be randomized. Plan 1. Handbook RSA and its insecurity a. introduction b. algebraic properties of RSA 2. Security definitions 3. How to encrypt with RSA a. a practical construction b. a theoretical construction based on hardcore bits 4. Rabin encryption 5. Theoretical constructions Encoding Therefore, before encrypting a message we usually encode it (adding some randomness). This has the following advantages: • makes the encryption non-deterministic • breaks the “algebraic properties” of encryption. How is it done in real-life? PKCS #1: RSA Encryption Standard Version 1.5: public-key: (N,e) let k := length on N in bytes. let D := length of the plaintext requirement: D ≤ k - 11. Enc((N,e), m) := xe mod N, where x is equal to: k bytes 00000000 00000001 r 00000000 (k - D - 3) random non-zero bytes m D bytes How to encrypt? m Encoding(x) := 00000000 00000001 r 00000000 RSA RSA(Encoding(x)) m How to decrypt? ciphertext y RSA-1(y) check if the format agrees.... 00000000 00000001 r 00000000 m output m Example If the adversary can calculate the Jacobi symbol of 00000000 00000001 r 00000000 m most probably it doesn’t help him in learning any information about m... Security of the PKCS #1: RSA Encryption Standard Version 1.5. It is believed to be CPA-secure. It has however some weaknesses (it is not “chosenciphertext secure”). Optimal Asymmetric Encryption Padding (OAEP) is a more secure encoding. (we will discuss it later) The situation ??? the PKCS #1 encryption scheme is secure RSA assumption holds Can we construct a public-key encryption scheme whose security can be provably based on the RSA assumption? Answer: yes! Plan 1. Handbook RSA and its insecurity a. introduction b. algebraic properties of RSA 2. Security definitions 3. How to encrypt with RSA a. a practical construction b. a theoretical construction based on hardcore bits 4. Rabin encryption 5. Theoretical constructions Notation For an integer x we will write LSB(x) to denote the least significant bit of x. LSB(x) x: In other words: LSB(x) = x mod 2 Fact (informally) LSB is the “hardest bit to compute” in RSA. (it is called a “hard-core bit”). More precisely: If you can compute LSB then you can invert RSA. Note: In some sense it is a “dual” predicate to Jacobi symbol... Recall: security parameter 1k adversary (x,e,N) oracle choose: • N = pq where p and q are random primes such that |p| = |q| = k • x – a random element of ZN* , • e – a random element of Zφ(N)* outputs y We say that the adversary wins if y = RSA-1(e,N) (x) mod N RSA assumption No poly-time adversary wins this game with a non-negligible probability. Game 2 security parameter 1k adversary (x,e,N) oracle choose: • N = pq where p and q are random primes such that |p| = |q| = k • x – a random element of ZN* , • e – is random element of Zφ(N)* • d – such that ed = 1 mod φ(N) outputs b We say that the adversary wins if b is the least significant bit of y = RSA-1(e,N) (x) mod N Theorem Suppose the RSA assumption holds. Then every poly-time adversary wins Game 2 with a probability at most 0.5 + ε(k), where ε is negligible. W. Alexi, B. Chor, O. Goldreich, and C.P. Schnorr On the hardness of the least-signficant bits of the RSA and Rabin functions, 1984 In other words: The least significant bit is a hard-core bit for RSA. Proof strategy Suppose we are given a poly-time adversary For simplicity suppose that this happens with probability 1 that wins Game 2. (not: 0.5 + something) We construct a poly-time adversary that breaks the RSA assumption. Outline of the construction (x,e,N) (x1,e,N) b1 ... (xt,e,N) y=xd bt Observation Adversary can be used to compute LSB of xd mod N. It can also be used to compute (for any c) LSB of c · xd mod N. How? (ce · x, e, N) outputs b’ = LSB((ce· x)d) = LSB (ced · xd ) = LSB (c · xd ) The method The adversary compute: • LSB(2x) • LSB(4x) • LSB(8x) ... Why is it usefull? will use to Observation x≤(N-1)/2 1 2x 2 2x mod N 1 ... N-1 ... ... N-1 1 even = 2x Moral: x [1,...,(N-1)/2] iff 2x mod N is even 2N-2 ... = 2x - N odd x x>(N-1)/2 N-1 Remember: N=pq is odd (N-1)/2 (N-1)/4 1 x 1 N-1 ... ... even = 4x N-1 1 ... N-1 1 = 4x - N 4N-4 ... N-1 1 = 4x – 2N ... = 4x - 3N odd 4x mod N ... even 4 odd 4x 3(N-1)/4 Moral: x [1,...,(N-1)/4] [(N/2)+1,...,3(N-1)/4] iff 4x mod N is even N-1 (N-1)/8 ... x ... 8x ... 7(N-1)/8 Moral: x [1,...,(N-1)/8] [(2N/8)+1,...,3(N-1)/8] [4(N/8)+1,...,5(N-1)/8] [6(N/8)+1,...,7(N-1)/8] iff 8x mod N is even = 8x-7N odd even = 8x-5N = 8x-6N odd = 8x-4N even odd = 8x-2N = 8x-3N odd = 8x-N even = 8x even 8x mod N So we can use bisection 1 N-1 calculate LSB((2·x)d) calculate LSB((4·x)d) calculate LSB((8·x)d) calculate LSB((16·x)d) ... How to encrypt a one-bit message b? (N,e) – public key (N,d) – private key Enc1(N,e)(b) = (LSB(x) b, xe mod N), where x ZN* is random. Dec1(N,d)(b’,y) = LSB(yd mod N) b’ How to encrypt long messages? Let m=(m1,..., mt) Use the one-bit scheme bit-by-bit Enc(N,e)(m1,..., mt) = (Enc1(N,e)(m1),..., (Enc1(N,e)(mt)) Dec(N,d)(c1,..., ct) = (Dec1(N,d)(c1),..., (Dec1(N,d)(ct)) (we omit the security proof) Conclusion Advantage: Security of this scheme is implied by the RSA assumption. RSA assumption holds the public-key encryption scheme that we just constructed is secure Disadvantage: The ciphertext is much longer than the plaintext. It is a rather theoretical construction! Plan 1. Handbook RSA and its insecurity a. introduction b. algebraic properties of RSA 2. Security definitions 3. How to encrypt with RSA a. a practical construction b. a theoretical construction based on hardcore bits 4. Rabin encryption 5. Theoretical constructions question: The situation can we construct PKE based on the “factoring assumption” factoring RSA moduli is hard RSA assumption holds Yes: Rabin encryption public-key encryption exists Rabin encrypion Michael O. Rabin (1931 – ) One of the founding fathers of computer science. • introduced non-determinism • decidability of the monadic second order logic • efficient primality testing • oblivious transfer, • .... received Turing Award in 1976 • introduced by Michael O. Rabin in 1979 • based on squaring in ZN* • security equivalent to factoring Remember squaring modulo N=pq? ZN* ZN* RabinN(x) = x2 mod N This function “glues” 4 elements together Example Z15*: a 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 a2 0 1 4 3 1 5 6 4 4 9 10 1 12 4 1 A nice thing about Rabin’s function factoring RSA moduli is hard RabinN(x) = x2 mod N is a one-way function Finding a square root modulo N is as hard as factoring. Can we base an encryption scheme on this? YES! How to do it? First step: “make the inversion unique”. How to do it? An ad-hoc method: add an encoding (like in the RSA encryption). In such a way that only 1 out of the 4 square roots “make sense”. ZN* ZN* In other words: make the set of legal ciphertexts “sparse” f(x) = x2 mod N Another approach Such an N is called a “Blum integer” Fact Suppose N=pq where p = q = 3 (mod 4) Then the function RabinN(x) = x2 mod N is a permutation RabinN : QRN QRN How does it look like? ZN* ZN* RabinN (x) = x2 mod N QRN QRN Rabin restricted to QRN is a permutation ZN* QRN ZN* RabinN(x) = x2 mod N QRN Rabin restricted to QRN is a permutation - proof Suppose we have x,y QRN such that x2 = y2 mod N Let i,j N be such that x2 = y2 mod p g2i = x mod p and g2j = y mod q where g is a generator of Zp* g4i = g4j mod p and (p-1)/2 ≥ i > j ≥ 0. g4(i-j) mod p p-1 | 4(i-j) = (4k+2)/2 = 2k+1 4k+2 | 4(i-j) 2k+1 | 2(i-j) 2k+1 | i-j i=j x = y (mod p) p = 4k + 3 q = 4k’ + 3 N=pq By a symmetric argument: x = y (mod q) x = y mod N QED How to encrypt a one-bit message b? Fact The least significant bit is also a hard-core bit for the Rabin permutation. a Blum integer RabinN (x) = x2 mod N RabinN : QRN QRN N – public key (N,p,q) – private key Enc1N(b) = (LSB(x) b, RabinN(x)), where x QRN is random. this can be computed if one-1 knows p and q 1 Dec (N,p,q)(b’,y) = LSB(RabinN (y)) b’ Plan 1. Handbook RSA and its insecurity a. introduction b. algebraic properties of RSA 2. Security definitions 3. How to encrypt with RSA a. a practical construction b. a theoretical construction based on hardcore bits 4. Rabin encryption 5. Theoretical constructions Hard-core predicates A concept of a hard-core bit can be generalized to a hard core predicate. Definition (informal) π : {0,1}n {0,1} is a hard core predicate for a trap-door permutation f: {0,1}n {0,1}n if it is impossible to guess π(f-1(y)) from y (significantly better than with prob. 0.5) Example π : {0,1}n {0,1} defined as π(x1,...,xn) = xn is a hard-core predicate for RSA and Rabin. π : {0,1}n {0,1} defined as π(x) = JN(x) for sure is not a hard core predicate for RSA. A fact Does every trap-door permutation have a hard-core predicate? Almost: Suppose that f is a trap-door permutation. It can be used to build a trap-door permutation g that has a hard-core predicate. How to encrypt with such an g? public key: description of g private key: trapdoor t for g Enc1g(b) = (π(x) b, g(x)), where x ZN* is random. Dec1t(b’,y) = π(g-1(y)) b’ Is the public-key encryption in Minicrypt? As far as we know: no! cryptomania public-key encryption exists minicrypt trap-door permutations exist one way functions exist ©2011 by Stefan Dziembowski. Permission to make digital or hard copies of part or all of this material is currently granted without fee provided that copies are made only for personal or classroom use, are not distributed for profit or commercial advantage, and that new copies bear this notice and the full citation.