This is a note of week 5 of the Coursera course Cryptography I. The topic is basic key exchange: how to setup a secret key between two parties. Public-key cryptography can be used to generate shared keys without an online Tursted Third Party (TTP). Merkle (1974), Diffie-Hellman (1976), and RSA (1977) are three early solutions.
1 Merkle Puzzles
The main tool in Merkle’s solution is puzzle: a solvable problem that takes some time to solve. For example, a puzzle is try 2^32 values to find the right key. Then
- Alice prepares
n = 2^32puzzles by choosing randomP_i in {0, 1}^32andx_i, k_i in {0, 1}^128, setpuzzle_i = E(0^96 || P_i, "Puzzle # x_i" || k_i). The complexity isO(n). - Send all puzzles to Bob.
- Bob chooses a random
puzzle_jand solve it. Obtain(x_j, k_j). The complexity isO(n). - Bob send
x_jto Alice. - Alice and Bob use
k_jas the shared key.
The eavesdropper takes O(n^2) = 2^64 to find the key if the cipher/hash implementation is not used. It is unknown if we can achieve a better gap with a block cipher.
2 The Diffie-Hellman Protocol
This is the first practical public key protocol.
Fix a large prime p about 600 digits or 2000 bits. Fix an interger g in {1, ..., p}. The pair of (p, g) is fixed.
- Alice chooses a random number
ain{1, ..., p - 1}and sendsA = g^a mod pto Bob. - Bob chooses a random number
bin in{1, ..., p - 1}and sendsB = g^b mod pto Alice. - Alice calculates shared key as
B^a mod p = g^(ab) mod p. - Bob calculates shared key as
A^b mod p = g^(ab) mod p.
The Diffie-Hellman protocol can be applied in other algerbic structures such as elliptic curve that is much harder to break. New systems are using Elliptic Curve Cryptograph (ECC).
| Cipher key size | DH | EC |
|---|---|---|
| 80 | 1024 | 160 |
| 128 | 3072 | 256 |
| 256 | 15360 | 512 |
DH is insecure against man-in-the-middle attach.
DH protocol can be non-interactive as long as everyone post his g^k first, then any two of them can have the shared secret key without any interaction. For three-person party, thre is Joux protocol to create a shared key. It is an open problem when the party has four or more members.
3 Modular Arithmetic
3.1 Basics
Number theory can be used to construct key exchange protocol, digital signature, and public-key encryption.
Let N denote a positive integer, p denote a prime, Let set Zn = {0, 1, ..., N - 1} that does addition and multiplication modulo N. All the laws (distributive, associative, commutative) also work in the set.
Fact: for all integer x and y, there exist integers a and b such that: ax + by = gcd(x, y). Extended Euclid algorithm can be used to find a and b.
If gcd(x, y) = 1, then x and y are relatively prime.
The inverse of x in Zn is an element y in Zn such that xy = 1 in Zn. y is denoted as x^(-1).
Lemma: x in Zn has an inverse if and only if gcd(x, N) = 1. Because gcd(x, N) = ax + bN, the extended Euclid algorithm can be used to find the inverse. The runtime is log squared O((logN)^2).
Set of invertible elements in Zn is denoted as Z*, it is the set of elment x that gcd(x, N) = 1. For prime p, the Z* for Zp is all elments in Zp except 0.
For a linear equation: ax + b = 0 in Zn, the solution is x = - b * a^(-1).
3.2 Fermat, Euler and Lagrange
Fermat theorem: let p be a prime, for every x: {1, 2, ..., p - 1}, i.e., Z*, x^(p-1) = 1 in Zp.
It also means that x^(-1) = x^(p-2) can be used to find an inverse, but it is less efficient (it is O(logp)^3) than Euclid.
Another application (also less efficient) is to find a large random prime p by testing 2^(p-1) = 1 in Zp, the result could be a false prime but the probability of false prime is negligible for large prime numbers.
Euler theorem: Z* is a cyclic group that there exists a g such that {1, g, g^2,,, g^(p-2)} = Z*, g is called a generator of Z*. For example, 3 is a generator for p=7.
For any g in Z* of p, the set {1, g, g^2,,, g^(p-2)} is called the group generated by g, denoted <g>. The order of g is the size of <g> that is the smallest a such that g^a = 1 in Zp.
Euler’s generalization of Fermat: for any x in Z*, x^(phi(N)) = 1. The phi function is defined as the size of Z*, phi(N) = |Z*|. If N = p * q a product of two primes, then phi(N) = N-p-q+1 = (p-1)(q-1).
Lagrange theorem: for any g in Z* of p, its order divides p-1. In other words, an order is always a factor of p-1. It is a generalization of Euler’s theorem.
3.3 Modular e'th Roots
Let p be a prime and c in Zp. If x in Zp such that x^e = c, then x is the e‘th root of c.
The e'th root may not exist. If gcd(e, p-1) = 1, then e’th root of any c exists. Because gcd(e, p-1) implies there exists d such that de=1 in Z(p-1) and c^d^e = 1. c^d is the e'th root of c.
When e=2, we have the square root.
Definition: z in Zp is a quadratic residue (Q.R.) if it has a square root in Zp. Bcause x^2 = (-x)^2, if p is an odd prime, then the number of Q.R. in Zp is (p - 1) / 2 + 1. Adding one here because 0 is always a Q.R.
Euler’s theorem: if x in Z* for odd prime p is a Q.R., then x^((p-1)/2)=1 in Zp.
Note that for x!=0, x^((p-1)/2)=((x^(p-1))^(1/2))=1^(1/2) that has results of either 1 or -1.
x^((p-1)/2) is called the Legendre Symbol of x over p (in year 1798).
When p = 3 (mod 4), then the square root of c is c^((p+1)/4). When p = 1 (mod 4), it is a lit harder ,O((logp)^3)), to find square root of c.
Finally, finding e'th root of modulo composite is much harder.
4 Intractable Problems
Distributed Log (DLOG) algorithm: if y = g^x in Zp, find x = log(y) with base g.
DLOG is hard if for all efficient algorithm, the probability of sovling it is negligible.
Two examples of hard problems are 1) Z* for large p and, 2)elliptic curve groups mod p. The elliptic curve is harder than the Z* for the same bits problems.
An application of the hard problem is the construction of ollision cesistant hash function. Let q=|G| be a prime, choose generators g, h of G, for x, y in {1,...,q}, define the hash function H(x, y) = g^x * h^y.
Another application uses composites. Let N = P * q where p, q are n-bit primes, there are two hard problems: 1) factor a random N and 2) find a solution for polynomial f(x) where degree(f) > 1 and a random N.