Bloom-Micali algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2017. január 15-én felülvizsgált verziótól ; az ellenőrzésekhez 10 szerkesztés szükséges .

A Blum- Micali algoritmus egy kriptográfiailag biztonságos algoritmus pszeudo-véletlen sorozatok generálására Random seed segítségével . Az algoritmus mögött meghúzódó ötleteket Bloom és Micali vázolta fel 1984-ben. Az algoritmust az Adi Shamir által egy évvel korábban javasolt Shamir generátor algoritmus alapján fejlesztették ki [1] . Az algoritmus abban különbözik elődjétől, hogy szigorúbb követelményeket támaszt a kimeneti sorozat kiszámításának bonyolultságával szemben. A Shamir generátorral ellentétben ennek az algoritmusnak a kimenete bitek, nem számok.

Az algoritmus fő ötlete

Tekintsük a pszeudo-véletlenszám-generátor felépítésének legegyszerűbb ötletét: kapunk egy kezdeti véletlenszerű sorozatot (magot), és válasszunk valamilyen titkosítási algoritmust. Továbbá minden iterációnál az aktuális állapot titkosításával és az eredményből egy bitkészlet kiválasztásával egy meglehetősen véletlenszerűnek tűnő számsorozatot kaphatunk.

A Bloom-Micali algoritmus pontosan ezt a folyamatot használja, "kemény biteket" (hard-core bit, hard-core predikátum ) használ.

Az algoritmus kidolgozása során Bloom és Micali három követelményt támaszt a kimeneti szekvenciára vonatkozóan:

A kimeneti bitek számának polinomiálisan kell függnie a szemcsehossztól (az algoritmus véges ciklushossza miatt). $kettős}$
A bitek beszerzése számításilag egyszerű legyen – a műveletek számát felülről korlátozni kell a szemcsehosszúság valamilyen polinomfüggvényével. $kettős}$
Az ütemeknek kiszámíthatatlannak kell lenniük. Ismert generátorral és a sorozat ismert első bitjeivel , de nem ismerve a magot, a következő bit 50%-tól eltérő valószínűséggel történő meghatározása számításilag nehéz feladat. Vagyis ilyen számítást nem szabad a szemcsehosszúságú műveletek számának polinomjában elvégezni. $kettős}$ $k$ $b_1, ..., b_k$ $b_{k+1}$

A hardcore beat fogalma

Az f függvény B "kemény üteme" (predikátuma) olyan függvény, amely:

B kimeneti értéke 1 bit.
Ehhez nem létezik olyan polinom-idő (vagyis a BPP - Bounded-error probabilistic polinom) algoritmus, amely 1/2-től eltérő valószínűséggel tudja helyesen jelezni B (x) egy ismert f (x)-ből.

Blum-Micali tétel

$S$ — Seed — a függvény argumentumának hossza . Ő a hossz . - konverzió -ról -ra és -ról -ról {0,1}-re - trükkös bit a -hoz . ; a végső generált sorozat bitjei. ; . -pszeudo-véletlenség - annak a sorozatnak a tulajdonsága, amelyre végrehajtják - összetett bit - annak a függvénynek a tulajdonsága, amelyre , ahol a kriptoanalitikus által időben talált algoritmus .
$n$ $f$ $S$
$f$ $\{0,1\}^n$ $\{0,1\}^n$ $B$ $\{0,1\}^n$ $f$
$h_i = B(S_i)$ $Szia}$
$S_i = f(S_{i-1})$ $S_0 = S$
$(t,\varepszilon)$ $|P(A(B_1..B_i) == B_i+1) - 1/2| < \varepsilon$
$(t,\varepszilon)$ $A$ $|P(A(B_1..B_i) == 0) - 1/2| < \varepsilon$
$A()$ $t$

Definiáljuk a következő folyamatként: Vegyünk valamilyen véletlenszerű sorozatot (mag). Ha egy -komplex bit, akkor egy -pszeudo-véletlen számgenerátor. - függvény számítási idő . A tételt ellentmondás bizonyítja; Feltételezzük, hogy létezik egy algoritmus, amely lehetővé teszi az elem megtalálását az előző [2] ismeretében . $G_{BM}$ $B$ $(t,\varepszilon)$ $G_{BM}$ $(t-p*IDŐ(f), \varepszilon*m)$ $IDŐ (f)$ $f$

$i + 1$ $én$

Alkalmazás

Az ezen az algoritmuson alapuló generátorokat privát és nyilvános kulcsú rendszerekben is használják.

A privát kulcsú rendszerekben

Két partner, miután biztonságosan felcseréltek egy titkos kezdeti sorozatot, egy közös véletlenszerű sorozatot kapnak, amelynek hossza sokszorosa a kezdeti sorozatnak.

Nyilvános kulcsú rendszerekben (aszimmetrikus titkosítás)

Goldwasser és Micali kimutatta [3] , hogy feltételezve, hogy a másodfokú maradékok modulo összetett számok meghatározása nehéz számítási feladat, létezik egy titkosítási séma, amely a következő tulajdonsággal rendelkezik:
"A titkosítási algoritmus ismeretében és a titkosítással rendelkező támadó nem tudja megszerezni bármilyen információ az eredeti szövegről." Ezt a tulajdonságot Kerckhoff-elvnek
is nevezik .

Példák generátorokra

Bloom-Blum-Fur coat (BBS) generátor

Vegyünk olyan egyszerű és , hogy - 1024 bites és . Funkció . Az összetett bit egy olyan függvény, amely a legkisebb jelentőségű bitet adja vissza. olyan, ha feltételezzük, hogy nincs algoritmus a komplexitás diszkrét logaritmusának kiszámítására, amely jobb vagy egyenlő, mint . Azt is megmutattuk [4] , hogy a generátor aszimptotikusan stabil marad, ha nem egy, hanem több alsó bitet választunk a kimeneti sorozatnak. De érdemes megjegyezni, hogy az ilyen módosításban lévő generátor már nem felel meg a Blume-Micali algoritmusnak. $p$ $q$ $N = pq$ $p=q=3\ mod\ 4$ $f(x)=x^{2}\ mod\ N$ $B(x)$ $n^{2}$

Adjunk meg néhány numerikus becslést a BBS-re két támadási lehetőséghez:
Tegyük fel, hogy egy hosszúságú sorozatot kell generálni , hogy egyetlen algoritmus sem tudja megkülönböztetni ezt a sorozatot a valóban véletlenszerű sorozattól 1 /100-nál nagyobb valószínűséggel végzett műveletek során. A számítás azt mutatja, hogy egy ilyen sorozat létrehozásához bithosszúságú szemcse szükséges. Abban az esetben, ha szükséges a generátor kompromittálása, pl. keresse meg a magot a kimeneti sorozatból ugyanazon időkre azonos pontossággal, akkor az ilyen támadások elleni védelem csak a bitek számára lesz biztosítva [4] . $10^{7}$ $2^{80}$ $n\geqslant 6800$ $n \geqslant 1100$

Dlog generátor

Legyen egy 1024 bites prímszám, és . Definiáljuk a → -t mint . Bonyolult kicsit $p$ $g$ $\mathbb {Z} _{p}$ $f: \{1, ..., p - 1\}$ $\{1, ..., p - 1\}$ $f(x)=g^{x}\ mod\ p$

$B(x) = \left\{\begin{mátrix} 0, & x < p/2 \\ 1, & x \geqslant p/2 \end{mátrix}\jobbra.$

B(x) olyan, feltételezve, hogy nincs algoritmus a diszkrét logaritmus kiszámítására komplexitásfüggvénnyel vagy jobbval. $n^3$

Kalinske generátora

A fenti generátorok kriptográfiai erőssége a diszkrét logaritmus megtalálásának nehézségén alapult. A Kalinske generátor az elliptikus görbék ötletét használja.

Legyen olyan prímszám, hogy . Tekintsünk egy görbét x -ben ( Galois mező ) a következő alakban: . A görbe pontjai a végtelenben lévő ponttal együtt ciklikus rendű csoportot alkotnak . Legyen ennek a csoportnak a generátora. Vezessük be a következő függvényt: Ennek megfelelően a generátorban használt függvény alakja: A generátor komplex bitje: $p$ $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{mátrix} y, & P = (x, y) \\ p, & P = \mathcal{O}\end{mátrix}\jobbra.$
$f(P) = \phi(P)*Q$
$B(P) = \left\{\begin{mátrix} 1, & P = \phi(P) \geqslant (p + 1)/2 \\ 0, & P = \phi(P) < (p + 1 ) )/2\end{mátrix}\jobbra.$

Egy ilyen generátor magja a görbe valamely pontján van.

Algoritmus-sebezhetőségek

Bebizonyosodott, hogy a valódi véletlen sorozat és a Bloom-Micali séma szerint generált sorozat megkülönböztetésének problémája a függvényinverzió problémájára redukálható [5] . $f$

Ennek az algoritmusnak a megvalósítása általában az inverz függvények kiszámításának bonyolultságán alapul, például a diszkrét logaritmus kiszámításának bonyolultságán . Ezért ennek az algoritmusnak a megszakításához csak egy diszkrét logaritmust kell tudnia venni előre látható időn belül. Valódi számítógépes megvalósításokon a helyesen kiválasztott számok esetében ez nagyon erőforrás-igényes művelet. Egy kvantumszámítógépen alkalmazott hasonló algoritmus azonban négyzetes sebességnövelést ad, ami sokkal reálisabbá teszi egy ilyen generátor feltörését. A támadás a kvantumalgoritmusok egyik változatán – az amplitúdóugráson –, a Grover-féle algoritmus [6] általánosabb változatán alapul .

Jegyzetek

↑ Adi Shamir A kriptográfiailag erős pszeudovéletlen szekvenciák generálásáról, 1983
↑ [Manuel Blum és Silvio Micali, How to Generate Cryptographically Strong Sequences of Pseudorandom Bits, SIAM Journal on Computing 13, no. 4, 850-864 (1984).
↑ S. Goldwasser és S. Micali, Valószínűségi titkosítás és mentális pókerezés, minden részleges információ titokban tartása, Proc 14th ACM Symposium on Theory of Computing, 1982, pp. 365-377
↑ 1 2 Andrey Sidorenko és Berry Schoenmakers, State Recovery Attacks on Pseudorandom Generators, 2005.
↑ O. Goldreich. A kriptográfia alapjai. alapvető eszközök. Cambridge University Press, Cambridge, Egyesült Királyság, 2001.
↑ Elloá B. Guedes, Francisco Marcos de Assis, Bernardo Lula Jr – Példák a Blum-Micali konstrukció elleni általános kvantum-kompromisszumtámadásra. http://arxiv.org/abs/1012.1776 Archiválva : 2016. augusztus 15. a Wayback Machine -nél

Lásd még

Tesztelje a következő darabot

Irodalom

BS Kaliski. Elliptikus görbék és kriptográfia: álvéletlen bitgenerátor és egyéb eszközök. PhD értekezés, 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