Algoritmo de Blum-Micali

El algoritmo Blum-Micali es un generador de números pseudoaleatorios criptográficamente seguro . El algoritmo obtiene su seguridad de la dificultad de calcular logaritmos discretos . ^[1]

Sea un primo impar, y sea una raíz primitiva módulo . Sea una semilla, y sea ${\estilo de visualización p}$ ${\estilo de visualización g}$ ${\estilo de visualización p}$ $estilo de visualización x_{0}}$

$x_{i+1}=g^{x_{i}}\ {\bmod {\ p}}$ .

La salida n del algoritmo es 1 si . De lo contrario, la salida es 0. Esto es equivalente a usar un bit de como número aleatorio. Se ha demostrado que se pueden usar bits de si resolver el problema del logaritmo discreto no es factible incluso para exponentes con tan solo bits. ^[2] ${\estilo de visualización i}$ $x_{i}\leq {\frac {p-1}{2}}$ $Estilo de visualización x_{i}}$ ${\estilo de visualización nc-1}$ $Estilo de visualización x_{i}}$ ${\estilo de visualización c}$

Para que este generador sea seguro, el número primo debe ser lo suficientemente grande como para que el cálculo de logaritmos discretos módulo sea inviable. ^[1] Para ser más precisos, cualquier método que prediga los números generados conducirá a un algoritmo que resuelva el problema del logaritmo discreto para ese primo. ^[3] ${\estilo de visualización p}$ ${\estilo de visualización p}$

Hay un artículo que analiza posibles ejemplos de ataques de compromiso permanente cuántico a la construcción Blum-Micali. Estos ataques ilustran cómo un ataque previo al generador Blum-Micali puede extenderse a toda la construcción Blum-Micali, incluidos los generadores Blum Blum Shub y Kaliski . ^[4]

Referencias

^ de Bruce Schneier, Criptografía aplicada: protocolos, algoritmos y código fuente en C , páginas 416-417, Wiley; 2.ª edición (18 de octubre de 1996), ISBN 0471117099
^ Gennaro, Rosario (2004). "Un generador pseudoaleatorio mejorado basado en el problema del logaritmo discreto". Revista de criptología . 18 (2): 91–110. doi :10.1007/s00145-004-0215-y. ISSN 0933-2790. S2CID 18063426.
^ Blum, Manuel; Micali, Silvio (1984). "Cómo generar secuencias criptográficamente fuertes de bits pseudoaleatorios" (PDF) . SIAM Journal on Computing . 13 (4): 850–864. doi :10.1137/0213053. S2CID 7008910. Archivado desde el original (PDF) el 24 de febrero de 2015.
^ Guedes, Elloá B.; Francisco Marcos de Assis; Bernardo Lula Jr (2010). "Ejemplos del ataque generalizado de compromiso permanente cuántico a la construcción de Blum-Micali". arXiv : 1012.1776 [cs.IT].

Enlaces externos

https://web.archive.org/web/20080216164459/http://crypto.stanford.edu/pbc/notes/crypto/blummicali.xhtml

[schneier-1] Bruce Schneier, Criptografía aplicada: protocolos, algoritmos y código fuente en C , páginas 416-417, Wiley; 2.ª edición (18 de octubre de 1996), ISBN 0471117099

[Gennaro2004-2] Gennaro, Rosario (2004). "Un generador pseudoaleatorio mejorado basado en el problema del logaritmo discreto". Revista de criptología . 18 (2): 91–110. doi :10.1007/s00145-004-0215-y. ISSN 0933-2790. S2CID 18063426.

[3] Blum, Manuel; Micali, Silvio (1984). "Cómo generar secuencias criptográficamente fuertes de bits pseudoaleatorios" (PDF) . SIAM Journal on Computing . 13 (4): 850–864. doi :10.1137/0213053. S2CID 7008910. Archivado desde el original (PDF) el 24 de febrero de 2015.

[4] Guedes, Elloá B.; Francisco Marcos de Assis; Bernardo Lula Jr (2010). "Ejemplos del ataque generalizado de compromiso permanente cuántico a la construcción de Blum-Micali". arXiv : 1012.1776 [cs.IT].