RSA uitgelegd
Telkens als een browser een hangslotje toont, een bericht wordt ondertekend of software een update controleert, is publieke-sleutelcryptografie aan het werk, en RSA is daarvan de bekendste vorm. Het idee is dat de sleutel die een bericht op slot doet openbaar mag zijn, terwijl de sleutel die het opent privé blijft. Opmerkelijk genoeg rust het hele systeem op rekenwerk dat op school wordt geleerd: priemgetallen, vermenigvuldigen en resten.
Het probleem dat RSA oplost
Oudere versleutelingsmethoden, van het caesarcijfer tot het moderne AES, gebruiken dezelfde sleutel om te vergrendelen en te ontgrendelen, dus moeten beide kanten eerst in het geheim een sleutel delen. Publieke-sleutelcryptografie schrapt die stap. Iedereen heeft twee sleutels: een publieke sleutel die iedereen mag gebruiken om een bericht voor die persoon te versleutelen, en een privésleutel die alleen die persoon bezit en die als enige het bericht kan ontsleutelen. Whitfield Diffie en Martin Hellman beschreven het idee in 1976, en een jaar later vonden Ron Rivest, Adi Shamir en Leonard Adleman aan het MIT een manier om het te doen, die naar hun initialen RSA werd genoemd.
De sleutels maken
Kies twee grote priemgetallen, p en q, en vermenigvuldig ze: n = p × q. Bereken φ(n) = (p − 1)(q − 1), de phi-functie van Euler, die de getallen onder n telt die geen factor met n gemeen hebben. Kies een publieke exponent e die geen factor met φ(n) gemeen heeft; 65537 is de gebruikelijke keuze. Zoek dan de private exponent d zodat e × d bij deling door φ(n) rest 1 geeft. Het uitgebreide algoritme van Euclides doet dat snel. De publieke sleutel is het paar (e, n); de privésleutel is d. Met p = 61 en q = 53 levert dit n = 3233, φ(n) = 3120, e = 17 en d = 2753 op.
Versleutelen en ontsleutelen
Een bericht wordt eerst omgezet in een getal m dat kleiner is dan n. Om het te versleutelen bereken je c = mᵉ mod n, de rest van mᵉ bij deling door n. Om te ontsleutelen bereken je cᵈ mod n. De stelling van Euler garandeert dat dit weer m oplevert, omdat e × d 1 meer is dan een veelvoud van φ(n). Met de sleutels hierboven wordt de letter A, code 65, 65¹⁷ mod 3233 = 2790, en 2790²⁷⁵³ mod 3233 is weer 65. Zulke grote machten worden nooit uitgeschreven: herhaald kwadrateren berekent ze met één kwadratering per bit van de exponent, waarbij bij elke stap de rest wordt genomen.
Digitale handtekeningen
RSA werkt ook omgekeerd. Een bericht tot de macht van de private exponent verheffen, s = mᵈ mod n, levert een handtekening op die alleen de eigenaar van de sleutel kan maken. Iedereen kan die controleren met de publieke sleutel: als sᵉ mod n weer m oplevert, komt het bericht van de houder van d en is het onderweg niet veranderd. In de praktijk wordt niet het bericht zelf ondertekend, maar een korte hash ervan. Zulke handtekeningen beschermen software-updates, beveiligde websites en elektronische documenten.
Waarom het veilig is
Iedereen kan n en e zien. Om d te vinden heeft een aanvaller φ(n) nodig, en om φ(n) te vinden heeft die p en q nodig, dus RSA kraken komt neer op n ontbinden in factoren. Twee priemgetallen vermenigvuldigen kost een computer een fractie van een microseconde; het product weer opsplitsen geldt als extreem moeilijk. Het grootste RSA-challengegetal dat tot nu toe is ontbonden, RSA-250 in 2020, heeft 829 bits en kostte ongeveer 2700 jaar rekentijd. Sleutels die vandaag worden gebruikt, hebben minstens 2048 bits, ongeveer 617 cijfers.
Een geheim dat twee keer werd ontdekt
In 1973, vier jaar vóór RSA, vond de Britse wiskundige Clifford Cocks hetzelfde schema toen hij bij de inlichtingendienst GCHQ werkte, voortbouwend op een idee van zijn collega James Ellis. Het werk was geheim en werd pas in 1997 openbaar gemaakt. RSA zelf werd in 1983 in de Verenigde Staten gepatenteerd; het patent verliep in september 2000, twee weken nadat het algoritme was vrijgegeven voor het publieke domein.
RSA in de praktijk
Echte RSA versleutelt nooit direct tekst. Het bericht wordt aangevuld met willekeurige bytes, volgens een schema zoals OAEP, zodat hetzelfde bericht elke keer anders wordt versleuteld en er geen patronen kunnen uitlekken. Omdat RSA traag is, wordt het vooral gebruikt om een korte sleutel voor een snel symmetrisch versleutelingsalgoritme zoals AES uit te wisselen of te beschermen, of om te ondertekenen. Voldoende grote kwantumcomputers zouden n snel kunnen ontbinden met het algoritme van Shor uit 1994, en daarom worden er nu nieuwe post-kwantummethoden naast RSA ingevoerd.
Ontdek het zelf
Open de demo van RSA-versleuteling om sleutels te maken van je eigen priemgetallen of van willekeurige van 2 tot 8 cijfers, het uitgebreide algoritme van Euclides rij voor rij d te zien vinden, een bericht teken voor teken te versleutelen of te ondertekenen, en het herhaald kwadrateren voor elk teken te volgen. Laat Eve dan n ontbinden en kijk hoe de tijd die ze nodig heeft groeit met de grootte van de priemgetallen.
Veelgestelde vragen
Waarom heeft RSA priemgetallen nodig?
Omdat φ(n) alleen makkelijk te berekenen is als je weet hoe n uiteenvalt in priemgetallen. Voor n = p × q met p en q priem is φ(n) = (p − 1)(q − 1). Priemgetallen maken n bovendien zo moeilijk mogelijk te ontbinden voor zijn grootte, omdat het helemaal geen kleine factoren heeft.
Waarom is e vaak 65537?
65537 = 2¹⁶ + 1 is priem en heeft binair maar twee enen, dus versleutelen ermee kost slechts 16 kwadrateringen en één vermenigvuldiging. Het is ook groot genoeg om de zwakheden van heel kleine exponenten zoals 3 te vermijden.
Wat is het verschil tussen RSA en Diffie–Hellman?
Met Diffie–Hellman kunnen twee mensen over een open kanaal een gedeelde geheime sleutel afspreken; het versleutelt of ondertekent zelf niets. RSA versleutelt en ondertekent direct met een sleutelpaar. Beide berusten op problemen die in de ene richting makkelijk zijn en in de andere moeilijk: factorisatie bij RSA, de discrete logaritme bij Diffie–Hellman.
Kunnen de sleutels van de demo worden gebruikt voor echte versleuteling?
Nee. De priemgetallen hebben hoogstens een dozijn cijfers, dus elke sleutel die de demo maakt, kan in seconden of minder worden ontbonden, en de demo versleutelt elk teken afzonderlijk zonder padding. Hij is bedoeld om te zien hoe RSA werkt, niet om iets te beschermen.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Open de demo van RSA-versleuteling