??? Peter Stevenhagen. 7 augustus 2008 Vierkant voor wiskunde

1

??? Peter Stevenhagen

7 augustus 2008 Vierkant voor wiskunde 2

”Wiskunde en cryptografie” Peter Stevenhagen


Crypto is voor iedereen Peter Stevenhagen


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


Serieuzer: voor spionnen en generaals!

9

Geschiedenis



Geen dagelijkse bezigheid voor de gewone man?

10

Geschiedenis



In deze eeuw een dagelijkse bezigheid voor iedereen!

11

Caesar’s geheimschrift

REANGWJPRKKNSEOGQJZA

12


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


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


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


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


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


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


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


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


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



Breken van de code:

probeer alle mogelijke verschuivingen.

22



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


Nadeel: niet zo handig over de e-mail...

26


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


Breken van de code:

Ga alle permutaties na?

36


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


Hoe lang duurt dat?

41


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


Nu is 1018 seconden is ongeveer 32 miljard jaar. De geschatte leeftijd van het heelal is maar 13 miljard jaar.

43


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


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


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


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




56




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


Algebra voor iedereen Peter Stevenhagen

ALGEBRA I P. Stevenhagen

2007

vanaf 5 februari 2009 in Leiden..... 69

??? Peter Stevenhagen. 7 augustus 2008 Vierkant voor wiskunde

Recommend Documents