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
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( )
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
odd ?
397 1
198 0
99 1
49 1
24 0
12 0
6 0
3 1
1 1
0b 110001101
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
1977 April MIT Rivest Shamir Adelman
1977 August Martin Gardner a new kind of cipher that would take millions of years to break
Bletchley Park => GCHQ => Communications Electronic Security Group (CESG)
James Ellis unpredictable, innovative, not a teamworker, brilliant
save costs on key distribution
Bell telephone report: Alice adds noise, receives msg, subtracts noise
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
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 )
αb = (ga)b = ga × b = gb × a = (gb)a = βa
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)
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)
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
Eratosthenes? too slow
use probabilistic algorithm
definition: b divides n … ?
b,n are integers, and there exists an integer k such that n = b*k
Fermat a lawyer curious about math
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
better than Fermat, because it gives a guaranteed probability bound
try it: clone and run numeric/millerRabin.py
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)
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)
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
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)
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
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)