MAA11 Algoritmit ja lukuteoria

RSA-salaus

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(\text{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(\text{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(\text{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(\text{mod}143).$$ Salattu viesti $s$ on siis vain luku 7. Viestin voi purkaa laskemalla $$s^d=7^{103}\equiv 123(\text{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=114097104097116032111118097116032117108108097107111108108097.$$ Käytetään lukuja $$e=65537$$ ja 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)

Tuloksena saadaan 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

Kirjaudu sisään ratkoaksesi tehtäviä.

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

Kirjaudu sisään ratkoaksesi tehtäviä.

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:

1. Valitaan kaksi suurta alkulukua $p$ ja $q$
   (Mielellään melkein samaa kokoluokkaa.)
2. Lasketaan $n=p\cdot q$
3. Lasketaan $\lambda (n)=\text{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$.)
4. Valitaan $e$ siten, että $1<e<\lambda (n)$ ja $\text{syt}(e,\lambda (n))=1$.
   Tyypillisesti $e$ on suhteellisen pieni, esimerkiksi alkuluku $2^{16}+1=65537$.
5. Luku $d$ ratkaistaan yhtälöstä $d\cdot e\equiv 1(\text{mod}\lambda (n))$.
   Yhtälö on muotoa $ed-k\lambda (n)=1$ eli muotoa $ax+by=c$, joten sillä on ratkaisu, kun $\text{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(\text{mod }\lambda (n))$. 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=p{q}_1$ ja $n_2=p{q}_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(\text{mod}p).$$ Lause voidaan muotoilla myös näin: Kun $p$ on alkuluku jolla $a$ ei ole jaollinen, $$a^{p-1}\equiv 1(\text{mod}p).$$ Ylempi muotoilu seuraa alemmasta kertomalla puolittain luvulla $a$ ja tutkimalla erikseen tapauksen $a\equiv 0(\text{mod}p)$.

Fermat'n pienen lauseen todistus

Olkoon $p$ alkuluku ja $a$ luku, joka ei ole jaollinen $p$:llä. Tutkitaan lukuja $$a,2a,3a,\dots ,(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(\text{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,\dots ,(p-1)a$ jakojäännökset ovat siis (jossakin järjestyksessä) $1,2,3,\dots ,(p-1)$. Voidaan kirjoittaa $$a\cdot 2a\cdot 3a\cdot \dots \cdot (p-1)a\equiv 1\cdot 2\cdot 3\dots \cdot (p-1)(\text{mod}p),$$ eli $$a^{p-1}\cdot (p-1)!\equiv (p-1)!(\text{mod}p).$$ Koska $(p-1)!$ ei voi olla jaollinen alkuluvulla $p$, se voidaan supistaa pois ja saadaan $$a^{p-1}\equiv 1(\text{mod}p).{}_{◻}$$

Lemma jakojäännöksistä

Olkoot $p$ ja $q$ lukuja, joilla ei ole yhteisiä tekijöitä.

Väite: Jos $a\equiv r(\text{mod}p)$ ja $a\equiv r(\text{mod}q)$, pätee $a\equiv r(\text{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(\text{mod}pq).$

Itse todistus

Väite on, että kaikille luvuille $v$ pätee $$(v^e{)}^d\equiv v(\text{mod}n)$$ aina kun $$n=pq\text{ja}ed\equiv 1(\text{mod}(p-1)(q-1)),$$ missä $p$ ja $q$ ovat alkulukuja.

Todistus on seuraava:

Koska $ed\equiv 1(\text{mod}\text{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(\text{mod}n)$. Tämän toteamiseksi riittää tarkistaa, että $(v^e{)}^d\equiv v(\text{mod}p)$ ja $(v^e{)}^d\equiv v(\text{mod}q)$ (ks. lemma jakojäännöksistä).

Tapaus $v\equiv 0(\text{mod}p)$ on selvä, sillä kongruenssin laskusääntöjen nojalla myös $(v^e{)}^d\equiv 0(\text{mod}p)$.

Jos taas $v\not\equiv 0(\text{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(\text{mod}p).$$ Välivaihe $v^{p-1}\equiv 1(\text{mod}p)$ seuraa Fermat'n pienestä lauseesta.

Vastaava päättely osoittaan, että $(v^e{)}^d\equiv v(\text{mod}q)$.

Koska $(v^e{)}^d\equiv v(\text{mod}p)$ ja $(v^e{)}^d\equiv v(\text{mod}q)$, pätee $(v^e{)}^d\equiv v(\text{mod}n)$. ${}_{◻}$