Asymmetrische encryptie
Het probleem met symmetrische encryptie
Wat als je bij symmetrische encryptie met meerdere mensen wilt communiceren zonder dat iedereen elkaars berichten kan zien? Bob kan onmogelijk dezelfde sleutel gebruiken om met Alfredo te communiceren die hij al gebruikte met Alice. Kortom, je hebt per eindpunt een aparte sleutel nodig. Het aantal sleutels dat je nodig hebt, zeker als ook alle gebruikers onderling nog eens willen communiceren wordt snel erg groot. Je kan het aantal benodigde sleutels berekenen met de formule \(n * \frac{(n - 1)}{2}\), waarbij n het aantal gebruikers voorstelt:
- 6 gebruikers vereisen 15 sleutels.
- 7 gebruikers vereisen 21 sleutels.
- 10 gebruikers vereisen er al 45.
- 100 gebruikers vereisen er 4950!
Symmetrische encryptie heeft dus een key distribution problem wanneer er encryptie op een grote schaal nodig is. Zeker als we spreken over online communicatie, over het Internet, wordt de schaal ogenblikkelijk gigantisch groot en wordt het sleutelmanagement problematisch. Een andere oplossing is dus aan de orde.
Publieke cryptografie
Publieke crypto oftewel asymmetrische encryptie zal het probleem met symmetrische encryptie oplossen doordat er gebruikt wordt gemaakt van twee sleutels:
- Eén publieke sleutel.
- Eén private sleutel.
Iedereen kan de publieke sleutel gebruiken om versleutelde berichten naar de eigenaar te sturen. Enkel de eigenaar van de bijhorende private sleutel kan deze berichten echter decrypteren. Kortom, we lossen nu een deel van het sleutelprobleem op: iedereen heeft z’n eigen private sleutel (en moet deze geheim houden!) en kan via z’n publieke sleutel berichten ontvangen.
Het concept van publieke cryptografie werd in 1976 gepubliceerd door Diffie en Hellman en had een grote impact op de manier waarop beveiligde communicatie op het Internet mogelijk werd. Hun eigen artikel beschreef meteen een sleuteluitwisselingsprotocol (Diffie-Hellman, zie verder); het eerste volwaardige asymmetrische encryptie-algoritme (RSA) volgde een jaar later, in 1977.
Je kan publieke encryptie beschouwen als volgt: de publieke sleutel, die niet geheim is, is een openstaande kist. Iedereen kan de kist gebruiken om een geheime boodschap in te plaatsen en vervolgens deze op slot te klikken (encrypteren). Enkel de eigenaar van deze kist heeft de bijpassende private sleutel die echter deze kist kan opendoen en de originele boodschap kan lezen (decrypteren).
Enkele van de bekendere publieke cryptosystemen zijn onder andere RSA, DSS en El Gamal.
Drie toepassingen van publieke cryptografie
Publieke cryptografie wordt in de praktijk voor drie doeleinden ingezet:
- Asymmetrische encryptie (bv. RSA): berichten versleutelen met de publieke sleutel van de ontvanger, die ze enkel met zijn private sleutel kan lezen.
- Sleuteluitwisseling (key exchange, bv. Diffie-Hellman): twee partijen spreken over een onveilig kanaal een gemeenschappelijke symmetrische sleutel af, die daarna voor snellere symmetrische encryptie wordt gebruikt.
- Digitale handtekeningen: met de private sleutel wordt een bericht “getekend”, en iedereen kan met de bijhorende publieke sleutel verifiëren dat het bericht effectief van die persoon afkomstig is en onderweg niet werd aangepast.
Die laatste toepassing is een erg nuttige extra eigenschap: daar enkel de ondertekenaar de private sleutel in z’n bezit heeft, levert een geldige handtekening tegelijk authenticatie (de verzender is wie hij beweert te zijn) én integriteit (het bericht is onderweg niet gewijzigd).
In wat volgt werken we deze drie toepassingen één voor één uit, te beginnen met sleuteluitwisseling.
Diffie-Hellman sleuteluitwisseling
We starten met sleuteluitwisseling, omdat dit concept mooi illustreert hoe publieke crypto in de praktijk wordt gebruikt.
Het is namelijk zo dat symmetrische crypto sneller is én dus voor (realtime) communicatie interessanter is. We weten echter dat het sleutelmanagement bij symmetrische crypto een probleem is als we met grote groepen gebruikers zitten. Het Diffie-Hellman sleuteluitwisselingsconcept helpt ons hierbij: het laat toe dat twee gebruikers over een onveilig kanaal op een veilige manier een gemeenschappelijk geheim (shared secret) afspreken.
Belangrijk om meteen mee te geven: de waarden die Bob en Alice bij Diffie-Hellman gebruiken zijn sessie-specifiek (ephemeral) en worden na de uitwisseling weggegooid. Ze zijn dus niet hetzelfde als een langdurig publiek/privaat sleutelpaar zoals bij RSA - DH dient louter om een gemeenschappelijke symmetrische sleutel af te spreken, niet om berichten rechtstreeks te versleutelen.
Voor de eigenlijke uitwisseling start, spreken Alice en Bob eerst twee publieke parameters af: een (groot) priemgetal \(p\) dat als modulus dient, en een basis \(g\) (ook wel generator genoemd), kleiner dan \(p\). Deze twee waarden mogen over een onveilig kanaal worden uitgewisseld - een eventuele afluisteraar mag ze gerust kennen, dat is geen probleem voor de veiligheid. In het rekenvoorbeeld hieronder gebruiken we \(g = 7\) en \(p = 11\).
Zowel Bob als Alice kiezen vervolgens elk een geheime waarde die ze enkel voor deze sessie gebruiken. Op basis van deze geheime waarde berekenen ze elk een publieke waarde (via de formule \(g^{geheim} \bmod p\)) die ze naar de ander sturen (wat kan over een onbeveiligd kanaal). De ontvanger zal deze publieke waarde combineren met de eigen geheime waarde wat zal resulteren in een shared secret dat beiden nu kennen en kunnen gebruiken, bijvoorbeeld als de symmetrische sleutel om verdere communicatie te beveiligen.
De reden dat dit werkt, is met dank aan de modulo operator en de eigenschappen ervan. Een voorbeeld (met \(g = 7\) en \(p = 11\)):
| Stap | Alice | Bob |
|---|---|---|
| 1 | Alice kiest een geheim getal A. Ze kiest A= 3 | Bob kiest ook een geheim getal B = 6. |
| 2 | Alice berekent \(7^A \bmod 11 = 343 \bmod 11 = 2\), genaamd X. | Bob berekent \(7^B \bmod 11 = 117649 \bmod 11 = 4\), genaamd Y. |
| 3 | Alice stuurt X=2 naar Bob | Bob stuurt Y=4 naar Alice. |
| 4 | Alice berekent \(Y^A \bmod 11 = 4^3 \bmod 11 = 9\). | Bob berekent \(X^B \bmod 11 = 2^6 \bmod 11 = 9\). |
Zoals je merkt kunnen nu Alice en Bob het berekende getal 9 als gedeeld geheim gebruiken. Enkel zij kennen dit getal.
Uiteraard zullen in de praktijk Bob en Alice véél grotere getallen kiezen dan 3 en 6.
Dat Bob en Alice de waarden X en Y naar elkaar kunnen sturen is dankzij de eigenschappen van de modulo-berekening. X en Y kunnen het resultaat zijn van een gigantische hoeveelheid berekeningen en een stroper zal dus veel rekenwerk nodig hebben om alle mogelijkheden te testen.
Je kan Diffie-Hellman visueel begrijpen via verfkleuren:
- Alice en Bob spreken publiek een gemeenschappelijke startkleur af (bijvoorbeeld geel).
- Elk kiest daarnaast een geheime kleur die nooit gedeeld wordt (bijvoorbeeld Alice oranje, Bob turquoise).
- Beiden mengen hun geheime kleur met de gemeenschappelijke kleur en sturen het mengsel naar de andere partij. Een stroper kan de mengsels onderweg zien, maar kan ze niet ontleden in de originele kleuren.
- Alice voegt haar geheime kleur toe aan Bobs mengsel; Bob doet hetzelfde met het mengsel van Alice.
- Beiden komen uit op exact dezelfde eindkleur: het gedeeld geheim.
Het principe berust erop dat mengen makkelijk is, maar ontmengen praktisch onmogelijk. In de digitale versie vervult de modulo-berekening die rol.
RSA
Eén van de oudste, maar nog steeds populairste, publieke cryptosystemen is het in 1977 ontwikkelde RSA algoritme. RSA, wat staat voor de achternamen van de drie ontwikkelaars (Rivest, Shamir en Adleman) gebruikt sleutels van 1536 tot 4096 bits lang. Het systeem is vrij traag maar heeft als voordeel dat het veilige sleuteltransmissie toestaat over een onveilig kanaal: we zien daarom vaak RSA gebruikt worden om eerst sessiesleutels uit te wisselen, vervolgens wordt overgeschakeld op een sneller symmetrisch cipher.
De exacte berekeningen die gebeuren tijdens encryptie en decryptie leiden ons iets te ver, maar volgend voorbeeld toont een vereenvoudigde wijze waarop RSA wordt toegepast:
Data encrypteren met behulp van asymmetrische versleuteling gebeurt op bijna dezelfde wijze als de Diffie-Hellman sleutel uitwisseling. Ook nu zullen beide zijden rekenen op de eigenschappen van de modulo-operator om over een onveilig kanaal veilige communicatie te kunnen doen.
Eerst dient een publieke sleutel aangemaakt te worden:
- Hiertoe dient Bob twee grote priemgetallen,
qenpte kiezen, bijvoorbeeldp=17enq=11. - Vervolgens berekent Bob
Ndoor deze priemgetallen met elkaar te vermenigvuldigen (p*qgeeft 17 * 11,N=187). - Bob kiest nu nog een priemgetal
e, bijvoorbeeld7. - Bob kan nu zijn eigen geheime, private sleutel
dmaken, zodat geldt: \(e \cdot d \equiv 1 \pmod{(p-1)(q-1)}\). In dit voorbeeld wordt dat \(7 \cdot d \equiv 1 \pmod{16 \cdot 10}\), oftewel \(7 \cdot d \equiv 1 \pmod{160}\). - Om
dte vinden zoeken we dus een getal zodat \(7 \cdot d \bmod 160 = 1\). De mogelijke waarden voor \(7 \cdot d\) zijn bijgevolg \(1, 161, 321, \dots\). Met \(7 \cdot 23 = 161\) klopt het:d=23.
Om \(d\) te berekenen maken we gebruik van de zogenaamde Uitgebreid Euclidisch algoritme, een eeuwenoud algoritme gebaseerd op het Algoritme van Euclides dat we in het lager leerden gebruiken om de grootste gemene deler te berekenen van twee getallen.
Bob heeft dus nu:
- Publieke sleutel bestaande uit \(N=187\) en \(e=7\).
- Private sleutel \(d=23\).
Iedereen die nu naar Bob iets wilt sturen, kan dit via z’n publieke sleutel (N en e).
Stel dat Alice het ASCII-karakter X naar Bob wil sturen:
- De ASCII-waarde van X is 88.
- De encryptie door Alice gebeurt dan als volgt: \(C = \text{data}^e \bmod N\).
- De te versturen ciphertext C wordt dus: \(88^7 \bmod 187\) oftewel
C=11.
Enkel Bob zal deze ciphertext met zijn private sleutel d kunnen decrypteren door \(C^d \bmod N\) te doen, oftewel \(11^{23} \bmod 187\) wat terug de plaintext 88 geeft!
De sterkte van publieke crypto stoelt dus op het feit dat ontbinden van (grote) getallen in factoren computationeel veel moeilijker is dan de omgekeerde stap, namelijk twee getallen met elkaar vermenigvuldigen.
15621 in z’n factoren ontbinden is veel moeilijker dan de getallen 123 en 127 vermenigvuldigen (wat dus ook 15621 zal geven).
Zonder in detail te treden hoe cryptocoins en blockchains werken, is het nuttig om te vermelden dat bij cryptocoins ook de public crypto concepten worden gebruikt. Ook hier is je private sleutel uiterst belangrijk: enkel de eigenaar van de private sleutel “bezit” de bijhorende cryptocoins in de blockchain. Daarom is het belangrijk dat je NOOIT je private sleutel aan derden geeft, want zo geef je hen toegang tot jouw coins en kunnen ze vervolgens deze stelen door de private sleutel te vervangen.
Elliptic Curve Cryptografie (ECC)
RSA baseert zich op de moeilijkheid van het ontbinden van grote getallen in priemfactoren. Elliptic Curve Cryptografie (ECC) is een modernere vorm van asymmetrische crypto die zich baseert op de wiskundige eigenschappen van elliptische krommen over eindige velden. Het onderliggende wiskundige probleem - het Elliptic Curve Discrete Logarithm Problem (ECDLP) - is nóg moeilijker op te lossen dan factorisatie, waardoor ECC met veel kleinere sleutels hetzelfde beveiligingsniveau kan bieden als RSA:
| ECC sleutellengte | RSA equivalent | Beveiligingsniveau |
|---|---|---|
| 256 bits | 3072 bits | 128 bits |
| 384 bits | 7680 bits | 192 bits |
Het beveiligingsniveau (security strength) drukt uit hoeveel rekenwerk een aanvaller nodig heeft om de encryptie te kraken, uitgedrukt in bits. Een beveiligingsniveau van 128 bits betekent dat een aanvaller \(2^{128}\) bewerkingen moet uitvoeren - evenveel als nodig is om een symmetrische sleutel van 128 bits (zoals AES-128) te bruteforcen. Zo kunnen we de sterkte van verschillende cryptosystemen met elkaar vergelijken: een ECC-sleutel van 256 bits en een RSA-sleutel van 3072 bits zijn dus even moeilijk te kraken.
Kleinere sleutels betekenen snellere berekeningen, minder dataverkeer en lager energieverbruik. Dat maakt ECC bijzonder geschikt voor toepassingen waar rekenkracht of bandbreedte beperkt is, zoals mobiele toestellen en IoT-apparaten.
ECC wordt vandaag breed ingezet. De twee belangrijkste toepassingen zijn:
- ECDH (Elliptic Curve Diffie-Hellman): een variant van de eerder besproken Diffie-Hellman sleuteluitwisseling, maar dan gebaseerd op elliptische krommen.
- ECDSA (Elliptic Curve Digital Signature Algorithm): een digitaal handtekening-algoritme dat onder andere door Bitcoin en andere blockchains wordt gebruikt.
Moderne TLS-verbindingen (en dus HTTPS) gebruiken vrijwel altijd ECC-gebaseerde algoritmes voor de sleuteluitwisseling, omdat ze sneller en veiliger zijn dan klassiek RSA bij vergelijkbare sleutellengtes.
Net als RSA is ook ECC kwetsbaar voor toekomstige quantumcomputers. Daarom wordt er actief gewerkt aan zogenaamde post-quantum cryptografie: nieuwe algoritmes die bestand zijn tegen aanvallen met quantumcomputers. In 2024 publiceerde NIST de eerste standaarden hiervoor.
Intermezzo: Hashes
Voor we de digitale handtekeningen uitwerken, slaan we even een zijtak in om het concept “hash” te bespreken. Een hash is een concept uit de informatica dat we gebruiken om te controleren of een digitaal stuk tekst werd aangepast of niet. Door de tekst in een hashfuntie te steken wordt een hash aangemaakt. Deze hash is een stuk code met een vaste lengte, ongeacht de originele input. Wanneer 1 bit of meer wordt aangepast in de originele boodschap dan zal deze in een totaal andere hash resulteren. Enkel dus wanneer een identiek stuk tekst als invoer (tot op bitniveau identiek) wordt gebruikt, zullen twee hashes gelijk zijn.
Voorgaande is uiteraard onmogelijk: daar een hash meestal veel korter is dan de originele boodschap, is het mathematisch mogelijk dat twee totaal verschillende teksten toch dezelfde hash geven. Het is de opdracht van een goede hashfunctie om dit soort hash collisions zo klein mogelijk te houden.
Een hashfunctie is niet omkeerbaar: men mag onmogelijk aan de hand van een hash (ook wel digest of hashcode genoemd) terug de originele tekst kunnen achterhalen. Een hashfunctie is dus een eenrichtingsfunctie, ook wel afbeelding genoemd in wiskundige termen.
Er bestaan veel verschillende hashfuncties. Enkele van de bekendere zijn:
- MD5, oftewel Message Digest 5: deze zal een 128-bit hashwaarde genereren.
- SHA-X, oftewel Secure Hash Algorithms. Zo is er SHA-256 wat een 256 bits hash zal genereren.
De sterkte van een hash algoritme zit hem in de grootte van de kans waarop hash collisions kunnen optreden. Zo zijn er bij MD5 al veel meer collisions gevonden dan bijvoorbeeld bij het recenter gepubliceerde SHA3-512 algoritme.
Een digitale hash is dus een ideaal middel om boodschappen digitaal te ondertekenen.
Boodschappen ondertekenen
Een probleem bij online communicatie is dat we geen zekerheid hebben dat het ontvangen bericht wel degelijk van de persoon komt van wie we verwachtten dat deze het bericht had opgesteld. We kunnen daarom het publieke crypto systeem gebruiken om berichten te ondertekenen. Daar enkel Bob de bijhorende private sleutel kan hebben die bij z’n publieke sleutel hoort, is het bezit van deze private sleutel hebben het bewijs dat hij de rechtmatige eigenaar van een bepaalde publieke sleutel is.
Onder andere RSA laat toe om een digitale handtekening (digital signature) te plaatsen bij een bericht om zo te bewijzen dat de verzender de rechtmatige eigenaar van een bijhorende publieke sleutel is.
Een digitale handtekening wordt als extra bericht achteraan de te versturen boodschap geplaatst. De signature is als het ware een hash berekend aan de hand van de private sleutel. De ontvanger zal nu met de bijhorende publieke sleutel van de verzender kunnen verifiëren of de bijhorende private sleutel werd gebruikt om de handtekening te genereren.
Om een digitale handtekening te berekenen moeten we eerst een hash van het bericht berekenen. We gebruiken hier bijvoorbeeld MD5 of één van de SHA-algoritmes voor. Deze hash gaan we nu “verpakken” met de private sleutel.
Stel dat de berekende hash van ons bericht de waarde 35 heeft (in werkelijkheid is een hash veel langer, maar voor dit voorbeeld houden we het klein) en we beschikken over volgend sleutelpaar (bron):
- publieke sleutel: \(e=5\) en \(n=91\).
- private sleutel: \(d=29\).
De handtekening wordt berekend door de hash te versleutelen met de private sleutel: \(s = m^d \bmod n\), oftewel \(s = 35^{29} \bmod 91 = 42\).
We versturen naar de ontvanger dus de boodschap zelf én de bijhorende handtekening 42.
De ontvanger kan nu controleren of de boodschap klopt. Hij berekent eerst zelf de hash van het ontvangen bericht. Vervolgens “ontsleutelt” hij de handtekening met de publieke sleutel van de verzender door \(s^e \bmod n\) te berekenen, oftewel \(42^5 \bmod 91 = 35\). Als de zelf berekende hash gelijk is aan dit resultaat, dan weet de ontvanger dat het bericht afkomstig is van de verwachte verzender én onderweg niet werd aangepast.
Het probleem met digitale handtekeningen
We hebben echter een probleem. Hoe weet je eigenlijk dat je wel de juiste publieke sleutel gebruikt? Publieke sleutels zijn, wel, publiek. Iedereen kan jou een publieke sleutel geven en zeggen “Dit is de sleutel van persoon X” zonder dat jij kan controleren of dat zo is.
We kunnen daarom als kwaadwillig persoon bijvoorbeeld een legaal bericht onderscheppen, aanpassen en dan vervolgens ondertekenen met onze eigen handtekening. Als we vervolgens aan de ontvanger kunnen wijsmaken dat jouw publieke sleutel zogezegd bij de originele verzender hoort, dan zal de ontvanger jouw aangepaste bericht “geloven”.
Kortom, we hebben een manier nodig om de identiteit van de eigenaar van een publieke sleutel te verifiëren. Kom binnen: certificaten.