Cryptography - Notes #3 - Asymmetric-Key Encryption --------------------------------------------------- Symmetric cryptography is useful and efficient, but requires that both parties share a secret key. Establishing such a key can be difficult. Diffie and Hellman investigated the notion of a one-way trapdoor function and its application to cryptography. They are - One way: Meaning that f_t(x) = y is easy to compute, but that f_t^{-1}(y) = x is difficult to compute for most y. - Trapdoor: If some "trapdoor" information t is known, then f_t^{-1}(y) = x is easy to compute. First, some math... ------------------- Definitions: Let Z_n represent the set of integers { 0, 1, 2, ..., n-1 }. Numbers x and y are "relatively prime" or "coprime" if they share no common factors, that is gcd(x,y) = 1. Groups ------ A group is a non-empty set G and binary operation . where - G is closed under . - (a.b).c = a.(b.c) for all a,b,c in G (Associative) - Exists an e in G such that e.a = a.e = a for all a in G (Identity) - Exists for each b in G and inverse a in G so that a.b = b.a = e (Inverse) If (G,.) is also commutative it is an Abelian group. All the groups we will deal with are Abelian. Ex: (Z,+) is an infinite group with identity 0 and inverse of a being -a. (Q-{0},*) is an infinite group with identity 1 and inverse of a being 1/a. Is Q a group? No. Identity must be 1 and then 1 has no inverse. (Z_n, + mod n) is finite with identity 0 and inverse of a being n-a. (Z_n, * mod n) cannot be a group (because 1 must be the identity and 0 is not invertible). So, what subset of Z_n forms a multiplicative group? Z_6^* = { 1, 5 } [figure it out on the board] It turns out that all of the numbers coprime with n are in Z_n^*. (If x shares a factor with n, x will have no inverse.) -- If (G,.) is a group, then x^i is x.x.x ... .x with x appearing i times. If (G,.) is a group and \forall b, \exists i, a^i = b, then a is a generator of G. For example, Z_6^* has no generator, but Z_5 Lagranges Theorem: If (G,.) is a finite group with n elements, then a^n = e for all a \in G. [Try Z_5^* = {1,2,3,4}] -- Rings and Fields are related to Groups, but allow both addition and multiplication (and zeros). Euler Phi --------- Let \phi(n) represent the number of integers in the range 0..n that share no common factors with n. Theorem: If m and n are different coprime numbers, \phi(mn) = \phi(m) \phi(n) = (m-1)(n-1). Proof idea: - Draw out all mn numbers as in 6.3.1 on page 184. - Notice that each column is an equal collection of numbers (mod m), and so there are \phi(m) columns each coprime with m. - Notice that each row (mod n) is Z_n, and so each row has \phi(n) numbers coprime with n. - There are therefore \phi(m)\phi(n) numbers which have no common factors with both m and n, and so do not share any common factors with mn. Diffie-Hellman Key Exchange --------------------------- As part of their work, Diffie and Hellman discovered one of the most famous and well-used techniques in asymetric cryptography: key-exchange. Algorithm. A large prime p and a generator g of Z_p^* are agreed upon. 1. Alice picks a random element a from 1...p-1 (ie, from Z_p^*) and sends g^a (mod p) to Bob. 2. Bob picks a random element b from 1...p-1 (ie, from Z_p^*) and sends g^b (mod p) to Alice. Alice and Bob both now can compute g^{ab} mod p, but a passive eavesdropper only knows g^a and g^b. [Do example] Attacks ------- - There are technical conditions for p, g, a and b which if not met can weaken the scheme. See book. - Because there is no authentication, Malice can launch a "man-in-the-middle" attack by impersonating both parties and establishing keys with each separately. Security -------- Why is this secure? A passive adversary gets g^a, g^b and so g^{a+b} easily. But, she cannot compute g^{ab} without knowing at least a or b. Of course, Malice can compute g^{ab} if she can compute the discrete logarithm of g^a or g^b (mod p). The security depends on the difficulty of discrete logarithm: given g, n and g^x mod n, find x. It is assumed that no adversary can compute the discrete logarithm of a random element of the group with a non-negligible probability in polynomial time (polynomial in n). There are known algorithms that solve the discrete log problem in sub-exponential time, so the modulus should be at least 1024 bits. Note that f(a) = g^a is one way if the discrete logarithm is intractable. But, nobody knows of any trapdoor. RSA --- The RSA function (1978) is a trapdoor function. Alice Key Setup: 1. Choose two random prime numbers so that |p| \approx |q|. 2. Let N = pq. 3. Let \phi(N) = (p-1)(q-1) 4. Choose random e < \phi(N) so that gcd(e,\phi(N)) = 1 and let d = e^{-1} mod \phi(N). 5. Publicize (N,e), keep d as secret. Encryption (one-way function) Given message m < N, e and N. 1. Compute c = m^e (mod N) Decryption (trap-door inversion) Given c, d and N 1. Compute m = c^d (mod N) How does it work? e and d were chosen so that ed = 1 (mod \phi(N) which means ed = 1 + k \phi(N) for some k. So, c^d = m^{ed} = m^{1+k\phi(N)} = (m^1)(m^\phi(N))^k = m(1^k) = m(mod \phi(N)) This works: - So long as m \in Z_N^* // (p-1)(q-1)/pq messages are. - m^\phi(N) = 1 // Which LaGrange's theorem ensures. [Do example, either new or from page 259] Why is this secure? - If Malice knew \phi(N), she could easily compute d from e. - Because p and q are secret, so are (p-1) and (q-1). - \phi(N) will use about the same number of bits as N. - Malice can guess potential \phi(N) values, but there are too many. It is thought that factoring N is the best attack on RSA. So long as factoring large numbers is difficult, RSA is thought to be a good one-way trapdoor function. Security Models --------------- How secure is the RSA primitive? That depends on what model of attack you use. Oracle - Imagine that a key has been established and your job is to: * Find the secret key, or * Discover a plaintext from a ciphertext. You could imagine that you have access to some data that might help you. The oracle gives you the data you request, but limits what you get in the following ways. KCA (known ciphertext attack) - An eavesdropper sees ciphertexts crossing the network. Getting known ciphertexts from the oracle mimics this situation. KPA (known plaintext) - Sometimes an adversary knows what is being encrypted. If the oracle supplies pairs then the adversary can mount a KPA. CPA (chosen plaintext) - If the oracle will encrypt plaintexts for the adversary, then a chosen plaintext attack can be mounted. CCA (chosen ciphertext) - If the adversary can get decryptions from the oracle for a limited time, and then try to break the system by decrypting a new ciphertext, the attack is CCA. CCA2 (adaptive chosen ciphertext) - If the oracle will decrypt for an unlimited time, then the attack is a CCA2 attack. Ex: CCA2 attack on RSA. Let's say an oracle has been instantiated with a secret decryption key d, and everyone has access to the corresponding (e,N) for encryption. The oracle will decrypt anything you give it. The goal is to find the decryption of ciphertext c. We know c = m^e. 1. r \in Z_N^* 2. Send r^e c mod N to the oracle. 3. Oracle returns (r^e c)^d = (r^e m^e)^d = r^{ed} m^{ed} = rm 4. Dividing by r (multiplying by the inverse) yields m So, raw RSA is not secure against CCA2 attack.