Hoofdstuk 9 Cryptografie 9.1
Geheimtaal
Ter bescherming van privacy en van vertrouwelijke mededelingen wordt sinds de oudheid gebruik gemaakt van geheimschriften. Als kind wisselden mijn vriendjes en ik boodschappen onder elkaar uit die gecodeerd waren. De code bestond eruit dat elke letter van het bericht over een vaste afstand in het alfabet verschoven werd. Met verschuiving over afstand 2 zou het bericht DIT IS EEN BERICHT gecodeerd worden als FKV KU GGP DGTKEJV Dit bood volgens ons destijds voldoende bescherming tegen vermeende spionnen. Later kwam ik er achter dat deze codering bekend staat als de Caesar substitutie, naar de Romeinse keizer Julius Caesar (100-44 v.Chr.). Het aantal mogelijke coderingen op deze wijze is natuurlijk 26, het aantal verschillende verschuivingsafstanden dat mogelijk is. Als het eenmaal bekend is dat we de Caesar methode gebruiken dan is het voor een afluisteraar niet moeilijk meer de code te kraken. Iets moeilijker wordt het als we een substitutiecode gebruiken. Iedere letter van het alfabet wordt vervangen door een andere letter. Het aantal manieren daarvoor is natuurlijk 26!, heel wat meer dan de 26 van daarnet en voor een afluisteraar dus lastiger te kraken. Om de substitutie te onthouden kan men gebruik maken van bepaalde sleutelzinnen, zoals, De aardappels zijn gaar maar de wortels nog niet De substitutie bestaat erin dat we de letters van het alfabet ABCDEFGHIJKLMNOPQRSTUVWXYZ vervangen door de verschillende letters van de sleutelzin in de volgorde waarin ze verschijnen, gevolgd door de overige letters van het alfabet. De vervangende letters in ons voorbeeld zijn dus 67
68
HOOFDSTUK 9. CRYPTOGRAFIE DEARPLSZIJNGMWOTBCFHKMQUVXY
Het bericht AAP NOOT MIES wordt met deze codering vertaald in DDT WOOH MIPF. De eerlijkheid gebiedt ons te zeggen dat ook dergelijke substitutiecodes voor een professionele kraker niet moeilijk te ontcijferen zijn vanwege de vele redundanties die er in de geschreven taal voorkomen. In de loop van de tijd zijn er vele, steeds ingewikkelder, methoden bedacht om berichten te coderen. Het meest tot de verbeelding sprekende voorbeeld is dat van de Duitse coderingsmachine Enigma waarvan de codering in de tweede wereldoorlog door de geallieerden gekraakt werd. In onze tegenwoordige wereld, waarin telecommunicatie en electronisch dataverkeer cruciaal zijn, is het van groot belang dat onze privacy bij deze uitwisseling gewaarborgd blijft. Denk alleen maar aan de vele financiele transacties die bijna iedereen via internet uitvoert. Zoals het thuisbankieren en de internetbetalingen met creditcard. Daarom is een goede coderings- of encryptiemethode van levensbelang voor onze communicatie. Een zeer veel gebruikte coderingsmethode bij electronisch verkeer is het DES-algoritme (Data Encryption Standard), een Amerikaanse standaard encryptiemethode die rond 1976 ontwikkeld is door IBM. Voor de uitvoering van het DES-algoritme wordt een bericht in blokken van 64 bits verdeeld. Elk van deze blokken wordt vervolgens met een reeks arithmetische operaties versleuteld, waarbij een vaste sleutel van eveneens 64 bits wordt gebruikt. Het aardige is dat het DES-algoritme met dezelfde sleutel het bericht ook weer ontcijfert. Een voor ons belangrijke toepassing van DES is die in onze Chipknipkaarten. Dit zijn kaarten waarop zo’n mooi electronisch uitziend plakje gemonteerd zit. Dit is in feite een klein computertje waarin het saldo van de kaart in electronsiche vorm opgeslagen zit. Bovendien is de chip in staat een aantal eenvoudige bewerkingen uit te voeren. Stoppen we zo’n kaart in een chipkaartautomaat, dan willen we graag dat de automaat onze kaart accepteert als betaalmiddel en vervolgens het bedrag van onze aankoop van de kaart afschrijft. Voordat het zover is moet de automaat er van overtuigd worden dat de kaart bonafide is. Het is namelijk niet moeilijk om illegale chipkaarten te maken die de automaat (electronisch) vertellen dat er een hoop geld op staat. Een chipkaartautomaat is echter zeer wantrouwig en onderneemt eerst een aantal stappen, een zogenaamd protocol, om de echtheid van de kaart te verifi¨eren. Dit protocol berust op het DESalgoritme en het gaat als volgt. De chipkaart bevat een DES-sleutel S die strict geheim is. Deze sleutel zit zo in de chip verborgen dat het vrijwel onmogelijk is deze te achterhalen. Verder bevat de chipkaart een getal D(S) dat ontstaan is door S met een supersleutel te coderen. Deze supersleutel is ingebouwd in alle chipkaartautomaten. Eigenlijk gaat het om meerdere supersleutels, maar voor het verhaal houden we het op ´e´en. De kaart geeft eerst zijn getal D(S) aan de automaat af. Deze ontcijfert het het met de supersleutel en vindt zo dus de
9.2. PUBLIEKE SLEUTELS
69
geheime code S van de kaart. Nu is het weer de beurt aan de kaart. Deze wil eerst weten of de automaat wel bonafide is. Daartoe stuurt de chipkaart een willekeurig getal naar de automaat. Deze vercijfert het getal met de S die hij gevonden heeft en stuurt het antwoord naar de kaart. De kaart ontcijfert dit getal weer met zijn sleutel S en kijkt of het oorspronkelijke getal weer tevoorschijn komt. Is dat het geval, dan weet de kaart dat de automaat de goede sleutel S te pakken heeft. De enige manier voor de automaat om daar achter te komen was het in bezit hebben van de supersleutel. Dus moet de automaat wel bonafide zijn. Nadat aldus de chipkaart is gerustgesteld is het de beurt aan de automaat. Deze wil weten of de kaart echt is en doet het omgekeerde. De automaat stuurt een willekeurig getal naar de kaart die het met de sleutel S vercijfert. Het antwoord gaat naar de automaat terug. Vervolgens ontcijfert de automaat dit weer met S en vergelijkt het resultaat met het oorspronkelijke getal. Zijn ze gelijk dan is ook de automaat gerustgesteld. Het is nu duidelijk dat de kaart de sleutel S bevat en de enige manier waarop de kaart in bezit kan zijn van zowel S als D(S) is doordat de kaartenmakers de supersleutel gebruikt hebben. Deze is echter in de vertrouwde handen van de autoriteit die de kaarten en automaten beheert. Met deze laatste opmerking hebben we ook meteen een zwak punt van het systeem aangestipt. De supersleutel is immers bevat in de chipkaartautomaten die bij wijze van spreken zomaar op straat staan. Er hoeft maar ´e´en zo’n automaat gekraakt te worden en het leed kan groot zijn. In de praktijk blijkt echter dat het ontfutselen van de geheime sleutel van een chipkaart een flinke dosis techniek vereist, zo het al mogelijk is. Het kraken van een automaat is, volgens de banken, nog vele malen lastiger. Een andere belangrijke toepassing van DES is die bij het wachtwoordbeheer in UNIX-systemen, waar men met verschillende personen op ´e´en computer of binnen ´e´en netwerk werkt. Omdat de sleutellengte bij DES wat te kort zou worden, is er inmiddels een opvolger van verschenen in de vorm van AES (Advanced Encrypted Standard, 2001). Een voordeel van systemen als DES en AES is hun grote snelheid. Een nadeel is dat men met de encryptie-sleutel ook meteen de decryptie- of ontcijferingsmethode in handen heeft. Sinds de 70’er jaren is dit kritieke probleem echter ondervangen door de zogenaamde public key cryptografie. Men verwacht dan ook dat naarmate de chips sneller worden, de rol van DES/AES overgenomen gaat worden door public key-methoden. In de volgende paragrafen besteden we daar aandacht aan.
9.2
Publieke sleutels
De laatste 30 jaar heeft men cryptografisch systemen ontwikkeld met als bijzondere eigenschap dat, gegeven de codeersleutel, het praktisch onmogelijk is om de decodeersleutel te vinden. Deze ontwikkeling heeft de wereld van de cryptografie
70
HOOFDSTUK 9. CRYPTOGRAFIE
in een enorme stroomversnelling gebracht. Iedere instelling of persoon, die we even aangeven met Otto, kan een eigen codeer/decodeer sleutelpaar aanmaken en vervolgens de codeersleutel publiek bekend maken aan iedereen die het maar horen wil. De decodeersleutel is daarentegen strikt geheim en als het goed is alleen aan Otto bekend. Iedereen die een vertrouwelijk bericht naar Otto wil sturen versleutelt dat eerst met de publieke codeersleutel en verzendt dat. De verzender hoeft niet bang te zijn dat het bericht gelezen wordt door onbevoegden, aangezien de decodeersleutel niet uit de codeersleutel afgeleid kan worden. Alleen Otto, die in het bezit is van de decodeersleutel, kan het bericht lezen en doet dat ook als het bericht aankomt. Tegenwoordig is er al software verkrijgbaar, public domain zelfs, waarmee het mogelijk is om bijvoorbeeld via e-mail op deze wijze met elkaar te communiceren. Voor degenen die een dergelijk verhaal voor het eerst lezen is de brandendste vraag: hoe kun je een codeersleutel maken, zonder dat de decodeersleutel daaruit afgeleid kan worden? Hiervoor zijn verschillende methoden bekend waarvan wij alleen de populairste behandelen, namelijk het RSA-cryptosysteem, genoemd naar hun uitvinders Rivest, Shamir, Adleman. Het sleutelpaar wordt als volgt gemaakt. Kies een tweetal priemgetallen p, q van, zeg, minstens 200 cijfers en stel N = pq. Bereken λ = φ(N ) = (p − 1)(q − 1) en vernietig vervolgens p en q. We hebben ze niet meer nodig. Kies k ∈ N zo dat ggd(k, λ) = 1 en l ∈ N z´o dat kl ≡ 1 (mod λ). De keuze van k is makkelijk. Omdat λ zo’n groot getal is, zal vrijwel iedere keuze van k een getal opleveren waarvoor ggd(k, λ) = 1. Voor de berekening van l gebruiken we vervolgens het Euclidisch algoritme. De publieke sleutel bestaat uit het paar k, N en de geheime sleutel bestaat uit l, N . Stel we willen een bericht versturen. Op de computer staat dit bericht al als een lange rij hexadecimale cijfers op onze harde schijf opgeslagen. We hakken deze rij in een aantal blokken met vaste lengte en beschouwen deze als getallen die verzonden moeten worden. Geef zo’n getal met B aan (van Bericht). We nemen aan dat B < N voor alle blokken met getalwaarde B. Het protocol verloopt als volgt. De verzender bepaalt het gecodeerde bericht C door de berekening C ≡ B k (mod N ). Zoals we in Hoofdstuk 8 uitgelegd hebben is er voor machtsverheffing modulo N een zeer snel algoritme, zelfs als k erg groot is. De verzender verstuurt het getal C naar Otto. Vervolgens berekent Otto het getal C l (mod N ). Nu komt het aardige. We weten dat kl gelijk is aan een veelvoud van λ plus 1, zeg kl = 1 + mλ. Verder weten we dat aλ ≡ 1 (mod N ) voor elke a ∈ (Z/N Z)∗ . Dus, C l ≡ B kl ≡ B 1+mλ ≡ B (mod N ) en Otto kan de waarde van B aflezen. Stel nu dat een eventuele hacker het bericht C onderweg afluistert en het wil ontcijferen. Om de decodeersleutel te achterhalen moet deze hacker het getal l bepalen. Omdat dit uit kl ≡ 1 (mod φ(N )) moet gebeuren, moet de hacker het
9.2. PUBLIEKE SLEUTELS
71
getal φ(N ) kennen. Over het probleem om φ(N ) uit N , te berekenen hebben we het al eens gehad. We moeten N in de factoren p, q ontbinden en vervolgens φ(N ) = (p − 1)(q − 1) berekenen. Dit is de enig bekende methode en het grote probleem daarbij is het feit dat we N moeten ontbinden. Met de tegenwoordige techniek is het namelijk onmogelijk een willekeurig getal van bijvoorbeeld 200 cijfers te ontbinden, ook al gooien we alle rekenkracht van de computers over de wereld tegen dit probleem aan. Let wel, de ons bekende ontbindingsmethoden leveren uiteindelijk altijd wel een antwoord, omdat het om een eindig probleem gaat. De tijd die een dergelijke ontbinding vergt is echter veel langer dan de leeftijd van het universum, in ieder geval te lang om nog bruikbaar te zijn. De functie die twee priemgetallen met elkaar vermenigvuldigt is een hele simpele, ook als die priemgetallen 100 of meer cijfers lang zijn. Het omgekeerde proc´ed´e, de ontbinding van het product, is praktisch onuitvoerbaar. Een dergelijke functie noemen we een ‘trapdoor’ functie. De naam ‘trapdoor’ slaat op het feit dat de functie in ´e´en richting makkelijk uit te voeren in, maar in de tegenovergestelde richting praktisch onuitvoerbaar. Met praktisch onuitvoerbaar bedoelen we dat er wel een methode is die uiteindelijk tot een antwoord leidt, alleen kost het veel te veel tijd om nog bruikbaar te zijn. In een Scientific American artikel uit 1977 legde Martin Gardner de werking van het RSA-systeem uit. Als uitdaging voor de lezers had Rivest daarin een geheime boodschap versleuteld met een sleutel van 129 cijfers. Deze code kraken betekende dat een getal van 129 cijfers ontbonden moest worden, een onmogelijke opgave in 1977. Echter, in 1994 slaagde de Nederlandse wiskundige Arjen Lenstra erin de geheime sleutel in handen te krijgen. Hiervoor was een half jaar rekentijd nodig, verspreid over zo’n 1600 werkstations, bereidwillig beschikbaar gesteld door collegas over de hele wereld. De geheime boodschap luidde: The magic words are squeamish ossifrage Deze ontwikkeling betekent dat RSA-sleutels van zo’n 130 cijfers tegenwoordig niet meer veilig zijn. Dat is echter geen probleem, we maken gewoon de sleutels wat langer, bijvoorbeeld 200 cijfers. Het zal waarschijnlijk zeer lang duren voordat getallenfactoriseerders raad weten met dit soort getallen. Ik moet hier aan toevoegen dat H.te Riele en zijn team er in 1999 in slaagden een RSA-getal van 140 te cijfers te ontbinden (februari) en een RSA-getal van 155 cijfers (september). Het enorme voordeel van een publieke sleutel is duidelijk. Otto hoeft niet met elke gesprekspartner een nieuwe afspraak te maken over een geheim codeer/decodeer sleutelpaar. Iedereen kan de publieke sleutel gebruiken om vertrouwelijke berichten naar Otto te sturen. Het aardige is dat dit idee ook omgedraaid kan worden om electronische handtekeningen te zetten. Stel dat Otto een bank is, die van ´e´en van zijn klanten, Peter, te horen krijgt dat er f 5000,- naar een meubelzaak moet worden overgemaakt. Alvorens een bank dit doet moet er wel geverifieerd worden of de opdracht inder-
72
HOOFDSTUK 9. CRYPTOGRAFIE
daad van Peter afkomstig is. Bovendien wil Otto er zeker van zijn dat Peter later niet kan ontkennen dat hij de opdracht ooit gestuurd heeft. Hiervoor gebruiken we het volgende idee. Peter maakt ook gebruik van RSA en heeft in het kader daarvan een publieke sleutel en een geheime sleutel. Peter’s publieke sleutel is bij de bank bekend, in analogie met de handtekeningkaart die een bank van zijn klanten heeft. Peter schrijft nu een bericht naar de bank, bijvoorbeeld ‘Mijn naam is Peter, maak s.v.p. f 5000,- over naar de meubelwinkel’. Dit bericht wordt door Peter met zijn geheime sleutel versleuteld en samen met het bericht zelf naar de bank verstuurd. De bank ontcijfert het versleutelde deel met Peter’s publieke sleutel en constateert dat de ontcijfering overeenkomt met de gewone tekst. Dus moet het bericht afkomstig zijn van Peter. Hij is namelijk de enige die het bericht z´o kan versleutelen dat de publieke sleutel weer de oorspronkelijke tekst oplevert. Dit laatste impliceert tevens dat Peter later niet kan ontkennen dat hij het bericht verstuurd heeft. Dit systeem werkt dus precies als een handtekening, alleen veel betrouwbaarder en bovendien electronisch. Een klein saillant detail dat steeds oplaait in discussies over de juridische aspecten van systemen als RSA is dat ook de criminele wereld van dit soort systemen gebruik kan maken. Zelfs als de politie daarvoor toestemming heeft, is het niet mogelijk om RSA-gecodeerde berichten af te luisteren. Bij de standaardisering van cryptografische technieken wordt er daarom naar subtielere vormen van codering gezocht. Een van de technieken is dat er een soort ‘master’-sleutel bestaat waarmee zelfs gecodeerde berichten door justitie ontcijferd kunnen worden. Echter, deze sleutel wordt verdeeld over meerdere betrouwbare instanties (wat ‘betrouwbaar’ ook mag betekenen). Pas als een bepaalde meerderheid van deze instanties toestemming verleent, kan de sleutel gereconstrueerd worden en gebruikt. De getaltheoretische trucs die hier achter zitten zijn echter steeds ingewikkelder varianten op het gebruik van Euler’s stelling aφ(n) ≡ 1 (mod n).
9.3
Zero-knowledge proofs
Een andere toepassing van trapdoor-functies is die voor zero-knowledge proofs. Kort gezegd betekent dit dat het mogelijk is om aan te tonen dat men bepaalde sleutelinformatie bezit zonder deze sleutel prijs te geven. Om iets concreter te zijn stellen we ons twee personen voor, Anton en Vera. Deze namen heb ik niet zelf verzonnen, ze zijn afkomstig van een soortgelijk verhaal dat Jan van der Craats eens tijdens een lerarencursus heeft gehouden (zie [Cra]). Anton neemt contact op met Vera en wil aantonen (vandaar Anton) dat hij werkelijk Anton is en niet een of andere bedrieger die zich als Anton voor wil doen. Vera moet dit kunnen verifieren (vandaar Vera) alvorens haar gesprekspartner te vertrouwen (nogmaals Vera). E´en methode zou zijn dat Anton zijn geheime password aan Vera doorgeeft, dat alleen bekend is aan hem en Vera. Het zwakke punt hiervan is dat de lijn afgeluisterd kan worden. Onbevoegden zouden zo het password
9.3. ZERO-KNOWLEDGE PROOFS
73
van Anton te weten kunnen komen en zich vervolgens voor Anton uitgeven. Een ander probleem kan zijn dat Vera nogal slordig is met passwords en Anton zijn password liever niet aan haar toevertrouwt. Beide problemen kunnen omzeild worden met een zero-knowledge proof. Een eerste mogelijkheid zou zijn om gebruik te maken van een RSA sleutelpaar zoals in de vorige paragraaf beschreven. Het password van Anton zou bestaan uit de geheime sleutel en de publieke sleutel fungeert als de naam waaronder Anton publiekelijk bekend is. Een mogelijk protocol zou zijn dat Vera aan Anton een willekeurig bericht stuurt. Hierop versleutelt Anton dit bericht met zijn geheime sleutel en stuurt dit naar Vera terug. Vera ontvangt dit versleutelde bericht en laat de publieke sleutel erop los. Als het resultaat overeenkomt met de originele tekst door Vera verstuurd, dan kan Vera ervan uitgaan dat ze Anton aan de lijn heeft. Anton is immers de enige die in staat is het bericht zo te versleutelen dat de publieke sleutel er weer het originele bericht van maakt. Een nadeel van deze op RSA gebaseerde methode is dat de machtsverheffingen die nodig nodig zijn voor (de)coderingen tamelijk reken-intensief zijn. Als Anton bijvoorbeeld een gewone chipkaart is, en Vera de chipkaart-automaat, geeft dit problemen. De gangbare chips op een chipkaart zijn tegenwoordig nog te zwak om deze berekeningen aan te kunnen. Een goed alternatief, dat veel minder rekenintensief is, is de identificatieprocedure van Goldwasser, Micali en Rackof uit 1985. Dit gaat als volgt. Neem voor N een getal dat product is van twee grote priemgetallen p, q. Het geheime password van Anton noemen we a. Voor de naam waarmee Anton publiekelijk bekend is neemt hij A ≡ a2 (mod N ) met 0 < A < N . Het identificatie protocol verloopt als volgt. Anton kiest een willekeurig getal x en stuurt het kwadraat X ≡ x2 (mod N ) naar Vera. Vervolgens stelt Vera ´e´en van de volgende twee vragen, i. Stuur x ii. Stuur ax Als Anton werkelijk Anton is vormt dit geen probleem en Vera kan verifi¨eren dat x2 ≡ X (mod N ) in geval (i) en dat (ax)2 ≡ AX (mod N ) in geval (ii). Wat zou een bedrieger kunnen doen om zich als Anton voor te doen? Na verzending van A, om zich als Anton aan te kondigen, heeft hij een keus. Hij kan gokken dat Vera vraag (i) gaat stellen. In dat geval kiest hij x willekeurig en verstuurt X ≡ x2 (mod N ). Als antwoord op Vera’s vraag (i) kan hij vervolgens x versturen. De bedrieger kan ook gokken dat Vera vraag (ii) gaat stellen. In dat geval kiest hij x willekeurig, maar verstuurt A−1 X (mod N ). Als antwoord op Vera’s vraag (ii) kan hij vervolgens x versturen. De kans dat de bedrieger de goede vraag kiest is 1/2. We kunnen dit vraag- en antwoordspel echter herhalen. De kans dat een bedrieger twee maal goed gokt is uiteraard 1/4 en de kans dat het 50 maal goed gaat voor de bedrieger is 2−50 ≈ 10−15 . Deze kans is voor Vera klein genoeg om voor lief te nemen en als ze 50 maal het goede antwoord heeft ontvangen kan ze
74
HOOFDSTUK 9. CRYPTOGRAFIE
er vrijwel zeker van zijn dat Anton aan de andere kant van de lijn zit. Uiteraard verloopt een dergelijk protocol geheel geautomatiseerd zonder tussenkomst van werkelijke personen. Een tweede mogelijkheid voor een bedrieger om zich als Anton uit te geven is de vergelijking a2 ≡ A (mod N ) oplossen. Echter, de enig bekende manier is om het equivalente simultane stelsel a2 ≡ A (mod p) , a2 ≡ A (mod q) op te lossen. Hiervoor hebben we wel p, q nodig en dus moet de bedrieger het getal N in factoren kunnen ontbinden. Als p, q voldoend grote priemgetallen zijn kunnen we er moreel zeker van zijn dat dit de bedrieger niet lukt. De toepassing van bovenstaande zero-knowledge proof hoeft zich niet te beperken tot levende personen Anton en Vera. Het kan ook gebruikt worden bij een verificatie-protocol van bijvoorbeeld chipkaarten. Om een idee te geven, stel dat een centrale autoriteit, een bank, een warenhuis of de overheid, een chipkaart wil uitgeven waarmee een groot aantal gebruikers aankopen kan doen. Met dit doel maakt de instelling een tweetal grote priemgetallen P en Q aan. Het product N = P Q mag publiekelijk bekend zijn, de getallen P, Q zelf zijn strict geheim. Stel dat Anton een chipkaart aanvraagt. De instelling maakt van Anton’s gegevens een groot getal A en zorgt daarbij dat het een kwadraat modulo N is. De berekening van een a z´o dat a2 ≡ A (mod N ) is een koud kunstje voor iemand die over de priemfactoren P, Q beschikt. Dit wordt aan het eind van Hoofdstuk 11 uitgelegd. Vervolgens wordt een chipkaart voor Anton gemaakt die de publieke naam A van Anton bevat en, verborgen voor de buitenwereld, het getal a. Verder bevat de chipkaart ook de benodigde programmatuur om het zero-knowledge protocol uit te voeren, evenals de gevraagde transacties. Met deze chipkaart kan Anton zijn boodschappen doen bij de chipautomaten van de instelling.
