Cryptografie-uitleg aan de hand van RSA

Inleiding

Cryptografie is iets wat in onze geautomatiseerde wereld een steeds grotere rol gaat spelen. Om deze reden leek het mij wel interessant om wat meer te weten te komen over de werking en het gebruik van versleutelmethodes. Ik dook dus voor jullie het internet in op zoek naar informatie over cryptografie en de de daarbij gebruikte algoritmes. Hiervan zal ik als voorbeeld het RSA-algoritme uitgebreid beschrijven.

Wat is cryptografie?

Cryptografie is de gedigitaliseerde vorm van wat men vroeger geheimschrift noemde. De bedoeling van het hele gebeuren is ervoor te zorgen dat onbevoegden geen toegang kunnen krijgen tot bepaalde informatie. Vroeger werd de professionele cryptografie alleen nog door de overheid gebruikt voor beveiliging van zaken als topgeheime militaire informatie, maar tegenwoordig wordt het meer en meer een algemeen goed. Persoonsgegevens, wachtwoorden, E-Mails, internetsites, documenten, elektronische betalingen en nog veel meer andere data wordt versleuteld. Dit is ook wel nodig, aangezien steeds meer belangrijke gegevens tegenwoordig in computers zit opgeslagen.

De terminologie

Bij een ingewikkeld onderwerp als cryptografie horen vanzelfsprekend ook een hoop ingewikkelde termen. Ik zal de belangrijkste hier even kort bespreken. Hierbij zal ik de Engelse termen aanhouden, omdat die toch praktisch altijd gebruikt worden.

Plaintext / Cleartext

Het ongecodeerde bericht. Dit is de belangrijke boodschap die niet in verkeerde handen mag komen.

Encryption

Met encryption wordt de codering van de plaintext bedoeld. Via deze stap wordt ervoor gezorgd dat de boodschap alleen via een lastige omweg weer leesbaar zal worden.

Ciphertext

Dit is de uiteindelijke tekst, in versleutelde vorm. Bij een goed gecodeerde tekst is de ciphertext een onbegrijpelijke boodschap, waaruit onbevoegden praktisch onmogelijk de plaintext kunnen halen.

Decryption

De decryption (het decoderen) is de stap die de ontvanger uitvoert om het originele bericht weer uit de ciphertext te halen. Dit gebeurt via een key.

Key

De key is zoals het woord al zegt de sleutel die je nodig hebt om een ciphertext te decoderen. Weet je de key, dan is het ontcijferen van de boodschap een fluitje van een cent. Zonder sleutel is dit bij een goed gecodeerde tekst bijna niet mogelijk.

Cryptanalysis

Dit begrip houdt het kraken van een gecodeerde tekst in. De echte cryptanalysten bedenkten hier ingenieuze manieren voor, zodat snel een code gekraakt kan worden.

Cryptology

Cryptologie is een net iets minder ruim begrip dan Cryptografie. Bij cryptologie wordt namelijk alleen de wiskundige kant van de cryptografie bestudeerd.

Algoritmes

Om iets te versleutelen heb je altijd een algoritme nodig. Hiermee wordt de manier bedoeld, waarop informatie veranderd (gecodeerd) wordt. Algoritmes zijn er van enorm eenvoudig, tot zeer complex; zo kent iedereen waarschijnlijk wel het algoritme dat kleine kinderen soms gebruiken om 'geheimschrift' te maken. Hierbij tel je bij elke letter er eentje op, zodat een onleesbaar woord ontstaat. In 'computertaal' komt dit op het volgende neer:

c = chr$(asc(m) + 1)
m = chr$(asc(c) - 1)

De ciphertext (c) is dus de plainplain (m) waarbij 1 letter is opgeteld. Zo wordt een a een b (a + 1 = b), en krijg je de originele boodschap weer terug door het algoritme om te keren: b - 1 = a. Aangezien je natuurlijk reëel gezien niet een getal bij een letter kan optellen, wordt er met ASCII-codes gewerkt. Zet de letter om in een code, tel daar 1 bij op en verander dan die code weer terug in een letter.

Uiteraard worden er bij professionele cryptografie wel wat ingewikkeldere algoritmes gebruikt. De belangrijkste algoritmes zijn onder te verdelen in twee categorieën: "Public Key Cryptosystems" en "Secret Key Cryptosystems".

Public Key Cryptosystems (Asymmetrische Cryptosystemen)

Deze vorm van cryptografie is al in de jaren 70 uitgevonden. Hierbij wordt gebruik gemaakt van een publieke sleutel voor het coderen en een geheime sleutel voor het decoderen. Een voorbeeld van Public Key Cryptosystems is de RSA-beveiliging. Een uitleg over de werking hiervan vind je behoorlijk uitgebreid vanaf bladzijde 4. Er wordt gebruik gemaakt van wiskundige zaken zoals priemgetallen, logaritmes en vermenigvuldigingen. De precieze werking verschilt uiteraard per beveiliging.

Symmetrische Cryptosystemen

Bij deze vorm van cryptografie is er maar één sleutel: de geheime key. Deze sleutel wordt gebruikt voor het coderen en ook voor het decoderen (of in ieder geval is de decodeer-sleutel eenvoudig af te leiden van de codeer-sleutel). Het grote nadeel hiervan is dus dat de sleutel van de zender aan de ontvanger moet worden doorgegeven. Hierbij kan onderschepping van de communicatie voorkomen, waardoor de beveiliging steeds minder gebruikt wordt. De 'kindercryptografie' waar ik het eerder over had behoort tot deze categorie.

RSA

Om een goed beeld te krijgen van hoe een algoritme nu precies werkt, ging ik op zoek naar een gedetailleerde beschrijving van eentje. Ik koos hierbij voor een asymmetrische, aangezien deze het ingewikkeldste en daardoor ook het interessantste zijn.

De keuze is gevallen op de RSA-beveiliging. Hiervan vond ik de volgende informatie:

RSA is a public-key cryptosystem for both encryption and authentication; it was invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman. It works as follows: take two large primes, p and q, and find their product n=pq; n is called the modulus. Choose a number, e, less than n and relatively prime to (p-1)(q-1), which means that e and (p-1)(q-1) have no common factors except 1. Find another number d such that (ed - 1) is divisible by (p-1)(q-1). The values e and d are called the public and private exponents, respectively. The public key is the pair (n,e); the private key is (n,d). The factors p and q maybe kept with the private key, or destroyed.

RSA privacy encryption: Suppose Alice wants to send a message m to Bob. Alice creates the ciphertext c by exponentiating: c=m^e mod n,
where e and n are Bob’s public key. She sends c to Bob. To decrypt, Bob also exponentiates: m=c^d mod n; the relationship between e
and d ensures that Bob correctly recovers m. Since only Bob knows d, only Bob can decrypt.

Aangezien dit behoorlijk ingewikkeld lijkt heb ik zelf een iets duidelijkere beschrijving gemaakt. Overigens werkt het in het echt zelfs nog iets ingewikkelder, maar dit is te lastig om duidelijk uit te leggen. Hierom zal ik mij beperken tot de voor velen waarschijnlijk toch al behoorlijk lastige basis.

Om te beginnen is het belangrijk te snappen hoe de basisprincipes in elkaar zitten. De ontvanger van de boodschap heeft een tweetal sleutels (in dit geval e en n) die public zijn, wat wil zeggen dat iedereen deze codes mag weten. Deze keys worden door de zender gebruikt om het bericht te coderen. Verder heeft de ontvanger ook nog een private key (in dit geval d), waarmee de via de public keys versleutelde boodschap weer te ontcijferen is.

RSA gedetailleerd

Voordat er berichten versleuteld kunnen worden, moeten er eerst een aantal getallen bij een aantal letters gezocht worden. Dit gaat volgens het volgende stappenplan:

Neem twee grote priemgetallen (p en q) die niet aan elkaar gelijk zijn. Priemgetallen zijn getallen die alleen maar deelbaar zijn door 1 en zichzelf.
Bereken n aan de hand van n = p * q.
Bereken a via a = (p-1) * (q-1)
Zoek een getal voor e, kleiner dan n en relatief priem aan a. Hiermee wordt bedoeld dat e en a geen gemeenschappelijke deler hebben behalve 1.
Kies voor d een getal, zodat e * d - 1 deelbaar is door a.

De benodigde letters hebben nu een waarde gekregen, waarna het echte werk kan beginnen. Hiervoor zijn alleen n, d en e nog nodig. Je kan p, q en a dus in principe weggooien.

Het versturen van een bericht

Degene die het bericht wil ontvangen, maakt zijn hierboven aangemaakte waardes n en e openbaar (public). Aan de hand van deze getallen zullen berichten door andere mensen versleuteld kunnen worden, maar voor het decoderen zal de d-waarde noodzakelijk zijn. Aangezien deze waarde niet nodig is voor het coderen, zal deze niet via communicatie van de ene naar de andere persoon gebracht hoeven worden. Dit is dus een stuk veiliger dan een cryptografie-manier waarbij dezelfde sleutel wordt gebruikt voor coderen en decoderen; dan heb je altijd de kans dat iemand de communicatie onderschept en hierdoor de originele boodschap kan achterhalen.

Bij de RSA-beveiliging is er dus geen sprake van het bovenstaande risico. Immers, de ontvanger hoeft alleen zijn public keys n en e, samen met het te gebruiken algoritme aan de zender door te geven. Met deze gegevens is het praktisch onmogelijk om het bericht te decoderen, zelfs voor de zender.

Het codeerproces

Als de benodigde waardes eenmaal verkregen zijn, is het coderen niet zo ingewikkeld meer. Via de formule c=m^e mod n wordt de ciphertext gemaakt. Hierbij is m de plaintext, en c de ciphertext. De meesten zullen echter niet weten wat mod inhoudt. Kort gezegd wordt hierbij het rest-getal van een deling berekend. Dus 11 mod 4 = 3, aangezien 4 twee keer in 11 past en er dan nog 3 overblijft. In een formule ziet het mod-commando er dus als volgt uit: a mod b = a - b * int(a / b). Het voordeel van het gebruik van de mod-operator is dat deze berekening niet omkeerbaar is. 11 mod 4 is namelijk 3, maar 15 mod 4 ook. De formule is dus niet zomaar om te draaien.

Het decodeerproces

Bij het decodeerproces wordt vanuit de ciphertext de plaintext weer achterhaald. Dit gebeurt op soortgelijke manier als het coderen, waarbij alleen de formule iets veranderd wordt: m=c^d mod n.

RSA getallenvoorbeeld

Om de formules iets meer vorm te laten krijgen zal ik met een getallenvoorbeeld laten zien hoe de beveiliging precies in elkaar steekt. Hierbij zal ik kleine waardes nemen, aangezien dat wat makkelijker rekent. In het echt worden hier uiteraard enorm grote getallen voor gebruikt.

p_(priemgetal) = 13
q_(priemgetal) = 17
n = p * q = 13 * 17 = 221
a = (p-1) * (q-1) = 12 * 16 = 192
e = 137 _{(kleiner dan n en geen gelijke deler met a)}
d = 185 _{(e*d-1 is nu deelbaar door a)}

Uiteraard kunnen ook andere getallen gebruikt worden, maar voor het voorbeeld zijn deze goed genoeg. Stel nu dat je een boodschap ("Tweakers.net") van iemand wil ontvangen. Je stuurt hem of haar dan de publieke sleutels (e en n), waarna de zender aan de slag kan.

Eerst zal de boodschap in getallen omgezet moeten worden, voordat er berekeningen mee gedaan kunnen worden. Hiervoor zal ik de ASCII-codes gebruiken. De boodschap 'Tweakers.net' wordt dan 84 , 119 , 101 , 97 , 107 , 101 , 114 , 115 , 46 , 110 , 101 , 116 (opgesplitst in code per letter).

Nu moeten alle getallen versleuteld worden, via de formule c = m^e mod n. Bij de eerste letter volgt hieruit de volgende c-waarde:

c = 84¹³⁷ mod 221 = 67

Dit is gewoon te berekenen via het programma calc.exe dat bij Windows geleverd wordt. Zo bereken je voor elke ASCII-code de c-waarde, waarna de boodschap verstuurd kan worden.

De ontvangen zal dan eenvoudig het oorspronkelijke bericht kunnen achterhalen:

m = 67¹⁸⁵ mod 221 = 84

Via een ASCII-tabel kan dan de bijbehorende letter (in dit geval de hoofdletter T) gezocht worden. Voer bovenstaande berekeningen uit voor elke letter, en klaar is Kees.

Zelf klooien

Lijkt het je leuk om zelf eens iets te versleutelen op bovenstaande wijze, maar wil je andere waardes gebruiken en kan je die niet berekenen? Geen nood! Via een door mij gemaakt programmaatje zijn alle waardes eenvoudig te verkrijgen. Aangezien ik slechts kan programmeren in Qbasic en Visual Basic moest ik uit deze twee talen kiezen. Het feit in acht genomen dat niet iedereen de Visual Basic 6 Runtime Files heeft, leek het me het beste om toch maar het oude vertrouwde DOS te gebruiken. Voor een aantal wiskundige berekeningen programmeert en bedient dat ook nog steeds het makkelijkste. Sta overigens niet raar te kijken als de e-waarde oploopt onder het berekenen. In dat geval was er geen d-waarde te vinden bij de laagst mogelijke e en wordt dit getal aangepast om de berekeningen toch goed te laten verlopen. Afsluiten kan op elk moment met Ctrl-Break.

Verificatie

Een onderwerp wat ook erg samenhangt met encryptie is de zogenaamde 'authentication'. Hierbij wordt het bericht niet versleuteld, maar wordt ervoor gezorgd dat de ontvanger er zeker van kan zijn dat de zender ook echter is wie hij zegt dat hij is.

Ik zal het verificatie-proces kort proberen uit te leggen aan de hand van de RSA-algoritme dat al eerder is uitgelegd. Bij het versturen van een boodschap met een digitale handtekening wordt echter het gebruik van de privé- en publieke sleutel omgedraaid. Bij het coderen werd door de zender de publieke sleutel van de ontvanger gebruikt, bij verifiëren maakt de zender gebruik van zijn eigen privé-sleutel. Aan de hand hiervan wordt via de formule s = m^d mod n een 'digital signature' geproduceerd, dat samen met de boodschap (gewoon in plaintext) verstuurd wordt.

Aangezien de ontvanger de publieke sleutels e en n weet, kan gecontroleerd worden of de handtekening inderdaad van de verwachte persoon afkomstig is.

Het enige wat de ontvanger hoeft te doen is kijken of via m = s^e mod n de oorspronkelijke boodschap (die ook is meegestuurd) weer tevoorschijn komt. In dat geval is het zeker dat degene waarvan hij de publieke keys heeft gekregen deze boodschap heeft verstuurd, omdat die persoon de enige is die een digitale handtekening kan maken waarbij via de publieke sleutels de plaintext weer terug te krijgen is.

RSA kraken

Bij RSA is het mogelijk om een gecodeerde boodschap op meerdere manieren te kraken. De twee belangrijkste zijn:

De private key berekenen

Aangezien je via de d- en n-waardes een bericht kan decoderen en n al bekend is, zou je alleen nog maar d hoeven te berekenen om de plaintext terug te krijgen. Je zal dus de modulus n moeten ontbinden in de factoren p en q; de priemgetallen. Daarna kan eenvoudig via de andere publieke sleutel e de d-waarde berekend worden.

Is dit eenmaal gelukt, kan de hacker voortaan alle berichten lezen die met dezelfde e- en n-waarde zijn gecodeerd en zelfs valse digitale handtekeningen maken. Dit is echter praktisch onmogelijk, aangezien het ontbinden van een enorm getal zoals bij RSA (in de orde van grootte van 2⁶⁴) in priemgetallen zeer lang duurt. Deze methode is dan ook niet bruikbaar bij RSA.

Brute-force hacking

De manier die beter van toepassing is, is brute-force hacking. Hierbij worden geen lastige berekeningen uitgevoerd, maar probeert men eenvoudigweg zoals het woord al zegt met brute kracht alle mogelijkheden uit.

Dit werkt zo: je neemt een random waarde voor m (de boodschap die dus ontcijferd moet worden) en codeert deze aan de hand van de publieke sleutels (c = m^e mod n). Controleer daarna of de gevonden ciphertext overeen komt met de werkelijke ciphertext. Is dit het geval, dan was de gegokte plaintext juist.

Gezien het feit dat er ontelbaar veel mogelijkheid zijn, duurt ook de tweede kraak-manier zeer lang. Maar, de code zal eens gevonden worden, ook al kan het zeer lang duren.

Bedankje

Paul Kruyt, erg bedankt voor de handige links die je me opstuurde met betrekking tot dit onderwerp.

Overigens, stay tuned voor een vervolgverhaal op dit onderwerp. Over een tijdje zal Robin van Rootseler nog meer informatie geven in een komende feature over cryptografie.

(sommige bezoekers wilden graag een printbare versie, dus ben ik even creatief geweest met Word )