Cryptography course - Basic key exchange

Online Trusted third party(TTP)
If A,B want to communicate, Eavesdropper sees E (K_a, "A,B" || K_ab) and E (K_b, "A,B" || K_ab)

Similar mechanism is basis of Kerberos system.

It's only safe against evaesdropping attacks not against an active attacker.

TTP should always be online.

Active attack

 - If a money transaction is taking place, what if the attacker just replays the request? Since the key is still the same, another transaction would take place.

Key question

 - can we design key exchange protocols without online TTPs?

- Yes! Public key cryptography.

Merkle puzzles

- Quadratic gap between participants and attackers (2^32 vs 2^64)

 - This looks like the best we can achieve from symmetric block ciphers

Diffie Hellman protocol

 - exponential gap

- Fix a large prime p (e.g. 600 digits), Fix an integer g in {1,...,p}

- Alice: choose random a in {1,...,p-1}

- Bob: choose random b in {1,...,p-1}

- A <- g^a mod p

- B <- g^b mod p

- Alice sends A to Bob and she sends B back

- Now the shared key is : g^ab mod p since both of them can compute it.

How hard is DH function mod p?

- suppose Prime p is n bits long

- best known algo (GNFS): run time exp (O(n^1/3)), so exponential in cube root of n.

- to achieve same security as AES 256 bits, we need modulus size 15360 bits in DH

- but only 512 bits if we use Elliptic curves in place of mod p

- as a result there is slow transition away from (mod p) to elliptic curves

The way we have defined it so far it's insecure against MiTM

Public key encryption

Intro. to Number theory

Z_N = {1,2...N-1} a ring where addition and multiplication mod N can be done.

x.(y+z) = x.y + x.z

For all ints x,y there exist ints a,b s.t. a.x + b.y = gcd(x,y) and a,b can be found efficiently using the extended Euclid alg. For e.g. 2.12 - 1.18 = 6 = gcd(12,18)

If gcd(x,y)=1 we say that x and y are relatively prime.

Modular inversion

Over the rationals, inverse of 2 is 1/2. 

Def: The inverse of x in Z_N is an element y in Z_N s.t. x.y = 1 in Z_N

Lemma: x in Z_N has an inverse iff gcd(x,N) = 1 so Z_N* = set of invertible elements in Z_N = all x s.t. gcd(x,N) = 1

Solving modular linear equations

Solve a.x + b= 0 in Z_N

=> a.x = -b

=> x = -b.a^-1

Find a^-1 in Z_N using extended Euclid. Run time: O(log^2 N)

Fermat's theorem

Let p be a prime. For all x in (Z_p)*: x^(p-1) = 1 in Z_p

Example p=5. 3^4 = 81 = 1 in Z_5

This gives us another way to compute inverses, but less efficient than Euclid

x e (Z_p)* => x.x^(p-2) = 1 => x^(-1) =x x^(p-2) in Z_p

but it doesn't work for non primes.

Run time O(log^3 N)

So, less general and less efficient.

Application of Fermat's theorem - Generating random primes

Let's say we want to generate a large random prime

say, prime p of length 1024 bits (i.e. p ~ 2^1024)

Step 1: choose a random integer p e [2^1024, 2^1025 -1]

Step 2: test if 2^(p-1) = 1 in Z_p

If so, output p and stop. Else goto Step 1.

For 1024 bits prime Pr[p not prime] < 2^-60

We can also get False primes through this method.

Structure of (Z_p)*

It's a cyclic group, there exists g e (Z_p)* {1,g,g^2,...g^p-2} = (Z_p)*

g is called a generator of (Z_p)*

Not every element is a generator.

Lagrange theorem: ord_p(g) always divides p-1

ord_p(g) = |<g>| = generated group of g

Euler's generalization of Fermat

phi(N) = |(Z_N)*|

phi(12) = |{1,5,7,11}| = 4

Phi(p) = p - 1 where p is prime.

If N = p.q where p,q are prime then phi(N) = N-p-q+1  = (p-1)(q-1)

Euler's theorem - For all x in (Z_N)* x^phi(N) = 1 in Z_N - basis of RSA

Example : 5^phi(12) = 5^4 = 625 = 1 in Z_12

Practice questions:

2^10001 % 11 = 1 (Fermat), since gcd(2,11) = 1 and 11 is prime => 2^(11-1) = 2^10 % 11 = 1 => 2^10001 % 11 = 2^1 % 11 = 2

2^245 % 35 = 1 (Euler's generalization) since gcd(35,2) =1 and 35 is not prime, N = 35 = 7.5, so |phi(N)| = 7-1.5-1 = 24 => 2^24 % 35 = 1 => 2^245 % 35 = 2^5 = 32

Modular e'th root

When does the root exist?

e=2, square roots

x, -x => x^2

If p is an odd prime then gcd(2, p-1) !- 1

In Z_11 * , (1)^2 = 1 (-1)^2 = 1 where -1 = 10 (since mod 11)

similarly 2 and 9 map to 4, 3,8 map to 9 and so on.

x in Z_p is a quadratic residue if it has a square root in Z_p.

p odd prime => the number of Q.R. (Quadratic Residue) in Z_p is (p-1)/2 + 1 , extra 1 is for 0.

Euler's theorem about when does a number have a Q.R.

This theorem is not constructive, i.e. it tells us about existence but not how to construct it.

Arithmetic algorithms

Addition,subraction - linear in n (input size)

Division O(n^2)

Multiplication is naively O(n^2) if inputs are n-bits. Karatsuba's algorithm O(n^1.585)

Best(asymptotic) algo: On(n.logn).but is practical on very large numbers.

But Karatsuba's more practical and most crypto libraries use it.

Modular exponentiation is O(n^3).

Some hard problems

District log base 2 mod p for (1) (Z_p)* for large p, (2) Elliptic curve groups mod p

An application: collision resistance

If H(x,y) = g^x.h^y where g,h are generators of G where G = (Z_p)* for large p the finding collisions of H is as difficult as DLog problem.

Now look at some difficult problems modulo composites(above is modulo prime)