RSA Kraken

PDF version

RSA is een van de meest gebruikte cryptografieën die we momenteel kennen. Het idee was simpel. Je hebt een publieke sleutel en een geheime sleutel. Met de publieke sleutel kan een zender een bericht encrypten en met de geheime sleutel kan dit bericht weer worden gedecrypt. Helaas is deze manier van encryptie niet helemaal veilig. In dit artikel zal ik uitleggen hoe RSA nu precies werkt en hoe je deze eenvoudig kunt kraken.

Encrypten met RSA

Zoals ik al in de inleiding aangaf, is er een zogenaamd publiek gedeelte. Iedereen kan dit deel van de versleuteling inzien. Als ontvanger van de informatie verspreid je deze dus.

N = 143
e = 37

Dit is een voorbeeldje van zo’n publieke sleutel. Belangrijk is dat e een priemgetal is en dat N de vermenigvuldiging is van twee priemgetallen. In dit geval 13*11. Dit houdt in dat ze alleen door zichzelf deelbaar zijn of deelbaar door 1. Het getal 1 is om wiskundige redenen echter geen priemgetal. Het rijtje begint dus met 2, 3, 5, 7, 11… Naast een sleutel heb je ook een codeboek waarin staat welke letter welke numerieke waarde heeft.

c = 3

Voor de encryptie gebruiken we de volgende formule:

ne % N

In deze situatie leidt dat tot:

337 % 143

Het %-teken heet de modulo. Dit is een operator die de restwaarde van een deling uitrekent. Dus 16 % 5 = 1, want er kan drie keer een hele vijf uit en dan hou je er nog maar één over.

Om dit uit te rekenen kun je natuurlijk een rekenmachine pakken, maar bij grotere getallen zal dit ongetwijfeld problemen op gaan leveren, omdat het simpelweg niet meer past en er dus afgerond moet worden.

Daarom gebruiken we de volgende techniek:

1 0 0 1 0 1 = 37 binair
1 (12 * 3) % 143 = 3 32 % 143 = 9 92 % 143 = 81 (812 * 3) % 143 = 92 922 % 143 = 27 (272 * 3) % 143 = 42 % 143

We kwadrateren het voorgaande getal dus steeds en bereken de restwaarde. Wanneer er een 1 staat in de binaire reeks, moet het voorgaande getal ook nog met het grondtal vermenigvuldigd (3) worden.

Het laatste item uit de reeks, 42, is het resultaat van de encryptie. Deze versturen we nu naar de ontvanger.

Decrypten

In het vorige hoofdstuk hebben we gezien hoe we eenvoudig een bericht kunnen versleutelen met RSA. Nu hebben we slechts één letter (c) geëncrypt, maar normaal gesproken krijg je dus een hele reeks getallen.

Voor het decrypten hebben we een geheime sleutel nodig. Deze sleutel is dus alleen bij de ontvanger bekend. Om door te gaan met het eerdere voorbeeld, gebruiken we de volgende sleutel:

d = 13

Om te decrypten gebruiken we een soortgelijke formule als bij het encrypten.

cd % N

Als we deze invullen, krijgen we in dit geval:

4213 % 143

1 1 0 1 = 13 binair
1 42 14 53 3 % 143

we krijgen nu de 3 weer terug en als we in het codeboek kijken, zien we dat hier de “c” bij hoort.

RSA kraken

We kunnen nu dus RSA encrypten en decrypten, maar het leukste is natuurlijk om deze te kraken. Om de RSA-codering te kraken heb je enige kennis nodig over hoe deze precies werkt. Oftewel: hoe kom je aan die N, e en d?

De e en d zijn priem. Daarbij komt dat d de inverse is van e. Om d uit te rekenen kunnen we dus de volgende formule gebruiken:

d = e-1 % φ(N)

Om te beginnen, gaan we de φ(N) uitrekenen. Aangezien N is opgebouw uit 11 en 13, gebruiken we:

φ(11) * φ(13)
(11-1)*(13-1) = 120

Dit geeft ons de volgende formule:

d = 37-1 % 120

Om dit uit te rekenen gaan we een tabel maken:

1 * 120 + 0 * 37 = 120
0 * 120 + 1 * 37 = 37
1 * 120 + -3 * 37 = 9
-4 * 120 + 13 * 37 = 1

Maar hoe komen we nu aan deze getallen? Dat is vrij ingewikkeld om uit te leggen, maar eenvoudig te begrijpen.
De bovenste twee regels zijn standaard-regels. Daarna ga je kijken hoe vaak de 37 in de 120 past. Dat is drie keer en de restwaarde is dan 9. De 9 vullen we daarom in, in het laatste vakje.
Nu hebben we de 1 uit het allereerste vakje en de 0 uit het tweede vakje van boven nodig. We doen nu 1 – 3 * 0. De één komt dus uit het bovenste vakje, de 0 uit het vakje daar onder en de 3 hebben we net uitgerekend door te kijken hoe vaak 37 in 120 past. Deze zelfde formule gebruiken we om de -3 uit te rekenen. 0 – 3 * 1 = -3.

We herhalen deze formule net zo lang tot we in het laatste vakje als resultaat 1 krijgen. In dit geval krijgen we:

-4 * 120 + 13 * 37 = 1

De -4 * 120 is niet belangrijk. Dit geeft alleen aan hoe vaak de modulo eraf gehaald is. De 13 * 37 is echter wel belangrijk. We weten nu namelijk dat d = 13.
Nu we dit weten, kunnen we het bericht eenvoudig decrypten.

Gevolgen

We hebben RSA nu gekraakt, maar is deze daarom per se onveilig? RSA wordt nog steeds op grote schaal gebruikt, waaronder het bankwezen. Maar met deze methodiek zou je dat toch allemaal kunnen kraken? Ja, dat klopt! MAAR… niet met een simpele thuiscomputer. Het bovenstaande voorbeeld is een minimaal voorbeeld. 11*13? Probeer het eens met N=10850763853. Dan moet je een machine hebben om het uit te kunnen rekenen. Hoe groter de priemgetallen zijn, hoe moeilijker het wordt om te kraken. Alleen met een kwantumcomputer zal een echt sterke RSA-encryptie te kraken zijn. Helaas zijn kwantumcomputers alleen op papier uitgevonden en niet in praktijk. Voorlopig is RSA dus nog wel veilig, alleen over een x aantal jaren zal die kwantumcomputer er echt wel komen en dan zijn de codes makkelijk te kraken. Dit betekent dat niet alleen systemen aangepast moeten worden in de toekomst, maar ook dat berichten die momenteel zijn afgeluisterd, alsnog gekraakt kunnen worden. Een pincode die door middel van RSA gekraakt is, zou dan alsnog gekraakt kunnen worden. Ik kan niet voorspellen wanneer deze kwantumcomputer op de markt komt, maar als ik de ontwikkelingen van de afgelopen 40 jaar bekijk, dan verwacht ik dat hij er wel komt de aankomende 40 jaar. Over 40 jaar is mijn pincode waarschijnlijk nog steeds hetzelfde en dan zou iemand alleen nog mijn pasje hoeven stelen.

Pincodes zouden alleen daarom al iedere tien jaar vervangen moeten worden. De miljoenennota voor volgend jaar kan prima opgeslagen worden met RSA-encryptie, omdat deze toch niet te kraken valt voordat deze publiek wordt gemaakt.

Conclusie

In het artikel heb ik besproken hoe je een bericht kunt encrypten en decrypten met RSA. Ook heb ik uitgelegd hoe een eenvoudige RSA-encryptie te kraken is. Voorlopig is RSA nog veilig, maar in de toekomst zal het te kraken zijn en we moeten dus ook voorkomen dat we data encrypten met RSA die over 40 jaar nog geheim moeten blijven.

126 Comments

jorgeFebruary 4th, 2015 at 16:19

.

thanks!!…

ChadFebruary 5th, 2015 at 10:00

.

tnx for info!…

craigFebruary 5th, 2015 at 10:31

.

ñïñ….

daleFebruary 5th, 2015 at 11:03

.

tnx….

CameronFebruary 5th, 2015 at 11:33

.

tnx for info….

alfredoFebruary 5th, 2015 at 22:37

.

thanks….

ErnestFebruary 6th, 2015 at 00:44

.

ñïñ!!…

freddieFebruary 6th, 2015 at 11:48

.

ñïàñèáî!…

BrianFebruary 6th, 2015 at 14:35

.

ñïñ çà èíôó!!…

BernardFebruary 6th, 2015 at 21:58

.

ñïñ çà èíôó….

leslieFebruary 7th, 2015 at 13:31

.

ñïàñèáî çà èíôó….

jimFebruary 7th, 2015 at 20:30

.

ñïñ….

JamesFebruary 8th, 2015 at 04:32

.

tnx for info!…

TrevorFebruary 8th, 2015 at 23:54

.

tnx!…

danielFebruary 9th, 2015 at 00:32

.

thanks for information!…

FelixFebruary 9th, 2015 at 01:07

.

good info….

kennethFebruary 9th, 2015 at 14:25

.

ñïàñèáî çà èíôó….

brettFebruary 10th, 2015 at 19:07

.

thanks for information!!…

edwardFebruary 12th, 2015 at 17:52

.

ñýíêñ çà èíôó!…

dannyFebruary 12th, 2015 at 22:05

.

good!…

JessieFebruary 13th, 2015 at 03:16

.

good info….

sidneyFebruary 14th, 2015 at 07:19

.

good….

willardFebruary 14th, 2015 at 07:54

.

thanks….

georgeFebruary 14th, 2015 at 10:26

.

thank you….

PerryFebruary 14th, 2015 at 15:03

.

áëàãîäàðþ!…

ChesterFebruary 14th, 2015 at 15:34

.

thank you!…

Leave a comment

Your comment