Modulus n
φ(n) (p − 1)(q − 1)
Publieke sleutel (e, n)
Privésleutel d e · d mod φ(n) = 1

De sleutels

    Hoe d wordt gevonden: het uitgebreide algoritme van Euclides

    Elke rij ontstaat door de twee rijen erboven op elkaar te delen. In de rij met rest 1 staat in de laatste kolom d (tel er φ(n) bij op als die negatief is).

    QuotiëntRestCoëfficiënt van e

    Het bericht

    Teken Code m Resultaat

    Verstuurd over het netwerk

    BitKwadraterenVermenigvuldigen met m

    De sleutel kraken

    Wat wil je doen

    Meer informatie over RSA

    Demo van RSA-versleuteling

    Met RSA kan iedereen een bericht op slot doen met jouw publieke sleutel, terwijl alleen jij het kunt openen met je privésleutel. Daarachter zitten een paar regels schoolrekenwerk: twee priemgetallen, een vermenigvuldiging, een rest en een slimme inverse. Maak een sleutelpaar van priemgetallen die je zelf kiest, versleutel en ontsleutel een bericht teken voor teken, onderteken het zodat iedereen kan controleren dat het van jou komt, en speel dan zelf de aanvaller en ontbind n in factoren om te zien waarom echte sleutels honderden cijfers nodig hebben. Kies twee priemgetallen p en q, of druk op ‘Nieuwe priemgetallen’. De app maakt de publieke sleutel (e, n) en de privésleutel d, en laat zien hoe het uitgebreide algoritme van Euclides d vindt. Typ een bericht: elk teken wordt versleuteld met de publieke sleutel en ontsleuteld met de privésleutel. Klik op een rij om de macht te zien die met herhaald kwadrateren wordt berekend. Schakel over naar Ondertekenen om in plaats daarvan met de privésleutel te ondertekenen, en druk op ‘n ontbinden’ om te zien hoe snel kleine sleutels breken.

    Hoe het werkt

    1. Voer twee priemgetallen p en q in, of kies een grootte en druk op ‘Nieuwe priemgetallen’; de app berekent n, φ(n), e en d, en laat zien hoe d wordt gevonden.
    2. Typ een bericht en kies Versleutelen of Ondertekenen. Elk teken wordt omgezet in een getal en mod n tot een macht verheven; klik op een rij om het herhaald kwadrateren te zien.
    3. Druk op ‘n ontbinden’ om Eve n te laten splitsen in zijn twee priemgetallen en de privésleutel te laten achterhalen.

    Hoe de sleutels werken

    Vermenigvuldig twee priemgetallen: n = p × q. Met p = 61 en q = 53 is n = 3233. Het getal φ(n) = (p − 1)(q − 1) = 3120 telt de getallen onder n die geen factor met n gemeen hebben, en alleen iemand die p en q kent, kan het berekenen. Kies e = 17, dat geen factor met 3120 gemeen heeft, en zoek d zodat e × d 1 meer is dan een veelvoud van φ(n): hier d = 2753, want 17 × 2753 = 46801 = 15 × 3120 + 1. Publiceer (e, n) en houd d voor jezelf. Een bericht m wordt c = mᵉ mod n, en de stelling van Euler garandeert dat cᵈ mod n weer m oplevert.

    Waarom het moeilijk te kraken is

    Alles wat een aanvaller nodig heeft, zit verborgen in de factoren van n. Met n = 3233 is dat geen bescherming: oneven delers proberen vindt 53 na ongeveer twee dozijn pogingen. Maar de moeite groeit met de wortel van n. Een modulus van 2048 bits heeft ongeveer 617 cijfers, en geen enkele bekende methode kan hem op een computer die vandaag bestaat binnen een bruikbare tijd ontbinden. Ondertekenen laat RSA achteruit lopen: s = mᵈ mod n kan alleen met de privésleutel worden gemaakt, en iedereen kan controleren dat sᵉ mod n weer m oplevert.

    Veelgestelde vragen

    Waarom kan niemand d berekenen uit de publieke sleutel?

    Om d te vinden heb je φ(n) = (p − 1)(q − 1) nodig, en om φ(n) te krijgen heb je p en q nodig. Die uit n terugvinden betekent n in factoren ontbinden, en voor getallen met honderden cijfers is geen snelle methode bekend. In de demo ontbind je speelgoedsleutels in een fractie van een seconde, en dat laat precies zien waarom echte sleutels zo groot zijn.

    Waarom wordt het bericht teken voor teken versleuteld?

    Omdat de speelgoedsleutels klein zijn: RSA kan alleen een getal versleutelen dat kleiner is dan n. Met n = 3233 past elke tekencode, maar een hele zin niet. Echte RSA gebruikt een modulus van 2048 bits of meer, vult het bericht aan met willekeurige bytes zodat hetzelfde bericht nooit twee keer op dezelfde manier wordt versleuteld, en versleutelt in de praktijk alleen een korte sleutel voor een sneller versleutelingsalgoritme zoals AES.

    Wat doet herhaald kwadrateren?

    Het berekent enorme machten zoals m²⁷⁵³ mod n zonder het enorme getal ooit op te schrijven. Schrijf de exponent binair en loop dan zijn bits langs: kwadrateer het tussenresultaat bij elke bit en vermenigvuldig met m bij elke 1, en neem elke keer de rest mod n. Een exponent van 2048 bits heeft maar ongeveer 2048 kwadrateringen nodig.

    Wat is het verschil tussen versleutelen en ondertekenen?

    Bij versleutelen wordt de publieke sleutel van de ontvanger gebruikt, zodat alleen de privésleutel van de ontvanger het ongedaan kan maken. Bij ondertekenen wordt de privésleutel van de afzender gebruikt, zodat iedereen de handtekening kan controleren met de publieke sleutel van de afzender en weet dat het bericht van de houder van die sleutel komt en niet is veranderd.

    Wordt mijn bericht ergens naartoe gestuurd?

    Nee. Alles wordt in je browser berekend, en je priemgetallen en bericht blijven bewaard in de lokale opslag van deze browser.

    Klaar om het te proberen?

    Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

    Ga naar Editor