Algoritmo Bloom-Micali

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 15 de enero de 2017; las comprobaciones requieren 10 ediciones .

El algoritmo de Blum- Micali es un algoritmo criptográficamente seguro para generar secuencias pseudoaleatorias utilizando semillas aleatorias . Las ideas detrás del algoritmo fueron esbozadas por Bloom y Micali en 1984. El algoritmo fue desarrollado en base al algoritmo generador de Shamir propuesto por Adi Shamir un año antes [1] . El algoritmo se diferencia de su predecesor en requisitos más estrictos para la complejidad del cálculo de la secuencia de salida. A diferencia del generador Shamir, la salida de este algoritmo son bits, no números.

La idea principal del algoritmo

Considere la idea más simple de construir un generador de números pseudoaleatorios: nos dan una secuencia aleatoria inicial (semilla) y elegimos algún algoritmo de cifrado. Además, en cada iteración, al cifrar el estado actual y elegir un conjunto de bits del resultado, podemos obtener una secuencia de números que parece bastante aleatoria.

El algoritmo Bloom-Micali usa exactamente este proceso, usando "bits de núcleo duro" (bit de núcleo duro, predicado de núcleo duro ).

Al idear el algoritmo, Bloom y Micali propusieron tres requisitos para la secuencia de salida:

El número de bits de salida debe depender polinómicamente de la longitud del grano (debido a la longitud finita del ciclo del algoritmo). $bi}$
Obtener bits debería ser computacionalmente simple: el número de acciones debería estar limitado desde arriba por alguna función polinomial de la longitud del grano. $bi}$
Los latidos deben ser impredecibles. Con un generador conocido y los primeros bits conocidos de la secuencia , pero sin conocer la semilla, determinar el siguiente bit con una probabilidad distinta del 50% debería ser una tarea computacionalmente difícil. Es decir, dicho cálculo no debe realizarse en un polinomio del número de operaciones de longitud de grano. $bi}$ $k$ $b_1, ..., b_k$ $b_{k+1}$

Concepto de ritmo hardcore

Un "ritmo extremo" (predicado) B para una función f es una función tal que:

El valor de salida de B es 1 bit.
Para ello, no existe tal algoritmo de tiempo polinomial (es decir, del BPP - Polinomio probabilístico de error acotado) que pueda indicar correctamente B (x) a partir de un f (x) conocido con una probabilidad distinta de 1/2.

Teorema de Blum-Micali

$S$ — Semilla — longitud del argumento de la función . Ella es la longitud . - conversión de a , y - de a {0,1} - un poco complicado para . ; son los bits de la secuencia final generada. ; . -pseudo-aleatoriedad - una propiedad de la secuencia para la cual se realiza -bit complejo - una propiedad de la función para la cual , donde está el algoritmo encontrado por el criptoanalista en el tiempo .
$norte$ $F$ $S$
$F$ $\{0,1\}^n$ $\{0,1\}^n$ $B$ $\{0,1\}^n$ $F$
$h_i = B(S_i)$ $hola}$
$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$

Definámoslo como el siguiente proceso: Tome alguna secuencia aleatoria (semilla). Si es un bit complejo, entonces es un generador de números pseudoaleatorios. - tiempo de cálculo de la función . El teorema se demuestra por contradicción; Se supone que existe un algoritmo que permite encontrar un elemento, sabiendo lo anterior [2] . $G_{BM}$ $B$ $(t,\varepsilon)$ $G_{BM}$ $(t- m*TIEMPO(f), \varepsilon*m)$ $TIEMPO(f)$ $F$

$yo + 1$ $i$

Aplicación

Los generadores basados en este algoritmo se utilizan tanto en sistemas de clave privada como pública.

En sistemas de clave privada

Dos socios, habiendo intercambiado con seguridad una secuencia inicial secreta, reciben una secuencia aleatoria común de longitud muchas veces mayor que la secuencia inicial.

En sistemas de clave pública (cifrado asimétrico)

Goldwasser y Micali demostraron [3] que, asumiendo que la determinación de números compuestos de módulo de residuos cuadráticos es una tarea computacionalmente difícil, existe un esquema de encriptación con la siguiente propiedad:
"Un atacante, conociendo el algoritmo de encriptación y teniendo el texto cifrado, no puede obtener cualquier información sobre el texto original".
Esta propiedad también se conoce como el principio de Kerckhoff .

Ejemplos de generadores

Generador Bloom-Blum-Fur coat (BBS)

Tomemos tan simple y , que - 1024 bits y . función _ El bit complejo es una función que devuelve el bit menos significativo. es tal bajo el supuesto de que no existe un algoritmo para calcular el logaritmo discreto de complejidad mejor o igual que . También se demostró [4] que el generador permanece asintóticamente estable si no se eligen uno, sino varios bits inferiores para la secuencia de salida. Pero vale la pena señalar que el generador en tal modificación ya no corresponderá al algoritmo Blume-Micali. $pags$ $q$ $N = pq$ $p=q=3\ mod\ 4$ $f(x)=x^{2}\mod\N$ $B(x)$ $n^{2}$

Demos algunas estimaciones numéricas para BBS para dos opciones de ataque:
Digamos que se requiere generar una secuencia de longitud , tal que ningún algoritmo pueda distinguir esta secuencia de una verdaderamente aleatoria durante operaciones con una probabilidad mayor a 1/100. El cálculo muestra que para generar tal secuencia, se requiere un grano de longitud de bits. En caso de que se requiera comprometer el generador, es decir, encuentre una semilla de la secuencia de salida para los mismos tiempos con la misma precisión, entonces la protección contra tal ataque se proporcionará solo para bits [4] . $10^{7}$ $2^{80}$ $n\geqslant 6800$ $n \geqslant 1100$

Generador de Dlogs

Sea un número primo de 1024 bits y . Definamos → como . un poco complicado $pags$ $gramo$ $\mathbb {Z} _{p}$ $f: \{1, ..., p - 1\}$ $\{1, ..., p - 1\}$ ${\ estilo de visualización f (x) = g ^ {x} \ mod \ p}$

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

B(x) es tal bajo el supuesto de que no existe un algoritmo para calcular el logaritmo discreto con una función de complejidad o mejor. $n ^ 3$

Generador de Kalinske

La fuerza criptográfica de los generadores anteriores se basaba en la dificultad de encontrar un logaritmo discreto. El generador de Kalinske utiliza la idea de las curvas elípticas.

Sea un número primo tal que . Considere una curva en x ( campo de Galois ) de la forma: . Los puntos de la curva , junto con el punto en el infinito , forman un grupo de orden cíclico . Sea el generador de este grupo. Introduzcamos la siguiente función: En consecuencia, la función utilizada en el generador tiene la forma: Bit complejo del generador: $pags$ $p=2\ mod\ 3$ $F_{p}$ $F_{p}$ $y^2 = x^3 + c$ $(x, y)$ $\mathcal{O}$ $p+1$ $q$ $PAGS$ $\phi(P) = \left\{\begin{matriz} y, & P = (x, y) \\ p, & P = \mathcal{O}\end{matriz}\right.$
$f(P) = \phi(P)*Q$
$B(P) = \left\{\begin{matriz} 1, & P = \phi(P) \geqslant (p + 1)/2 \\ 0, & P = \phi(P) < (p + 1 ) )/2\end{matriz}\right.$

La semilla de tal generador es algún punto de la curva.

Vulnerabilidades del algoritmo

Se demuestra que el problema de distinguir entre una secuencia aleatoria verdadera y una secuencia generada según el esquema Bloom-Micali puede reducirse al problema de la inversión de funciones [5] . $F$

Las implementaciones de este algoritmo, por regla general, se basan en la complejidad de calcular funciones inversas, por ejemplo, en la complejidad de calcular el logaritmo discreto . Por lo tanto, para romper este algoritmo, solo necesita poder tomar un logaritmo discreto en un tiempo previsible. En implementaciones informáticas reales, para números elegidos correctamente, esta es una operación que consume muchos recursos. Sin embargo, un algoritmo similar en una computadora cuántica da una ganancia de velocidad al cuadrado, lo que hace que piratear dicho generador sea mucho más realista. El ataque se basa en una de las variantes de los algoritmos cuánticos : el salto de amplitud , una versión más generalizada del algoritmo de Grover [6] .

Notas

↑ Adi Shamir Sobre la generación de secuencias pseudoaleatorias criptográficamente fuertes, 1983
↑ [Manuel Blum y Silvio Micali, How to Generate Cryptographically Strong Sequences of Pseudorandom Bits, SIAM Journal on Computing 13, no. 4 (1984): 850-864.
↑ S. Goldwasser y S. Micali, Cifrado probabilístico y cómo jugar al póquer mental manteniendo en secreto toda la información parcial, Proc 14th ACM Symposium on Theory of Computing, 1982, págs. 365-377
↑ 1 2 Andrey Sidorenko y Berry Schoenmakers, State Recovery Attacks on Pseudorandom Generators, 2005.
↑ O. Goldreich. Fundamentos de Criptografía. herramientas básicas. Cambridge University Press, Cambridge, Reino Unido, 2001.
↑ Elloá B. Guedes, Francisco Marcos de Assis, Bernardo Lula Jr - Ejemplos del ataque de compromiso permanente cuántico generalizado a la construcción Blum-Micali. http://arxiv.org/abs/1012.1776 Archivado el 15 de agosto de 2016 en Wayback Machine .

Véase también

Prueba para el siguiente bit

Literatura

BS Kaliski. Curvas elípticas y criptografía: un generador de bits pseudoaleatorios y otras herramientas. Tesis doctoral, MIT, Cambridge, MA, EE. UU., 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