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 randomP_i in {0, 1}^32
andx_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_j
and solve it. Obtain(x_j, k_j)
. The complexity isO(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 sendsA = g^a mod p
to Bob. - Bob chooses a random number
b
in in{1, ..., p - 1}
and sendsB = 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
.