Bloom-Micali-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 15. tammikuuta 2017 tarkistetusta versiosta . tarkastukset vaativat 10 muokkausta .

Blum - Micali - algoritmi on kryptografisesti turvallinen algoritmi näennäissatunnaisten sekvenssien luomiseen Random siemen avulla . Bloom ja Micali hahmottelivat algoritmin taustalla olevat ideat vuonna 1984. Algoritmi kehitettiin Adi Shamirin vuotta aiemmin ehdottaman Shamir-generaattorialgoritmin perusteella [1] . Algoritmi eroaa edeltäjästään tiukemmilla vaatimuksilla tulossekvenssin laskennan monimutkaisuudesta. Toisin kuin Shamir-generaattori, tämän algoritmin tulos on bittejä, ei numeroita.

Algoritmin pääidea

Harkitse yksinkertaisinta ideaa pseudosatunnaislukugeneraattorin rakentamisesta: meille annetaan alkusatunnaissekvenssi (siemen) ja valitaan jokin salausalgoritmi. Lisäksi jokaisessa iteraatiossa, salaamalla nykyinen tila ja valitsemalla tuloksesta bittijoukon, voimme saada numerosarjan, joka näyttää melko satunnaiselta.

Bloom-Micali-algoritmi käyttää täsmälleen tätä prosessia käyttämällä "hardcore-bittejä" (kovaydinbitti, kovaydinpredikaatti ).

Algoritmia keksiessään Bloom ja Micali esittivät kolme vaatimusta tulossekvenssille:

Lähtöbittien lukumäärän tulee riippua polynomiaalisesti raepituudesta (algoritmin äärellisen syklin pituuden vuoksi). $b_{i}$
Bittien saamisen tulee olla laskennallisesti yksinkertaista - toimintojen määrää ylhäältäpäin tulee rajoittaa jollakin raepituuden polynomifunktiolla. $b_{i}$
Ryttien tulee olla arvaamattomia. Tunnetulla generaattorilla ja tunnetuilla sekvenssin ensimmäisillä biteillä , mutta siementä tietämättä, seuraavan bitin määrittäminen muulla kuin 50 %:n todennäköisyydellä pitäisi olla laskennallisesti vaikea tehtävä. Toisin sanoen tällaista laskentaa ei pitäisi suorittaa operaatioiden raepituuden polynomissa. $b_{i}$ $k$ $b_1, ..., b_k$ $b_{k+1}$

Käsite hardcore beat

"Vakava lyönti" (predikaatti) B funktiolle f on jokin funktio, joka:

B:n lähtöarvo on 1 bitti.
Sille ei ole olemassa sellaista polynomi-aika-algoritmia ( eli BPP - Bounded-error probabilistic polynomial) -algoritmia, joka voisi oikein osoittaa B (x):n tunnetusta f (x):stä muulla todennäköisyydellä kuin 1/2.

Blum-Micalin lause

$S$ — Seed — funktion argumentin pituus . Hän on pituus . - muunnos arvosta muotoon , ja - arvosta arvoon {0,1} - hankala bitti kohteelle . ; ovat lopullisen generoidun sekvenssin bittejä. ; . -pseudo-satunnaisuus - sen sekvenssin ominaisuus, jolle se suoritetaan - kompleksibitti - funktion ominaisuus , jolle , missä on kryptanalyytikon ajassa löytämä algoritmi .
$n$ $f$ $S$
$f$ $\{0,1\}^n$ $\{0,1\}^n$ $B$ $\{0,1\}^n$ $f$
$h_i = B(S_i)$ $Hei}$
$S_i = f(S_{i-1})$ $S_0 = S$
$(t,\varepsilon)$ $|P(A(B_1..B_i) == B_i+1) - 1/2| < \varepsilon$
$(t,\varepsilon)$ $A$ $|P(A(B_1..B_i) == 0) - 1/2| < \varepsilon$
$A()$ $t$

Määritellään se seuraavaksi prosessiksi: Otetaan jokin satunnainen sarja (siemen). Jos on -kompleksibitti , niin se on -pseudosatunnaislukugeneraattori. - funktion laskenta-aika . Lause todistetaan ristiriidalla; Oletetaan, että on olemassa algoritmi, jonka avulla voit löytää elementin, kun tiedät edellisen [2] . $G_{BM}$ $B$ $(t,\varepsilon)$ $G_{BM}$ $(t- m*TIME(f), \varepsilon*m)$ $AIKA (f)$ $f$

$i + 1$ $i$

Sovellus

Tähän algoritmiin perustuvia generaattoreita käytetään sekä yksityisen että julkisen avaimen järjestelmissä.

Yksityisen avaimen järjestelmissä

Kaksi kumppania, jotka ovat vaihtaneet turvallisesti salaisen alkusekvenssin, saavat yhteisen satunnaisjonon, jonka pituus on monta kertaa suurempi kuin alkuperäinen sekvenssi.

Julkisen avaimen järjestelmissä (epäsymmetrinen salaus)

Goldwasser ja Micali osoittivat [3] , että olettaen, että neliötähteiden modulo-yhdistelmälukujen määrittäminen on laskennallisesti vaikea tehtävä, on olemassa salausjärjestelmä, jolla on seuraava ominaisuus:
"Hyökkääjä, joka tuntee salausalgoritmin ja jolla on salateksti, ei voi saada mitään tietoa alkuperäisestä tekstistä."
Tämä ominaisuus tunnetaan myös nimellä Kerckhoffin periaate .

Esimerkkejä generaattoreista

Bloom-Blum-Fur coat (BBS) generaattori

Otetaan niin yksinkertainen ja , että - 1024-bittinen ja . Toiminto . Kompleksibitti on funktio, joka palauttaa vähiten merkitsevän bitin. on sellainen olettaen, että ei ole algoritmia diskreetin monimutkaisuuden logaritmin laskemiseksi, joka on parempi tai yhtä suuri kuin . On myös osoitettu [4] , että generaattori pysyy asymptoottisesti vakaana, jos lähtösekvenssille ei valita yksi, vaan useampi alempi bitti. Mutta on syytä huomata, että tällaisessa modifikaatiossa oleva generaattori ei enää vastaa Blume-Micali-algoritmia. $s$ $q$ $N = pq$ $p=q=3\ mod\ 4$ $f(x)=x^{2}\ mod\ N$ $B(x)$ $n^{2}$

Annetaan joitain numeerisia arvioita BBS:lle kahdelle hyökkäysvaihtoehdolle:
Oletetaan, että vaaditaan sekvenssin luominen, jonka pituus on , jotta mikään algoritmi ei voi erottaa tätä sarjaa todella satunnaisesta toimintojen aikana , joiden todennäköisyys on suurempi kuin 1/100. Laskelma osoittaa, että tällaisen sekvenssin luomiseen tarvitaan bittipituinen jyvä. Siinä tapauksessa, että generaattori on vaarannettava, ts. löytää siemen lähtösekvenssistä samoihin aikoihin samalla tarkkuudella, silloin suojaus tällaista hyökkäystä vastaan tarjotaan vain biteille [4] . $10^{7}$ $2^{80}$ $n\geqslant 6800$ $n \geqslant 1100$

Dlog-generaattori

Antaa olla 1024- bittinen alkuluku, ja . Määritellään → nimellä . Monimutkainen bitti $s$ $g$ $\mathbb {Z} _{p}$ $f: \{1, ..., p - 1\}$ $\{1, ..., p - 1\}$ $f(x)=g^{x}\ mod\ p$

$B(x) = \left\{\begin{matrix} 0, & x < p/2 \\ 1, & x \geqslant p/2 \end{matrix}\right.$

B(x) on sellainen olettaen, että ei ole algoritmia diskreetin logaritmin laskemiseksi kompleksisuusfunktiolla tai paremmalla. $n^3$

Kalinsken generaattori

Yllä olevien generaattoreiden kryptografinen vahvuus perustui vaikeuteen löytää diskreetti logaritmi. Kalinske-generaattori käyttää elliptisten käyrien ideaa.

Antaa olla alkuluku sellainen, että . Tarkastellaan käyrää x :ssä ( Galois'n kenttä ) muodossa: . Käyrän pisteet yhdessä äärettömyyden pisteen kanssa muodostavat syklisen järjestyksen ryhmän . Olkoon tämän ryhmän generaattori. Esitetään seuraava funktio: Sen mukaisesti generaattorissa käytettävä funktio on muotoa: Generaattorin kompleksibitti: $s$ $p=2\ mod\ 3$ $F_{p}$ $F_{p}$ $y^2 = x^3 + c$ $(x, y)$ $\mathcal{O}$ $p+1$ $K$ $P$ $\phi(P) = \left\{\begin{matrix} y, & P = (x, y) \\ p, & P = \mathcal{O}\end{matriisi}\oikea.$
$f(P) = \phi(P)*Q$
$B(P) = \left\{\begin{matrix} 1, & P = \phi(P) \geqslant (p + 1)/2 \\ 0, & P = \phi(P) < (p + 1 ) )/2\end{matrix}\right.$

Tällaisen generaattorin siemen on jossain pisteessä käyrällä.

Algoritmin haavoittuvuudet

On todistettu, että ongelma todellisen satunnaisen sekvenssin ja Bloom-Micali-kaavion mukaisesti generoidun sekvenssin erottamisessa voidaan pelkistää funktion inversion ongelmaksi [5] . $f$

Tämän algoritmin toteutukset perustuvat pääsääntöisesti käänteisfunktioiden laskemisen monimutkaisuuteen, esimerkiksi diskreetin logaritmin laskennan monimutkaisuuteen . Siksi tämän algoritmin rikkomiseksi sinun tarvitsee vain kyetä ottamaan diskreetti logaritmi ennakoitavissa olevassa ajassa. Oikeissa tietokonetoteutuksissa oikein valituille numeroille tämä on erittäin resursseja vaativa toimenpide. Kuitenkin samanlainen algoritmi kvanttitietokoneessa antaa nopeusvahvistuksen neliöitynä, mikä tekee tällaisen generaattorin hakkerointista paljon realistisemman. Hyökkäys perustuu yhteen kvanttialgoritmien muunnelmista - amplitudihyppy , Groverin algoritmin yleistetympi versio [6] .

Muistiinpanot

↑ Adi Shamir kryptografisesti vahvojen näennäissatunnaisten sekvenssien luomisesta, 1983
↑ [Manuel Blum ja Silvio Micali, How to Generate Cryptographically Strong Sequences of Pseudorandom Bits, SIAM Journal on Computing 13, no. 4 (1984): 850-864.
↑ S. Goldwasser ja S. Micali, Probabilistinen salaus ja kuinka pelata mentaalista pokeria pitämällä salassa kaikki osittaiset tiedot, Proc 14th ACM Symposium on Theory of Computing, 1982, pp. 365-377
↑ 1 2 Andrey Sidorenko ja Berry Schoenmakers, State Recovery Attacks on pseudoradom Generaators, 2005.
↑ O. Goldreich. Kryptografian perusteet. perustyökalut. Cambridge University Press, Cambridge, Iso-Britannia, 2001.
↑ Elloá B. Guedes, Francisco Marcos de Assis, Bernardo Lula Jr - Esimerkkejä yleisestä kvantti-pysyvä kompromissihyökkäys Blum-Micali-rakenteeseen. http://arxiv.org/abs/1012.1776 Arkistoitu 15. elokuuta 2016 Wayback Machinessa

Katso myös

Testaa seuraavaa osaa

Kirjallisuus

BS Kaliski. Elliptiset käyrät ja kryptografia: näennäissatunnainen bittigeneraattori ja muita työkaluja. Väitöskirja, MIT, Cambridge, MA, USA, 1988.
https://web.archive.org/web/20080216164459/http://crypto.stanford.edu/pbc/notes/crypto/blummicali.xhtml
https://web.archive.org/web/20150224041435/http://www.csee.wvu.edu/~xinl/library/papers/comp/Blum_FOCS1982.pdf