**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)