Tutustu RSA-salaukseen vaihe vaiheelta: muodosta avaimet kahdesta alkuluvusta, salaa viesti ja pura se takaisin – opetuskäyttöön pienillä luvuilla.
Alkuluvut
Anna kaksi eri alkulukua. Laskuri laskee modulin n = p·q ja totientin φ(n) = (p−1)(q−1).
Julkinen eksponentti
e:n on oltava jaoton φ(n):n kanssa. Tästä laskuri muodostaa yksityisen eksponentin d.
Viesti
Viesti esitetään kokonaislukuna, joka on pienempi kuin moduli n.
Tulokset
RSA-salauslaskuri – julkisen avaimen salaus vaihe vaiheelta
RSA-salauslaskuri havainnollistaa, miten julkisen avaimen salaus toimii. Syötä kaksi alkulukua ja julkinen eksponentti, niin laskuri muodostaa avaimet, laskee yksityisen eksponentin sekä salaa ja purkaa viestin. Laskuri käyttää pieniä lukuja opetustarkoituksessa, jotta jokainen vaihe näkyy selvästi. Kyseessä on oppimistyökalu, ei oikeaan tietoturvaan tarkoitettu salain.
RSA:n idea
RSA on epäsymmetrinen salausmenetelmä: salaamiseen ja purkamiseen käytetään eri avaimia. Julkista avainta voi jakaa vapaasti, ja sillä kuka tahansa voi salata viestin. Vain yksityisen avaimen haltija voi purkaa viestin. Menetelmän turvallisuus perustuu siihen, että suuren luvun jakaminen alkutekijöihinsä on laskennallisesti erittäin vaikeaa.
Avainten muodostus
Avaimet rakennetaan kahdesta alkuluvusta p ja q seuraavasti:
n = p · q
φ(n) = (p − 1)(q − 1)
Julkinen eksponentti e valitaan niin, että se on jaoton φ(n):n kanssa eli syt(e, φ(n)) = 1. Yksityinen eksponentti d on e:n käänteisluku modulo φ(n):
d = e⁻¹ mod φ(n), eli e · d mod φ(n) = 1
Julkinen avain on pari (e, n) ja yksityinen avain pari (d, n).
Salaus ja purku
Viesti esitetään kokonaislukuna m, jonka on oltava pienempi kuin n. Salaus ja purku ovat molemmat modulaarisia potensseja:
salaus: c = mᵉ mod n
purku: m = cᵈ mod n
Koska e ja d ovat toistensa käänteislukuja modulo φ(n), purku palauttaa aina alkuperäisen viestin.
Vaiheittainen esimerkki
Otetaan p = 61 ja q = 53.
Moduli: n = 61 · 53 = 3233.
Totientti: φ(n) = 60 · 52 = 3120.
Valitaan e = 17 (jaoton 3120:n kanssa). Käänteisluku on d = 2753, sillä 17 · 2753 mod 3120 = 1.
Salataan viesti m = 65: c = 65¹⁷ mod 3233 = 2790.
Puretaan: 2790²⁷⁵³ mod 3233 = 65 – alkuperäinen viesti palautuu.
Eulerin lause RSA:n takana
RSA:n toimivuus seuraa Eulerin lauseesta: jos syt(m, n) = 1, niin m^φ(n) mod n = 1. Koska e · d = 1 + k·φ(n) jollakin kokonaisluvulla k, saadaan m^(e·d) = m · (m^φ(n))^k ≡ m (mod n). Tämä takaa, että salaus ja purku ovat toistensa käänteisoperaatioita.
Turvallisuus ja rajoitukset
Avainkoko: oikeassa käytössä alkuluvut ovat satoja numeroita pitkiä, jolloin n:n tekijöihinjako on käytännössä mahdotonta.
Täyte (padding): oikea RSA muotoilee viestin standardin mukaisesti ennen salausta; pelkkä mᵉ mod n ei ole turvallinen sellaisenaan.
Vain opetukseen: pienillä luvuilla salaus murtuu hetkessä, joten tätä laskuria ei pidä käyttää oikeiden tietojen suojaamiseen.
Usein kysytyt kysymykset
Mihin RSA-salaus perustuu?
RSA on julkisen avaimen salausmenetelmä, jonka turvallisuus perustuu siihen, että suuren luvun jakaminen alkutekijöihin on käytännössä erittäin hidasta. Julkista avainta voi jakaa vapaasti viestien salaamiseen, mutta vain yksityisen avaimen haltija voi purkaa ne. Salaus ja purku tehdään modulaarisella potenssilla.
Miten RSA-avaimet muodostetaan?
Valitaan kaksi alkulukua p ja q ja lasketaan niiden tulo n = p·q. Eulerin totientti on φ(n) = (p−1)(q−1). Julkinen eksponentti e valitaan niin, että se on jaoton φ(n):n kanssa, ja yksityinen eksponentti on e:n käänteisluku modulo φ(n), eli d = e⁻¹ mod φ(n). Julkinen avain on pari (e, n) ja yksityinen avain pari (d, n).
Miten viesti salataan ja puretaan?
Viesti esitetään lukuna m, jonka on oltava pienempi kuin n. Salaus tehdään kaavalla c = mᵉ mod n julkisella eksponentilla, ja purku kaavalla m = cᵈ mod n yksityisellä eksponentilla. Koska e ja d ovat toistensa käänteislukuja modulo φ(n), purku palauttaa alkuperäisen viestin.
Miksi tämä laskuri ei sovi oikeaan salaukseen?
Tämä laskuri käyttää pieniä lukuja, jotta laskennan vaiheet näkyvät selvästi opetustarkoituksessa. Oikeassa käytössä RSA-avaimet ovat tuhansia bittejä pitkiä, ja viesti täytetään (padding) sekä muotoillaan standardin mukaisesti. Pienillä luvuilla salaus on triviaalisti murrettavissa, joten työkalu on tarkoitettu vain oppimiseen.
Miksi e:n on oltava jaoton φ(n):n kanssa?
Yksityinen eksponentti d on e:n käänteisluku modulo φ(n). Käänteisluku on olemassa täsmälleen silloin, kun e:n ja φ(n):n suurin yhteinen tekijä on 1, eli ne ovat keskenään jaottomat. Jos näin ei ole, d:tä ei voida laskea eikä salausta purkaa. Yleisesti käytetty arvo on e = 65537.