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^32 puzzles by choosing random P_i in {0, 1}^32 and x_i, k_i in {0, 1}^128, set puzzle_i = E(0^96 || P_i, "Puzzle # x_i" || k_i). The complexity is O(n).
  • Send all puzzles to Bob.
  • Bob chooses a random puzzle_j and solve it. Obtain (x_j, k_j). The complexity is O(n).
  • Bob send x_j to Alice.
  • Alice and Bob use k_j as 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 a in {1, ..., p - 1} and sends A = g^a mod p to Bob.
  • Bob chooses a random number b in in {1, ..., p - 1} and sends B = g^b mod p to 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.