1
??? Peter Stevenhagen
7 augustus 2008 Vierkant voor wiskunde 2
”Wiskunde en cryptografie” Peter Stevenhagen
7 augustus 2008 Vierkant voor wiskunde 3
Crypto is voor iedereen Peter Stevenhagen
7 augustus 2008 Vierkant voor wiskunde 4
Cryptografie
5
Cryptografie
de kunst (het ambacht?) om geheimschrift te schrijven
6
Cryptografie
de kunst (het ambacht?) om geheimschrift te schrijven
(Grieks: κρυπτ ǫιν + γραφǫιν)
7
Geschiedenis
Voor spelende kinderen en geheime verliefden.
8
Geschiedenis
Voor spelende kinderen en geheime verliefden.
Serieuzer: voor spionnen en generaals!
9
Geschiedenis
Voor spelende kinderen en geheime verliefden.
Serieuzer: voor spionnen en generaals!
Geen dagelijkse bezigheid voor de gewone man?
10
Geschiedenis
Voor spelende kinderen en geheime verliefden.
Serieuzer: voor spionnen en generaals!
In deze eeuw een dagelijkse bezigheid voor iedereen!
11
Caesar’s geheimschrift
REANGWJPRKKNSEOGQJZA
12
Caesar’s geheimschrift
REANGWJPRKKNSEOGQJZA A BCDE FGH I J K L MNOPQR S T U VW X YZ WXY Z ABCDEFGH I J K LMNO P QR S TUV
13
Caesar’s geheimschrift
REANGWJPRKKNSEOGQJZA A BCDE FGH I J K L MNOPQR S T U VW X YZ WXY Z ABCDEFGH I J K LMNO P QR S TUV V – – – – – – – – – – – – – – – – – – – – – – –
14
Caesar’s geheimschrift
REANGWJPRKKNSEOGQJZA A BCDE FGH I J K L MNOPQR S T U VW X YZ WXY Z ABCDEFGH I J K LMNO P QR S TUV V I – – – – – – – – – – – – – – – – – – – – – –
15
Caesar’s geheimschrift
REANGWJPRKKNSEOGQJZA A BCDE FGH I J K L MNOPQR S T U VW X YZ WXY Z ABCDEFGH I J K LMNO P QR S TUV V I E – – – – – – – – – – – – – – – – – – – – –
16
Caesar’s geheimschrift
REANGWJPRKKNSEOGQJZA A BCDE FGH I J K L MNOPQR S T U VW X YZ WXY Z ABCDEFGH I J K LMNO P QR S TUV V I E R – – – – – – – – – – – – – – – – – – – –
17
Caesar’s geheimschrift
REANGWJPRKKNSEOGQJZA A BCDE FGH I J K L MNOPQR S T U VW X YZ WXY Z ABCDEFGH I J K LMNO P QR S TUV V I E R K – – – – – – – – – – – – – – – – – – –
18
Caesar’s geheimschrift
REANGWJPRKKNSEOGQJZA A BCDE FGH I J K L MNOPQR S T U VW X YZ WXY Z ABCDEFGH I J K LMNO P QR S TUV V I E R K A N T – – – – – – – – – – – –
19
Caesar’s geheimschrift
REANGWJPRKKNSEOGQJZA A BCDE FGH I J K L MNOPQR S T U VW X YZ WXY Z ABCDEFGH I J K LMNO P QR S TUV V I E R K A N T V O O R W I S K U N D E
20
Caesar’s geheimschrift
REANGWJPRKKNSEOGQJZA A BCDE FGH I J K L MNOPQR S T U VW X YZ WXY Z ABCDEFGH I J K LMNO P QR S TUV VIERKANT VOOR WISKUNDE
21
Caesar’s geheimschrift
REANGWJPRKKNSEOGQJZA A BCDE FGH I J K L MNOPQR S T U VW X YZ WXY Z ABCDEFGH I J K LMNO P QR S TUV VIERKANT VOOR WISKUNDE
Breken van de code:
probeer alle mogelijke verschuivingen.
22
Caesar’s geheimschrift
REANGWJPRKKNSEOGQJZA A BCDE FGH I J K L MNOPQR S T U VW X YZ WXY Z ABCDEFGH I J K LMNO P QR S TUV VIERKANT VOOR WISKUNDE
Breken van de code:
probeer alle mogelijke verschuivingen.
Er zijn maar 25 (of 26?) mogelijkheden. 23
Susanne’s geheimschrift Vervang iedere letter door een zelf te kiezen exotisch symbool.
24
Susanne’s geheimschrift Vervang iedere letter door een zelf te kiezen exotisch symbool. A B CD E F GH I JK L MNOPQ R S TUVWX Y Z ∼ ⊘ ⊢ ∈ ⊙ ≈ ⊑△× = % ! | & + − ⋆ < > † ⊕ ∩ ∝ ⊲⊳ =
25
Susanne’s geheimschrift Vervang iedere letter door een zelf te kiezen exotisch symbool. A B CD E F GH I JK L MNOPQ R S TUVWX Y Z ∼ ⊘ ⊢ ∈ ⊙ ≈ ⊑△× = % ! | & + − ⋆ < > † ⊕ ∩ ∝ ⊲⊳ =
Nadeel: niet zo handig over de e-mail...
26
Susanne’s geheimschrift Vervang iedere letter door een zelf te kiezen exotisch symbool. A B CD E F GH I JK L MNOPQ R S TUVWX Y Z ∼ ⊘ ⊢ ∈ ⊙ ≈ ⊑△× = % ! | & + − ⋆ < > † ⊕ ∩ ∝ ⊲⊳ =
Nadeel: niet zo handig over de e-mail... Oplossing: je kunt net zo goede gewone letters gebruiken!
27
Substitutieversleuteling HWMWEJGGYUXGWYWTVGL
28
Substitutieversleuteling HWMWEJGGYUXGWYWTVGL QAZ X SWEDCV F R T G B N H YU J MK I O L P A BCDE F GH I J K L MNOPQR S T U VW X YZ
29
Substitutieversleuteling HWMWEJGGYUXGWYWTVGL QAZ X SWEDCV F R T G B N H YU J MK I O L P A BCDE F GH I J K L MNOPQR S T U VW X YZ D – – – – – – – – – – – – – – – – – –
30
Substitutieversleuteling HWMWEJGGYUXGWYWTVGL QAZ X SWEDCV F R T G B N H YU J MK I O L P A BCDE F GH I J K L MNOPQR S T U VW X YZ D I – – – – – – – – – – – – – – – – –
31
Substitutieversleuteling HWM WEJGGYUXGWYWTVGL QAZ X SWEDCV F R T G B N H YU J MK I O L P A BCDE F GH I J K L MNOPQR S T U VW X YZ DIT
– – – – – – – – – – – – – – – –
32
Substitutieversleuteling HWM WE JGGYUXGWYWTVGL QAZ X SWEDCV F R T G B N H YU J MK I O L P A BCDE F GH I J K L MNOPQR S T U VW X YZ DIT
IS
– – – – – – – – – – – – – –
33
Substitutieversleuteling HWM WE JGGY UXGWYWTVGL QAZ X SWEDCV F R T G B N H YU J MK I O L P A BCDE F GH I J K L MNOPQR S T U VW X YZ DIT
IS
VEEL
– – – – – – – – – –
34
Substitutieversleuteling HWM WE JGGY UXGWYWTVGL QAZ X SWEDCV F R T G B N H YU J MK I O L P A BCDE F GH I J K L MNOPQR S T U VW X YZ DIT IS VEEL MOEILIJKER
35
Substitutieversleuteling HWM WE JGGY UXGWYWTVGL QAZ X SWEDCV F R T G B N H YU J MK I O L P A BCDE F GH I J K L MNOPQR S T U VW X YZ DIT IS VEEL MOEILIJKER
Breken van de code:
Ga alle permutaties na?
36
Substitutieversleuteling HWM WE JGGY UXGWYWTVGL QAZ X SWEDCV F R T G B N H YU J MK I O L P A BCDE F GH I J K L MNOPQR S T U VW X YZ DIT IS VEEL MOEILIJKER
Breken van de code:
Ga alle 26! = 403 291 461 126 605 635 584 000 000 permutaties na.
37
Snelle computers en grote getallen Hoe lang duurt het om 26! ≈ 4 · 1026 dingen te doen met een snelle computer?
38
Snelle computers en grote getallen Hoe lang duurt het om 26! ≈ 4 · 1026 dingen te doen met een snelle computer? Kloksnelheden van computers zijn een paar gigahertz: een paar miljard (109) pulsen per seconde! Iets zinnigs doen kost natuurlijk wel een riedeltje pulsen...
39
Snelle computers en grote getallen Hoe lang duurt het om 26! ≈ 4 · 1026 dingen te doen met een snelle computer? Als je computer 400 miljoen dingen per seconde kan doen, ben je klaar na 4 · 1026 18 seconden. ≈ 10 4 · 108
40
Snelle computers en grote getallen Hoe lang duurt het om 26! ≈ 4 · 1026 dingen te doen met een snelle computer? Als je computer 400 miljoen dingen per seconde kan doen, ben je klaar na 4 · 1026 18 seconden. ≈ 10 4 · 108
Hoe lang duurt dat?
41
Snelle computers en grote getallen Hoe lang duurt het om 26! ≈ 4 · 1026 dingen te doen met een snelle computer? Als je computer 400 miljoen dingen per seconde kan doen, ben je klaar na 4 · 1026 18 seconden. ≈ 10 4 · 108
Een jaar heeft 365 × 24 × 60 × 60 = 31536000 seconden. Dus in een eeuw zitten zo’n 3 · 109 seconden, en 1018 seconden is ongeveer 32 miljard jaar. 42
Snelle computers en grote getallen Hoe lang duurt het om 26! ≈ 4 · 1026 dingen te doen met een snelle computer? Als je computer 400 miljoen dingen per seconde kan doen, ben je klaar na 4 · 1026 18 seconden. ≈ 10 4 · 108
Nu is 1018 seconden is ongeveer 32 miljard jaar. De geschatte leeftijd van het heelal is maar 13 miljard jaar.
43
Snelle computers en grote getallen Hoe lang duurt het om 26! ≈ 4 · 1026 dingen te doen met een snelle computer? Als je computer 400 miljoen dingen per seconde kan doen, ben je klaar na 4 · 1026 18 seconden. ≈ 10 4 · 108
Maar 1018 seconden is ongeveer 32 miljard jaar! De geschatte leeftijd van het heelal is maar 13 miljard jaar.... Is de methode dus veilig?? 44
Letterfrequenties Substitutieversleutelingen zijn onveilig voor iedere tekst van enige lengte. Iedere taal heeft namelijk een tamelijk precieze vingerafdruk in zijn relatieve letterfrequenties. Identificatie van de taal van de berichten is daarom vaak al voldoende!
45
Letterfrequenties: voorbeeld A B C D E F G H I J K L M
Engels 82 14 28 38 131 29 20 53 63 1 4 34 25
Nederlands 75 16 12 59 189 8 34 24 65 15 23 36 22
N O P Q R S T U V W X Y Z
Engels 71 80 20 1 68 61 105 25 9 15 2 20 1
Nederlands 100 61 16 0.1 64 37 68 20 29 15 0.4 0.4 14
aantal per 1000 letters 46
Veiligheid Er zijn allerlei verfijningen van schuif- en substitutieversleutelingen die proberen de meest evidente valkuilen te vermijden. Al deze versleutelingen blijken onveilig te zijn als de vijand het versleuteltype kent. Bovendien moet iedere keer vooraf een sleutel worden afgesproken!
47
Enigma
De door de geallieerden gebroken WW2-code
48
ROTORS 1
2
Periode van 263 substituties 3 A
REFLECTOR
B C D E F
49
ROTORS 1
2
Periode van 263 substituties 3 A
REFLECTOR
B C
Zwaktes: Permutaties zijn involuties de letter x gaat niet naar x Rotors kunnen gestolen worden Boeken met begincodes ook
D E F
50
ROTORS 1
2
Periode van 263 substituties 3 A
REFLECTOR
B C D E F
Zwaktes: Permutaties zijn involuties de letter x gaat niet naar x Rotors kunnen gestolen worden Boeken met begincodes ook Gebruiksfouten: herhaling van de drie beginletters testberichten met alleen T ’s uniforme berichtstructuren
51
ROTORS 1
2
Periode van 263 substituties 3 A
REFLECTOR
B C D E F
Zwaktes: Permutaties zijn involuties de letter x gaat niet naar x Rotors kunnen gestolen worden Boeken met begincodes ook Gebruiksfouten: herhaling van de drie beginletters testberichten met alleen T ’s uniforme berichtstructuren
Gedurende de oorlog werden veel berichten ontcijferd. De Duitsers bleven geloven in de onkraakbaarheid van Enigma.
52
Geleerde lessen Een cryptosysteem moet veilig blijven als • de vijand de encryptiemethode kent; • de vijand veel plaintext berichten met versleutelingen kent. De cryptologie schept een theoretisch kader voor dit soort veiligheid.
53
Moderne oplossing • Gebruik een publieke algorithme met een geheime sleutel.
Voorbeelden: DES (Data Encryption Standard, 1974), Rijndael (2001).
54
Crypto voor iedereen
Vandaag de dag zijn er talloze routinematige cryptobehoeften: • • • •
e-mail, credit card data over internet electronische toegang tot persoonlijke (bank)gegevens electronische (betalings)opdrachten mobiel telefoonverkeer
Vaak is er geen tijd of gelegenheid om vooraf een sleutel af te spreken!
55
Crypto voor iedereen
Vandaag de dag zijn er talloze routinematige cryptobehoeften: • • • •
e-mail, credit card data over internet electronische toegang tot persoonlijke (bank)gegevens electronische (betalings)opdrachten mobiel telefoonverkeer
56
Crypto voor iedereen
Vandaag de dag zijn er talloze routinematige cryptobehoeften: • • • •
e-mail, credit card data over internet electronische toegang tot persoonlijke (bank)gegevens electronische (betalings)opdrachten mobiel telefoonverkeer
Moderne crypto-oplossingen • maak de sleutel ook publiek! • spreek een geheime sleutel af over een publieke lijn! 57
INTERACTIEVE PAUZE: zelf versleutelen!
We doen wel een baby-voorbeeld, omdat mensen een miljard keer langzamer zijn in hoofdrekenen dan mijn laptop...
58
Publieke versleuteling
Ieder bericht is te schrijven als een groot getal, of een aantal daarvan. Denk maar aan a = 01, b = 02, . . .. We hakken alle berichten op als getallen van 400 cijfers. (Een beetje meer dan twee dus....) Er zijn meer getallen van 400 cijfers dan er atomen in het heelal zijn. We gaan in plaats van het plaintext 400-cijfer-getal een ander 400cijfer-getal versturen, en we zeggen erbij hoe we dat uit het origineel gemaakt hebben!
59
Eenrichtingsfuncties
De wiskunde geeft ons eenvoudige functies die • de getallen van 400 cijfers permuteren; • in ´ e´ en richting heel gemakkelijk uit te rekenen zijn; • in de omgekeerde richting praktisch niet te berekenen zijn, tenzij je aanvullende informatie hebt
60
Eenrichtingsfuncties
De wiskunde geeft ons eenvoudige functies die • de getallen van 400 cijfers dblue permuteren; • in ´ e´ en richting heel gemakkelijk uit te rekenen zijn; • in de omgekeerde richting zonder aanvullende informatie praktisch niet te berekenen zijn. Wie de functie wel om kan keren heeft kennelijk geheime informatie. Daarmee kan een verzender een electronische handtekening plaatsen! 61
Voorbeeld: RSA (Rivest, Shamir, Adleman)
62
Voorbeeld: RSA Kies een groot getal N . (Denk aan iets van 400 cijfers in plaats van 2 cijfers...) Kies een publieke sleutel e en een geheime sleutel d en zorg dat voor alle gehele getallen
x het getal
xde modulo Voor
N bekeken gelijk is aan x zelf.
N = 100 werken e = 7 en d = 3. 63
0<M
Voorbeeld: RSA M ≡ (M e)d
M
Me
B
Me
? A M≡ (M d)e
coderen, verzenden, en decoderen van M
M
Md
Md
tekenen, verzenden, en verifi¨ eren van de handtekening van een bericht
64
Voorbeeld: RSA De veiligheid van RSA berust er op dat we geen e-de wortels kunnen trekken modulo N zonder N eerst in priemfactoren te ontbinden om een ‘decodeerexponent’ d te berekenen. De ontvanger maakt het grote getal N door twee priemgetallen van ongeveer 200 cijfers te vermenigvuldigen. Hij kan dan een d berekenen om berichten aan hem te decoderen, maar niemand anders kan dat....
65
Waar berusten public key systemen op? • Factoriseren van grote getallen
• Discrete logaritmen modulo grote priemgetallen
• Discrete logaritmen op elliptische krommen
• Discrete logaritmen op jacobianen
In alle gevallen wordt er gerekend in (grote) eindige groepen. 66
Waar berusten public key systemen op? • Factoriseren van grote getallen
• Discrete logaritmen modulo grote priemgetallen
• Discrete logaritmen op elliptische krommen
• Discrete logaritmen op jacobianen
Leer algebra en kom met je eigen methode! 67
Crypto voor iedereen Peter Stevenhagen
7 augustus 2008 Vierkant voor wiskunde 68
Algebra voor iedereen Peter Stevenhagen
ALGEBRA I P. Stevenhagen
2007
vanaf 5 februari 2009 in Leiden..... 69