RSA crypto.pdf

# Introductie tot cryptografie en RSA Dit onderwerp introduceert de principes van asymmetrische cryptografie, de rol van het RSA-algoritme daarin, en de essentiële processen van sleutelgeneratie, encryptie en decryptie. ### 1.1 Asymmetrische cryptografie en de rol van RSA Asymmetrische cryptografie, ook wel bekend als public-key cryptografie, maakt gebruik van een paar sleutels: een publieke sleutel voor encryptie en een private sleutel voor decryptie. Dit in tegenstelling tot symmetrische cryptografie, waar dezelfde sleutel wordt gebruikt voor zowel encryptie als decryptie [1](#page=1) [2](#page=2). Het RSA-algoritme is een van de meest bekende en wijdverbreide implementaties van asymmetrische cryptografie. Het is vernoemd naar de ontdekkers: Ron Rivest, Adi Shamir en Leonard Adleman [2](#page=2). Een belangrijk aspect van asymmetrische cryptografie is dat grote datablokken zelden direct worden versleuteld. In plaats daarvan wordt een willekeurige symmetrische sleutel gegenereerd om de grote datablokken efficiënt te versleutelen. Vervolgens wordt alleen deze symmetrische sleutel asymmetrisch versleuteld met de publieke sleutel van de ontvanger. Dit biedt niet alleen een oplossing voor de beperkte prestaties van asymmetrische encryptie, maar zorgt er ook voor dat het grootste deel van de communicatie symmetrisch en dus sneller wordt versleuteld [2](#page=2). ### 1.2 Het RSA-algoritme: sleutelgeneratie, encryptie en decryptie Het RSA-algoritme bestaat uit drie kernprocessen: sleutelgeneratie, encryptie en decryptie [2](#page=2). #### 1.2.1 Sleutelgeneratie Het genereren van een RSA-sleutelpaar door Alice omvat de volgende stappen [2](#page=2): 1. **Selecteer twee verschillende priemgetallen $p$ en $q$**: Het is cruciaal dat $p$ en $q$ uniek zijn ($p \neq q$) [2](#page=2). 2. **Bereken $n$**: Dit wordt gedaan door de twee priemgetallen met elkaar te vermenigvuldigen: $$n = p \times q$$ [2](#page=2). 3. **Bereken $\phi(n)$ (Euler's totiëntfunctie)**: Dit is het aantal positieve gehele getallen kleiner dan of gelijk aan $n$ die relatief priem zijn ten opzichte van $n$. Voor twee priemgetallen $p$ en $q$ wordt dit berekend als: $$\phi(n) = (p - 1)(q - 1)$$ [2](#page=2). 4. **Selecteer een geheel getal $e$**: Dit getal moet voldoen aan de volgende voorwaarden: * Het grootste gemene deler van $\phi(n)$ en $e$ moet 1 zijn: $\text{gcd}(\phi(n), e) = 1$ [2](#page=2). * $e$ moet groter zijn dan 1 en kleiner dan $\phi(n)$: $1 < e < \phi(n)$ [2](#page=2). * Vaak wordt een specifieke, kleine waarde gekozen voor $e$ om de encryptie te versnellen, zoals 65537 (wat gelijk is aan $2^{16} + 1$). Een zeer kleine waarde voor $e$, zoals 3, kan RSA kwetsbaar maken voor aanvallen [2](#page=2). 5. **Bereken $d$**: Dit is de modulaire multiplicatieve inverse van $e$ modulo $\phi(n)$. Met andere woorden, $d$ voldoet aan de congruence: $$d \equiv e^{-1} \pmod{\phi(n)}$$ [2](#page=2). Dit betekent dat $d \times e \equiv 1 \pmod{\phi(n)}$. 6. **Publieke sleutel**: De publieke sleutel, aangeduid als $PU$, bestaat uit het paar $\{e, n\}$ [2](#page=2). 7. **Private sleutel**: De private sleutel, aangeduid als $PR$, bestaat uit het paar $\{d, n\}$ [2](#page=2). #### 1.2.2 Encryptie door Bob Bob wil een bericht $M$ naar Alice sturen. Hij gebruikt hiervoor Alice's publieke sleutel $\{e, n\}$. Het oorspronkelijke bericht $M$ moet kleiner zijn dan $n$ ($M < n$). De ciphertext $C$ wordt berekend met de volgende formule [2](#page=2): $$C = M^e \pmod{n}$$ [2](#page=2). #### 1.2.3 Decryptie door Alice Alice ontvangt de ciphertext $C$ en gebruikt haar private sleutel $\{d, n\}$ om het oorspronkelijke bericht $M$ te reconstrueren. De decryptieformule is als volgt: $$M = C^d \pmod{n}$$ [2](#page=2). > **Tip:** De keuze van $e$ is van belang voor zowel de beveiliging als de efficiëntie van RSA. Hoewel een kleinere $e$ encryptie sneller maakt, kan een te kleine $e$ de beveiliging compromitteren. De waarde 65537 wordt vaak gebruikt omdat deze een efficiënte berekening mogelijk maakt (door het lage aantal bits dat '1' is) zonder de beveiliging significant te verminderen [2](#page=2). --- # Aanvallen op het RSA-algoritme Dit gedeelte behandelt diverse methoden waarmee het RSA-cryptosysteem kan worden aangevallen, variërend van brute force tot meer geavanceerde technieken zoals timingaanvallen en hardware fault-based aanvallen. ### 2.1 Brute force aanval Een brute force aanval op RSA houdt in dat alle mogelijke privésleutels systematisch worden geprobeerd totdat de juiste sleutel is gevonden. De enige verdediging hiertegen is het gebruik van een voldoende grote sleutelruimte. Een groter aantal bits in de privésleutel ($d$) verhoogt de veiligheid, maar leidt ook tot langzamere berekeningen bij sleutelgeneratie, encryptie en decryptie [3](#page=3). ### 2.2 Wiskundige aanvallen Wiskundige aanvallen op RSA omvatten verschillende benaderingen. Alle equivalenten qua inspanning aan het factoriseren van het product van twee grote priemgetallen, wat de basis vormt van RSA's beveiliging [3](#page=3). ### 2.3 Timingaanvallen Timingaanvallen maken gebruik van de variërende looptijd van het decryptie-algoritme om informatie over de privésleutel te achterhalen. Dit is vergelijkbaar met het raden van een kluiscombinatie door te luisteren naar de draaitijd van de cijfers. De aanval kan worden uitgelegd aan de hand van het modulaire exponentiatie-algoritme, waarbij voor elke bit van de exponent een modulaire vermenigvuldiging wordt uitgevoerd, met een extra vermenigvuldiging voor elke '1'-bit [3](#page=3). #### 2.3.1 Tegenmaatregelen tegen timingaanvallen Er zijn verschillende strategieën om timingaanvallen tegen te gaan: * **Constante exponentiatietijd**: Zorgen dat alle exponentiaties een gelijke hoeveelheid tijd in beslag nemen voordat een resultaat wordt teruggegeven. Dit is een eenvoudige oplossing, maar kan de prestaties verminderen [4](#page=4). * **Willekeurige vertraging**: Het toevoegen van een willekeurige vertraging aan het exponentiatie-algoritme kan de timingaanval bemoeilijken en de prestaties mogelijk verbeteren. Als er echter onvoldoende ruis wordt toegevoegd, kunnen aanvallers door middel van extra metingen de willekeurige vertragingen compenseren [4](#page=4). * **Blinding**: Het vermenigvuldigen van de cijfertekst met een willekeurig getal vóór het uitvoeren van de exponentiatie. Dit voorkomt dat de aanvaller weet welke cijfertekstbits intern worden verwerkt, waardoor de bit-voor-bit analyse die essentieel is voor timingaanvallen, wordt voorkomen [4](#page=4). ### 2.4 Hardware fault-based aanvallen Fault-based aanvallen zijn een onorthodoxe benadering die gericht is op processors die RSA digitale handtekeningen genereren. De aanval induceert fouten in de handtekeningberekening, bijvoorbeeld door de stroomtoevoer naar de processor te verminderen. Deze fouten leiden tot ongeldige handtekeningen, die de aanvaller kan analyseren om de privésleutel te achterhalen. Het extraheren van een 1024-bit privé RSA-sleutel kan hiermee in ongeveer 100 uur worden bereikt met een commercieel verkrijgbare microprocessor. Het algoritme omvat het induceren van single-bit fouten en het observeren van de resultaten [4](#page=4). > **Tip:** Hoewel fault-based aanvallen een potentiële bedreiging vormen, vereisen ze fysieke toegang tot de doelmachine en de mogelijkheid om de voedingsspanning van de processor direct te manipuleren. Als een aanvaller deze mate van toegang heeft, kan deze mogelijk ook de sleutel rechtstreeks uit het geheugen lezen [4](#page=4). ### 2.5 Chosen ciphertext attacks (CCA) De basisversie van het RSA-algoritme is kwetsbaar voor een chosen ciphertext attack (CCA). Bij een CCA kiest de aanvaller een aantal cijferteksten en ontvangt vervolgens de bijbehorende platte teksten, gedecodeerd met de privésleutel van het doelwit. Dit geeft de aanvaller op zichzelf geen nieuwe informatie, tenzij de aanvaller gebruikmaakt van specifieke eigenschappen van RSA. De aanvaller kan dan specifieke datablokken selecteren die, wanneer verwerkt met de privésleutel, informatie opleveren die nuttig is voor cryptanalyse [4](#page=4). > **Tip:** Om CCA-aanvallen tegen te gaan, wordt aangeraden de platte tekst te modificeren met een geschikte methode [4](#page=4). --- # Verdedigingstechnieken tegen RSA-aanvallen Dit onderwerp behandelt methoden ter beveiliging van het RSA-cryptosysteem, met focus op technieken zoals constante exponentiatietijd, willekeurige vertragingen en 'blinding' [4](#page=4). ### 3.1 Mitigatie van timingaanvallen Timingaanvallen maken gebruik van de variatie in rekentijd van exponentiatie-operaties om informatie over de geheime sleutel te achterhalen. Verschillende technieken kunnen worden toegepast om deze aanvallen te weerstaan [4](#page=4). #### 3.1.1 Constante exponentiatietijd Een eenvoudige methode is om ervoor te zorgen dat de exponentiatie-operatie altijd dezelfde hoeveelheid tijd in beslag neemt, ongeacht de input. Hoewel dit een effectieve verdediging is, kan het leiden tot een prestatievermindering [4](#page=4). #### 3.1.2 Willekeurige vertraging Een andere benadering is het toevoegen van een willekeurige vertraging aan het exponentiatie-algoritme. Dit maakt het voor aanvallers moeilijker om conclusies te trekken op basis van timingverschillen. Echter, als de toegevoegde 'ruis' onvoldoende is, kan een aanvaller door het verzamelen van meer metingen de vertragingen compenseren en de aanval alsnog succesvol uitvoeren [4](#page=4). #### 3.1.3 Blinding Blinding behelst het vermenigvuldigen van de cijfertekst met een willekeurig getal alvorens de exponentiatie uit te voeren. Dit voorkomt dat een aanvaller kennis heeft van de cijfertekstbits die tijdens de berekening worden verwerkt, wat essentieel is voor bit-gebaseerde analyse in timingaanvallen [4](#page=4). ### 3.2 Weerstand tegen foutgebaseerde aanvallen Foutgebaseerde aanvallen richten zich op processoren die RSA digitale handtekeningen genereren. Door storingen te induceren, bijvoorbeeld door de stroomtoevoer naar de processor te verminderen, kunnen fouten ontstaan in de handtekeningberekening. Deze ongeldige handtekeningen kunnen vervolgens door een aanvaller worden geanalyseerd om de privésleutel te achterhalen. Er is aangetoond dat het extraheren van een 1024-bit privésleutel via deze methode ongeveer 100 uur kan duren met een commercieel verkrijgbare microprocessor. De aanval maakt gebruik van het induceren van single-bit fouten en het observeren van de resultaten [4](#page=4). > **Tip:** Hoewel foutgebaseerde aanvallen een theoretische bedreiging vormen, vereisen ze fysieke toegang tot de doelmachine en directe controle over de stroomtoevoer van de processor. In dergelijke situaties kan een aanvaller mogelijk ook de sleutel rechtstreeks uit het geheugen lezen [4](#page=4). ### 3.3 Verdediging tegen gekozen cijfertekstaanvallen (CCA) Het basale RSA-algoritme is kwetsbaar voor gekozen cijfertekstaanvallen (CCA). Bij een CCA kan een aanvaller specifieke cijferteksten selecteren en de bijbehorende klare teksten ontvangen, gedecodeerd met de privésleutel van het doelwit. Hoewel dit op zichzelf geen nieuwe informatie oplevert, kan de aanvaller deze aanval misbruiken door eigenschappen van RSA te exploiteren en blokken data te selecteren die, bij verwerking met de privésleutel, informatie prijsgeven voor cryptanalyse [4](#page=4). #### 3.3.1 Optimaal asymmetrisch encryptie-padding (OAEP) Om CCA's tegen te gaan, wordt aanbevolen de klare tekst te modificeren met behulp van een procedure die 'optimal asymmetric encryption padding' (OAEP) wordt genoemd. OAEP introduceert randomisatie en zorgt ervoor dat het herhaaldelijk versleutelen van dezelfde boodschap resulteert in verschillende cijferteksten [4](#page=4) [6](#page=6). ##### 3.3.1.1 Werking van OAEP-encryptie Bij OAEP-encryptie wordt de te versleutelen boodschap ($M$) eerst opgevuld. Optionele parameters ($P$) worden gehasht met een hashfunctie ($H$), waarvan de output wordt aangevuld met nullen om de gewenste lengte te verkrijgen voor het data block ($DB$). Vervolgens wordt een willekeurige zaadwaarde (seed) gegenereerd en gehasht met een 'mask generating function' (MGF). Het resultaat wordt bit-voor-bit ge-XORd met $DB$ om een gemaskeerde $DB$ ($maskedDB$) te verkrijgen. De $maskedDB$ wordt opnieuw door de MGF geleid om een hash te vormen, die vervolgens met de zaadwaarde wordt ge-XORd om een gemaskeerde zaadwaarde ($maskedseed$) te creëren. De concatenatie van de $maskedseed$ en de $maskedDB$ vormt de gecodeerde boodschap ($EM$). De $EM$ wordt vervolgens met RSA versleuteld [6](#page=6). > **Voorbeeld:** De gecodeerde boodschap ($EM$) omvat de opgevulde boodschap ($M$), gemaskeerd door de zaadwaarde, en de zaadwaarde, gemaskeerd door de $maskedDB$ [6](#page=6). --- # RSA-OAEP: Optimale asymmetrische encryptiepading RSA-OAEP is een methode die wordt gebruikt om de veiligheid van RSA te verbeteren door middel van padding van berichten, ter bescherming tegen aanvallen [5](#page=5). ### 4.1 Werking van RSA-OAEP encryptie Het encryptieproces met OAEP omvat de volgende stappen, zoals geïllustreerd in Figuur 9.10 [6](#page=6). #### 4.1.1 Voorbereiding van de data 1. **Padding van de boodschap:** De te versleutelen boodschap, aangeduid als $M$, wordt eerst opgevuld. 2. **Hash van optionele parameters:** Een set optionele parameters, $P$, wordt door een hash-functie $H$ geleid. 3. **Vorming van de Data Block (DB):** De output van de hash-functie $H(P)$ wordt opgevuld met nullen om de gewenste lengte voor het algehele datablok $DB$ te verkrijgen [6](#page=6). #### 4.1.2 Masking en codering 1. **Genereren van een willekeurige seed:** Een willekeurige seed wordt gegenereerd [6](#page=6). 2. **Genereren van de gemaskeerde DB:** Deze seed wordt door een maskeer-genererende functie (MGF) geleid, waarvan de output bit-voor-bit wordt XORed met $DB$. Het resultaat hiervan is de gemaskeerde $DB$ (maskedDB) [6](#page=6). > **Tip:** De MGF wordt gebruikt om een pseudo-willekeurige reeks bytes te genereren op basis van de seed. 3. **Genereren van de gemaskeerde seed:** De gemaskeerde $DB$ wordt vervolgens op zijn beurt door de MGF geleid. De output van deze tweede MGF-applicatie wordt geXORd met de oorspronkelijke seed om de gemaskeerde seed (masked seed) te produceren [6](#page=6). 4. **Vorming van de gecodeerde boodschap (EM):** De concatenatie van de gemaskeerde seed en de gemaskeerde $DB$ vormt de gecodeerde boodschap $EM$ [6](#page=6). > **Formule:** $EM = \text{masked\_seed} \Vert \text{maskedDB}$ #### 4.1.3 RSA-encryptie De gevormde gecodeerde boodschap $EM$ wordt vervolgens versleuteld met behulp van het RSA-algoritme [6](#page=6). > **Belangrijk:** OAEP maakt gebruik van randomisatie. Dit betekent dat het herhaaldelijk versleutelen van dezelfde boodschap $M$ zal resulteren in verschillende encrypties van $EM$ [6](#page=6). * $M$: Boodschap die gecodeerd moet worden. * $P$: Optionele coderingsparameters. * $H$: Hash-functie. * $DB$: Datablok. * $MGF$: Maskeer-genererende functie. * $EM$: Gecodeerde boodschap. * $\text{seed}$: Willekeurige seed. * $\text{maskedDB}$: Gemaskeerde datablok. * $\text{masked\_seed}$: Gemaskeerde seed. --- ## Veelgemaakte fouten om te vermijden - Bestudeer alle onderwerpen grondig voor examens - Let op formules en belangrijke definities - Oefen met de voorbeelden in elke sectie - Memoriseer niet zonder de onderliggende concepten te begrijpen

| Term | Definition | |------|------------| | Asymmetrische cryptografie | Een cryptografisch systeem dat twee verschillende, maar wiskundig gerelateerde sleutels gebruikt: een publieke sleutel voor versleuteling en een private sleutel voor ontsleuteling. Dit staat in contrast met symmetrische cryptografie dat slechts één sleutel gebruikt. | | RSA | Een cryptografisch algoritme dat behoort tot de asymmetrische cryptografie, ontwikkeld door Rivest, Shamir en Adleman. Het wordt gebruikt voor zowel versleuteling als digitale handtekeningen en is gebaseerd op de moeilijkheid van het ontbinden van grote getallen in priemfactoren. | | Sleutelgeneratie | Het proces waarbij een paar cryptografische sleutels, een publieke en een private sleutel, wordt aangemaakt. Voor RSA omvat dit het selecteren van twee grote priemgetallen ($p$ en $q$), het berekenen van hun product ($n$), en het bepalen van de bijbehorende exponenten ($e$ en $d$). | | Publieke sleutel | Een van de twee sleutels in asymmetrische cryptografie die vrij gedeeld kan worden. Deze sleutel wordt gebruikt om informatie te versleutelen, zodat alleen de houder van de corresponderende private sleutel de informatie kan ontsleutelen. | | Private sleutel | De geheime sleutel in asymmetrische cryptografie die zorgvuldig beschermd moet worden door de eigenaar. Deze sleutel wordt gebruikt om informatie te ontsleutelen die met de bijbehorende publieke sleutel is versleuteld, of om digitale handtekeningen te creëren. | | Ciphertext (cijfertekst) | De versleutelde vorm van een oorspronkelijk bericht (plaintext). Ciphertext is onleesbaar zonder de juiste ontsleutelingssleutel en vormt de output van een encryptieproces. | | Plaintext (plat tekst) | Het oorspronkelijke, onversleutelde bericht dat door een cryptografisch algoritme wordt verwerkt. Dit is de menselijk leesbare invoer voordat deze wordt versleuteld of na ontsleuteling. | | Modulaire exponentiatie | Een wiskundige operatie die bestaat uit het verheffen van een getal tot een bepaalde macht, gevolgd door een deling door een modulus, waarbij alleen de rest wordt genomen. In RSA wordt dit vaak gebruikt als $C = M^e \pmod{n}$ voor encryptie en $M = C^d \pmod{n}$ voor decryptie. | | Brute force aanval | Een methode om een cryptografisch systeem te kraken door systematisch alle mogelijke wachtwoorden, sleutels of combinaties te proberen totdat de juiste is gevonden. De effectiviteit hangt af van de sleutelgrootte. | | Timing aanval | Een cryptanalytische aanval die misbruik maakt van de tijd die een cryptografisch systeem nodig heeft om bewerkingen uit te voeren. Door de duur van deze bewerkingen te meten, kan informatie over de geheime sleutel worden verkregen. | | Blinding | Een techniek die wordt gebruikt om cryptografische systemen, zoals RSA, te beschermen tegen timingaanvallen. Het houdt in dat de gegevens die door het algoritme worden verwerkt, worden vermenigvuldigd met een willekeurige factor, waardoor de uitvoertijd wordt gemaskeerd. | | Hardware fault-based attack (Hardware fout-gebaseerde aanval) | Een aanval waarbij opzettelijk fouten worden geïnduceerd in de hardware van een cryptografisch apparaat (bijvoorbeeld door de stroomtoevoer te manipuleren) om ongeldige uitvoer te genereren. Deze foutieve uitvoer kan vervolgens worden geanalyseerd om geheime informatie te achterhalen. | | Chosen ciphertext attack (CCA) (Gekozen cijfertekst aanval) | Een type cryptanalytische aanval waarbij de aanvaller de mogelijkheid heeft om specifieke cijferteksten te selecteren en de overeenkomstige ontsleutelde platte teksten te ontvangen. Dit kan leiden tot het achterhalen van de private sleutel. | | OAEP (Optimal Asymmetric Encryption Padding) | Een padding-schema dat wordt gebruikt om de veiligheid van asymmetrische encryptie, met name RSA, te verbeteren tegen gekozen cijfertekst aanvallen. Het voegt willekeurigheid toe en zorgt voor een veilige transformatie van de platte tekst voordat deze wordt versleuteld. |