Nøglerne
Sådan findes d: den udvidede euklidiske algoritme
Hver række dividerer de to rækker over den. I rækken med rest 1 er den sidste kolonne d (læg φ(n) til, hvis den er negativ).
| Kvotient | Rest | Koefficient for e |
|---|
Beskeden
Sendes over nettet
| Bit | Kvadrér | Gang med m |
|---|
At bryde nøglen
RSA-krypteringsdemo
Med RSA kan alle låse en besked med din offentlige nøgle, mens kun du kan låse den op med din private nøgle. Bag det ligger nogle få linjer skolematematik: to primtal, en multiplikation, en rest og en snedig invers. Byg et nøglepar af primtal, du selv vælger, kryptér og dekryptér en besked tegn for tegn, signér den, så alle kan kontrollere, at den kom fra dig, og spil så angriber og faktorisér n for at se, hvorfor rigtige nøgler skal have hundredvis af cifre. Vælg to primtal p og q, eller tryk på Nye primtal. Appen bygger den offentlige nøgle (e, n) og den private nøgle d og viser, hvordan den udvidede euklidiske algoritme finder d. Skriv en besked: hvert tegn krypteres med den offentlige nøgle og dekrypteres med den private nøgle. Klik på en række for at se potensen beregnet ved gentagen kvadrering. Skift til Signér for i stedet at signere med den private nøgle, og tryk på Faktorisér n for at se, hvor hurtigt små nøgler brydes.
Sådan virker det
- Indtast to primtal p og q, eller vælg en størrelse, og tryk på Nye primtal; appen beregner n, φ(n), e og d og viser, hvordan d findes.
- Skriv en besked, og vælg Kryptér eller Signér. Hvert tegn omdannes til et tal og opløftes til en potens mod n; klik på en række for at se den gentagne kvadrering.
- Tryk på Faktorisér n for at lade Eve splitte n i dets to primtal og genskabe den private nøgle.
Sådan virker nøglerne
Gang to primtal sammen: n = p × q. Med p = 61 og q = 53 er n = 3233. Tallet φ(n) = (p − 1)(q − 1) = 3120 tæller de tal under n, der ikke har nogen fælles faktor med det, og det kan kun beregnes af en, der kender p og q. Vælg e = 17, der ikke har nogen fælles faktor med 3120, og find d, så e × d er 1 mere end et multiplum af φ(n): her er d = 2753, fordi 17 × 2753 = 46801 = 15 × 3120 + 1. Offentliggør (e, n), og behold d. En besked m bliver til c = mᵉ mod n, og Eulers sætning garanterer, at cᵈ mod n giver m tilbage.
Hvorfor den er svær at bryde
Alt, hvad en angriber har brug for, er skjult i faktorerne i n. Med n = 3233 er det ingen beskyttelse: ved at prøve ulige divisorer finder man 53 efter omkring to dusin forsøg. Men arbejdet vokser med kvadratroden af n. Et modulus på 2048 bit har omkring 617 cifre, og ingen kendt metode på nogen computer, der findes i dag, kan faktorisere det inden for en brugbar tid. Signering kører RSA baglæns: s = mᵈ mod n kan kun laves med den private nøgle, og alle kan kontrollere, at sᵉ mod n giver m tilbage.
Ofte stillede spørgsmål
Hvorfor kan ingen beregne d ud fra den offentlige nøgle?
For at finde d skal du bruge φ(n) = (p − 1)(q − 1), og for at få φ(n) skal du bruge p og q. At genskabe dem ud fra n betyder at faktorisere det, og for tal med hundredvis af cifre kendes ingen hurtig metode. Demoen lader dig faktorisere legetøjsnøgler på en brøkdel af et sekund, hvilket viser præcis, hvorfor rigtige nøgler er så store.
Hvorfor krypteres beskeden ét tegn ad gangen?
Fordi legetøjsnøglerne er små: RSA kan kun kryptere et tal, der er mindre end n. Med n = 3233 passer hver tegnkode, men en hel sætning ville ikke gøre det. Rigtig RSA bruger et modulus på 2048 bit eller mere, udfylder beskeden med tilfældige bytes, så den samme besked aldrig krypteres på samme måde to gange, og krypterer i praksis kun en kort nøgle til en hurtigere kryptering som AES.
Hvad gør gentagen kvadrering?
Den beregner enorme potenser som m²⁷⁵³ mod n uden nogensinde at skrive det enorme tal ned. Skriv eksponenten binært, og gå så dens bit igennem: kvadrér det løbende resultat for hver bit, og gang med m for hvert 1-tal, og tag resten mod n hver gang. En eksponent på 2048 bit kræver kun omkring 2048 kvadreringer.
Hvad er forskellen på at kryptere og at signere?
Kryptering bruger modtagerens offentlige nøgle, så kun modtagerens private nøgle kan gøre den om. Signering bruger afsenderens private nøgle, så alle kan kontrollere signaturen med afsenderens offentlige nøgle og vide, at beskeden kom fra indehaveren af den nøgle og ikke er blevet ændret.
Bliver min besked sendt nogen steder hen?
Nej. Alt beregnes i din browser, og dine primtal og din besked gemmes i denne browsers lokale lager.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor