Bloom-Micaliho algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 15. ledna 2017; kontroly vyžadují 10 úprav .

Algoritmus Blum- Micali je kryptograficky bezpečný algoritmus pro generování pseudonáhodných sekvencí pomocí Random seed . Myšlenky algoritmu nastínili Bloom a Micali v roce 1984. Algoritmus byl vyvinut na základě algoritmu generátoru Shamir navrženého Adi Shamirem o rok dříve [1] . Algoritmus se od svého předchůdce liší vyššími požadavky na složitost výpočtu výstupní sekvence. Na rozdíl od generátoru Shamir jsou výstupem tohoto algoritmu bity, nikoli čísla.

Hlavní myšlenka algoritmu

Zvažte nejjednodušší myšlenku sestavení generátoru pseudonáhodných čísel: dostaneme nějakou počáteční náhodnou sekvenci (seed) a zvolíme nějaký šifrovací algoritmus. Dále, při každé iteraci, zašifrováním aktuálního stavu a výběrem sady bitů z výsledku, můžeme získat sekvenci čísel, která vypadá spíše náhodně.

Algoritmus Bloom-Micali používá přesně tento proces s použitím "hardcore bitů" (hard-core bit, hard-core predikát ).

Bloom a Micali, kteří přišli s algoritmem, předložili tři požadavky na výstupní sekvenci:

Počet výstupních bitů musí polynomiálně záviset na délce zrna (kvůli konečné délce cyklu algoritmu). $bi}$
Získávání bitů by mělo být výpočetně jednoduché – počet akcí by měl být shora omezen nějakou polynomickou funkcí délky zrna. $bi}$
Údery musí být nepředvídatelné. Se známým generátorem a známými prvními bity sekvence , ale bez znalosti semene, by mělo být určení dalšího bitu s pravděpodobností jinou než 50 % výpočetně obtížným úkolem. To znamená, že takový výpočet by neměl být prováděn v polynomu počtu operací délky zrn. $bi}$ $k$ $b_1, ..., b_k$ $b_{k+1}$

Koncept hardcore beatu

"Hardcore beat" (predikát) B pro funkci f je nějaká funkce taková, že:

Výstupní hodnota B je 1 bit.
Pro ni neexistuje takový polynomiálně-časový (tedy z BPP - Bounded-error probabilistic polynomial) algoritmus, který by dokázal správně indikovat B (x) ze známé f (x) s pravděpodobností jinou než 1/2.

Blumova-Micaliho věta

$S$ — Seed — délka argumentu funkce . Ona je délka . - převod z na a - z na {0,1} - složitý bit pro . ; jsou bity konečné generované sekvence. ; . -pseudo-randomness - vlastnost sekvence, pro kterou se provádí -komplexní bit - vlastnost funkce , pro kterou , kde je algoritmus nalezený kryptoanalytikem v čase .
$n$ $F$ $S$
$F$ $\{0,1\}^n$ $\{0,1\}^n$ $B$ $\{0,1\}^n$ $F$
$h_i = B(S_i)$ $Ahoj}$
$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$

Definujme to jako následující proces: Vezměte nějakou náhodnou sekvenci (seed). Jestliže je -komplexní bit, pak je -generátor -pseudonáhodných čísel. - doba výpočtu funkce . Věta se dokazuje kontradikcí; Předpokládá se, že existuje algoritmus, který vám umožní najít prvek se znalostí předchozího [2] . $G_{BM}$ $B$ $(t,\varepsilon)$ $G_{BM}$ $(t- m*TIME(f), \varepsilon*m)$ $ČAS(f)$ $F$

$i + 1$ $i$

Aplikace

Generátory založené na tomto algoritmu se používají v systémech soukromých i veřejných klíčů.

V systémech soukromých klíčů

Dva partneři, kteří si bezpečně vyměnili tajnou počáteční sekvenci, obdrží společnou náhodnou sekvenci o délce mnohonásobně větší než počáteční sekvence.

V systémech veřejného klíče (asymetrické šifrování)

Goldwasser a Micali ukázali [3] , že za předpokladu, že určení kvadratických reziduí modulo složených čísel je výpočetně obtížný úkol, existuje schéma šifrování s následující vlastností:
„Útočník, který zná šifrovací algoritmus a má šifrovaný text, nemůže získat jakékoli informace o původním textu."
Tato vlastnost je také známá jako Kerckhoffsův princip .

Příklady generátorů

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

Vezměme si takové jednoduché a , že - 1024-bit a . Funkce . Komplexní bit je funkce, která vrací nejméně významný bit. je takový za předpokladu, že neexistuje žádný algoritmus pro výpočet diskrétního logaritmu složitosti lepšího nebo rovného . Bylo také ukázáno [4] , že generátor zůstává asymptoticky stabilní, pokud není pro výstupní sekvenci zvolen jeden, ale několik nižších bitů. Je však třeba poznamenat, že generátor v takové modifikaci již nebude odpovídat algoritmu Blume-Micali. $p$ $q$ $N = pq$ $p=q=3\ mod\ 4$ $f(x)=x^{2}\ mod\ N$ $B(x)$ $n^{2}$

Uveďme nějaké numerické odhady pro BBS pro dvě možnosti útoku:
Řekněme, že je potřeba vygenerovat sekvenci délky , takže žádný algoritmus nedokáže rozlišit tuto sekvenci od skutečně náhodné během operací s pravděpodobností větší než 1/100. Výpočet ukazuje, že pro generování takové sekvence je zapotřebí zrno bitové délky. V případě, že je potřeba kompromitovat generátor, tzn. najít seed z výstupní sekvence pro stejné časy se stejnou přesností, pak bude ochrana proti takovému útoku poskytnuta pouze pro bity [4] . $10^{7}$ $2^{80}$ $n\geqslant 6800$ $n \geqslant 1100$

Generátor Dlogů

Nechť je 1024bitové prvočíslo a . Definujme → jako . Složitý kousek $p$ $G$ $\mathbb {Z} _{p}$ $f: \{1, ..., p - 1\}$ $\{1, ..., p - 1\}$ $f(x)=g^{x}\ mod\ p$

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

B(x) je takové za předpokladu, že neexistuje žádný algoritmus pro výpočet diskrétního logaritmu s funkcí složitosti nebo lepší. $n^3$

Kalinskeho generátor

Kryptografická síla výše uvedených generátorů byla založena na obtížnosti nalezení diskrétního logaritmu. Kalinske generátor využívá myšlenku eliptických křivek.

Nechť je prvočíslo takové, že . Uvažujme křivku v x ( Galoisovo pole ) ve tvaru: . Body křivky spolu s bodem v nekonečnu tvoří cyklickou uspořádanou skupinu . Nechť je generátorem této skupiny. Představme si následující funkci: Podle toho má funkce použitá v generátoru tvar: Komplexní bit generátoru: $p$ $p=2\ mod\ 3$ $F_{p}$ $F_{p}$ $y^2 = x^3 + c$ $(x, y)$ $\mathcal{O}$ $p+1$ $Q$ $P$ $\phi(P) = \left\{\begin{matice} y, & P = (x, y) \\ p, & P = \mathcal{O}\end{matice}\right.$
$f(P) = \phi(P)*Q$
$B(P) = \left\{\begin{matice} 1, & P = \phi(P) \geqslant (p + 1)/2 \\ 0, & P = \phi(P) < (p + 1 ) )/2\end{matice}\vpravo.$

Zárodkem takového generátoru je nějaký bod na křivce.

Zranitelnost algoritmů

Je dokázáno, že problém rozlišení mezi skutečnou náhodnou sekvencí a sekvencí generovanou podle Bloom-Micaliho schématu lze redukovat na problém inverze funkce [5] . $F$

Implementace tohoto algoritmu se zpravidla spoléhají na složitost výpočtu inverzních funkcí, například na složitost výpočtu diskrétního logaritmu . Chcete-li tedy tento algoritmus prolomit, musíte být schopni provést diskrétní logaritmus v dohledné době. Na reálných počítačových implementacích je to pro správně zvolená čísla operace velmi náročná na zdroje. Podobný algoritmus na kvantovém počítači však poskytuje nárůst rychlosti na druhou, díky čemuž je hackování takového generátoru mnohem realističtější. Útok je založen na jedné z variant kvantových algoritmů – skoku amplitudy , zobecněné verzi Groverova algoritmu [6] .

Poznámky

↑ Adi Shamir O generaci kryptograficky silných pseudonáhodných sekvencí, 1983
↑ [Manuel Blum a Silvio Micali, How to Generate Cryptographically Strong Sequences of Pseudorandom Bits, SIAM Journal on Computing 13, no. 4 (1984): 850-864.
↑ S. Goldwasser a S. Micali, Pravděpodobnostní šifrování a jak hrát mentální poker utajování všech dílčích informací, Proc 14th ACM Symposium on Theory of Computing, 1982, str. 365-377
↑ 1 2 Andrey Sidorenko a Berry Schoenmakers, State Recovery Attacks on Pseudorandom Generators, 2005.
↑ O. Goldreich. Základy kryptografie. základní nástroje. Cambridge University Press, Cambridge, Spojené království, 2001.
↑ Elloá B. Guedes, Francisco Marcos de Assis, Bernardo Lula Jr. - Příklady zobecněného kvantového trvalého kompromisního útoku na konstrukci Blum-Micali. http://arxiv.org/abs/1012.1776 Archivováno 15. srpna 2016 na Wayback Machine

Viz také

Test na další bit

Literatura

BS Kaliski. Eliptické křivky a kryptografie: Generátor pseudonáhodných bitů a další nástroje. Disertační práce, 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