Satunnaisluvuista (2-A)

Satunnaisluku tarkoittaa sellaista lukua, joka valitaan annetusta lukujoukosta siten, että jokaisella luvulla on sama todennäköisyys tulla valituksi. Salasanoista tutulla? entropiakäsitteellä asian voisi ilmaista niin, että satunnaisluvulla on maksmimaalinen entropia (esim. satunnaisluvulla väliltä 0..999 se on hitusen alle 10 bittiä).

Satunnaislukuja tarvitaan avainten generoinnissa (sekä symmetrinen että julkinen), autentikointihaasteissa ja viestin tuoreuden osoitukseen (viimeksi vastaanotetun satunnaisluvun, ns. 'nonce'n palauttaminen kryptattuna).

Satunnaislukuja tuotetaan generaattoreilla, jollaiseksi riittää satunnaisbittijonon tuottava algoritmi tai laite. Yleisiä vaatimuksia tuotetulle bittijonolle: bitit ovat toisistaan riippumattomia ja jakauma on tasainen. Käytännössä tämä todetaan tilastollisilla testeillä, jotka jättävät aina tietyn epävarmuuden asiasta. Tuotetusta bittijonosta lasketaan tunnuslukuja, joita verrataan teoreettisesti johdettuihin täysin satunnaisen bittijonon vastaaviin lukuihin (Khin neliön testillä). Vertailut koskevat esim. erilaisten k bitin osajonojen frekvenssejä, erimittaisten juoksujen (runs) eli maksimaalisten peräkkäisistä ykkösistä (tai nollista) koostuvien osajonojen frekvenssejä ja autokorrelaatiota (tietyllä bittimäärällä siirretyn jonon samanlaisuutta alkuperäisen kanssa).

Yleisesti käytetty ja sopivilla parametreilla (a, b ja m) tilastollisesti hyvä menetelmä satunnaislukujen generointiin on modulaarinen iteraatio: x(n+1) = a*x(n) + b modulo m, missä x(0)=siemenluku (satunnainen). Esimerkiksi m=231-1, a = 75 ja b=0. Ongelmana kryptografian kannalta on se, että muutamasta luvusta voidaan päätellä koko jono.

Kryptografisessa käytössä satunnaisluvuilta vaaditaan lisäksi ennustamattomuutta. Satunnaisten bittien generaattorit (BG) jaotellaan seuraavasti:

  • (todelliset) satunnaiset BG:t: perustuvat johonkin luonnossa esiintyvään satunnaiseen ilmiöön kuten radioaktiiviseen hajoamiseen, diodin tai vastuksen lämpökohinaan, värähtelijän taajuusvaihteluihin, kondensaattorin varautumiseen annetussa ajassa, ilmapyörteiden aiheuttamiin aikaeroihin tietokoneen levyn luvussa, mikrofonin tai videon signaaliin. Myös ohjelmistolla voidaan yrittää tavoitella luonnollista satunnaisuutta: systeemikello on suosittu lähde, samoin ajanotto näppäinten painalluksista tai hiiren liikkeistä.
  • näennäiset BG:t: ovat algoritmeja jotka kasvattavat jonkin todella satunnaisen jonon (siemenen) satunnaisen näköiseksi pitemmäksi jonoksi. (Esim. em. modulaarinen algoritmi)
  • kryptografisesti turvalliset näennäiset BG:t (cryptographically secure pseudorandom bit generators): Sellainen näennäinen BG, joka toteuttaa "seuraavan bitin testin": Ei ole polynomiaalista algoritmia, joka aiemmista biteistä ennustaisi seuraavan bitin todennäköisyydellä, joka poikkeaa merkittävästi puolikkaasta.

Esimerkki "CSPRBG":stä on BBS-generaattori (keksijöinä Blum, Blum ja Shub). Oletuksena turvallisuudelle on tekijöihinjakoprobleeman vaikeus.

  1. generoi kaksi suurta alkulukua p ja q ja laske n=p*q.
  2. valitse satunnaisesti sellainen luku s väliltä [1,n-1], ettei sillä ole yhteisiä tekijöitä n:n kanssa. Laske x0 = s2 mod n.
  3. toista kun i=1,...,m: xi = xi-12 mod n. tulosta xi:n vähiten merkitsevä bitti.

Algoritmia voidaan tehostaa tulostamalla useampia bittejä kerralla, mutta on selvittämättä, montako voidaan ottaa niin, että seuraavan bitin testi vielä läpäistään.

Käytännössä tyydytään vähempään kuin todistettuun turvallisuuteen. Esimerkiksi muutamat standardit käyttävät avainten generointiin algoritmeja, joiden on vain "todettu" toimivan turvallisesti. Erityisesti satunnaisbittien generointiin käytetään muita kryptografisia primitiivejä, kuten salausalgoritmeja sekä (yksisuuntaisia) tiivistealgoritmeja.

Monet laitteet tekevät käynnistyessään tilastollisia itsetestejä, joilla varmistetaan, ettei kovin suurta epäsatunnaisuutta esiinny. Esimerkiksi kryptomoduulien standardin FIPS 140-1? määrittelemä (§4.11.1) Power-Up Test vaatii 20000 bittiä ja niille neljä testiä: Monobit, Poker, Runs, Long Runs. Monobit edellyttää, että ykkösbittien lukumäärä on välillä 9655--10345. Runs puolestaan asettaa lukumäärärajat juoksuille, joiden pituudet ovat 1..5 ja yli 5 (ja erikseen 1- ja 0-juoksut). Long Runs kieltää yli 33:n mittaiset juoksut. Poker jakaa bitit jonoksi heksa-lukuja ja asettaa rajat niiden lukumäärien neliösummalle.

-- JukkaKoskinen?

SivuTiedotLaajennettu edit

Vaativuus Perus
Valmius Valmisteilla
Tyyppi Ydin
Luokitus Uhkat
Mitä Luottamuksellisuus
Miltä Ihmisetön uhka
Missä Organisaatio
Kuka Tite-ammattilainen
Milloin Ennakolta
Miksi Hyvä tapa
Print version |  PDF  | History: r2 < r1 | 
Topic revision: r2 - 26 Sep 2010 - 11:10:35 - MarkoHelenius
 

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