You are here: TUTWiki>Tietoturva/Tutkielmat>TyoLuettelo?>2008-38

Anssi Alahuhta

Satunnaislukujen generoinnin käytäntöjä

Johdanto

Työn aiheena on tutustuminen satunnaislukujen generointiin. Generointi voidaan toteuttaa useilla erilaisilla algoritmeilla ja siemenluvuilla, joita tarkastellaan lähemmin omissa luvuissaan. Lisäksi tutustutaan näennäissatunaisuuteen ja todelliseen satunnaisuuteen sekä satunnaisuuden todentamiseen erilaisilla testeillä.

Yleistä

Satunnaisluvut toteutetaan nykyään useimmiten matemaattisten kaavojen avulla, joihin käytetään jotain siemenlukua tuomaan entropiaa. Nykyaikaisiin satunnaislukugeneraattoreihin on käytetty huomattavan paljon aikaa ja vaikuttavatkin ulkopuoliselle täysin satunnaisilta jopa näennäisen satunnaisilla siemenarvoilla. [3]

Satunnaislukujen tuottamiseen käytettävät generaattorit jakaantuvat kolmeen eri luokkaan: Todellisiin satunnaislukugeneraattoreihin, näennäisiin satunnaislukugeneraattoreihin sekä kryptografisesti turvallisiin näennäislukugeneraattoreihin.

Todelliset satunnaislukugeneraattorit mittaavat jotain tiettyä fyysistä ilmiötä jonka perusteella bittivirta luodaan. Yksi todella hyvä ilmiö satunnaislukujen tuottamiseen on jokin radioaktiivinen lähde. Radioaktiivisen aineen hajoaminen on täysin ennustamatonta, jonka lisäksi se on helposti mitattavissa ja siirrettävissä tietokoneelle. [3]

Näennäisen satunnaiset generaattorit toteutetaan jonkin algoritmin avulla siten, että käytetään jotain siemenlukua alustamaan algoritmi. Alustuksen jälkeen generaattori tuottaa samalla siemenluvulla aina saman sarjan arvoja. [4]

Kryptografisesti turvalliset näennäiset satunnaislukugeneraattorit ovat vastaavia kuin normaalit näennäisten satunnaislukujen generaattorit, mutta niille asetetaan myös muita vaatimuksia joita käsitellään enemmän näennäisten satunnaislukujen luvussa.

Näennäiset satunnaisluvut

Näennäiset satunnaisluvut tuotetaan siis generaattoreilla, jotka ottavat syötteenään jonkin siemenarvon josta lasketaan aina seuraava arvo ja saadaan näin generoitua haluttu määrä satunnaislukuja. Koska algoritmi on aina sama, saadaan tietyllä siemenarvolla aina sama satunnaislukujono. Generaattorit ovat siis deterministisiä.

Satunnaislukugeneraattoreilla on aina sisäinen tila. Generaattorin ottama siemenluku on siis mielivaltainen alkutila, jonka perusteella kaikki seuraavat arvot lasketaan. Generaattorin tilan koko ilmoitetaan yleensä biteissä. Bittimäärän perusteella saadaan tuotetun satunnaislukusekvenssin maksimipituus siten, että sekvenssin ehdoton maksimipituus on 2n arvoa, missä n on kyseisen generaattorin tilan bittimäärä. Todellinen arvo kuitenkin vaihtelee paljon sen mukaan millainen generaattori on kyseessä. [4]

Kun generaattorin tilat on käyty läpi, alkaa sekvenssi uudelleen eli generaattorit ovat jaksollisia. Bittejä lisäämällä on kuitenkin mahdollista kasvattaa eri tilojen määrää niin suureksi, että ne riittävät käytännössä kaikkien sovellusten tarpeisiin.

Kryptografisesti turvalliset satunnaislukugeneraattorit

Kryptografisesti turvalliset satunnaislukugeneraattorit ovat vastaavia ei-turvallisten kanssa. Vaatimuksena generaattorille on kuitenkin tässä tapauksessa kaksi asiaa:
  • Generaattorin tulee toteuttaa seuraavan bitin testin. Tämä testi tarkoittaa sitä, että vaikka tunnettaisiin sekvenssistä aiemmin saadut tulokset, ei ole mahdollista ennustaa seuraavaa bittiä polynomiaalisessa ajassa. [5]
  • Generaattorin tulisi kestää tilanne, jossa sen tila on kokonaisuudessaan tai osittain paljastunut siten, että paljastusta edeltäviä tiloja ei pystytä selvittämään. [5]

Näennäisten satunnaislukugeneraattorien hyödyt ja haitat

Näennäiset satunnaisluvut ovat jossain tapauksissa huomattavasti käytännöllisempiä kuin todelliset satunnaisluvut. Suurin hyöty näennäisissä satunnaisluvuissa on niiden tuottamisen tehokkuus. Tehokkuudesta saadaan ilmiselvää hyötyä, mikäli ohjelma vaatii paljon satunnaislukuja pienessä ajassa, mutta niiden todellisella satunnaisuudella ei ole väliä. Tälläisiä ohjelmia ovat esimerkiksi useimmat pelit ja simulaatiot.

Toinen hyöty näennäisestä satunnaisuudesta on generoinnin deterministisyys. Deterministisyyden avulla on helppoa toteuttaa vastaava sarja lukuja uudestaan, mikäli tarvetta on. [3]

Näennäisessä satunnaisuudessa on myös ongelmansa. Useat käytetyt satunnaislukugeneraattorit epäonnistuvat tilastollisissa testeissä esimerkiksi epätasaisen jakauman tai tietyillä siemenluvuilla oletettua lyhyemmän jakson vuoksi.

Tietoturvallisuuden näkökulmasta myös generoinnin deterministisyys on ongelmallista jopa kryptografisesti turvallisten satunnaislukugeneraattoreiden tapauksessa, mikäli hyökkääjä saa siemenluvut tietoonsa.

Käytetyt siemenluvut

Näennäisten satunnaislukugeneraattoreiden tapauksessa käytetään usein jotain tietokoneesta saatavaa tietoa siemenlukuna. Näitä voivat olla esimerkiksi tietokoneen kello, hiiren liikkeet, näppäimistön painallukset tai näiden yhdistelmät. On kuitenkin huomioitavaa, että kyseiset tietokoneesta saatavat tiedot ovat helposti arvattavissa, jolloin koko sekvenssi voidaan laskea läpi.

Näiden lisäksi on mahdollista käyttää lähteenä jotain fyysistä ilmiötä, jolloin siemenluvusta ei voida olettaa mitään. Ilmiöiden mittaaminen ja käsittely on kuitenkin huomattavasti hitaampaa.

Erilaiset satunnaislukugeneraattorit

Linear congruential generator

Linear congruential generator, eli lyhyesti LCG käyttää yhtä vanhimmista ja tunnetuimmista näennäissatunnaisten lukujen generaattoria. [6]

Generaattori on yksinkertainen toteuttaa ja hyvin nopea. Alla on esitettynä LCG:n matemaattinen algoritmi. (Huom! Wikiteknisistä syistä on käytetty suurempi tai yhtäsuuri-merkkinä <= ja vastaavasti pienempi tai yhtäsuuri >=)

Xn+1 = (aXn + c) mod m, missä
Xn on satunnaislukusekvenssin n:s arvos ja
0 < m, jossa m on modulona käytettävä arvo
0 < a < m, jossa a on edellisen satunnaisluvun kerroin
0 <= c < m, jossa c on kertomaan lisättävä arvo
0 <= X0 < m, jossa X0 on siemenluku
Edellämainitut a, m, c ja X0 ovat vakioita kokonaislukuarvoja, jotka määrittelevät generaattorin. [6]

LCG:n jakso on enintään m:n mittainen ja joillakin arvoilla hyvin paljon lyhyempi. LCG:llä on täysi m:n mittainen jakso vain siinä tapauksessa, mikäli seuraavat ehdot täyttyvät:
  • c:n ja m:n suurin yhteinen tekijä on 1
  • a-1 on jaettavissa kaikilla m:n alkutekijöillä
  • a-1 on 4:n kertoma, mikäli m:kin on.
LCG on kohtalaisen hyvä satunnaislukugeneraattori, mutta huomattavan riippuvainen c:n, m:n ja a:n valinnasta[6]. Näiden valintaan liittyvät asiat tulisikin huomioida generaattorin toteutuksessa.

LCG:n hyödyt ja haitat

LCG ei sovellu sovelluksiin, joissa on laadukas satunnaisuus on tärkeää, eikä täten ole myöskään kryptografisesti turvallinen, koska se ei toteuta seuraavan bitin testiä. Generaattori on kuitenkin todella tehokas ja vaatii vähän muistia, joten esimerkiksi sulautettujen järjestelmien tapauksessa LCG voi olla varteenotettava vaihtoehto. [6]

LCG:ssä on myös ongelma, mikäli m on asetettu kahden potenssiksi. Tällöin sekvenssin vähiten merkitsevien bittien jaksot ovat huomattavasti lyhyempiä kuin koko sekvenssin. [6]

Mikäli muistista ja suoritintehosta ei ole pulaa, on järkevää valita jokin muu satunnaislukugeneraattori kuin LCG.

Blum Blum Shub

Blum Blum Shub, lyhyesti B.B.S. on vuonna 1986 esitetty satunnaislukugeneraattori, joiden kehittäjinä ovat toimineet Lenore Blum, Manuel Blum ja Michael Shub [7]. Generaattori on kryptografisesti turvallinen.

Algoritmi

Generaattorin algoritmi on toteutukseltaan yksinkertainen:
Xn+1 = (Xn)2 mod M, jossa X on sekvenssin jokin luku ja M=pq. M:n kertoimet p ja q ovat suuria alkulukuja. Tavallisesti algoritmin ulostulona on Xn:n bittipariteetti tai yksi tai useampia vähiten merkitseviä bittejä Xn:stä. [7]

Alkuluvut p ja q tulisi molemmat olla kongruentteja kolmen kanssa modulo neljä [7]. Toisinsanoen tulisi päteä p-3 mod 4 = 0 ja q-3 mod 4 = 0. Lisäksi p-1:n ja q-1:n suurin yhteinen tekijä tulisi olla mahdollisimman pieni, jotta generaattorin jakson pituus olisi mahdollisimman pitkä [7].

B.B.S.-generaattorilla on myös mahdollista laskea mikä tahansa sekvenssin arvo Xi suoraan:
Xi = (X02^i mod(p-1)(q-1)) mod M. [7]

Turvallisuus

B.B.S.-generaattori ei sovellu lainkaan esimerkiksi simulointiin, koska se on todella hidas verrattuna myös moniin muihin kryptografisesti turvallisiin generaattoreihin. Algoritmin turvallisuus perustuu kokonaislukujen tekijöihin jaon laskennalliseen vaikeuteen, samalla tavoin kuin esimerkiksi RSA. [7] Ongelmaksi tietoturvallisuuden näkökulmasta kuitenkin muodostuu käytetyt alkuluvut, koska mikäli hyökkääjä saa käsiinsä käytetyt alkuluvut, voidaan arvot selvittää.

Mersenne twister

Mersenne twister on vuonna 1997 kehitetty generaattori näennäisten satunnaislukujen generointiin. Generaattorin nimi tulee siitä, että generaattorissa käytetään Mersennen alkulukua, eli mitä tahansa alkulukua joka saadaan kaavalla 2n-1. Generaattori tuottaa nopeasti satunnaislukuja ja satunnaisluvut ovat hyvin laadukkaita, koska algoritmi on toteutettu nimenomaan paikkaamaan aikaisempien generaattoreiden kanssa esiintyneitä ongelmia. [8]

Mersenne twister ei sovellu lainkaan kryptografiaan, koska tutkimalla tarpeeksi iteraatioita voidaan ennustaa kaikki tulevat iteraatiot. Mersenne twister on kuitenkin tietyissä sovelluksissa paljon käytetty sen nopeuden ja laadukkaiden satunnaislukujen vuoksi. Myös kirjaston vapaa saatavuus ja siirrettävyys on edesauttanut algoritmin yleistymisessä. [8]

Mersenne twisterissä on myös huomattavan pitkät jaksot, joten satunnaislukuja voidaan tuottaa varmasti jokaisen sovelluksen vaatima määrä. Yleisimmän variaation eli MT19937:n jakson maksimipituus on 219937 -1, joten tilan arvojen loppumisesta ei useimmissa sovelluksissa ole ongelmaa [8].

Todelliset satunnaisluvut

Erona näennäisiin satunnaislukuihin, todellisissa satunnaisluvuissa luvut tuotetaan jostain fyysisestä lähteestä. Satunnaislukujen tuottaminen tapahtuu siis samalla tavalla, kuin tietyissä tilanteissa näennäisten satunnaislukugeneraattoreiden siemenluvut tuotetaan. Näiden lukujen tuottaminen on kuitenkin todella paljon hitaampaa kuin näennäisten satunnaislukujen tapauksessa. Tämä johtuu siitä syystä, että fyysisen ilmiön mittaamiseen kuluu huomattavasti aikaa ja jokainen luku täytyy erikseen generoida kyseisestä lähteestä. Myöskin lähteiden epädeterministisyys aiheuttaa sen, että joihinkin sovellusalueisiin todelliset satunnaisluvut eivät sovi yhtä hyvin kuin näennäiset.

Tietoturvallisuuden näkökulmasta todelliset satunnaisluvut ovat kuitenkin huomattavasti parempia nimenomaan näiden epädeterministisyyden vuoksi. Tietoturvallisuudessa ei myöskään ole tarvetta tuottaa satunnaislukuja suuria määriä nopealla tahdilla, jolloin lukujen tuottamisen tehokkuus ei ole ongelma.

Satunnaisuuden todentaminen testeillä

Satunnaisuuden todentaminen tilastollisilla testeillä on todella tärkeää sekä näennäissatunnaisilla- että satunnaisilla generaattoreilla. Näennäissatunnaisilla generaattoreilla testien syy on selvä: Generaattorin testaus verrattuna todellisiin satunnaislukujonoihin. Myös todellisten satunnaislukujen tapauksessa testit ovat tärkeitä. Esimerkiksi luettaessa satunnaislukuja jostain fyysisestä lähteestä, voivat saadut sekvenssit poiketa todellisesta satunnaisuudesta tilastojen valossa. Tilastojen avulla voidaan muokata lähteen lukemista siten, että poikkeavuutta ei enää esiinny.

National Institute of Standards and Technology (NIST) on kehittänyt todella kattavat tilastolliset testit todellisten sekä näennäisten satunnaislukugeneraattorien testaamiseen. Testejä on yhteensä 16 kappaletta ja niiden avulla saadaan testattua generaattoreita todella kattavasti. [2]

Alla on esitelty muutama testipatteriston yksinkertaisempi testi:
  • Taajuustesti - Testissä tarkastellaan kokonaisen sekvenssin ykkösten ja nollien määrää selvittämään kuinka lähellä jakauma on todellisia satunnaisia lukujonoja. Todellisessa satunnaislukujonossa määrät ovat melko lähellä toisiaan.
  • Sarjatesti - Testissä keskitytään tutkimaan kuinka pitkiä ykkösen ja nollan sarjoja sekvenssissä esiintyy. Näitä verrataan jälleen odotettuihin todellisen satunnaisjonon arvoihin ja selvitetään onko vaihtelu liian nopeaa tai liian hidasta todelliseen satunnaislukujonoon nähden.
  • Jaksollinen malliin sopimistesti - Testin lähtökohtana on löytää ennalta määriteltyjä sarjamalleja sekvenssistä. Testin tarkoituksena on hylätä sekvenssit, joissa esiintyy liikaa tai liian vähän tietyn mittaisia ykkösiä sisältäviä sarjoja.
  • Kumulatiivinen summa-testi - Testi keskittyy tutkimaan sekvenssin bittejä siten, että jokaisesta ykkösestä tulokseen lisätään yksi ja jokaisesta nollasta tuloksesta vähennetään yksi. Todellisella satunnaisjonolla arvon tulisi olla melko lähellä nollaa, joten jos eroa on paljon, voidaan sekvenssi hylätä. Tästä testistä suoritetaan myös variaatioita, joissa käydään vain osa sekvenssistä läpi, jolloin voidaan testata sekvenssin eri osia.
[2]

Testipatteristo sisältää esiteltyjen lisäksi muita testejä. Useat testeistä ovat huomattavasti monimutkaisempia kuin yllä esitetyt ja sisältäväkin matriiseja, fourier-muunnoksia ja muita matemaattisia menetelmiä sekvenssin tutkimiseen.

Päätelmät

Näennäisten ja todellisten satunnaislukujen valinnassa on tärkeää huomioida sovelluksen tarpeet. Näennäisten satunnaislukujen tapauksessa ehdottomia hyötyjä ovat lukujen generoinnin tehokkuus ja sekvenssien toistettavuus. Toistettavuus on kuitenkin ongelmallisin ominaisuus näennäisillä satunnaislukugeneraattoreilla tietoturvallisuuden näkökulmasta, mikäli lähtötila saadaan selville.

Todelliset satunnaisluvut taas ovat huomattavan raskaita generoida, joten niiden käyttö tietyillä sovellusalueilla ei ole järkevää. Tietoturvallisuuden näkökulmasta todelliset satunnaisluvut ovat kuitenkin usein järkevin tapa, koska generoinnin tehokkuudella ei ole useimmissa tapauksissa merkitystä. Mikäli sovellus on kuitenkin kriittinen sekä tehokkuuden että tietoturvallisuuden näkökulmasta, tulee valita joko kryptografisesti turvallinen satunnaislukugeneraattori tai todellinen satunnaislukugeneraattori tilanteesta riippuen.

Generaattoreiden ja todellisten satunnaislukulähteiden testaamiseen liittyy myös paljon erilaisia tilastollisia testejä. Kovin yksinkertaisella testipatterilla ei vielä satunnaisuutta voida todistaa vaan todentamiseen tarvitaan paljon monimutkaisia testejä.

Lähteet

  • [1] Salzburgin yliopiston matematiikan laitoksen satunnaislukuihin keskittyvä sivusto [http://random.mat.sbg.ac.at/] (viitattu xx.xx.2008)
  • [2] National Institute of Standards and Technology - Computer Security Divisionin satunnaislukuja käsittelevä sivusto [http://csrc.nist.gov/groups/ST/toolkit/rng/index.html] (viitattu xx.xx.2008)
  • [3] random.org todellisten satunnaislukujen generointiin keskittyvä sivusto [http://www.random.org/] (viitattu 13.10.2008)
  • [4] Wikipedian näennäisiä satunnaislukugeneraattoreita käsittelevä sivu [http://en.wikipedia.org/wiki/Pseudorandom_number_generator] (viitattu 13.10.2008)
  • [5] Wikipedian kryptografisesti turvallisia näennäisiä satunnaislukugeneraattoreita käsittelevä sivu [http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator] (viitattu 13.10.2008)
  • [6] Wikipedian Linear Congruential Generaattoria käsittelevä sivu [http://en.wikipedia.org/wiki/Linear_congruential_generator] (viitattu 27.10.2008)
  • [7] Wikipedian Blum Blum Shub-generaattoria käsittelevä sivu [http://en.wikipedia.org/wiki/Blum_Blum_Shub] (viitattu 28.10.2008)
  • [8] Wikipedian Mersenne Twister-generaattoria käsittelevä sivu [http://en.wikipedia.org/wiki/Mersenne_twister] (viitattu 28.10.2008)
Print version |  PDF  | History: r3 < r2 < r1 | 
Topic revision: r3 - 05 Oct 2009 - 20:23:16 - NiroAAhman?
 

TUTWiki

Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TUTWiki? Send feedback