RSA-Järjestelmän toteuttaminen C++

RSA-järjestelmän toteuttaminen C++ - ohjelmointikielellä

Markku-Juhani O. Saarinen
mjos@math.jyu.fi

10.10.1996

Sisältö

1. Suurten kokonaislukujen aritmetiikkaa
1.1 Klassiset kerto- ja jakolaskualgoritmit
1.2 Karatsuban kertolasku
1.3 Nopeaan Fourier-muunnokseen perustuva menetelmä
1.4 Osamäärän ja modulon laskeminen nopeiden kertolaskualgoritmien avulla

2. RSA:n tarvitsemia algoritmeja
2.1 Modulaarieksponentaatio
2.2 Suurimman yhteisen tekijän ja multiplikatiivisten käänteislukujen laskeminen
2.3 Satunnaisluvut
2.4 Suurten satunnaisten alkulukujen luominen

3. RSA-järjestelmän toiminta
3.1 Julkisen ja salaisen avaimen luominen
3.2 RSA:n perustoiminnot
3.3 Hybridi-RSA
3.4 RSA:n turvallisuus

4. Esimerkki ZenRSA:n toiminnasta

Lähteet

Liitteet
A. Suurten luonnolisten lukujen luokka kbn
- kbn.h
- kbn.cxx
B. Kryptoalgoritmit RC4 ja SHA
- rc4.h
- rc4.cxx
- sha.h
- sha.cxx
C. ZenRSA:n lähdekoodi
- zrsa.cxx
- Makefile

Disclaimer:

Lähdekoodit eivät ole hirvittävän kauniissa kunnossa nyt. Valmistelen julkaisevani koko jutun "oikeasti" lähiaikoina. Never the less: Jos löydät näistä koodeista jonkun puutteen tai bugin tms niin ole hyvä ja ilmoita siitä minulle! ( Siellä nimittäin 100% todennäköisyydellä on yhtä sun toista bugia/thinkoa, kuten kaikissa upouusissa ohjelmissa aina. Älä kuitenkaan pelästy; juttu on todistettavasti toiminut oikein ainakin minun koneessani! )

0. Johdanto

Seminaarityö käsittelee RSA (Rivest, Shamir ja Adleman, 1977) - kryptojärjestelmän totetuttamista. Pyrin myös hieman analysoimaan järjestelmän luotettavuutta nykyisen tietämyksen valossa. Lähestymistapa on tekninen; esitän menetelmät ja algoritmit, joita tarvitaan tehokkaan ja luotettavan RSA-järjestelmän toteuttamiseen C++ - ohjelmointikielellä. Liitteenä on täydellinen listaus toimivasta järjestelmästä.

Aluksi käsitellään hieman RSA-järjestelmän vaatimien suurten lukujen käsittelyä.

1. Suurten kokonaislukujen aritmetiikkaa

Peruslaskutoimitusten (yhteen-, vähennys-, kerto- ja jakolasku) toimittamiseen on lukuisia muitakin menetelmiä kuin ne, jotka opetetaan koulussa. Näillä menetelmillä on kullakin omat hyötynsä, haittansa ja soveliaat käyttökohteensa. Keskityn luonnolisten lukujen operaatioihin, koska liukuluvuilla ei ole käyttöä RSA-järjestelmän piirissä (eikä kryptografiassa muutenkaan pahemmin).

Peruskoulussa esitettävät yhteen- ja vähennyslasku ovat lineaarisia pidemmän luvun pituuden suhteen, ja ne ovatkin (kompleksisuudeltaan) näin ollen varsin edullisia.

1.1 Klassiset kerto- ja jakolaskualgoritmit

Suoritetaan esimerkin vuoksi perinteinen kertolasku luvuille 3142 * 2718:

	3*2 3*7 3*1 3*8
	    1*2 1*7 1*1 1*8
                4*2 4*7 4*1 4*8
                    2*2 2*7 2*1 2*8

          6  23  18  57  26  34  16

Muistilukujen kantamisen jälkeen:

          8   5   3   9   9   5   6

Nähdään, että kahden n-numeroisen luvun kertomiseen tarvitaan n² kertolaskua (1-numeroisilla luvuilla), n² yhteenlaskua (2 - numeroisilla luvuilla) ja lisäksi 2n yhteenlaskua muistilukujen kantamisen vuoksi. Perinteinen kertolasku on siis kompleksisuudeltaan tyyppiä O( n² ). On vastaavalla tavalla todettavissa, että klassinen jakokulma on myöskin tyyppiä O( n² ). [CER25, ss. 1-30] [KNU81, ss. 250-265]

Tietokonesovellutuksessa on tietenkin järkevää käyttää mahdollisimman suurikantaista sisäistä esitystä, jotta operaatioiden määrä saadaan mahdollisimman pieneksi. Tyypillinen kanta onkin 256 tai suurempi, omassa toteutuksessani 4096 = 12 bittiä. Tätä kovin paljon suurempia kantalukuja ei ole järkevä käyttää, sillä silloin välitulokset saattavat kasvaa suuremmiksi kuin koneen prosessorin rekisterityyppi (esim. unsigned int) pystyy pitämään sisällään.

Klassiset algoritmit ovat yksinkertaisuutensa takia nopeimpia menetelmiä nykyisillä avaimen pituuksilla vaadittavassa aritmetiikassa, mutta avainten pituuksien kasvaessa (ei edes kovin huomattavasti) kerto- ja jakolaskun neliöllinen kompleksisuus käy liian epäedulliseksi.

1.2 Karatsuban kertolasku

Klassisissa menetelmissä lukujen pituuden tuplaaminen johti operaatioiden määrän nelinkertaistumiseen. Ensimmäisen kerran kompleksisuudeltaan tätä nopeampi menetelmä esitettiin vuonna 1962, kun A. Karatsuba esitti menetelmän, jossa lukujen pituuden tuplaaminen johti operaatioiden määrän kolminkertaistumiseen.

Oletetaan, että halutaan kertoa kaksi 2n-bittistä lukua u ja v s.e :

u = U₁ 2ⁿ + U₀, U₀ < 2ⁿ
v = V₁ 2ⁿ + V₀, V₀ < 2ⁿ

tällöin U₁ on u:n ylemmät n bittiä ja U₀ alemmat n bittiä. Vastaavasti V₁ on v:n ylimmät n bittiä ja V₀ alemmat n bittiä. Tulo uv voidaankin kirjoittaa seuraavasti: [KNU81, s. 278]

uv = U₁V₁ (2²ⁿ + 2ⁿ ) + (U₁-U₀)(V₀-V₁) 2ⁿ + U₀V₀ (2ⁿ + 1)
Tämä voidaan ilmaista C:n syntaksilla seuraavasti (t1, t2 ja t3 väliaikaisia muuttujia, uv tulos) :

	t1 = U0 * V0;
	t2 = (U1-U0) * (V0-V1);
	t3 = U1 * V1;

	uv = ( ( (t3 << n) + t3 + t2 + t1) << n ) + t1;

Nähdään, että 2n-bittisen luvun kertolaskuun tarvittiin vain kolme kertolaskua ja lisäksi muutama nopea bitin pyöritys ja yhteenlasku. Menetelmää voi kayttää myös rekursiivisesti, jolloin päästään kompleksisuusluokkaan O (n^{log₂ 3}) eli likimain O (n^1.5850). Menetelmä ei ole sidottu binäärijärjestelmään. Esimerkiksi kertolasku 3142*2718 (desimaalijärjestelmässä) muuttuu muotoon:

 	n = 2
	u = 2718 : U₁ = 27, U₀ = 18
	v = 3142 : V₁ = 31, V₀ = 42

	t1 = 18 * 42 = 756 
	t2 = (42-31) * (27-18) = 11 * 9 = 99
	t3 = 27 * 31 = 837

	uv = (837 10² + 837 + 99 + 756) 10² + 756
	uv = 8 539 956

Karatsuban menetelmä voidaan myöskin yleistää ns. Tom-Cook menetelmiksi, joilla voidaan päästä vielä edullisempiin kompleksisuusluokkiin. Nämä menetelmät ovat tosin järkeviä vasta erittäin pitkillä luvuilla. [KNU81, ss. 279-286]

1.3 Nopeaan Fourier-muunnokseen perustuva menetelmä

Kertolasku voidaan toteuttaa myös ns. nopean fourier-muunnoksen (FFT) avulla. Kertolaskun n = pq vaiheet tällä menetelmällä ovat seuraavat:

Tallennetaan (esim. 256-kantaiset) kerrottavat luvut kompleksivektoreihin P ja Q. Vektoreiden tulee olla saman kokoiset (vähintään 2*max(p, q)). FFT-menetelmälle on edullista, jos kompleksivektorin pituus on kahden potenssi.
Vektoreille P ja Q suoritetaan FFT
Muodostetaan kolmas vektori N, jonka kukin alkio on kompleksiarvoinen tulo N_i = P_i * Q_i.
Suoritetaan vektorille N käänteinen FFT
Kannetaan muistiluvut ja tallennetaan (toivottavasti kokonaan reaalinen) kompleksivektori N binääriluvuksi n (tulos).

Menetelmä käyttää siis hyväkseen Fourier-muunnettujen funktioiden konvoluutio-ominaisuutta. Koska itse kompleksilukujen päittäinen kertolasku on lineaari-nopeuksinen, on koko operaation kompleksisuus sama kuin FFT:n, eli O ( n log n ).

Liukulukujen (double-tyypin) tarkkuus loppuu kesken vasta satojen tuhansien desimaalien pituisia lukuja käsiteltäessä. FFT voidaan toteuttaa myös käyttäen modulaariaritmetiikkaa, jolloin päästään eroon aproksimatiivisesta liukulukumaailmasta vielä tätäkin suuremman tarkkuuden piiriin. [PRE92, ss. 918-925] [KNU81, ss. 290-295] [COR90 s. 799]

1.4 Osamäärän ja modulon laskeminen nopeiden kertolaskualgoritmien avulla

RSA-järjestelmä perustuu täysin modulaariaritmetiikkaan, joten pelkällä kertolaskulla ei päästä pitkälle. Tarvitaan myöskin nopea menetelmä jakolaskun (ja näin ollen myös jakojäänöksen, joka on mainittu modulo) saamiseksi.

Yli neliöllisellä nopeudella toimiva jakolaskualgoritmi saadaan aikaiseksi Karatsuban- tai FFT-menetelmistä käyttäen vanhaa kunnon Newtonin menetelmää. Iteraatio luvun V käänteisluvun U_n = 1/V laskemiseksi voidaan kirjoittaa:

U_i+1 = U_i(2 - V U_i)

Osamäärä saadaan laskettua käänteisluvusta yhdellä ylimääräisellä kertolaskulla, ja tästä saadaan edelleen jakojäännös yhdellä kertolaskulla ja yhdellä vähennyslaskulla. Tällä menetelmällä on (hyvällä alkuarvauksella) kvadranttinen konvergenssi, joten käänteisluku ja sitä myöden myös jako- ja jakojäännös ovat tyyppiä O( n log n ). Tämä kompleksisuusluokka on kuitenkin harhaanjohtava, sillä menetelmä ohittaa nopeudeltaan klassisen neliöllisen jakolaskun vasta kymmenien tuhansien desimaalien lukuja laskettaessa. [PRE92, ss. 918-921]

2. RSA:n tarvitsemia algoritmeja

Käsittelen RSA:n toteutuksessa ilmenevien osaongelmien ratkaisuun tarvittavien algoritmien valintaa ja ohjelmointia.

2.1 Modulaarieksponentaatio

RSA:n purkuoperaatio on seuraava:

M = C^d mod n

Tässä M, C, d ja n ovat kukin esimerkiksi 1024-bittisiä. On selvää, että

Potenssiinkorotusta ei voida tehdä peräkkäisillä kertolaskuilla, koska d on hirvittävän suuri luku (noin 10³⁰⁸).
Modulon laskemista ei voida jättää viimeiseksi, sillä välituloksessa C^d olisi noin 10³¹¹ bittiä.
Potenssiinkorotusta ei kannata lähteä laskemaan eksponenttisarjojen kautta operaation kokonaislukuluonteen ja välituloksen valtavuuden takia.

Modulaarieksponentaatio voidaan toteuttaa nopeammin seuraavasti:

//           b
//  laskee  a  mod n

kbn& modexp (kbn a, kbn b, kbn n)
{
    static kbn r;
    int i, explen;

    r = 1;  
    explen = b.log2();

    for(i=0; i<=explen; i++)
    { 
        if ( b.testbit(i) )
            r = (r*a) % n;
        a = a.sqr() % n;
    }
    return r;
}

Tässä esimerkissä kbn on oma suuren tarkkuuden luonnollisten lukujen käsittelyyn kirjoittamani luokka. Käytännössä siis tarkastellaan eksponentin bittejä vähemmän merkitsevästä enemmän merkitsevään päin. Jos bitti on eksponentissa päällä, muuttuja r kerrotaan mod n välituloksella a. Muuttuja a neliöidään mod n joka kierroksella. Nähdään että tämä menetelmä tarvitsee keskimäärin O ( log b ) neliöintiä ja kertolaskua (mod n). Itse kompleksisuusluokka ajan suhteen riippuu siitä, miten nämä operaatiot on toteutettu. [DEN82, s. 39]

Nopeampiakin menetelmiä on esitetty, mutta ne soveltuvat lähinnä tapauksiin, joissa eksponentti pysyy vakiona (esim. optimoiviin kääntäjiin). [KNU81, s. 441-458]

2.2 Suurimman yhteisen tekijän ja multiplikatiivisten käänteislukujen laskeminen

Suurimman yhteisen tekijän laskeminen on triviaali operaatio, joka hoituu nopeasti Euklideen algoritmilla. Seuraava aliohjelma laskee annettujen lukujen a ja b suurimman yhteisen tekijän:

//  laskee syt(a, b)

kbn gcd(kbn a, kbn b)
{
    static kbn g0, g1, g2, zero;   

    g0 = a;
    g1 = b;
    zero = 0;

    while ( g1 != zero )
    {
        g2 = g0 % g1;
        g0 = g1;
        g1 = g2;
    }

    return g0;
}

RSA-järjestelmän avainten generoinnissa on laskettava multiplikatiivisiä käänteislukuja. Tämä tarkoittaa positiivisen kokonaisluvun a^-1 etsimistä, joka toteuttaa yhtälön

a a^-1 mod n = 1

Tämä voidan tehdä ns. laajennetulla Euklideen algoritmilla. Algoritmi on esitetty alunperin [KNU81 ss. 325-327], josta Denning lainasi sen kirjaansa [DEN82 s.44]. Toteutukseni seuraa lähinnä tätä mallia. Schneierin esittää kirjassaan sekavan toteutuksen (ilman kommentteja) binäärisestä laajennetusta Euklideen algoritmista [SCH96 ss. 246-248].


//  laskee b:n joka toteuttaa  ab mod n = 1  (jos mahdollista)

kbn& inverse (kbn a, kbn n)
{
    // nämä on pidettävä staattisina, sillä muuten ne söisivät koko
    // pinon ja kaataisivat ohjelman

    static kbn u1, u3, v1, v3, t1, t3, q, w, zero;
    int sign;

    // alustetaan nollavakio ja kiertomuuttajat

    zero = 0;

    // alustetaan muuttujat

    u1 = 1;
    u3 = a;
    v1 = 0;
    v3 = n;

    // laajennettu euklideen algoritmi
    // (muunnettu negatiivisten lukujen välttämiseksi)

    sign = 0;

    while( v3 != zero )
    {
        q = u3 / v3;
        t3 = u3 % v3;
        w = q * v1;
        t1 = u1 + w;
        u1 = v1;
        v1 = t1;
        u3 = v3;
        v3 = t3;

        sign = !sign;
    }

    // käännetään merkin mukaisesti

    if (sign)
        u1 = n - u1;

    return u1;
}

2.3 Satunnaisluvut

RSA-avainten generoinnissa tarvitaan hyvää satunnaislukugeneraattoria. Satunnaislukujen tulee toteuttaa ainakin seuraavat ehdot:

Satunnaislukujen tulee olla täysin riippuvaisia siemenluvusta
Siemenluvussa tulee olla riittävästi entropiaa (ts. mahdollisimman monta merkitsevää bittiä), jotta lukujonoja ei voitaisi etsiä raa'alla voimalla (silmukassa kokeillen kaikki mahdollisuudet läpi).
Mistään satunnaislukujonon osajonosta ei tule pystyä ennustamaan osajonon ulkopuolisia lukuja
Luvuilla ei saa olla havaittavia tasaisesta jakaumasta eriäviä tilastollisia ominaisuuksia

C:n standardikirjastoissa olevat satunnaislukugeneraattorit eivät täytä kaikkia mainittuja ominaisuuksia, varsinkaan siemenluvun pituuden osalta.

Eräs tyylikkäimmistä moderneista satunnaislukugeneraattoreista on MIT:n Ronald Rivestin kehittämä RC4. RC4:n siemenluvun (tai stream-cipher terminologialla avaimen) pituus on maksimissaan jopa 2048 bittiä (256 tavua). RC4:n sisäinen tila koostuu 256:n 8 bittisen luvun taulukosta S ja kahdesta 8-bittisestä luvusta rc4_i ja rc4_j. Näiden alustus siemenluvun key perusteella tapahtuu seuraavasti:

// alustetaan RC4 annetulla avaimella

void rc4::init (unsigned char *key, int keylen)
{
    int     i, j;        
    unsigned char t;     

    for(i=0; i<0x100; i++)
        S[i] = i;        

    for(i=0, j=0; i<0x100; i++)
    {
        j = (j + S[i] + key[i % keylen]) & 0xff;
        t = S[i];        
        S[i] = S[j];     
        S[j] = t;        
    }

    rc4_i = 0;           
    rc4_j = 0;           
}

Satunnaislukublokin tuottaminen tapahtuu seuraavasti:

// tuottaa satunnaistavuja l kpl muistiosoitteeseen pt

void rc4::rand(unsigned char *pt, size_t l)
{
    register unsigned char Si, Sj;
    register unsigned long i;

    for(i=0; i < l; i++)
    {
        rc4_i = (rc4_i+1) & 0xff;
        Si = S[rc4_i];
        rc4_j = (rc4_j+Si) & 0xff;
        Sj = S[rc4_j];
        S[rc4_i] = Sj;
        S[rc4_j] = Si;

        pt[i] = S[(Si + Sj) & 0xff];
    }
}

Havaitaan, että operaatio on erittäin yksinkertainen ja nopea, mutta nykyisen näkemyksen mukaan erittäin turvallinen. Hyvää satunnaislukugeneraattoria voidaan käyttää myös tiedon salaukseen: tiedon salaamiseksi salattavan muistilohkon ja satunnaisluvun välille suoritetaan xor-operaatio. Xor on oma käänteisoperaationsa; salatun lohkon purkaminen tapahtuu samalla tavalla kuin salaaminen. Samaa avainta ei luonnollisestikaan saa käyttää useamman kuin yhden viestin salaamiseen, sillä kahden samalla avaimella salatun viestin xor on itse satunnaisluku.Tälläistä konstuktiota kutsutaan virta (stream) - tyyppiseksi kryptoalgoritmiksi. [SCH96, ss. 397-398]

Yksi perusongelmista on satunnaissiemenen alustus. Itse käytän satunnaissiemenen alustukseen seuraavia systeemimuuttujia, jotka toivottavasti tuovat alustukseen riittävän entropian (hyökkääjän olisi tunnettava kaikkien näiden arvot tarkasti, jotta satunnaisgeneraattorin alustuksen jäljittely onnistuisi):

Kiertolaskuri: kuinka monta satunnaislukua on generoitu
Ohjelman käyttämä prosessoriaika 1/100 sekunnin tarkkuudella
Tarkka päivämäärä ja kellonaika mikrosekunnin tarkkuudella
Aikavyöhyke (liittyy koneen sijaintiin)
Viimeisestä bootista kulunut aika sekunneissa
Koneen ram-muistin kokonaismäärä tavuina
Vapaan ram-muistin määrä tavuina
Jaetun muistin määrä tavuina
Puskureihin sijoitetun muistin määrä tavuina
Swap-tilan määrä
Vapaan swap-tilan määrä
Prosessien kokonaismäärä
Uuden 123-tavuisen muistilohkon tarkka muistiosoite

Kaikki nämä välitetään mahdollisimman suurella tarkkuudella siemeneksi satunnaislukugeneraattorille. Mikäli kone on monen käyttäjän kone (unix) ja hyökkääjä pystyy tarkkailemaan tai manipuloimaan suurta osaa näistä muuttujista on tietyn tyyppinen rajattu brute-force hyökkäys mahdollinen. Tämän riskin minimoimiseksi onkin avaimet hyvä luoda erillisessä, turvallisessa koneessa, mieluiten ei aivan heti koneen käynnistämisen jälkeen (jotta em. parametrit olisivat hieman muuttuneet oletusarvoista). Jotkut järjestelmät, kuten PGP, pyytävät käyttäjää syöttämään satunnaisia merkkejä näppäimistöltä, mutta myös tämä menetelmä on altis vastaavanlaiselle tarkkailulle.

// konstruktori; alustetaan RC4 satunnaisella avaimella

rc4::rc4()
{
    static struct {
        unsigned long       counter;
        clock_t             clock;
        struct timeval      tv;
        struct timezone     tz;
        struct sysinfo      info;
        char                *memadr;
    } randseed;

    // alustetaan satunnaissiemenluku

    randseed.counter++;
    gettimeofday(&randseed.tv, &randseed.tz);
    randseed.clock = clock();
    sysinfo( &randseed.info );
    randseed.memadr = new char[123];
    delete randseed.memadr;
    init( (unsigned char *) &randseed, sizeof(randseed) );

    // nollataan mahdolliset jäänteet muistista

    bzero((void *) &randseed, sizeof(randseed) );
}

2.4 Suurten satunnaisten alkulukujen luominen

Todennäköisyys P(n), että annettu luku n on alkuluku on alkulukuteoreeman mukaan noin 1 / ln n. Tämä voidaan suhteuttaa myös luvun n pituuteen (bitteinä) seuraavasti:

P(n) = ln 2 / len(n)

Nähdään, että todennäköisyys 512-bittisen satunnaisen luvun olemiseen alkuluku on siis noin 1/355. Mitään pelkoa ei alkulukujen loppumisesta ole, sillä esimerkiksi 512-bittisiä alkulukuja on yli 10¹⁵⁰ ( luku, jota on kaiketi mahdoton ilmaista sanallisesti ). Koska alkulukujen jakautumisessa ei ole todettu hyödyllisiä ominaisuuksia, joudutaan yksinkertaisesti kokeilemaan peräkkäisiä parittomia lukuja alkulukuja etsittäessä.

Näin pitkien lukujen alkuluvuksi todistamiseen ei ole löydetty riittävän nopeita algoritmeja jos luvuilla ei ole mitään erikoisominaisuuksia. Adleman on esittänyt yleistettyyn Riemannin hypoteesiin pohjaavan menetelmän, jolla voidaan todistaa (olettaen em. hypoteesi pitää paikkansa) kohtuullisen suuria lukuja. Mersennen lukujen todistamiseen on olemassa tehokas ns. Lucas-Lehmer-testi, jonka ansiosta suurimmat tunnetut alkuluvut ovat viimeiset sata vuotta ollet Mersennen lukuja (eli tyyppiä 2^a-1, binäärimuodossa kaikki bitit ykkösiä). [KNU81, ss. 380, 391-392]

Sen sijaan on olemassa joukko tehokkaita propabilistisiä testausmenetelmiä, joilla voidaan päätyä tähtitieteellisiin todennäköisyyksiin tietyn yleisen luvun primaliteetistä tai todistaa luvun olevan ei-alkuluku. Tälläisiä menetelmiä ovat esimerkiksi:

Solovay-Strassen, 1974 [DEN82, s. 106-107]
Rabin-Miller, 1977 [COR90, ss. 839-844] [KNU81, ss. 379-380]

Esitän seuraavassa käyttämäni (Knuth-variantin) Rabin-Miller - menetelmästä:

//  testaa, onko annettu luku (todennäköisesti) alkuluku

int prob_primetest (kbn *n)
{
    static kbn q, y, one;
    int j, k;

    one = 1;
    j = 0;

    //                                           k
    // (p0) hajoitetaan n luvuiksi (k, q) s.e.  2 q + 1 = n, q mod 2 = 1
    for(k=1; !(n->testbit(k)); k++);
    q = *n >> k;

    y = rc4rand( n );                   // y satunnaisluku välillä 0..n-1

    //                    q
    // (p2) j <- 0, y <- y  mod n

    y = modexp( y, q, *n );

    // jos y = 1, luku saattaa olla alkuluku

    if ( y == one )
        return 1;
    do
    {
        // jos y = n-1, luku saattaa olla alkuluku
        if ( y == (*n-one) )
            return 1;
        //                  2
        // asetetaan  y <- y  mod n
        y = y.sqr() % *n;

        // y = 1, luku EI ole alkuluku
        if ( y == one )
            return 0;
        j++;

    } while ( j < k );

    return 0;
}

Rabin-Miller -menetelmä ei siis ikinä erehdy väittämään alkulukua ei-alkuluvuksi, mutta todennäköisyydellä P=0.25 se saattaa väittää ei-alkulukua alkuluvuksi. Testi erehtyminen ei ole kuitenkaan riippuvainen luvusta n, vaan satunnaissiemenestä y. Tämän takia on mahdollista testata alkulukukandinaatti uudestaan n kertaa ja näin päästä varmuuteen P=0.25ⁿ. Seuraavaksi esitettävä aliohjelma satunnaisten alkulukujen tuottamiseen tekee 25 testiä, ja näin ollen sen erehtymistodennäköisyys on astronomisen pieni: P < 8.9 * 10^-16.

//  tuottaa satunnaisen alkuluvun, jossa bits bittiä                                 

kbn& random_prime (int bits)
{
    static kbn n;
    int i, primefound;
   
    // luodaan aloituspiste, jonka 2 ylintä bittiä ja alin on päällä
    // (luku on pariton)

    n = 0;
    n.setbit( bits-1, 1 );
    n = rc4rand( &n );    
    n.setbit( bits-1, 1 );
    n.setbit( bits-2, 1 );
    n.setbit( 0, 1 );   
     
    do {
        ++n; ++n;                           // siirrytään seuraavaan parittomaan lukuun
        primefound = 1;
       
        for(i=0; i<25 && primefound; i++)   // testataan 25 kertaa
        {
            primefound = prob_primetest(&n);
         
            // PGP-mäinen edistymisindikaattori                        
            cout << (primefound ? '*' : '.') << flush;
        }            
    } while (!primefound);
    cout << " prime!" << endl;

    // jos 25 testin mukaan n on alkuluku, palautetaan se

    return n;
}

3. RSA-järjestelmän toiminta

RSA-Järjestelmä on ns. julkisen avaimen (public key) järjestelmä. Tämä tarkoittaa sitä, että on olemassa kaksi toisistaan riippumatonta avainta (e, n) ja (d, n). Salaista avainta käytetään viestin purkamiseen tai digitaalisten allekirjoitusten luomiseen. Julkisella avaimella voidaan salata viesti tai tarkistaa allekirjoitus.

3.1 Julkisen ja salaisen avaimen luominen

Avainten generointiin tarvitaan kaksi satunnaisesti valittua suurta (vaikkapa 512-bittistä) alkulukua p ja q.

(funktiosta rsa_keygen)

    p = random_prime( bits / 2 );  
    q = random_prime( bits / 2 );

fii(n) on niiden positiivisten lukujen määrä, jotka eivät ole suurempia kuin n ja ovat n:n kanssa suhteellisia alkulukuja. Koska kaikki n:ää pienemmät luvut paitsi p:n ja q:n monikerrat ovat n:n kanssa suhteellisia alkulukuja, voidaan kirjoittaa:

fii(n) = (p-1)(q-1)

Lisäksi on valittava julkinen eksponentti e, joka on fii(n):n kanssa suhteellinen alkuluku eli syt(e, fii(n)) = 1. e on hyvä valita luvuksi, jossa on mahdollisimman vähän 1-bittejä, jotta modulaarieksponentaatio sujuu nopeasti. Yleisesti käytettyjä lukuja ovat 3, 17, ja 65537, joissa kussakin on 2 bittiä päällä. Näillä luvuilla modulaarieksponentaatio sujuu siis 2 kertolaskulla ja 1, 4 ja 16 neliöinnillä. Itse aloitan luvusta 17 ja etsin sen jälkeen parillisia e:n arvoja:

    // tuotetaan julkinen eksponentti e >= 17, jolle syt(e, phi(n)) = 1   

    e = 17;
    while ( gcd( e, phi ) != one )
        { ++e; ++e; }

Fii:n ja e:n avulla lasketaan salainen eksponentti e, jolle pätee:

e*d mod fii(n) = 1

Eli koodina:

    // tuotetaan salainen eksponentti d, jolle  ed mod phi = 1

    d = inverse( e, phi );

[DEN82, ss. 104-109] [COR90, ss. 831-837] [SCH96, ss. 466-470] [SAL90, ss. 125-134]

3.2 RSA:n perustoiminnot

Salaus- ja purkuoperaatiot ovat periaatteessa seuraavat:

Salaus:

C = M ^e mod n

Purku:

M = C ^d mod n

Tällöin M on viesti (käytännössä luku 2 .. n-2) joka halutaan salata, ja C on vastaava salattu viesti.

Koska modulaarieksponentaatiot ovat toistensa käänteisoperaatioita, voidaan näitä käyttää digitaalisten allekirjoitusten luomiseen. Olkoon M viesti, joka halutaan allekirjoittaa, ja S vastaava digitaalinen allekirjoitus. Kuten aiemminkin (e, n) on julkinen avain ja (d, n) on salainen avain.

Allekirjoituksen luominen:

S = M ^d mod n

Allekirjoituksen tarkistus:

S ^e mod n = M ?

Näiden perusoperaatioiden avulla voidaan toteuttaa joukko mitä erilaisimpia protokollia, mm. erilaisia salaisuuksien vaihdon menetelmiä. [DEN82, ss. 104-109] [COR90, ss. 831-837] [SCH96, ss. 466-470] [SAL90, ss. 125-134]

3.3 Hybridi-RSA

Käytännössä edellä esitettyssä yksinkertaistetussa mallissa on lukuisia ongelmia:

Viestit voivat olla pidempiä kuin n. Jos viesti jaetaan moneen n:ää lyhyempään lohkoon, mistä tiedetään saapuiko koko viesti perille ?
Modulaarieksponentaatio on varsin hidas operaatio. Jos lohkoja on monta, megatavujen kokoisen salatun tiedoston purkamiseen kuluu päiviä.
Miten voidaan varmistua siitä, että käsittämätöntä kohinaa sisältävä viesti on aito ?

Yleinen ratkaisu näihin ongelmiin on generoida ja salata RSA:lla kertakäyttöinen symmetrinen avain. Itse viestin salaamiseen käytetään sitten nopeaa symmetristä algoritmia tällä avaimella. Lisäksi alkuperäisestä viestistä lasketaan "tarkistussumma" (joka luonnollisestikaan ei ole summa, vaan kryptografisesti varma hash-funktio) joka myöskin salataan RSA:lla samalla kertaa kuin satunnainen avainkin.

Vastaanottavassa päässä:

Puretaan RSA-lohko salaisella RSA-avaimella.
Puretusta RSA-lohkosta saadulla symmetrisellä avaimella puretaan itse viestiosa.
Viestiosasta lasketaan hash-funktio, jota verrataan RSA-lohkosta löytyvään. Näin voidaan varmistua siitä että koko viesti on tullut täydellisesti ja oikein perille.

Vastaavasti digitaalisia allekirjoituksia luotaessa salaisella avaimella kryptataan ainoastaa viestistä laskettu turvallinen hash. [SCH96, ss. 32-34]

Toteutuksessani käytän SHA:ta (Secure Hash Algorithm), joka on yksi harvoista standardoiduista (Yhdysvallat) turvallisista hash-funktioista. SHA tuottaa 160-bittisen hash-arvon. SHA:sta ei tunneta kryptografisia heikkouksia. [BRO95] [SCH96, ss. 442-445 (puutteellinen kuvaus)]

3.4 RSA:n turvallisuus

RSA on erittäin levinnyt ja laajalti luotettu algoritmi. RSA-järjestelmän murtaminen ei ole vaikeampaa kuin seuraavien osaprobleemien ratkaisu:

Luvun n jakaminen tekijöihin.
Lukujen fii(n) tai d laskeminen
Diskreetin logaritmin tai e-juuren laskeminen.
Hybridisuojauksessa käytetyn symmetrisen salausalgoritmin murtaminen.

On todistettavissa, että mikä tahansa algoritmi jolla voidaan löytää luvut fii(n) tai d on muunnettavissa n:n tekijöihinjako-algoritmiksi. [SAL91, ss. 143-146]

Yleisesti esiintyy käsityksiä, että tehokkain menetelmä RSA:n murtamiseksi olisi ns. raaka voima (brute-force) hyökkäys, jossa kokeillaan yksinkertaisesti eri avaimia läpi. Tämä ei pidä paikkaansa. Paras tunnettu tekijöihinjakoalgitmi ( lukukunta seula - algoritmi ) on kompleksisuudeltaan:

e ^{(1.923 + O(1)) (ln n)^1/3( ln (ln n) )^1/2}

Voidaan arvioida, että tällä algoritmilla 1024-bittisen luvun tekijöihin jakoon kuluu (toteutuksesta riippuen) noin 3 * 10⁷ mips-vuotta (vuotta tietokoneaikaa kuvitteellisella tietokoneella, joka suorittaa 1 000 000 käskyä sekunnissa. Todelliset tietokoneet ovat nopeudeltaan nykyään jopa satoja mipsejä ). [SCH96 s. 161, 255-258]

Yksikään nykyään tunnettu tekijöihinjakoalgortmi ei kuulu polynomiseen kompleksisuusluokkaan (luvun pituuden suhteen), ja epäilläänkin että tekijöihinjaon ongelma kuuluu pohjimmiltaan exponentiaaliseen joukkoon. Tätä ei kuitenkaan ole pystytty todistamaan. Alkulukujen generoinnin ja salauksen algoritmit puolestaan kuuluvat alieksponentiaaliseen kompleksisuusluokaan, joten tietokoneiden nopeutuessa voidaankin ehkä aina siirtyä suurempiin avaimen pituuksiin ilman (suhteellisen) turvallisuuden heikkenemistä.

4. Esimerkki ZenRSA:n toiminnasta

Esittelen tässä kirjoittamani RSA-Järjestelmän "ZenRSA" toimintaa. ZenRSA:n täydelliset lähdekoodit löytyvät liitteistä A, B ja C.

Tulostetaan sisäänrakennettu helppi

AcidPluto:ZenRSA>zrsa
ZenRSA 0.0 (c)1996 Markku-Juhani O. Saarinen 
Kopiointi ja levittäminen sallittu vain tekijän luvalla.

Käyttö: zrsa < toiminto >, jossa toiminto on yksi seuraavista:

 g  RSA-Avainparin luominen
 e  Tiedoston salaus julkisella avaimella
 d  Salauksen purkaminen salaisella avaimella
 s  Tiedoston digitaalinen allekirjoitus salaisella avaimella
 c  Allekirjoituksen tarkistaminen julkisella avaimlla

AcidPluto:ZenRSA>

Luodaan avainpari

AcidPluto:ZenRSA>zrsa g
Julkisen ja salaisen avaimen luominen.

Julkinen avaintiedosto :foo.pub
Salainen avaintiedosto :foo.sec
odota hetki ...........************************* prime!
.............................................................***************
********** prime!
AcidPluto:ZenRSA>cat foo.pub
ACD75493596B6450530F8A35CA51B0666AC547EC4A36167B81C31CE7E94F4BB338797B976412
C671F7781009F3CE8C0D82CC64573A9F6FDF136349D2930D56A52ADED7F5CEC3FA89F8180562
200B856953E7402AFCC91AC0ABEB51894A25C591F4378ECDE592DBDEFDB347A7A6653F2556FF
21DBE56E3A09415A64A143A3D135
11
AcidPluto:ZenRSA>cat foo.sec
ACD75493596B6450530F8A35CA51B0666AC547EC4A36167B81C31CE7E94F4BB338797B976412
C671F7781009F3CE8C0D82CC64573A9F6FDF136349D2930D56A52ADED7F5CEC3FA89F8180562
200B856953E7402AFCC91AC0ABEB51894A25C591F4378ECDE592DBDEFDB347A7A6653F2556FF
21DBE56E3A09415A64A143A3D135
1455917ABF39CF90FAB688BB08BE50FCFD809F0CBD6FC668E216F45784DC270606A4E15D1AD5
0849A4A4B697C25488F287DBCF91CAA9587498DE8127D510A0C7F18066B2FDA7DBB722DF2FC0
863645BFEBE6C0B9928956850CD108ED3446F2F7E50877B51D0F46D8ED29EF67BC6DAAB026E6
61A24AE7021248D556E8C3FCC389
AcidPluto:ZenRSA>

Kryptataan tiedosto

AcidPluto:ZenRSA>cat salakala

                 Alien/OS root password is "Jeff Goldblum" !

AcidPluto:ZenRSA>zrsa e
Tiedoston salaaminen.

Julkinen avaintiedosto :foo.pub
Salattava tiedosto     :salakala
Salattu tiedosto       :salakala.zrsa
ok!
AcidPluto:ZenRSA>cat salakala.zrsa 
+à)iïÃñK{i6¥V°¾ECH"ro½ÈJE]*PÇöÈ
                                ¡¯ïÙØ®@h
AcidPluto:ZenRSA>

Puretaan salaus

AcidPluto:ZenRSA>zrsa d
Salauksen purkamien.

Salainen avaintiedosto :foo.sec
Salattu tiedosto       :salakala.zrsa
Purettu tiedosto       :salakala.2
ok!
AcidPluto:ZenRSA>cat salakala.2

                 Alien/OS root password is "Jeff Goldblum" !

AcidPluto:ZenRSA>

Luodaan digitaalinen allekirjoitus

AcidPluto:ZenRSA>zrsa s
Tiedoston allekirjoituksen luominen.

Salainen avaintiedosto :foo.sec
Allekirjoitettava tied :salakala
Signatuuritiedosto     :salakala.sig
ok!
AcidPluto:ZenRSA>cat salakala.sig 
19EA006D37E0971E5E61128084A66D235851FF2D34810491E5582B0794F85350A1112DC387C5
9729D50889A9243BF90527EBE90DAFE4E0FBFC00737D961F3F6B5D85A88F42357A0B18D3CCF5
1B829E55491116E01CE42B1178F366F7E970F0E07DA077BF5DE8136245F84A3023DAD9E02E9B
AAAC7C022F9866FE6FE667ACEE06AcidPluto:ZenRSA>

Tarkastetaan allekirjoitus

AcidPluto:ZenRSA>zrsa c
Tiedoston allekirjoituksen tarkastaminen.

Julkinen avaintiedosto :foo.pub
Allekirjoitettu tied.  :salakala.zrsa
Signatuuritiedosto     :salakala.sig

Allekirjoitus ei täsmää!
AcidPluto:ZenRSA>zrsa c
Tiedoston allekirjoituksen tarkastaminen.

Julkinen avaintiedosto :foo.pub
Allekirjoitettu tied.  :salakala.2
Signatuuritiedosto     :salakala.sig

Allekirjoitus on ok.
AcidPluto:ZenRSA>

Lähteet

[BRO95] Ronald H. Brown, Mary L. Good, Arati Prabhakar
FIPS PUB 180-1: Secure Hash Standard
National Institute of Standards and Technology, 1995

[CER25] R. Ceder
Luvunlaskun Oppikirja (3. Painos)
Otava, 1925

[COR90] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Introduction to Algorithms
MIT Press, 1990

[DEN82] Dorothy E. R. Denning
Cryptography and Data Security
Addison-Wesley, 1982

[KNU81] Donald E. Knuth
The Art of Computer Programming: Vol 2 / Seminumerical Algorithms
(2. painos)
Addison-Wesley, 1981

[PRE92] William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery
Numerical Recipes in C
(2. painos)
Cambridge University Press, 1992

[SAL90] Arto Salomaa
Public Key Cryptography
Springer-Verlag, 1990

[SCH96] Bruce Schneier
Applied Cryptography
(2. painos)
John Wiley & Sons, 1996