# ch6: alice and bob go public

fools   pkc   binary   rsa   alt   dhm   fastexp   prime   fermat   probp   miller   euler   euclid   rsa   correct   secure

## God rewards fools

• Whitfield Diffie, b 1944, MIT, ind. security expert: cipherpunk

• USDoD => Advanced Research Projects Agency => 1969 ARPAnet => internet

• key distribution ?

• 1974 IBM TJ Watson talk => drive to Stanford to find Martin Hellman b 1946

• joined by Ralph Merkle

• 1976 June National Computer Conference : DHM key exchange announced

## birth of public-key crypto

• 1975: Diffie proposes asymmetric key cipher

• symmetric/asymmetric cryptography

• encrypt c = ek1( m )   decrypt m = dk2( c )

• symmetric: easy to determine dk2( ) from ek1( ) (e.g. k2=k1)

• asymmetric: difficult to determine dk2( ) from ek1( )

## binary numbers

• computers use binary (base 2) numbers

• humans use decimal (base 10) numbers

• both are written in positional form

• 397

• 3 * 102     9 * 101     7 * 100

• 111012     0b 1101     (29 base 10)

• 24     23     22           20

convert decimal to binary
```      odd ?
397     1
198     0
99     1
49     1
24     0
12     0
6     0
3     1
1     1

0b 110001101
```
convert binary to decimal
```0b 110001101
0b 1                                        1
0b 11        =  2*(0b 1) +1  = 2*1 +1       3
0b 110       =  2* 0b 11     = 2*3          6
0b 1100      =  2* 0b 110    = 2*6         12
0b 11000     =  2* 0b 110    = 2*12        24
0b 110001    =  2* 0b 110 +1 = 2*24 +1     49
0b 1100011   =  2* 0b 110 +1 = 2*49 +1     99
0b 11000110  =  2* 0b 110    = 2*99       198
0b 110001101 =  2* 0b 110 +1 = 2*198 +1   397

397
```

## rsa

• 1977 April MIT Rivest Shamir Adelman

• 1977 August Martin Gardner   a new kind of cipher that would take millions of years to break

## alternative history pkc

• Bletchley Park => GCHQ => Communications Electronic Security Group (CESG)

• James Ellis   unpredictable, innovative, not a teamworker, brilliant

• save costs on key distribution

• 1969 non-secret encryption (PKC) possible, need one-way function

• 1973 Clifford Cocks (Cambridge) => solves problem (RSA)

• 1975 Malcolm Williamson   finds no flaw in Cocks’ system, key exchange (DHM)

• 1982 Diffie visits Ellis

• 1980s Thatcherism   government bad, private good   GCHQ: go public ?

• 1984 Peter Wright   publishes spycatcher   GCHQ: heads down, hats on

• 1997 Nov   Ellis dies

• 1997 Dec   conference: Cocks on RSA, brief history of GCHQ pkc

## DHM key exchange

• mutually-create random secret key over insecure channel   video

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

• Alice

• in secret: chooses random number a in p (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 p (say 76),

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

• over channel: sends β ( 24 ) to Alice

• secret key

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

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

DHM correctness
• αb = (ga)b = ga × b = gb × a = (gb)a = βa

DHM efficiency
• exponentiation   be = ?

• logarithm (exponent)   x = b?

• modular arithmetic   aka clock arithemetic

• a (mod n)   remainder after integer division a / n

• 46 (mod 12) = 10

• useful property:   for * any of mult, add, subtract:

• a * b (mod n)   =   (a mod n) * (b mod n)   (mod n)

• discrete exponentiation   be (mod n) = ?

• discrete logarithm   given x,n, find ? so that   x = b? (mod n)

## fast exponentiation

```a**423 ?   423 = 0b 110100111

x = 1        a ** 0
1  x = x*x*a    a ** 1
1  x = x*x*a    a ** 3
0  x = x*x      a ** 6
1  x = x*x*a    a ** 13
0  x = x*x      a ** 26
0  x = x*x      a ** 52
1  x = x*x*a    a ** 105
1  x = x*x*a    a ** 201
1  x = x*x*a    a ** 423

compute a**423        at most 2*9 = 18 mults
compute a**e          at most 2*lg(e)  mults
compute a**e (mod n)  at most 2*lg(e)  mults (mod n)
compute a**(10**1000) at most 2* 3322  mults (mod n)
```
DHM example
```p            = 613144603035200518605071627722399281527
base         = 347449578131074797459449734586666998031
alice_secret = 474140564715023867271727810192114419457
bob_secret   = 556327197178837163583577967104054021837

alice_sends  = pow(base,        alice_secret, p)    python pow function
bob_sends    = pow(base,        bob_secret,   p)
alice_key    = pow(bob_sends,   alice_secret, p)
bob_key      = pow(alice_sends, bob_secret,   p)

Alice,Bob probable prime 613144603035200518605071627722399281527
Alice,Bob base           347449578131074797459449734586666998031
Alice sends Bob          344627486120828843474388906075377334410
Bob   sends Alice        409706635860222822429885047531176332371
Alice creates key        450786317947341275948138905696766128062
Bob   creates key        450786317947341275948138905696766128062
```

## Fermat probabilistic primality test

• pick random n with desired number of bits

• repeat t times:

• pick random a in [2,n-1]

• if gcd(a,n) > 1 then n is not prime

• if gcd was 1 for all t choices of a, then n probably prime

## Miller-Rabin probabilistic primality test

• better than Fermat, because it gives a guaranteed probability bound

• try it: clone and run numeric/millerRabin.py

## Euler's theorem 1736

• in proving correctness of RSA, we need this special case of totient theorem:

• for p,q different primes, for n=p*q, for a relatively prime to n,

a(p-1)*(q-1) = 1   (mod n)

## Euclid's gcd 300BC

• for integers positive b and non-negative a, b ≥ a

• gcd(a,0) = a

• gcd(b,a) = gcd(b-a,a)

• can use extended gcd algorithm to find a-1 (mod n)

• try it

```find 35717371 inverse mod 60534384

60534384 - 35717371 * 1 = 24817013  <- remainder
35717371 - 24817013 * 1 = 10900358
24817013 - 10900358 * 2 = 3016297
10900358 - 3016297 * 3 = 1851467
3016297 - 1851467 * 1 = 1164830
1851467 - 1164830 * 1 = 686637
1164830 - 686637 * 1 = 478193
686637 - 478193 * 1 = 208444
478193 - 208444 * 2 = 61305
208444 - 61305 * 3 = 24529
61305 - 24529 * 2 = 12247
24529 - 12247 * 2 = 35
12247 - 35 * 349 = 32
35 - 32 * 1 = 3
32 - 3 * 10 = 2
3 - 2 * 1 = 1   <-- last non-zero remainder is gcd
2 - 1 * 2 = 0   <-- zero

unravel above equations: want gcd as linear combo a,b

1  =  3 * 1  +  2 * -1   ... substitute: 2 = 32 - 3 * 10
1  =  32 * -1  +  3 * 11   ... substitute: 3 = 35 - 32 * 1
1  =  35 * 11  +  32 * -12   ... substitute: 32 = 12247 - 35 * 349
1  =  12247 * -12  +  35 * 4199   ...
1  =  24529 * 4199  +  12247 * -8410  ...
1  =  61305 * -8410  +  24529 * 21019  ...
1  =  208444 * 21019  +  61305 * -71467  ...
1  =  478193 * -71467  +  208444 * 163953  ...
1  =  686637 * 163953  +  478193 * -235420  ...
1  =  1164830 * -235420  +  686637 * 399373  ...
1  =  1851467 * 399373  +  1164830 * -634793  ...
1  =  3016297 * -634793  +  1851467 * 1034166  ...
1  =  10900358 * 1034166  +  3016297 * -3737291  ...
1  =  24817013 * -3737291  +  10900358 * 8508748  ...
1  =  35717371 * 8508748  +  24817013 * -12246039  ...
1  =  60534384 * -12246039  +  35717371 * 20754787

35717371 * 20754787 = 1 + 60534384 * -12246039 = 1 (mod 60534384)  so

35717371 inverse (mod 60534384)  is  20754787
```

## rsa public key cryptosystem

Alice

• uses Miller-Rabin, picks 1000-bit secret primes p, q

• small example: 11, 13

• computes n = p*q

• picks random e in [2, n-1], say 23

• in secret, uses Euclid extended gcd, finds d = e-1 (mod (p-1)(q-1)

• publishes n 143, e 23,   keeps secret p, q, d

Bob, to send encrypted message to Alice,

• first converts from text to a sequence of numbers

• for each number m in sequence

• using fast modular exponentiation, computes β = me (mod n)

• sends β to Alice

• eg. assume m = 84, then β = 8423 (mod 143) = 24

Alice, to decrypt message from Bob,

• for each number β in the sequence she gets, computes βd (mod n)

## rsa correctness

• all arithmetic (mod n)

•   βd   =   (me)d   =   me*d   =   mk(p-1)(q-1)+1   =   m(p-1)(q-1)k * m1   =   (1)k * m1   =   m

## rsa security

Eve can either

• factor n (and then easily find e inverse) or

• solve the discrete log problem β = ?e (mod n)

so far, both problems are computationally intractable (and if either can be solved quickly, then thousands of other problems can also be solved quickly)