RSA krüpteerimise mänguasi

Vali kaks algarvu, sisesta sõnum ja vaata, kuidas RSA selle krüpteerib ning seejärel dekrüpteerib.

Näidisarvutus — RSA krüpteerimise mänguasi

Privaatvõti (n, d)	1783

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — RSA krüpteerimise mänguasi

RSA on üksainus tehe, mida kasutatakse kaks korda. Krüpteerimine on m^e mod n ja dekrüpteerimine c^d mod n — sama modulaarne astendamine, ainult teise astendajaga. Nipp on valida paar nii, et kaks korda rakendades saad sõnumi tagasi, kuid ühte astendajat teades ei tea sa teisest midagi. Kõik, mida paneel trükib, ongi selle paari otsimine. Rivest, Shamir ja Adleman avaldasid selle 1978. aastal — ja nagu selgus alles siis, kui GCHQ 1997 salastatuse maha võttis, leidis Clifford Cocks selle neli aastat varem ja jättis sahtlisse.

Mida iga sümbol tähendab

n: moodul, p·q. Avalik. Saladus on tema tegurid, mitte arv ise.
φ(n): Euleri funktsioon, (p−1)(q−1). Paneel saab selle trükkida, sest talle anti p ja q; ründaja, kellel on ainult n, ei saa, ja n-ist φ-ni jõudmine on sama raske kui tegurdamine.
e: avalik astendaja. Sobib iga φ(n)-ga ühistegurita arv — just seepärast see muutub, kui muudad üht algarvu.
d: salajane astendaja, e⁻¹ mod φ(n). Üksainus modulaarne pöördväärtus — silmapilkne, kui tead φ-d, ja kogu mäng, kui ei tea.

Kust valem tuleb

Korruta algarvud: n = p·q. Vaikeväärtustega 61 · 53 = 3233. See arv avaldatakse. 61 ja 53 tagasi saamine 3233-st võtab käsitsi hetke, ja just seepärast nimetatakse seda ausalt mänguasjaks.
Arvuta φ(n) = (p−1)(q−1) = 60 · 52 = 3120. See on kogu skeemi hingepunkt: n on avalik, φ(n) ei ole, ja ainus teadaolev tee ühelt teisele viib läbi tegurdamise.
Vali e, millel pole φ(n)-ga ühistegurit, ja lahenda e·d ≡ 1 (mod φ(n)) d suhtes. Paneel näitab 7⁻¹ mod 3120 = 1783. Pane tähele, mis see samm ei ole: see ei ole raske. φ-d teades on see üksainus modulaarne pöördväärtus. d salajasus tugineb tervenisti φ salajasusele.
Miks ringkäik toimib: konstruktsiooni järgi on e·d = 1 + kφ(n), seega m^ed = m^1+kφ(n) ≡ m (mod n) — Euleri teoreem. Dekrüpteerimine pole eraldi välja mõeldud pöördtehe; see on seesama astendamine astendajaga, mis esimese tagasi võtab.

Kuidas nähtut lugeda

Rida, mida tasub jälgida, on e, sest see ei ole konstant. Vaikimisi algarvudega näitab see 7; muuda p 67-ks ja sellest saab 5. Põhjus on real kohe ülalpool: e-l ei tohi olla φ(n)-ga ühistegurit, ja φ liikus 3120-lt 3432-le. Võrdle siis ekraanil kaht astendajat — e = 7 ja d = 1783. Avalik on tilluke ja salajane mitte, ning kumbki pole juhus: e valitakse meelega väike, et krüpteerimine oleks odav, ja d on see, mis pöördväärtusest välja tuleb. Viimane rida on tõend, et kõik õnnestus: m′ = 42, arv, mille sa sisestasid.

Eeldab: Et sõnum on arv, mis on väiksem kui n. Kui n = 3233, pole üle 3232 midagi krüpteerida — just seepärast ei krüpteeri päris RSA kunagi sõnumit otse: ta krüpteerib paarisaja bitise täidetud sümmeetrilise võtme ja jätab teksti enda kiiremale šifrile. Samuti eeldatakse, et p ≠ q ja et sa ei kasuta üht algarvu teises moodulis uuesti: kaks ühise teguriga moodulit on mõlemad murtud ühe ainsa suurima ühisteguriga.
Ei kehti, kui: Sa saad selle lehe murda ilma midagi tegurdamata. Sea p = 67, q = 53 ja sõnumiks 3. Paneel valib e = 5 ja trükib krüptogrammiks 243 — mis on lihtsalt 3⁵. Kuna 3⁵ on väiksem kui n = 3551, ei toimunud modulaarset taandamist üldse: krüptogramm on tavaline aste ja 243 viies juur on 3. Ei mingit võtit, ei mingit tegurdamist, sõnum käes. Proovi m = 5 ja saad 3125, mis on 5⁵; m = 8 juures ületab aste lõpuks n-i ja krüptogrammiks saab kasutu 809. See pole selle lehe viga — see on põhjus, miks keegi ei krüpteeri paljast arvu. Päris RSA täidab sõnumi enne struktureeritud juhuslikkusega, mille määrab RFC 8017 ja mis teebki astendamisest krüptosüsteemi.

Privaatvõti tuletatakse, seda ei valita 🖖

Vaata, kuidas paneel d üles ehitab. Vaikimisi algarvudega näitab see φ(n) = 60 · 52 = 3120, taandub siis väärtusele e = 7 — tema eelistatud 65537 on siin φ-st endast suurem — ja arvutab lõpuks d ≡ 7⁻¹ mod 3120 = 1783. See viimane samm on üksainus modulaarne pöördväärtus, igal masinal hetkega tehtud. Iseenesest pole d juures midagi salajast: see tuleb otse φ(n)-ist ja φ(n) tuleb otse p-st ja q-st. RSA ei peida seega privaateksponenti, vaid tegurdust. Siin on n = 3233, mille sülearvuti lahutab enne, kui sa selle lause lõpetad; RSA-2048 moodul on 617 kümnendkohta pikk ja kõik sammud ekraanil on muus osas samad.

Tabalukk, mida avad ainult sina 🖖

RSA annab igaühele lahtise tabaluku (sinu avaliku võtme), mille saab sõnumi ümber kinni klõpsata, kuid ainult sinu privaatvõti avab selle taas. Kuna lukustamine ja avamine kasutavad eri võtmeid, võid avaliku võtme kogu maailmale nähtavaks teha, reetmata, kuidas dekrüpteerida. See tööriist laseb kogu tsükli läbi mängida pisikeste algarvudega; päris süsteemid kasutavad samu samme sadade numbrikohtadega arvudega.

Krüpteerimine tagurpidi on allkiri 🖖

Seesama RSA tehe, tehtud vastupidises suunas, tõestab, kes sõnumi saatis, selle asemel et seda peita. Kui "dekrüpteerid" sõnumi oma privaatvõtmega, saab igaüks selle su avaliku võtmega tagasi "krüpteerida", et veenduda, et see tõesti pärineb sinult - see ongi digitaalallkiri. Nii toidab üksainus arvutus nii konfidentsiaalsust kui ka autentimist, lihtsalt vahetades, milline võti esimesena käiku läheb.

Ülesanded täielikult lahendatud

RSA võtmepaar, kus p = 61 ja q = 53 5 sammu
Genereerige RSA võtmepaar algarvude p = 61 ja q = 53 jaoks ning krüptige m = 42. Iga allpool toodud arv tuleneb nendest kolmest, sealhulgas avalik astendaja.
1. Moodul avaldatakse ja totient hävitatakse, kuid mõlemad on algarvudest vaid ühe korrutamise kaugusel. φ(n) loendab täisarve alla n, millel puudub sellega ühine tegur, mis kahe erineva algarvu korrutise puhul on (p − 1)(q − 1).
  
  $n = 61 \cdot 53 = 3233, ϕ (n) = (61 - 1) (53 - 1) = 60 \cdot 52 = 3120$
2. Avalik astendaja peab olema pööratav mooduli φ järgi, mis tähendab sellega ühisteguriteta olemist. Lahutage φ teguriteks ja väikesed kandidaadid langevad välja, jättes arvu 7 väikseimaks saadaolevaks paarituks astendajaks. Tegelikud võtmed kasutavad arvu 65537, kuid see on suurem kui antud φ, seega naaseb tööriist väikseima ühisteguriteta arvu juurde.
  
  $3120 = 2^{4} \cdot 3 \cdot 5 \cdot 13 ⟹ g cd (3, ϕ) = 3, g cd (5, ϕ) = 5, g cd (7, ϕ) = 1 ⟹ e = 7$
3. Arvu 7 pööramine mooduli 3120 järgi on laiendatud Eukleidese algoritm ja ei midagi enamat. Kolm jagamist jõuavad jäägini 1 ning samade kolme rea tagasiharutamine kirjutab selle 1 arvu 3120 ja 7 kombinatsioonina.
  
  $3120 = 445 \cdot 7 + 5, 7 = 1 \cdot 5 + 2, 5 = 2 \cdot 2 + 1 ⟹ 1 = 3 \cdot 3120 - 1337 \cdot 7$
4. Arvu 7 kordaja selles kombinatsioonis on negatiivne ja negatiivne pöördelement muudetakse positiivseks, liites mooduli ühe korra juurde. Krüptimine on seejärel üksainus mooduliga astendamine, mis tehakse kaks korda ruutuvõtmisega, mitte arvu 42 seitse korda iseendaga korrutamisega.
  
  $d \equiv - 1337 \equiv 1783 (mod 3120), c = 4 2^{4} \cdot 4 2^{2} \cdot 42 = 1550 \cdot 1764 \cdot 42 \equiv 240 (mod 3233)$
5. Dekrüptimist ei pea kunagi kontrollima jõumeetodil (brute force) ning realistlike võtmesuuruste puhul ei oleks see võimalikgi. Mõlemad astendajad konstrueeriti nii, et nende korrutis on ühe võrra suurem kui φ kordne, ja Euleri teoreem viib selle lõpule iga n suhtes algarvulise m korral — mida 42 ongi.
  
  $e d = 7 \cdot 1783 = 12481 = 4 \cdot 3120 + 1 ⟹ c^{d} \equiv m^{e d} = m (m^{ϕ})^{4} \equiv m = 42$
Vastus

Tööriist kuvab n = 3233, φ = 3120, d = 1783 ja c = 240 ning kinnitab, et 240 dekrüptides annab tagasi 42. Meeles pidamist vääriv osa on see, mis φ tegelikult on. See ei ole teine saladus p ja q kõrval — see on sama saladus teistmoodi kirja panduna. Kui n ja φ on antud, on teil p + q = n − φ + 1 = 114 ja pq = 3233, ruutvõrrand, mille diskriminant on täisruut, ning see annab ühe reaga tagasi arvud 61 ja 53. Seega võtmegenereerija, mis lekitab φ, on lekitanud teguriteks lahutamise sama täielikult, nagu oleks see trükkinud välja algarvud, mistõttu φ arvutatakse üks kord, kasutatakse d leidmiseks ja visatakse seejärel minema.

$p + q = n - ϕ + 1 = 114, pq = 3233 ⟹ x^{2} - 114 x + 3233 = 0 ⟹ x = 61, 53$
Arvu 3233 tegurdamine 61 × 53-ks RSA turvalisuse murdmiseks 6 sammu
Paneel tegurdab 3233 kujule 61 × 53 enne, kui sa lehe lõpuni loed. Just see tegurdamine ongi kogu RSA turvalisus, näiliselt hetkega murtud. Arvuta välja, mis teeb sama ülesande ühe võtmesuuruse võrra edasi võimatuks.
1. Kaks arvu, millest paneel alustab: moodul ja Euleri funktsioon, mis kahest algarvust tuleneb.
  
  $n = 61 \times 53 = 3233, ϕ (n) = 60 \times 52 = 3120$
2. Ründajal on vaja ainult üht fakti: väiksem algarv ei saa ületada mooduli ruutjuurt. Miski suurem vajaks partnerit, kes on temast endast väiksem.
  
  $p \leq n ⟹ 3233 = 56.86, π (56) = 16$
3. Otsing käib seega algarvude üle kuni 56-ni, ja neid on kuusteist. Kuueteistkümnes on 53. Kuusteist jagamist pole turvalisus, see on ümardusviga.
  
  $53 < 56.86 \in {2, 3, 5, \dots, 53} ⟹ k \leq 16$
4. Pane nüüd sisse moodul, mida keegi tegelikult kasutab. 2048 bitti tähendab n-i 2²⁰⁴⁸ lähedal, ja selle ruutjuur on 2¹⁰²⁴ ehk umbes 10³⁰⁸.
  
  $n \approx 2^{2048} ⟹ n = 2^{1024} \approx 1 0^{308}$
5. Pane sellele hind. Miljardi proovijagamise juures sekundis on see 10²⁹⁹ sekundit — vastu universumit, mis on umbes 4 × 10¹⁷ sekundit vana.
  
  $\frac{1 0 ^{308}}{1 0 ^{9} s ^{- 1}} = 1 0^{299} s \approx 1 0^{291} yr$
6. Aeg on sellise suurusega arvu jaoks vale ühik; võrdle seda pigem millegi füüsilisega.
  
  $1 0^{308} ⋙ 1 0^{80}$
Vastus

Kuusteist jagamist 10³⁰⁸ vastu. Kuna 10³⁰⁸ ületab nähtava universumi aatomite arvu 10²²⁸ korda, ei suudaks me isegi loendurit salvestada. Oluline on siinkohal kuju, mitte suurus: ründaja töömaht kasvab nagu √n, samas kui võti kasvab nagu log n. Iga kaks lisabitti võtmes kahekordistavad seega murdmise hinna, minnes kaitsjale maksma vaid kaks bitti. Selles ebasümmeetrias peitubki kogu lahenduse tuum. Tööriista välkkiire vastus ei ole näite puudus. See ongi kogu näite iva, sest 3233 on täpselt selline moodul, mille puhul ebasümmeetriale pole antud ruumi toimida.

$16 ⟷ 1 0^{308}; O (n), n = 2^{2048}$

Allikad (4)

The idea RSA is an instance of — public keys, two years earlier: W. Diffie & M. Hellman, "New directions in cryptography." IEEE Transactions on Information Theory 22(6), 644–654, 1976.
What real RSA wraps round the message, and why the bare exponentiation on this page is not a cryptosystem: K. Moriarty (Ed.), B. Kaliski, J. Jonsson & A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2." RFC 8017, November 2016 — RSAES-OAEP in §7.1.
The scheme the tool walks through, including e·d ≡ 1 mod φ(n): R. L. Rivest, A. Shamir and L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems." Communications of the ACM 21(2), 120–126, 1978.
Why the security rests on factoring rather than on hiding d: A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, §8.2. CRC Press, 1996. ISBN 978-0-8493-8523-0.

42Mathi meeskond · Uuendatud 2026-08-17

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Arvutustehnika õppetunnid →

Näiteülesanded

p=61, q=53 - p=61, q=53: klassikaline õpiku RSA näide
Väikesed algarvud - p=7, q=11: väikesed algarvud, lihtne jälgida
Suuremad algarvud - p=101, q=103: suurem võtmeruum
Õpikunäide - p=17, q=19: õpikuülesanne