Het geheim van goede koffie
Benne de Weger
oktober 2013
[email protected] http://www.win.tue.nl/~bdeweger
versturen van geheimen hoe moet je een geheim opsturen als onderweg iemand kan afluisteren? niet: achterop een ansichtkaart schrijven postbode (en wie al niet meer) leest mee
al veel beter: in een dichtgeplakte envelop een dichte envelop openen is strafbaar een slimme afluisteraar krijgt hem wel open
goed: in een kistje dat op slot kan veilig als het kistje goed stevig is
1
1
versleutelen: kistje met een slot twee vrijwilligers: Alice en Bob de rest van de klas is postbode / afluisteraar
Alice schrijft een geheim briefje aan Bob Alice krijgt een kistje met een sleuteltje Alice doet het briefje in het kistje en ze doet het kistje op slot Alice geeft het kistje aan een postbode via een paar postbodes komt het kistje bij Bob en dan…? Bob’s probleem: hoe komt hij aan het sleuteltje? verzin een paar mogelijke oplossingen
2
versleutelen: kistje met een hangslot een hangslot is bijzonder: het kan dichtgedaan worden zonder dat het sleuteltje nodig is Bob stuurt via de postbodes zijn open (!) hangslot naar Alice Alice sluit het kistje af met Bob’s hangslot Alice verstuurt het afgesloten kistje naar Bob via de postbodes Bob kan het nu met zijn sleutel openmaken Bob is de enige die dat kan
3
2
was dit veilig? was dit handig? de postbodes krijgen alleen een open hangslot en een afgesloten kistje in handen dit is veilig, mits het kistje stevig genoeg is Bob zijn sleuteltje goed bewaakt de postbode geen sleutel kan maken die bij het hangslot past
dit is handiger het kistje hoeft maar één keer opgestuurd te worden
dergelijke systemen worden veel gebruikt bijvoorbeeld voor internet-bankieren
4
publieke sleutel-cryptografie iedereen heeft een sleutelpaar bestaande uit een publieke sleutel (hangslot) en een privésleutel (sleuteltje) die op elkaar passen iedereen mag een kopie van de publieke sleutel hebben uit de publieke sleutel is de privésleutel niet af te leiden
bekendste methode heet RSA gebaseerd op het moeilijk zijn van ontbinden in priemfactoren
5
3
gedachtenexperiment Alice en Bob doen het volgende: ze doen elk apart eerst wat berekeningen dan roepen ze wat getallen naar elkaar die de hele klas kan afluisteren dan doen ze elk apart nog wat berekeningen
na afloop beschikken ze beide over hetzelfde geheime getal dat de anderen in de klas niet te weten kunnen komen
let wel: alle communicatie tussen Alice en Bob is afgeluisterd
denk je dat dit kan?
6
Alice, Bob, en de Cipier
7
4
de oplossing Alice zet koffie met precies genoeg melk stuurt die naar Bob
Bob zet koffie met precies genoeg suiker stuurt die naar Alice
Alice doet er precies genoeg melk bij Alice is blij
Bob doet er precies genoeg suiker bij Cipier kan wel beide onderscheppen en bij elkaar doen
Bob is blij
maar dat is teveel koffie Cipier is niet blij 8
Diffie-Hellman ja, dat kan bedacht door Whitfield Diffie en Martin Hellman in 1976
Alice en Bob hebben elk een sleutelpaar ze sturen elkaar hun publieke sleutel die mag iedereen weten, ook de afluisteraar wel moet je weer zeker weten van wie de publieke sleutel is
Alice en Bob maken nu ieder dezelfde geheime sleutel daarmee kan Alice een kistje op slot doen en Bob kan het kistje openmaken
in de digitale wereld zijn sleutels getallen 9
5
modulo-rekenen Diffie-Hellman werkt met modulo-rekenen klokrekenen is rekenen modulo 12 7 uur na 8 uur is het 3 uur 7 + 8 ≡ 3 (mod 12) 12 heet de modulus
kan ook met een andere modulus m je zegt a ≡ b (mod m) als a en b een m-voud verschillen modulo 17 zijn er maar 17 verschillende getallen 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 want 17 ≡ 0, 18 ≡ 1, 19 ≡ 2, … (mod 17) en -1 ≡ 16, -2 ≡ 15, -3 ≡ 14, … (mod 17)
je kunt altijd terug naar een getal ≥ 0 en ≤ m – 1 10
sleutelparen bij Diffie-Hellman Diffie-Hellman systeemparameters een groot priemgetal p een getal g met 1 < g < p – 1
voorbeeld: (met kleine getallen)
p = 19, g = 3
een Diffie-Hellman sleutelpaar privésleutel: willekeurig getal met 1 < x < p – 1 publieke sleutel: y ≡ gx (mod p)
x = 5, y = 15 want 35 = 243 ≡ 15 (mod 19) x = 6, y = 7 want 36 = 729 ≡ 7 (mod 19)
11
6
Diffie-Hellman sleutelafspraak
verschillende berekeningen zelfde uitkomst
12
een voorbeeld systeemparameters:
p = 19, g = 3
sleutelpaar van Alice:
xA = 5, yA = 15
sleutelpaar van Bob:
xB = 6, yB = 7
Alice berekent:
sA = 75 = 16807 ≡ 11 (mod 19)
Bob berekent:
sB = 156 ≡ (-4)6 = 4096 ≡ 11 (mod 19)
het gedeelde geheime getal is nu s = 11
13
7
waarom werkt dit? sleutelpaar van Alice is xA, yA ≡ gxA (mod p)
xA = 5 yA = 15 ≡ 35 (mod 19)
sleutelpaar van Bob is xB, yB ≡ gxB (mod p)
xB = 6 yB = 7 ≡ 36 (mod 19)
Alice berekent sA ≡ yBxA (mod p)
sA ≡ 75 (mod 19)
dit is yBxA ≡ (gxB)xA = gxBxA (mod p) Bob berekent sB ≡ yAxB (mod p) dit is yAxB ≡ (gxA)xB = gxAxB (mod p) dat is dus hetzelfde geheim: s = sA ≡ sB (mod p)
75 ≡ (36)5 = 36x5 (mod 19) sB ≡ 156 (mod 19) 156 ≡ (35)6 = 35x6 (mod 19) s ≡ 36x5 = 35x6 (mod 19) 330 ≡ 11 (mod 19)
14
veiligheid van Diffie-Hellman waarom is dit veilig? een afluisteraar ziet alleen: systeemparameters p, g en publieke sleutels yA, yB en wil graag een privésleutel weten kun je x berekenen uit y = gx ? als y = gx dan is x = glog(y) logaritmen zijn toch makkelijk? waarom is de privésleutel dan toch veilig? 15
8
logaritmen bij gewone getallen zijn makkelijk
6 5 4 3 2 1 20
40
60
80
100
16
logaritmen (mod p) zijn moeilijk 100 80 60 40 20
20
40
60
80
100
17
9
versleutelen en ontsleutelen met Diffie-Hellman met het gedeelde geheim s kun je nu een bericht B versleutelen tot een geheimschrift G een geheimschrift G ontsleutelen tot het oorspronkelijke bericht B
s = 11 B = 13
dat kan heel simpel: Alice versleutelt met vermenigvuldigen (mod p) G ≡ B x s (mod p) Bob ontsleutelt met delen (mod p) B ≡ G / s (mod p)
G = 9 want 13 x 11 = 143 ≡ 9 (mod 19) B = 13 want 9 / 11 ≡ 143 / 11 = 13 (mod 19)
(optellen en aftrekken is minder veilig…) 18
computerpraktikum Diffie-Hellman op school zelf doen met grotere getallen modulo-rekenen op de laptop met het programma MCB publieke sleutels en geheimschriften uitwisselen via een gedeelde netwerk-map privésleutels en geheime berichten alleen opgeslagen in eigen map of zelf met de web-versie MCR:
http://www.win.tue.nl/~bdeweger/MCR
19
10
de wiskunde erachter
20
11
