# cryptography

DHM, RSA,

## Diffie-Hellman-Merkle key exchange

• exchange mutually-created random secret key over insecure channel

• over channel: Alice and Bob agree on prime p (say 97) and base g (say 5)

• Alice

• in secret: chooses random number a in {2, …, p-1} (say 5)

• in secret: computes α = ga mod p ( here α = 55 mod 97 = 21 )

• over channel: sends α ( 21 ) to Bob

• Bob

• in secret: chooses random number b in {2, …, p-1} (say 76),

• in secret: computes β = gb mod p ( here β = 576 mod 97 = 24 )

• over channel: sends β ( 24 ) to Alice

• secret key

• Bob uses αb mod p ( here 2176 mod 97 = 88 )

• Alice uses βa mod p ( here 245 mod 97 = 88 )

DHM correctness

αb   =   (ga)b   =   ga⋅b   =   gb⋅a   =   (gb)a   =   βa

DHM efficiency
• use fast modular exponentiation

DHM security
• to break, eavesdropper needs to solve discrete log (exponent) problem:

given x, find e     ge = x (mod n)

• so far, no one knows how to do this much faster than trying all possible values for x

• how long will this take if n = 10200   ?

## RSA public-key cryptosystem

Alice publishes her public numbers
• picks secret primes p,q     11, 13

• sets public n = p ⋅ q     11 ⋅ 13 = 143

• computes secret φ(n) = (p-1)(q-1)     (11 - 1) ⋅ (13 - 1) = 120

• picks random e in {2, …, φ(n)-1} coprime to φ(n)     23 coprime to 120

• computes secret d = e-1 mod φ(n)     47 = 23-1 mod 120

• publishes n, e     143, 23

Alice's computation
```extended euclid(120,23)
120  23   5   3   2   1   0
5   4   1   1   2
47  -9   2  -1   1   0

so gcd(120,23) = 1 = 47*23 + 120*-9, so
23^-1 (mod 120) = 47
```
Bob sends secret message to Alice
• wants to send secret m=84 (must be coprime to n)   to Alice

• computes β = me mod n

• sends Alice β     24

Bob's computation
```23 = 10111_2

84^1  =  1 *   1 * 84 =  84 mod 143
84^2  =  84 *  84      =  49 mod 143
84^5  =  49 *  49 * 84 =  54 mod 143
84^11 =  54 *  54 * 84 = 128 mod 143
84^23 = 128 * 128 * 84 =  24 mod 143
```
Alice recovers Bob's secret message
• receives Bob's encrypted message β   = 24

• computes m = βd mod n   = 2447 mod 143   = 84

Alice's computation
```47 = 101111_2

24^1  =   1 *   1 * 24 =  24 mod 143
24^2  =  24 *  24      =   4 mod 143
24^5  =   4 *   4 * 24 =  98 mod 143
24^11 =  98 *  98 * 24 = 123 mod 143
24^23 = 123 * 123 * 24 =  19 mod 143
24^47 =  19 *  19 * 24 =  84 mod 143
```
RSA correctness
• mod n: βd = (me)d = me⋅d = m

• if m is coprime to n, by Euler's theorem

• mod n: me⋅d   =   mφ(n)⋅k +1 =   (mφ(n))k m1 =   1 ⋅ m = m

• mod 143: 2447 = (8423)47 = 8423⋅47 = 84120⋅9 +1 = (84120)9 841 = 1 ⋅ 84 = 84

RSA security
• Eve needs either

• to factor n (and then find e inverse, which is easy)

• factor 143 (and find 23 inverse)   or

• to solve β = ?e mod n

• solve 24 = ?23 mod 143

• so far, both problems seem hard … but math hackers keep learning