BEVEILIGING VROEGER EN NU EN HOE DE WISKUNDE HIERBIJ EEN HANDJE HELPT

BEVEILIGING VROEGER EN NU… EN HOE DE WISKUNDE HIERBIJ EEN HANDJE HELPT Ignace Van de Woestyne Katholieke Universiteit Brussel 1. Inleiding. De cryptologie is de leer die zich bezighoudt met het beveiligen van informatie d.m.v. het coderen en het decoderen ervan. In de cryptologie staan twee doelstellingen centraal. Enerzijds zal men pogen boodschappen zo goed mogelijk te beveiligen door ze met efficiënte technieken te coderen. Het onderdeel van de cryptologie dat deze doelstelling nastreeft noemt men de cryptografie. Anderzijds zal ook gepoogd worden om technieken en strategieën te ontwikkelen om gecodeerde boodschappen te ontcijferen. Het onderdeel van de cryptologie dat zich hiermee bezighoudt noemt men de crypto-analyse. Zonder reeds in technische details te treden kan de vraag gesteld worden naar de noodzaak van de mogelijkheid tot coderen. Codeertechnieken worden reeds eeuwen gebruikt door een eerder select publiek (koningen, spionnen, militairen, criminelen, …) om boodschappen te kunnen doorgeven zonder dat anderen er inzage in krijgen. Met de komst en de doorbraak van het internet hebben coderingstechnieken ook hun intrede gedaan bij elke internetgebruiker en dus weldra, gezien de populariteit van het internet, ook bij het merendeel van de bevolking. Coderen is belangrijk aangezien steeds meer “vertrouwelijke” transacties (bijvoorbeeld aankopen en betalingen via het internet, het opvragen van financiële gegevens en het uitvoeren van financiële transacties, …) via een publiek kanaal, wat het internet is, gebeuren. Aangezien we niet kunnen verhinderen dat informatie “opgevangen” wordt door derden kunnen we er beter voor zorgen dat die informatie niet kan worden ontcijferd waardoor ze voor derden waardeloos wordt. Diegene voor wie het bericht bestemd is moet dit uiteraard wel kunnen ontcijferen. Allereerst zullen we een aantal “oudere” coderingssystemen bespreken die nu nog in beperkte mate gebruikt worden maar volkomen onveilig zijn. Uit deze systemen kan wel een en ander geleerd worden. Daarna volgen enkele coderings- en beveiligingstechnieken die momenteel op het internet veel gebruikt worden.

2. Enkele populaire “oudere” coderingstechnieken. In de cryptologie is het zeer belangrijk kennis te hebben van de klassieke cryptografische systemen (of kortweg cryptosystemen) waarvan sommigen teruggaan tot het begin van onze jaartelling. Enkele hiervan, allen behorend tot de categorie van de substitutiemethodes, zullen we nu bespreken waarbij we eveneens aangeven hoe ze kunnen gekraakt worden (zie ook [2]). De basisidee bij de substitutiemethode bestaat erin elke letter van de oorspronkelijke tekst te vervangen door een andere letter waardoor de tekst onleesbaar wordt. Aangezien ook de lengte van de woorden in een tekst informatie bevat (een veelgebruikt woord in het Nederlands is bijvoorbeeld het woord ‘van’) maakt men dikwijls de afspraak alle spaties en leestekens te verwijderen uit de oorspronkelijke tekst en de letters opnieuw te groeperen in bijvoorbeeld groepjes van vijf. Hieronder volgt een voorbeeld. Voor: Dit is een voorbeeld van de brontekst. Na: DITIS EENVO ORBEE LDVAN DEBRO NTEKS T

Met behulp van het programma CRYPTO, te downloaden vanaf de internetsite http://www.kubrussel.ac.be/WSetew/ is het mogelijk de hieronder beschreven methodes toe te passen. Ook om teksten te decoderen wordt door dit programma handige bijkomende statistische informatie verstrekt zodat vrij snel geslaagd wordt in het opzet. Alle voorbeelden die in deze tekst vermeld worden zijn met behulp van Crypto geconstrueerd.

2.1. De Caesar-codering. Julius Caesar vertrouwde zijn boodschappers niet erg en codeerde daarom zijn berichten. Uit geschriften van die tijd zou blijken dat Julius Caesar elke letter in het alfabet verplaatste over een aantal plaatsen (drie in zijn geval). Indien we als voorbeeld een verschuiving over drie letters toepassen wordt de letter ‘a’ vervangen door de letter ‘d’, de letter ‘b’ door ‘e’, enzovoort. Wanneer we aan het einde van het alfabet gekomen zijn, beginnen we opnieuw van vooraf aan. De letter ‘x’ wordt in het voorbeeld ‘a’, ‘y’ wordt ‘b’ en ‘z’ wordt ‘c’. Samenvattend hebben we het volgende: Voor: ABCDEFGHIJKLMNOPQRSTUVWXYZ Na: DEFGHIJKLMNOPQRSTUVWXYZABC We passen deze methode toe op de onderstaande tekst: Voor: DITIS EENVO ORBEE LDVAN DEBRO NTEKS T Na: GLWLV HHQYR RUEHH OGYDQ GHEUR QWHNV W De ontcijfering gebeurt door het alfabet terug drie plaatsen naar links te verschuiven. Zoals snel kan worden ingezien biedt deze methode niet veel veiligheid. In het Nederlandse alfabet zijn slechts 26 letters, dus in maximaal 25 verschuivingen is de tekst gedecodeerd. We kunnen echter sneller te weten komen over welke afstand het alfabet moet worden verschoven door gebruik te maken van wat eenvoudige statistiek. In een Nederlandstalige tekst komt immers de letter ‘e’ het meeste voor. Door nu de frequenties te berekenen van de letters in de gecodeerde tekst komen we te weten welke letter vermoedelijk de letter ‘e’ is en weten we bijgevolg ook over welke afstand verschoven was. In de onderstaande figuur ziet men de frequentieverdeling van de letters uit het voorbeeld.

De frequentiedichtheid van de letters uit de gecodeerde tekst.

2.2. De mono-alfabetische substitutiemethode. Een veralgemening van de Caesar-codering bestaat erin elke letter van het alfabet te vervangen door een willekeurige andere letter in de plaats van door die letter die men vindt door over een vast aantal letters te verschuiven. In feite komt het hierop neer dat het alfabet vervangen wordt door een nieuw dat ontstaat door toepassing van een permutatie. Deze methode noemen we de monoalfabetische substitutiemethode. Op het eerste zicht hebben we hier te maken met een betrouwbare methode aangezien er 26! = 403291461126605635584000000 mogelijkheden bestaan. In de 2

praktijk zijn het er echter minder omdat een aantal van de permutaties de tekst niet echt zal beveiligen. Denken we bijvoorbeeld aan de permutatie die het alfabet onveranderd laat of die permutaties die slechts twee letters omwisselen. De redenering kan zijn dat, wanneer we de ‘triviale’ permutaties weglaten, er nog voldoende andere overblijven om veilig te zijn. Steunend op de statistiek kan echter toch vrij snel achterhaald worden welke letter staat voor welke. We weten reeds dat de letter ‘e’ het meeste voorkomt in een Nederlandse tekst. Verder is ook geweten wat we als de frequenties van de overige letters mogen verwachten. Naast de individuele letters kunnen we ook kijken naar lettercombinaties van twee letters (digrammen) en van drie letters (trigrammen). Gebruik makend van de te verwachten frequenties en de waargenomen frequenties, gecombineerd met wat gezond verstand en wat gokwerk, komt men vrij snel achter de boodschap. Het dient wel gezegd dat om gebruik te kunnen maken van de geschetste statistische methode, de gecodeerde tekst voldoende tekens moet bevatten. Hieronder bevinden zich de frequentietabellen voor de letters, digrammen en trigrammen zoals we deze mogen verwachten in een doorsnee Nederlandse tekst.

Letter E N A T D R O I L G S V H K M Y P W C B U Z F J X Q

Relatieve frequentie 0.1920 0.1110 0.0740 0.0680 0.0610 0.0590 0.0560 0.0550 0.0400 0.0380 0.0360 0.0340 0.0240 0.0190 0.0180 0.0170 0.0160 0.0150 0.0150 0.0140 0.0140 0.0130 0.0080 0.0010 0.0010 0.0000

Digram EN DE ER AN GE ND TE IN EE EL

Relatieve frequentie 0.0470 0.0334 0.0272 0.0257 0.0213 0.0212 0.0191 0.0166 0.0165 0.0137

Trigram VAN GEN DEN EEN ENT NGE VER AND END TEN


We illustreren het decoderen m.b.v. de bovenstaande frequentietabellen aan de hand van het volgende voorbeeld.

3

Voor: EDOVU DOVMY TQTWV ZRRPW VGRDO ZIVVG TEOVV RDOVS WWVPI DHWVG EMIEZ PVDFE SVNVP

PQNWS RTTEV KVDIR VYYED VTFJT VDVVD JEZOV SPTNP RRPOS RDOVI YTOVR WOVSS VDEDJ

YSHEV MVUPQ RPGRD HVDMV WEWFW TRRDH TFJTW SDMVY SPOVW SSPOV LTNPR PTNPS EZGSS

ETBVW NWSHP TSKKE YVBEV EVKVW VGVDB EWFWE EZMVW VMTWS DEDVV RMRYY DMVYE PJVVY

AVVPJ RLETU HVDWV PGRDR BSOVT SVAVM VKVWB VMTWW DYVVT DWVMT VTNRW ZMVWV OHPSV

VYRDH BVTQT PFHHR YYVDJ AFYYV FDDVD SOVJV VGVPG JRRPI WEDLS EVTVD MTWVD NZVTG

PEZMM WVKVD RDWSW VBSPV DIVDF HVMPR TWRRW RDHVD SPOWR PKRWE YVVTW OVYVW RDGEZ

VDDET SLMSP BVWJV DOWSW JVTNP RMWIS VPEDV OSSPV RDHVA VJVGR VMVDT WVPTS L

WVBVJ WIVHU HEDGR OVURW VMVDI POVDO YMVYV VDRDO EVDSS WKRRM WVGVP NDEVF

JVDGR PQNWS DSDAV VHSPE RRPJE VJRTE WWVPG VPVYV MOVYV WKVDO IEZOV IWVHP

We stellen eerst de frequentietabellen op van de letters, digrammen en trigrammen zoals ze voorkomen in deze tekst. We bekomen de volgende resultaten: Letter alfabet E N A T D R O I L G S V H K M Y P W C B U Z F J X Q


Letter tekst V D W R P S E T O M Y H J G I N Z F K B L A U Q X C


Digram alfabet EN DE ER AN GE ND TE IN EE EL Trigram alfabet VAN GEN DEN EEN ENT NGE VER AND END TEN

Relatieve frequentie 0.0470 0.0334 0.0272 0.0257 0.0213 0.0212 0.0191 0.0166 0.0165 0.0137 Relatieve frequentie 0.0104 0.0099 0.0084 0.0074 0.0072 0.0070 0.0070 0.0067 0.0063 0.0061

Digram tekst VD WV OV RD VP TW SP RR VY VT


Trigram tekst GRD DOV SSP TWV RDO RRP VYV VDO WVP DHV


Meteen valt op dat de letter ‘v’ het meeste voorkomt in de tekst waardoor we kunnen aannemen dat dit waarschijnlijk de letter ‘e’ is. De letter ‘n’ komt in de Nederlandse taal het tweedemeeste voor. Op basis van de frequentietabel van trigrammen mogen we aannemen dat ‘van’ in de tekst gecodeerd is als ‘grd’ aangezien dit het enige trigram is dat eindigt op ‘d’ (= ‘n’). Dit betekent meteen dat ‘g’ de letter ‘v’ voorstelt en dat ‘r’ de gecodeerde letter ‘a’ is. Op basis van de frequentietabellen kunnen we nu vermoeden dat de letter ‘o’ waarschijnlijk een ‘t’ of een ‘d’ is. Op 4

basis van de trigrammen is de ‘d’ het meest waarschijnlijke (‘rdo’ is dan ‘and’). Met deze gegevens hebben we reeds: .NDE. NDE.. ....E .AA.. EVAND ..EEV ..DEE ANDE. ..E.. N..EV ..... .EN.. .E.E.

..... A...E .EN.A E...N E.... ENEEN ...DE ..... AA.D. ANDE. ..DEA .DE.. EN.N.

....E .E... A.VAN .EN.E ..... .AAN. ..... .N.E. ..DE. ...DE ....A ..... ..V..

...E. ..... ..... .E..E .E.E. EVEN. ..... ...E. E.... N.NEE A.A.. N.E.. ..EE.

.EE.. A.... .EN.E .VANA ..DE. .E.E. E.E.. E.... N.EE. N.E.. E..A. ..E.E D...E

E.AN. .E... ....A ..EN. ....E .NNEN .DE.E EVE.V .AA.. ..N.. .E.EN ...EN ..E.V

..... .E.EN AN... E...E N.EN. .E..A ..AA. AN.EN ..D.A ..A.. .EE.. DE.E. ANV..

ENN.. ..... .E..E ND... .E... A.... E..NE D...E AN.E. E.EVA E.EN. .E... .

.E.E. ..E.. ..NVA DE.A. E.EN. .DEND ..E.E ENAND .EN.. ..AA. .EVE. .N.E.

.ENVA ..... N.N.E E.... AA... E.A.. ..E.V E.E.E .DE.E ..END ...DE ..E..

We beginnen nu reeds stukken van de tekst te kunnen ‘verstaan’ waardoor snel bijkomende letters kunnen geïdentificeerd worden. Uiteindelijk zijn we, met wat bijkomende pogingen in staat de volgende tekst terug te vinden. INDEC NDEKL SYSTE JAART EVAND JWEEV SIDEE ANDEO TTERW NGTEV IKWIJ RENUI OEPER

RYPTO ASSIE MENWA ELLIN ESUBS ENEEN BIJDE ORSPR AARDO ANDEW LSDEA TDEOO ENINB

LOGIE KECRY ARVAN GENKE TITUT SAANG SUBST ONKEL ORDET OORDE FSPRA RSPRO IJVOO

ISHET PTOGR SOMMI LEHIE IEMET EVENH ITUTI IJKET EKSTO NINEE AKALL NKELI RBEEL

ZEERB AFISC GENTE RVANA HODES OEZEK EMETH EKSTT NLEES NTEKS ESPAT JKETE DGROE

ELANG HESYS RUGGA LLENB ZULLE UNNEN ODEBE EVERV BAARW TINFO IESEN KSTEN PJESV

RIJKK TEMEN ANTOT EHORE NWENU GEKRA STAAT ANGEN ORDTA RMATI LEEST DELET ANVIJ

ENNIS OFKOR HETBE NDTOT BESPR AKTWO ERINE DOORE ANGEZ EBEVA EKENS TERSO F

TEHEB TWEGC GINVA DECAT EKENW RDEND LKELE ENAND IENOO TMAAK TEVER PNIEU

BENVA RYPTO NONZE EGORI AARBI EBASI TTERV ERELE KDELE TMEND WIJDE WTEGR

De code is gekraakt.

2.3. De poly-alfabetische substitutiemethode. In de voorgaande methodes wordt steeds het alfabet vervangen door een ander. We kunnen ook gebruik maken van meerdere alfabetten, waarbij we bijvoorbeeld afspreken dat het eerste gebruikt wordt om de eerste letter te coderen, het tweede voor de tweede letter en zo verder. We spreken in dit geval van een poly-alfabetische substitutie. De Vigenère-methode ontwikkeld in 1586 door de Fransman Blaise de Vigenère is de meest populaire poly-alfabetische substitutiemethode. De idee in deze methode is om elke letter van de tekst te coderen met de Caesar-methode steunend op verschillende verschuivingen. De sleutel in dit systeem wordt dan gevormd door de verschillende verschuivingen die achtereenvolgens moeten worden doorgevoerd. Praktisch noteert men het aantal verschuivingen door de eerste letter aan te geven van het verschoven alfabet. Meestal wordt als de sleutel een woord of een zin genomen die dan zoveel maal herhaald wordt tot lengte samenvalt met de lengte van de te coderen tekst. Hieronder geven we een voorbeeld.

5

Voor: DESLE UTELI NDITS YSTEE MWORD TDANG EVORM DDOOR DEVER SCHIL LENDE VERSC HUIVI NGEND IEACH TEREE NVOLG ENSMO ETENW ORDEN DOORG EVOER D Sleutel: WISKUNDE Uitgebreide sleutel: WISKU NDEWI SKUND EWISK UNDEW ISKUN DEWIS KUNDE WISKU NDEWI SKUND EWISK UNDEW ISKUN DEWIS KUNDE WISKU NDEWI SKUND EWISK UNDEW ISKUN D Na codering krijgen we het volgende resultaat: ZMKVY HWIHQ FNCGV COBWO GJRVZ BVKHT HZKZE NXBRV ZMNOL FFLET DOHQH ZAZKM BHLZE VYOHQ LIWKZ DYEHI JDGVA RQWIW WDYAZ SNLWX XBRVC MNYYE G Dit is het beste in te zien door gebruik te maken van de volgende tabel waarin de mogelijk gebruikte alfabetten in weergegeven worden. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

B C D E F G H I J K L M N O P Q R S T U V W X Y Z A

C D E F G H I J K L M N O P Q R S T U V W X Y Z A B

D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

E F G H I J K L M N O P Q R S T U V W X Y Z A B C D

F G H I J K L M N O P Q R S T U V W X Y Z A B C D E

G H I J K L M N O P Q R S T U V W X Y Z A B C D E F

H I J K L M N O P Q R S T U V W X Y Z A B C D E F G

I J K L M N O P Q R S T U V W X Y Z A B C D E F G H

J K L M N O P Q R S T U V W X Y Z A B C D E F G H I

K L M N O P Q R S T U V W X Y Z A B C D E F G H I J

L M N O P Q R S T U V W X Y Z A B C D E F G H I J K

M N O P Q R S T U V W X Y Z A B C D E F G H I J K L

N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

O P Q R S T U V W X Y Z A B C D E F G H I J K L M N

P Q R S T U V W X Y Z A B C D E F G H I J K L M N O

Q R S T U V W X Y Z A B C D E F G H I J K L M N O P

R S T U V W X Y Z A B C D E F G H I J K L M N O P Q

S T U V W X Y Z A B C D E F G H I J K L M N O P Q R

T U V W X Y Z A B C D E F G H I J K L M N O P Q R S

U V W X Y Z A B C D E F G H I J K L M N O P Q R S T

V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

W X Y Z A B C D E F G H I J K L M N O P Q R S T U V

X Y Z A B C D E F G H I J K L M N O P Q R S T U V W

Y Z A B C D E F G H I J K L M N O P Q R S T U V W X

Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

We zoeken de eerste letter van de uitgebreide sleutel op in de bovenste rij. Vervolgens zoeken we de eerste letter van de te coderen tekst op in de eerste kolom. Op de doorsnede van de resp. rij en kolom vinden we de gecodeerde letter. Dus ‘w’ bovenaan en ‘d’ links levert als codering ‘z’ op.

6

Gedurende een lange tijd heeft men gedacht dat deze coderingsmethode niet te kraken was. In 1863 echter werd door de Pruisische legerofficier Kasiski een methode ontdekt die de lengte van de gebruikte sleutel bepaalt. Eens deze lengte bepaald is kan vrij snel de codetekst gekraakt worden door telkens maar dat deel van de tekst te bekijken dat met dezelfde Caesar-codering werd gecodeerd. De lengte van de sleutel wordt bepaald door de codetekst verschillende malen te verschuiven tegenover zichzelf en telkens te kijken naar het aantal dezelfde letters op gelijke plaatsen. Een willekeurige verschuiving zal resulteren in een minder aantal overeenkomsten dan wanneer de tekst verschoven wordt over een veelvoud van de gebruikte sleutel. Dit is omdat een aantal letters (zoals de letter ‘e’ in het Nederlands meer voorkomt dan andere) waardoor zij ook meer waarschijnlijk zullen overeenkomen met zichzelf wanneer zij met dezelfde letter gecodeerd werden. Een vereiste om deze techniek te kunnen toepassen is echter dat de codetekst een voldoende aantal tekens bevat. Het bovenstaande voorbeeld is daarvoor net iets te klein. Vandaar een tweede voorbeeld: Gecodeerde tekst: UBGYN VKDWI WSSWH QXPOX OVMTI WSFLJ DCEHH GPRIO DLGEZ VODLE IXZLH RIZYH HPLRP SVOMW FWWOE UAQSY YYIQB VULRS EWGYP FUXGY DYNGW DHOIA CUMAV ABNYW EXQFZ ULVPC RLOIF ZUWYG EZRHQ ZSDRH LEHMV ZVXPE RGSLL CIZIL NOIAC UMAVA ASSYC IZWQV TNHCR

CDLQH TFCJL GRGXM FPLUS MQAHN SYYYL CEYFW MVYHN SNMES HTRQS EWOOF BNYWM LMIQZ

CYPVN LJUGF SSQNP UPLRM SSPSV ASCYV HGPXT POEHW ZZHYD QNPOE PWBOW VYHNP GACSQ

SOUYK BPWKG VGUJU ZOYYF TFPXS YZBHH CGYMI YGIDJ FMOUQ HLHQS CPWQB OEHHH DMYDZ

DWMEV WYXIZ LRFCW QVRLP QQPRG RIWFD EHDUE DHRIZ ZVPHD DADNT OYPWF OIXSW MBYCU

IZBLM CIEZV BPXNS RPHRN PHMAV UVXIC IDWQY RRICI UYKQN INSYU SNYYW NPVEC J

EITSE FKHAN JCYZM OIOOW QYHHH UXPRP WOQZH QBDHO LYYSA EQMON FSYYC SHTIG

VPRHO VKDWI BRHKI YRSDW EMFEC SEUDM NEIDJ IDSOY YGYWI NXIZR AUXGY KWYRV

De frequentiedichtheid van de overeenkomstige letters bij verschillende verschuivingen levert de volgende grafiek op.

Hierbij valt op dat bij een verschuiving over een veelvoud van 6 letters de frequentie van de overeenkomstige letters merkelijk hoger ligt. Dit betekent dat de sleutel vermoedelijk uit 6 letters bestaat. Onderzoek van de letters uit de tekst die met hetzelfde alfabet gecodeerd werden leert ons snel dat de gebruikte sleutel ‘MODULE’ is en de gedecodeerde tekst dezelfde is als deze gebruikt in het voorbeeld uit deel 2.2.

7

2.4. De Vernam-codering. Met de technieken die voorafgingen zou men de vraag kunnen stellen of er wel veilige of onbreekbare codeermethodes bestaan. Op deze vraag moet inderdaad bevestigend geantwoord worden. De Vernam-codering (ook wel one-time pad genoemd) die we nu zullen bespreken is een methode die deze perfecte veiligheid bereikt. De methode werd in 1926 door Vernam [4] voorgesteld met als doel toegepast te worden in de telegrafie. Ook tijdens en na de tweede wereldoorlog werd de methode bij militaire operaties gebruikt. Eerst wordt de tekst omgezet in een binaire voorstelling. Dit kan bijvoorbeeld gebeuren door gebruik te maken van de ASCII-code van elk teken uit de te coderen tekst. Vervolgens nemen we een willekeurige reeks tekens die als sleuteltekst dienst zal doen en die minstens even lang is als de te coderen tekst. Ook de sleuteltekst zetten we om in een binaire schrijfwijze. We overlopen nu de beide binaire voorstellingen en passen per bit de functie XOR (= exclusieve of) toe. In de onderstaande tabel zien we de mogelijke uitkomsten van deze functie. XOR 0 1

0 0 1

1 1 0

De resulterende binaire voorstelling kan nu terug worden omgezet in een tekst met tekens waardoor de gecodeerde tekst ontstaat. Hieronder wordt schematisch weergegeven hoe de letter ‘D’ gecodeerd wordt met de letter ‘G’ uit een sleuteltekst.

Teken Voor Sleutel Na

D G #

ASCII code 68 71 35

Decimale code -32 36 -32 39 +32 3

Binair 0100100 0100111 0000011

XOR

Het decoderen van de tekst gebeurt eenvoudigweg door de gecodeerde tekst nogmaals te ‘coderen’ met dezelfde sleutel. Hieronder volgt een meer volledig voorbeeld. Voor: Met de technieken die voorafgingen zou men de vraag kunnen stellen of er wel veilige of onbreekbare codeermethodes bestaan. Op deze vraag moet inderdaad bevestigend geantwoord worden. De Vernam-codering (ook wel one-time-pad genoemd) die we nu zullen bespreken is een methode die deze perfecte veiligheid bereikt. Sleutel: $d†b2Ÿ z$kƒž? hcˆ@S@+Aet‰E‚#"•YO—/zK,k‘ ‚Q@2qZj‹w"MK ’Ž$d} ™|…s4HL1Ž…PwŽqƒ;Š ? ’g„Y,!…Aˆ)“,j5ŠzX+8‹} A„rQ:j…ARV@–6y‰Ÿ ASh{V-|fO|fb‹e–~SX]MQAw„$r@‰{˜ H‰Œ8:„ “80uUYr5u$/‡Œ’0Nšy‰PtŽƒ–%\B^R"v/6. t6mj\ ‚xlu"HOa-CY–KL?œuRv_f‰… ™GCyˆI|“ 8

–0D0—0*RŸ~NUJDe e\NTs^ &|(f”„IJ <“o4'> † >ƒˆ…Oj^[g–+J)qFu? Œ ‚xE|CU–“$ŠiT“v’$$…^ .—>y Œ7S Na: I!RbvZ .a(KPvH#&F@—‰nA3;F—Cee\—ˆRaz‘c>‘ O”Ž25Ÿj]%cŒŒ Y[j*8C™/Q6x„‰ ŽJ–wK#ƒlOQ? D"M•ef@AGo“c$wX? `zJ/HAG=• /WŒ—‚ˆYr CUpƒE@›"‘Ÿ"–oƒlq‚0eUŒ]G*ƒ9• S“rO ˜Z1ZamA^ lRl
Geheim CA

DA=CA

Geheim CB

DB=CB

A

B

m CA(m) CB(CA(m)) CA(CB(CA(m)))= CB(CA(CA(m))) = CB(m)

CA(m) CB(CA(m)) CB(m) CB(CB (m)) = m

Deze methode werkt omdat bij de Vernam-codering CB(CA(x)) = CA(CB(x)), wat kan worden nagegaan. Enerzijds lijkt het hierboven neergeschreven protocol vrij omslachtig vooral wat de communicatie tussen A en B betreft. Daartegenover staat dat de perfecte veiligheid wordt gegarandeerd. 9

3. Populaire “internet-coderingstechnieken”. Zoals reeds in de inleiding werd aangestipt heeft de doorbraak van het internet als publiek communicatiemiddel de ontwikkeling van beveiligingstechnieken in een stroomversnelling gebracht. Immers de methodes die we tot hiertoe besproken hebben blijken ofwel onbetrouwbaar ofwel vrij omslachtig te zijn m.b.t. de communicatie en vereisen grote sleutels die ook steeds moeten hernieuwd worden. Bijkomend zal een aantal toepassingen dat bijvoorbeeld gebruik maakt van het internet (bijvoorbeeld financiële transacties, doorgeven van vertrouwelijke informatie, …) een elektronisch equivalent van een handtekening moeten kunnen gebruiken. De traditionele methoden die hiervoor beschreven werden zijn niet in staat een dergelijke elektronische handtekening te produceren. Men is dus op zoek gegaan naar andere technieken en heeft die ook gevonden.

3.1. Codering m.b.v. een publieke sleutel. In 1976 werd door Diffie en Hellman [1] de idee van een publieke sleutel cryptografie gelanceerd. De methode bestaat erin dat iemand die gecodeerde boodschappen wenst te ontvangen een volledig coderingsalgoritme inclusief een sleutel publiek maakt. Iedereen die aan die persoon een boodschap wil verzenden zal dit doen met het publieke algoritme en de bijhorende sleutel. Het algoritme moet van die aard zijn dat niemand behalve de ontvanger in staat is te decoderen. De ontvanger zal hiervoor een geheime sleutel (of ‘achterpoortje’) gebruiken. Het coderen werkt m.b.v. functies waarvan gemakkelijk de functiewaarde kan worden berekend voor een bepaalde x maar waarvan de inverse functie quasi onmogelijk te berekenen is. Wanneer dit het geval is kan de gebruikte functie gerust publiek gemaakt worden. De ontvanger moet natuurlijk wel in staat zijn de inverse te berekenen zoniet is hij niet in staat de toegezonden boodschap te decoderen. De meest gebruikte en dus ook uitvoerig geteste publieke sleutel methode is de zogenaamde RSAmethode daterend van 1978 en genoemd naar de ontdekkers Rivest, Shamir en Adleman [3]. De methode maakt gebruik van het gegeven dat het gemakkelijk is twee zeer grote priemgetallen (minstens tweehonderd cijfers per priemgetal) te vermenigvuldigen maar dat het bijzonder moeilijk is uit het product de priemfactoren terug te vinden. Concreet bestaat de RSA-methode uit de volgende stappen. 1. Persoon A wenst gecodeerde boodschappen te ontvangen. Daartoe zal hij twee grote priemgetallen (minstens honderd cijfers per priemgetal) p en q zoeken. Hij berekent hiermee de getallen n = pq en f = (p-1)(q-1). Vervolgens zoekt hij een (groot) getal d zodat 1
We passen de methode toe op een vereenvoudigd voorbeeld. B wil de onderstaande tekst gecodeerd doorsturen naar A. De meest gebruikte en dus ook uitvoerig geteste publieke sleutel methode is de zogenaamde RSA-methode daterend van 1978 en genoemd naar de ontdekkers Rivest, Shamir en Adleman. A heeft de volgende publieke sleutel gepubliceerd: n = 341; e = 43. Eerst zet B de tekst om in een getalvoorstelling. Eenvoudigheidshalve gaan we ervan uit dat elk getal omgezet wordt in een driecijferige code, nl. de ASCII-code. Dit levert de volgende getallen op: 068 101 110 117 103 112 108 104 032 101 116 114 057 111 114 107 115 032 110

101 098 032 105 101 117 101 111 122 032 104 101 055 101 032 107 116 101 046

032 114 100 116 116 098 117 100 111 013 111 110 056 109 100 101 044 110 013

109 117 117 118 101 108 116 101 103 010 100 100 032 100 101 114 032 032 010

101 105 115 111 115 105 101 032 101 082 101 032 101 032 032 115 083 065

101 107 032 101 116 101 108 105 110 083 032 118 110 013 111 032 104 100

115 116 111 114 101 107 032 115 097 065 100 097 032 010 110 082 097 108

116 101 111 105 032 101 109 032 097 045 097 110 103 110 116 105 109 101

032 032 107 103 013 032 101 100 109 109 116 032 101 097 100 118 105 109

103 101 032 032 010 115 116 101 100 101 101 049 110 097 101 101 114 097

Vervolgens berekent B voor elk getal de rest van de deling van de 43-ste macht door 341. Dit resulteert in het volgende. 316 140 220 167 009 107 058 114 032 140 139 053 305 144 053 028 323 032

140 098 032 172 140 167 140 144 023 032 114 140 198 140 032 028 139 140

032 053 298 139 139 098 167 298 144 228 144 220 056 252 298 140 011 220

252 167 167 149 140 058 139 140 009 164 298 298 032 298 140 053 032 032

140 172 323 144 323 172 140 032 140 103 140 032 140 032 032 323 084 241

140 028 032 140 139 140 058 172 220 084 032 149 220 228 144 032 114 298

323 139 144 053 140 028 032 323 157 241 298 157 032 164 220 103 157 058

139 140 144 172 032 140 252 032 157 276 157 220 009 220 139 172 252 140

032 032 028 009 228 032 140 298 252 252 139 032 140 157 298 149 172 252

009 140 032 032 164 323 139 140 298 140 140 268 220 157 140 140 053 157 11

220 151 228 164 Dit stuurt hij naar A. Wanneer A elk getal tot de macht 7 verheft (want 7 was het geheime getal d voor A) en vervolgens de rest berekent van de deling door 341, bekomt hij de gedecodeerde getallen. Er rest hem enkel nog om de getallen om te zetten in tekens om de tekst terug vinden. We merken op dat de in dit voorbeeld toegepaste methode niet veilig is omdat de priemgetallen te klein zijn en omdat elk teken in de tekst aanleiding geeft tot een driecijferig getal dat afzonderlijk gecodeerd wordt. Hierdoor wordt het mogelijk om m.b.v. statistische technieken terug te achterhalen welke code staat voor welke letter. Indien toch met grote priemgetallen gewerkt wordt en een hieraan aangepaste grootte van het blok is de methode wel veilig. Dit komt omdat het in een ‘redelijke tijd’ niet mogelijk is n te ontbinden in p en q met de huidige kennis. Dit betekent niet dat geen andere nog niet bekende technieken mogelijk zijn om te komen tot deze ontbinding. Worden deze gevonden, dan betekent dit het einde van deze beveiligingstechniek. Anderzijds is ook niet bekend of de ontbinding van n wel noodzakelijk is om te decoderen. Misschien bestaan er totaal andere technieken die toch leiden tot de decodering. Methoden die er bijvoorbeeld in slagen de ‘achterpoortjes’ te bereiken, leiden ook tot de decodering. We vermelden hier de wiskunde die schuilgaat achter de RSA-methode. De stelling van Bezout-Bachet: ∀a, b ∈ Ζ ∃ x, y ∈ Ζ : ggd( a, b) = xa + yb . Gevolg 1: Voor a, b ∈ Ζ : ggd( a, b) = 1 ⇔ ∃ x, y ∈ Ζ : 1 = xa + yb . Gevolg 2: Voor a, n ∈ Ζ : ggd( a, n) = 1 ⇔ ∃ b ∈ Ζ : ab ≡ 1 mod n . De kleine stelling van Fermat: Stel dat p een priemgetal is. Dan geldt voor elke a ∈ Ζ met ggd( a, p) = 1 : a p −1 ≡ 1 mod p . Eigenschap: Stel dat n = pq met p en q priemgetallen. Stel verder dat c ∈ Ζ 0+ zodat ggd(c, ( p − 1)(q − 1)) = 1 . Dan bestaat d ∈ Ζ 0+ zodat cd ≡ 1 mod ( p − 1)(q − 1) . Tevens geldt voor elke a ∈ Ζ dat a cd ≡ a mod n .

3.2. Digitale handtekeningen. Een elektronische handtekening is een stukje ‘tekst’ dat aan een boodschap wordt toegevoegd waaruit de ontvanger kan afleiden van wie het afkomstig is. Een elektronische handtekening moet voldoen aan de volgende vereisten: 1. Enkel de zender kan de elektronische handtekening maken. 2. De ontvanger kan controleren dat de handtekening afkomstig is van de zender. 3. De ontvanger kan tegenover derden aantonen dat de zender de handtekening gemaakt heeft. Stel dat A een boodschap m met digitale handtekening naar B wil sturen. Beiden hebben ze een publieke sleutel via de RSA-techniek ter beschikking. Dan dient het volgende te gebeuren:

12

1. A berekent DA(m). 2. A berekent vervolgens CB(DA(m)) en stuurt dit naar B. 3. B berekent DB(CB(DA(m))) = DA(m) en vervolgens CA(DA(m)) = DA(CA(m)) = m. Zo bekomt B de boodschap m en kan hij verifiëren dat ze wel degelijk van A komt aangezien enkel A DA(m) kan produceren. In het hierna volgende schema wordt het versturen van een boodschap met een digitale handtekening nog eens schematisch weergegeven.

Publiek

Geheim DA

CA

A m DA (m) CB(DA(m))

CB

Geheim DB

B CB(DA(m)) DB(CB(DA(m))) = DA(m) CA(DA(m)) = DA(CA(m)) = m

3.3. Secure Sockets Layer (SSL) Secure Sockets Layer, afgekort door SSL, is een veelgebruikte techniek op het internet die gebruik maakt van zowel publieke sleutel codering (RSA) als private sleutel codering (o.a. RC2, RC4, DES, Triple-DES). Op de vermelde private sleutel coderingen gaan we hier niet verder in. SSL wordt op het internet bijvoorbeeld gebruikt bij “digitale” aankopen, d.w.z. aankopen waarbij via het internet vertrouwelijke informatie zoals privé-gegevens of kredietkaart informatie moet worden doorgegeven. Stel bijvoorbeeld dat je een CD wilt aankopen bij Proxis. Proxis stuurt zijn publieke sleutel naar jouw browser. De browser creëert een willekeurige geheime sleutel (te gebruiken met een private sleutel codering) en stuurt deze gecodeerd met de publieke sleutel naar Proxis. Proxis decodeert en ontvangt zo de geheime sleutel. Vanaf nu gebeurt de codering via de gemeenschappelijk bekende geheime sleutel. Als belangrijkste voordelen van SSL zijn de eenvoud van de methode en de snellere codering en decodering wegens het gebruik van private sleutel coderingstechnieken te vermelden. De gebruiker hoeft zich niets aan te trekken van de beveiliging. Deze wordt volledig automatisch door de internetbrowser geregeld. Men merkt ondermeer aan het internetadres dat begint met ‘https’ i.p.v. ‘http’dat de browser communiceert via SSL. De meeste browsers maken gebruik van een 40-bit sleutel. Dit betekent 240 º 1012 mogelijke sleutels. Veiliger zou zijn gebruik te maken van een 128-bit sleutel. Dit betekent 2128 º 1038 mogelijke sleutels. In dat geval heeft men met een huidige computer ongeveer 1018 jaar nodig om de sleutel te vinden. De Amerikaanse wetgeving verbiedt momenteel echter de export van de 12813

bit coderingstechnieken. Als gevolg van de tweede wereldoorlog worden coderingstechnieken immers als oorlogswapens beschouwd.

4. Tot slot. In het overzicht hierboven gegeven vinden we enkele populaire coderingsmethodes. De RSAmethode is omwille van zijn eenvoud en toch grote veiligheid een op het internet veelgebruikte techniek om te coderen. Uiteraard worden er een hele reeks andere methodes gebruikt, de ene al veiliger dan de andere. We kunnen ze onmogelijk allemaal behandelen. Tot slot willen we nog opmerken dat het kraken van beveiligde informatie in de praktijk meestal gebeurt via de ‘zwakke schakel’ in de gebruikte methode. Ook de RSA-methode heeft zijn ‘zwakke punten’, namelijk de ‘achterpoortjes’ die noodzakelijkerwijze geheim moeten blijven. Wanneer deze niet zorgvuldig worden bewaard kunnen buitenstaanders er toegang toe krijgen waardoor ook RSA-gecodeerde informatie in een mum van tijd leesbaar wordt. Meestal krijgen krakers toegang tot de plaatsen waar de geheime informatie te vinden is doordat te voor de hand liggende paswoorden werden gebruikt.

BIBLIOGRAFIE 1. W. Diffie en M.E. Hellman, New directions in cryptography, IEEE Trans. On Information Theory, Vol IT-22 (1976), 644 – 654. 2. T. Moons, How large primes can keep a secret: an introduction to modern cryptology, Sciences, from experimentation to concepts, Proceedings of the “Colloques Scientifiques Internationaux Post-Universitaires” (CSIPWIC), J. Aghion, J. Depireux, R. Holvoet (Eds.), Université de Liège, (1992), 78 – 111. 3. R.L. Rivest, A. Shamir en L. Adleman, A method for obtaining digital signatures and publickey cryptosystems, ACM Communications, Vol. 21 (1978), 120 – 126. 4. G.S. Vernam, Cipher printing telegraph systems for secret wire and radio telegraphic communications, J. Amer. Inst. Elec. Eng., Vol 45 (1626), 109 – 115.

INTERESSANTE INTERNETSITES Museum Exhibits Cryptology, http://www.nsa.gov:8080/museum/tour.html NOVA Online Decoding Nazi Secrets, http://www.pbs.org/wgbh/nova/decoding/ Pythagoras' Cryptografie Links, http://www.wins.uva.nl/misc/pythagoras/cryptografie.html RSA Security Inc, http://www.rsasecurity.com SSH – Cryptographic Algorithms, http://www.ssh.fi/tech/crypto/algorithms.html Website van de workshops ETEW van de K.U.Brussel, http://www.kubrussel.ac.be/WSetew/

E-mail adres: [email protected]

14

BEVEILIGING VROEGER EN NU EN HOE DE WISKUNDE HIERBIJ EEN HANDJE HELPT

Recommend Documents