Tie koodariksi

MAA11 Algoritmit ja lukuteoria

Kieli:

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: 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: 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:
koodimerkkikoodimerkkikoodimerkki
032välilyönti105i114r
097a106j115s
098b107k116t
099c108l117u
100d109m118v
101e110n119w
102f111o120x
103g112p121y
104h113q122z
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
\[n=145906768007583323230186939349070635292401872375357164399581871019873438799005358938369571402670149802121818086292467422828157022922076746906543401224889672472407926969987100581290103199317858753663710862357656510507883714297115637342788911463535102712032765166518411726859837988672111837205085526346618740053\]
\[e = 65537\] ja
\[d=89489425009274444368228545921773093919669586065884257445497854456487674839629818390934941973262879616797970608917283679875499331574161113854088813275488110588247193077582527278437906504015680623423550067240042466665654232383502922215493623289472138866445818789127946123407807725702626644091036502372545139713.\]
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
\[s=129362260133002037911205669821349096109013114555220389075180309647457027354929114936310465933040775689832590791096225777722599052359976006517619344866260061864888787564616801663131914232638836421572467423245856503553550263804712544570493359258334774044147596429091771730328160386247102418020415951029413215592,\]
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:
  1. Valitaan kaksi suurta alkulukua $p$ ja $q$
    (Mielellään melkein samaa kokoluokkaa.)
  2. Lasketaan $n = p\cdot q$
  3. 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$.)
  4. 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$.
  5. 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:

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$

Datatähti 2025 – peruskoulun ja lukion ohjelmointikilpailu käynnissä 28.10.–10.11.2024