Key Exchange

How could Alice, Bob, and Christ to exchange keys safely? Use trusted third party, (TTP)

Centralized key exchange
Centralized key exchange

Basics of Kerbose. Insecure against active attacks, such as replay attacks.

Decentralized key exchanges:

  • Merkel (1974)
  • Diffe-Hellman (1976)
  • RSA (1977)
  • ID-based enc. (BF 2001)
  • Functional enc. (BSW 2011)

Merkel Puzzles

E(k, m) is a symmetric cipher with k{0,1}128k \in \{0,1\}^{128}, define puzzle(P) = E(P, “message”), where P=096b1,...b32P = 0^{96}||b_1,... b_{32}.

  • Alice prepare 2322^{32} puzzles, set puzzleiE(096Pi,Puzzle#xjkj)puzzle_i \leftarrow E(0^{96}|| Pi, Puzzle \#x_j || k_j), and send all of them to Bob.
  • Bob choose a random puzzle, solve it, obtain (xj,kj)(x_j, k_j), and send xjx_j to Alice.

The eavesdropper needs to to solve 2322^{32} puzzles to figure out the kjk_j specified by xjx_j, so the time complexity is O(n2)O(n^2).

Quadratic gap is possible if we treat ciper as a black box oracle.


Fix a large prime pp, (e.g 600 digits, {0,1}2000\{0, 1\}^{2000}). Fix an integer g such that 0<gp0 < g \le p.

Alice choose random a such a<pa < p, Bob choose random b such as b<pb < p.

  • Alice -> Bob: Aga(mod p)A \leftarrow g^a (mod\ p).
  • Bob -> Alice: Bgb(mod p)B \leftarrow g^b (mod \ p)

Then, they can get the secret:

  • Alice: Ba(mod p)=gabB^a (mod \ p) = g^{ab}
  • Bob: Ab(mod p)=gabA^b (mod \ p) = g^{ab}

the mod p is the number space ZpZ_p, see Number Theory below.

Best known algorithm to solve DH problem, arithmetic modular function, is roughly exp(O(n3))exp(O(\sqrt[3]{n})), thus

Cipher size Modulus size Elliptic Curve size
80bits 1024 bits 160 bits
128 b8ts 3072 bits 256 bits
256 bits 15360 bits 512 bits

Alternatively, we can use elliptic curve to decrease the size, see above.

The Diffie-Hellman is insure against man-in-the-middle attack.

Public-Key Encryption

Define the (G, E, D):

  • G: randomize algorithm to generate key pairs (pk, sk).
  • E(pk, m) takes mMm\in M and output cCc\in C.
  • D(sk, c) takes cCc \in C and outputs mMm \in M or \perp.

Number Theory

Notion: NN is a positive number, pp is a positive prime number, and ZN={0,1,...,N1}Z_N = \{0, 1, ..., N-1\}.

The modular arithmetic: x(y+z)=xy+xzx \cdot (y + z) = x \cdot y + x \cdot z.

For all integers. x,yx, y there exists integers. a,ba, b such that ax+by=gcd(x,y)a \cdot x + b \cdot y = gcd(x, y).

Inverse of x in ZNZ_N is an element in ZNZ_N, aka xy=1x \cdot y = 1 in ZNZ_N. x in ZNZ_N has an inverse if and only if gcd(x,N)=1gcd(x, N) = 1.

Proof: a,b:ax+bN=ax=1\exists a, b: a \cdot x + b \cdot N = a \cdot x = 1. thus x1=ax^{-1} = a in ZNZ_N.

ZN={xZN:gcd(x,N)=1}Z^*_N = \{ x \in Z_N: gcd(x, N) = 1\}

Fermat’s theorem

Let p be a prime, xZp:xp1=1\forall x \in Z^*_p: x^{p -1} = 1

To generate large random prime:

  1. Choose a a random integer p[21024,210251]p \in [2^{1024}, 2^{1025} -1]
  2. test if 2p1=12^{p-1} = 1 in ZpZ_p.
  3. If so, output p. Otherwise, go to step 1

The chance that p is not prime < 2602^{-60}.

Euler Theory

(Zp)(Z_p)^* is a cyclic group, that is g(Zp)\exists g\in (Z_p)^*, such that {1,g,g2,...gp2}=(Zp)\{1, g, g^2, ... g^{p-2}\} = (Z_p)^*. g is called a generator of (Zp)(Z_p)^*.

Given g(Zp)g \in (Zp)^*, the set of {1,g,g2,...}\{1, g, g^2, ... \} is called the group generated by g, denoted as <g>. The order of g(Zp)g \in (Z_p)^* is the size of <g><g>: ordp(g)=<g>=(smallest a>0,s.t. ga=1Zp)ord_p(g) = |<g>| = (smallest\ a > 0, s.t.\ g^a = 1 \in Z_p) Thm Lagranage: g(Zp):ordp(g) divides (p1)\forall g \in (Z_p)^*: ord_p(g)\ divides\ (p -1).

Euler’s ϕ\phi function

for an integer NN, define ϕ(N)=(ZN)\phi(N) = |(Z_N)^*|. Examples:

  • ϕ(p)=p1\phi(p) = p - 1.
  • For N=pq:ϕ(N)=Npq+1=(p1)(q1)N = p \cdot q: \phi(N) = N - p - q + 1 = (p -1)(q - 1).

Euler’s theorem: x(ZN):xϕ(N)=1\forall x \in (Z_N)^*: x^{\phi(N)} = 1.

Modular e’th roots

When does c1/ec^{1/e} in ZpZ_p exists? Suppose gcd(e,p1)=1gcd(e, p - 1) = 1, for all c in (Zp)(Z_p)^*, c1/ec^{1/e} in ZpZ_p exists. let d=e1d = e^{-1} in Zp1Z_{p-1} , c1/e=cdc^{1/e} = c^d in ZpZ_p.

x in (Zp)(Z_p)^* is Quadratic Residue, aka Q.R, if and only if x(p1)/2=1x^{(p - 1)/2} = 1 in ZpZ_p. p is odd prime.

Arithmetic algorithms

How to support 2048 bit number arithmetic operations? Karatsuba 1960: use 3 mults to achieve O(nlog23)=O(n1.585)O(n^{\log_2{3}}) = O(n^{1.585}).

Define: Dlogg(gx)=xDlog_g(g^x) = x.

DLOG is hard in G if for all efficient algorithm A: PrgG,xZq[A(G,q,g,gx)=x]Pr_{g \leftarrow G, x \leftarrow Z_q} [A(G, q, g, g^x) = x] is negligible. such as:

  • (Zp)(Z_p)^* for large p, see Diffle-Hellman
  • Elliptic curve group mod p

Collision resistance

For a group G, q = |G| be a prime, choose generate g, h of G, for x,y{1,...q}x, y \in \{1, ... q\}, define H(x,y)=gxgyH(x, y) = g^x \cdot g^y in G. Finding collision for HH is as hard as computing DLOGg(h)DLOG_g(h).