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`

.