Tietojen salaus ja toisten luotettava tunnistus on verkossa välttämätöntä. Esimerkiksi verkkopankin käyttö HTTPS-protokollalla varmistaa, että
tiedot kulkevat salattuna ja vain oikea vastaanottaja voi purkaa ne.
Ilman luotettavaa salausta kolmas osapuoli voisi lukea viestin matkan varrella.
RSA on eräs laajasti käytetty tapa vaihtaa salattua informaatiota. Sen kehittelivät
Ron Rivest, Adi Shamir ja Leonard Adleman vuonna 1977.
Epäsymmetrinen salaus
Tässä on epäsymmetrisen salauksen idea:
Anna haluaa vastaanottaa salaisia viestejä.
Anna laatii julkisen avaimen ja salaisen avaimen. Julkisella avaimella voi salata viestejä ja salaisella avaimella purkaa niitä.
Anna lähettää julkisen avaimen kaikille, jotka sen tarvitsevat (ei haittaa, vaikka koko maailma näkisi sen).
Ville saa julkisen avaimen ja salaa sen avulla viestinsä Annalle.
Ville lähettää salatun viestin Annalle.
Anna saa Villen viestin. Sen voi avata vain yksityisellä avaimella, joten vain Anna voi lukea Ville viestin.
Koko kirjeenvaihto voidaan käydä täysin julkisesti, mutta tieto on turvassa niin
kauan kun salainen avain on piilossa.
Tilannetta voisi verrata Annan avoimena lähettämään kassakaappiin, jonka Ville voi sulkea ja lähettää takaisin lukittuna; Annalla on ainoa avain.
RSA:n toiminta
RSA toimii seuraavasti:
Ensin valitaan kokonaisluvut $e$, $d$ ja $n$ siten, että
kaikille kokonaisluvuille $v$ pätee
\[ (v^e)^d \equiv v \quad (\textrm{mod} \ n) \]
(Tämä on mahdollista, palataan myöhemmin siihen, miten temppu tehdään.) Lukujen rooli on seuraava:
lukupari $e$ ja $n$ muodostaa julkisen avaimen
luku $d$ on salainen avain
Ville lähettää viestin Annalle seuraavasti: Ensin sanallinen viesti muutetaan kokonaisluvuksi $v$ jollakin tavalla (Esimerkiksi a = 10, b = 11, c = 12,...). Tässä kohtaa turvallisuutta voi lisätä monimutkaisella muunnoksella, esimerkiksi
OAEP-menetelmällä.
Sitten Ville salaa viestin. Salattu viesti $s$ on luvun $v^e$ jakojäännös, kun jaetaan luvulla $n$. Pätee siis
\[ v^e \equiv s \quad (\textrm{mod} \ n). \]
Salattu viesti $s$ lähetetään Annalle, joka voi purkaa sen laskemalla luvun $s^d$ jakojäännöksen, kun jaetaan luvulla $n$. Koska luvut $n$, $e$ ja $d$ on valittu sopivasti, tuloksena on alkuperäinen viesti:
\[ s^d \equiv (v^e)^d \equiv v \quad (\textrm{mod} \ n). \]
Algoritmi voi välittää viesteinä lukuja $v$, jotka ovat lukua $n$ pienempiä.
Esimerkki 1
Toimiva (joskin turvallisuuden kannalta aivan liian pieni) kolmikko RSA-algoritmin käyttöön on $n=143$, $e=7$, $d=103$.
Viesti $v$ voi olla mikä tahansa lukua $n$ pienempi epänegatiivinen kokonaisluku, esimerkiksi $v = 123$. Salattuna se on
\[v^e = 123^7 \equiv 7 \quad (\textrm{mod} \ 143 ). \]
Salattu viesti $s$ on siis vain luku 7. Viestin voi purkaa laskemalla
\[s^d = 7^{103} \equiv 123 \quad (\textrm{mod} \ 143 ). \]
Modulaaristen eksponenttien laskeminen tietokoneella on hyvin nopeaa sopivalla algoritmilla. Esimerkiksi Python-kielellä laskut voi suorittaa komennolla pow(v,e,n), joka palauttaa luvun $v^e$ jakojäännöksen modulo $n$.
n = 143
e = 7
d = 103
# Viesti:
v = 123
# Salaus
s = pow(v,e,n)
# Purku
purettu_viesti = pow(s,d,n)
Esimerkki 2
Sanallisen viestin voi lähettää muuttamalla kirjaimet numeroiksi esimerkiksi ASCII-koodeja käyttäen.
Käytetään seuraavaa muuntotaulukkoa:
koodi
merkki
koodi
merkki
koodi
merkki
032
välilyönti
105
i
114
r
097
a
106
j
115
s
098
b
107
k
116
t
099
c
108
l
117
u
100
d
109
m
118
v
101
e
110
n
119
w
102
f
111
o
120
x
103
g
112
p
121
y
104
h
113
q
122
z
Näin esimerkiksi viesti rahat ovat ullakolla koodataan muotoon
$$v = 114 097 104 097 116 032 111 118 097 116 032 117 108 108 097 107 111 108 108 097.$$
Käytetään lukuja
Salattu viesti on luvun $v^e$ jakojäännös modulo $n$, ja se voidaan laskea esimerkiksi Python-koodilla
n = 145906768007583323230186939349070635292401872375357164399581871019873438799005358938369571402670149802121818086292467422828157022922076746906543401224889672472407926969987100581290103199317858753663710862357656510507883714297115637342788911463535102712032765166518411726859837988672111837205085526346618740053
e = 65537
d = 89489425009274444368228545921773093919669586065884257445497854456487674839629818390934941973262879616797970608917283679875499331574161113854088813275488110588247193077582527278437906504015680623423550067240042466665654232383502922215493623289472138866445818789127946123407807725702626644091036502372545139713
v = 114097104097116032111118097116032117108108097107111108108097
s = pow(v,e,n)
josta alkuperäistä viestiä on hyvin vaikea arvata. Viesti voidaan purkaa laskemalla luvun $s^d$ jakojäännös modulo $n$, jolloin tulos on alkuperäinen viesti $v$.
Tehtävä 1
Ratkaisematon
Toteuta ohjelma, joka käyttää lukuja
$n = 143$, $e = 7$ ja $d = 103$. Ohjelman tulee salata viesti $42$ ja tulostaa salattu viesti.
Kirjoita ohjelma tähän:
Tehtävä 2
Ratkaisematon
Toteuta ohjelma, joka käyttää esimerkissä 2 olleita lukuja $n$, $e$ ja $d$. Salainen viesti on seuraava:
s = 85428277862587239591968124579786099007709414278223047737899318765259424056436086074826093092150818499345040297473507839007632632095558200735189531211857679546669771791600041613523605832579335482328444517404371063136115723068982913626804303813782231498500488302844347689387955529396562717610808940562862565420
Kirjoita ohjelma, joka tulostaa yhdelle riville puretun viestin lukuna ja toiselle riville viestin tulkittuna tekstiksi.
Voit tehdä tekstiksi muuntamisen joko suoraan koodissa tai sitten käsin esimerkin 2 taulukon kanssa.
Kirjoita ohjelma tähän:
RSA:n yksityiskohtia
Avainten generointi
Mistä luvut $n$, $e$ ja $d$ saadaan? Prosessi on seuraava:
Valitaan kaksi suurta alkulukua $p$ ja $q$
(Mielellään melkein samaa kokoluokkaa.)
Lasketaan $n = p\cdot q$
Lasketaan $\lambda (n) = \textrm{pym}(p-1, q-1)$
($\lambda (n)$ on Carmichaelin funktio, jonka ominaisuuksista ei tarvita
tässä todistuksessa muita kuin se, että $\lambda(n)$ on jaollinen luvuilla $p-1$ ja $q-1$.)
Valitaan $e$ siten, että $1 < e < \lambda (n)$ ja $\textrm{syt}(e, \lambda (n))=1$.
Tyypillisesti $e$ on suhteellisen pieni, esimerkiksi alkuluku $2^{16}+1=65537$.
Luku $d$ ratkaistaan yhtälöstä $d\cdot e \equiv 1 \left(\textrm{mod} \ \lambda (n) \right) $.
Yhtälö on muotoa $ed-k\lambda(n)=1$ eli muotoa $ax+by=c$, joten sillä on ratkaisu,
kun $\textrm{syt}(e, \lambda (n))=1$.
RSA:n turvallisuus
Periaatteessa RSA-salaus on yksinkertaista murtaa: tarvitsee vain jakaa luku $n$ tekijöihinsä
$p$ ja $q$ ja ratkaista salainen avain $d$ yhtälöstä $ed \equiv 1 \left(\text{mod } \lambda (n) \right)$. Suurten lukujen tekijöihinjako on kuitenkin hidasta puuhaa.
Nykyään RSA-salauksessa käytetään avaimia, joiden pituus on binaarijärjestelmässä 1024 ja 4096 bitin välillä. Näistä ainakin 4096 bittiä on täysin vuoden 2021 tietokoneiden kykyjen ulottumattomissa. Kvanttitietokoneet saattavat muuttaa peliä.
Ei ole osoitettu, etteikö RSA:ta voisi yleisessä tapauksessa murtaa helpommallakin tavalla kuin jakamalla $n$ tekijöihinsä. Tästä ei kuitenkaan ole viitteitä.
Joitakin tunnettuja ongelmia kuitenkin on:
Jos $p$ ja $q$ ovat samaa kokoluokkaa, $n$ on jaettavissa tekijöihin nopeasti.
(Fermat'n tekijöihin jako)
Jos luvuilla $p-1$ ja $q-1$ on vain pieniä alkutekijöitä, $n$ voidaan
jakaa tekijöihin nopeasti. (Pollardin $p-1$-algorithmi)
Jos yksityinen avain $d$ on liian pieni, se voidaan selvittää tehokkasti
lukujen $e$ ja $n$ avulla.
Jos luvut $p$ ja $q$ on valittu huonosti toimivalla pseudosatunnaislukugeneraattorilla, kahdessa julkisessa avaimessa $n$ voi olla sama
tekijä $p$. Siis $n_1 = pq_1$ ja $n_2=pq_2$. Tällöin laskemalla syt$(n_1,n_2) = p$
saadan murrettua kumpikin salaus.
Koska julkisen avaimen avulla kuka tahansa voi salata viestejä, on mahdollista
kokeilla miltä todennäköiset viestin näyttävät salattuina. Näitä voidaan verrata todelliseen viestiin ja saada siis sen sisältö selville. Tätä hyökkäystä vastaan
viesti muutetaan luvuksi $v$ monimutkaisella, satunnaisuutta sisältävällä tavalla.
Jo muutaman satunnaisen merkin lisääminen viestin loppuun auttaa paljon.
Todistus RSA:n toimivuudesta
Todistuksessa tarvitaan aputuloksena Fermat'n pientä lausetta:
Fermat'n pieni lause
Kun $p$ on alkuluku, pätee
\[ a^p \equiv a \quad (\textrm{mod} \ p ). \]
Lause voidaan muotoilla myös näin: Kun $p$ on alkuluku jolla $a$ ei ole jaollinen,
\[ a^{p-1} \equiv 1 \quad (\textrm{mod} \ p ). \]
Ylempi muotoilu seuraa alemmasta kertomalla puolittain luvulla $a$ ja tutkimalla erikseen tapauksen $a\equiv 0 (\textrm{mod} \ p)$.
Fermat'n pienen lauseen todistus
Olkoon $p$ alkuluku ja $a$ luku, joka ei ole jaollinen $p$:llä. Tutkitaan lukuja
\[ a, \ 2a, \ 3a, \ \ldots ,\ (p-1)a. \]
Väitetään, että näiden lukujen jakojäännökset modulo
$p$ ovat kaikki erisuuria. Näin täytyy olla, sillä jos olisi
$ma = na \ (\textrm{mod} \ p ) $, täytyisi olla $p|(ma-na)$ eli $p|a(m-n)$. Koska
$p$ ei jaa lukua $a$, täytyy olla $p|(m-n)$, mutta tämä on mahdollista vain
kun $m=n$, sillä $m$ ja $n$ ovat lukua $p$ pienempiä. Jakojäännökset ovat siis erisuuria.
Lukujen $a, \ 2a, \ 3a, \ \ldots ,\ (p-1)a$ jakojäännökset ovat siis (jossakin
järjestyksessä) $1, \ 2, \ 3, \ \ldots ,\ (p-1)$. Voidaan kirjoittaa
\[ a\cdot 2a \cdot 3a \cdot \ldots \cdot (p-1)a \equiv
1\cdot 2 \cdot 3 \ldots \cdot (p-1) \quad (\textrm{mod} \ p ), \]
eli
\[ a^{p-1}\cdot (p-1)! \equiv
(p-1)! \quad (\textrm{mod} \ p ). \]
Koska $(p-1)!$ ei voi olla jaollinen alkuluvulla $p$, se voidaan supistaa pois ja saadaan
\[ a^{p-1} \equiv
1 \quad (\textrm{mod} \ p ). \quad _\Box \]
Lemma jakojäännöksistä
Olkoot $p$ ja $q$ lukuja, joilla ei ole yhteisiä tekijöitä.
Väite: Jos $a \equiv r \ (\textrm{mod} \ p) $ ja $a \equiv r \ (\textrm{mod} \ q) $,
pätee $a \equiv r \ (\textrm{mod} \ pq) $
Todistus: Oletusten perustella $a = mp +r$ ja $a = nq + r$. Vähentämällä nämä
toisistaan saadaan $0=mp-nq$ eli $mp = nq$. Luku $mp$ on siis jaollinen luvulla
$q$, ja koska syt$(p,q)=1$, täytyy olla $m=kq$. Siis
\[a = mp +r = kqp +r, \]
eli $a \equiv r \ (\textrm{mod} \ pq).$
Itse todistus
Väite on, että kaikille luvuille $v$ pätee
\[(v^e)^d \equiv v \quad (\textrm{mod} \ n) \]
aina kun
\[n=pq \quad \textrm{ja} \quad ed \equiv 1 \ \ (\textrm{mod} \ (p-1)(q-1) ), \]
missä $p$ ja $q$ ovat alkulukuja.
Todistus on seuraava:
Koska $ed \equiv 1 \ \ (\textrm{mod} \ \textrm{pym}(p-1)(q-1))$, luku $ed - 1$ on jaollinen luvuilla $(p-1)$ ja $(q-1)$.
Voidaan siis kirjoittaa $ed-1 = k(q-1)$ ja toisaalta $ed-1 = r(p-1)$.
Halutaan nyt todistaan $(v^e)^d \equiv v \ \ (\textrm{mod} \ n )$. Tämän
toteamiseksi riittää tarkistaa, että $(v^e)^d \equiv v \ \ (\textrm{mod} \ p )$
ja $(v^e)^d \equiv v \ \ (\textrm{mod} \ q )$ (ks. lemma jakojäännöksistä).
Tapaus $v \equiv 0 \ \ (\textrm{mod} \ p )$ on selvä, sillä kongruenssin laskusääntöjen nojalla myös $(v^e)^d \equiv 0 \ \ (\textrm{mod} \ p )$.
Jos taas $v \not\equiv 0 \ \ (\textrm{mod} \ p )$, voidaan kirjoittaa
\[ (v^e)^d = v^{ed} = v^{ed-1}\cdot v = v^{r(p-1)}\cdot v =(v^{p-1})^r\cdot v \equiv
1^r\cdot v \equiv v \ \ (\textrm{mod} \ p ).\]
Välivaihe $v^{p-1} \equiv 1 \ \ (\textrm{mod} \ p )$ seuraa Fermat'n pienestä lauseesta.
Vastaava päättely osoittaan, että $(v^e)^d \equiv v \ \ (\textrm{mod} \ q )$.
Koska $(v^e)^d \equiv v \ \ (\textrm{mod} \ p )$ ja
$(v^e)^d \equiv v \ \ (\textrm{mod} \ q )$, pätee $(v^e)^d \equiv v \ \ (\textrm{mod} \ n )$. $_\Box$