👩🏽‍🍳 🧒 🛄 Generador Blum-Blum-Shub y su aplicación 👦🏾 🚶🏼 🐂

Introducción

Actualmente, los números aleatorios se utilizan en varios campos de la ciencia. Por ejemplo, para simular varios procesos reales, a menudo es necesario tener en cuenta no solo el comportamiento de la cantidad investigada, sino también la influencia de varios fenómenos impredecibles. Además, algunos métodos para analizar datos experimentales también utilizan números aleatorios. En la teoría de juegos, el azar también juega un papel importante. Y por supuesto en criptografía. Muchos algoritmos de cifrado o firma electrónica utilizan números aleatorios.

Pero, ¿cómo se obtiene un número aleatorio? En la naturaleza, hay muchos fenómenos aleatorios diferentes, sobre la base de los cuales se inventaron los generadores. Los generadores de números aleatorios por hardware se pueden basar en procesos aleatorios macroscópicos que utilizan elementos como una moneda, un dado o una ruleta. Pero estos generadores son muy lentos y no son adecuados para resolver problemas. Para obtener números aleatorios más rápidamente, se pueden utilizar fenómenos físicos de naturaleza cuántica, como el ruido en circuitos eléctricos. Pero la principal desventaja de los generadores de números aleatorios de hardware es su falta de confiabilidad asociada con fallas frecuentes. Para evitar la falta de fiabilidad, comenzaron a utilizar tablas de números aleatorios obtenidas previamente. Sin embargo, también tenían un gran inconveniente: ocupaban mucha memoria.

Dado que ni el método de hardware ni las tablas de números aleatorios satisfacían la necesidad de obtener números aleatorios de forma rápida y fiable, los científicos comenzaron a buscar métodos algorítmicos para obtener números aleatorios. Obviamente, la secuencia obtenida como resultado de tales métodos ya no es aleatoria, ya que está completamente determinada por una determinada fórmula y datos iniciales. Pero si el valor inicial se mantiene en secreto y el algoritmo es resistente (un algoritmo se considera resistente, un ataque exitoso que requiere que el atacante posea una cantidad inalcanzable de recursos informáticos), entonces los resultados que produce el generador serán impredecibles. Dicho algoritmo para obtener una secuencia de números, cuyas propiedades se aproximan a una secuencia de números aleatorios, se denomina generador de números pseudoaleatorios.

- BBS (Blum-Blum-Shub generator) - .

BBS :

- ,
– ,
– , ,
() - , n l(n), . ,

, « ». , , , , . , , .
x n n, y, $y ^ 2 \ equiv x \ mod \ n$ . x - n.
p , $p \ equiv 3 \ mod \ 4$ , .

2 :

, , , 1/2.
, , , r≤l(n)−1 s (r+1)- s 1/2.

BBS (Blum-Blum-Shub generator)

p q
$n: = p \ cdot q$
$s \ en Z_n ^ *$ ( n)
$x_0: = s ^ 2 \ mod \ n$
$x_i: = x_ {i-1} ^ 2 \ mod \ n$ $b_i: = x_i \ mod \ 2$
:

$n = p \ cdot q = 7 \ cdot 19 = 133$ s = 100 . $x_0 = 100 ^ 2 \ equiv 25 \ mod \ 133$ . : $x_1 = 25 ^ 2 \ equiv 93 \ mod \ 133$ $b_1 = 93 \ equiv 1 \ mod \ 2$ , $x_2 = 93 ^ 2 \ equiv 4 \ mod \ 133$ $b_2 = 4 \ equiv 0 \ mod \ 2$ , $x_3 = 4 ^ 2 = 16 \ mod \ 133$ $b_3 = 16 \ equiv 0 \ mod \ 2$ , $x_4 = 16 ^ 2 \ equiv 123 \ mod \ 133$ $b_4 = 123 \ equiv 1 \ mod \ 2$

1,0,0,1.

, BBS, , $\ lambda (\ lambda (x))$ , $\ lambda (n) = \ {\ min {m}: a ^ m \ equiv 1 \ mod n \}$ - .

BBS , n .

i- , x_0 , n, $\ lambda (n)$ .

BBS

, , .

BBS , :

, $x \ en Z_n ^ *$ .
- , , 1 , x 0 .

, BBS ( ) .

. BBS. , . BBS ,

, , , . : , RSA, ( ), , . , , . , . .

. — , . . , . , . , .

(Password-Based Key Derivation Function, PBKDF) — , - . , , -.

PBKDF . PRF. , , . , S - , , - MK_Length.

- MK , $MK = PBKDF _ {(PRF, C)} (P, S, MK \ _ Longitud)$

, , , , . - C. $2 ^ {Sal \ _ Longitud}$ , Salt_Length - .

Dummy _ Bits _ Number , BBS, -. , BBS, . - . a.

T U i : T_i , U_0 S i, Binary(). BBS T_i C. - . r .

, , , . , BBS , , .

Barker, Elaine; Barker, William; Burr, William; Polk, William; Smid, Miles (July 2012). "Recommendation for Key Management" (PDF). NIST Special Publication 800-57. NIST. Retrieved 19 August 2013.
Pascal Junod, «Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator», August 1999
..; ‘’ ’’, 2017
A. C. Yao. Theory and application of trapdoor functions. In Proc. 23rd IEEE Symp. on Foundations of Comp. Science, pages 80–91, Chicago, 1982. IEEE.
M. Blum and S. Micali. How to generate cryptographically strong se- quences of pseudo-random bits. SIAM J. Computing, 13(4):850–863, November 1984.
Lenore Blum, Manuel Blum, and Michael Shub. Comparison of two pseudo-random number generators. In R. L. Rivest, A. Sherman, and D. Chaum, editors, Proc. CRYPTO 82, pages 61–78, New York, 1983. Plenum Press.
A. J. (Alfred J.) Menezes, Paul C. Van Oorschot, and Scott A. Van- stone. Handbook of applied cryptography. The CRC Press series on discrete mathematics and its applications. CRC Press, 2000 N.W. Cor- porate Blvd., Boca Raton, FL 33431-9868, USA, 1997.
E. Kranakis. Primality and Cryptography. Wiley-Teubner Series in Computer Science, 1986.
S. Goldwasser y S. Micali. Cifrado probabilístico y cómo jugar al póquer mental manteniendo en secreto toda la información parcial. En Proc. 14th ACM Symp. on Theory of Computing, páginas 365–377, San Francisco, 1982. ACM.
Vybornova, Yu.D. Implementación del generador Blum-Blum-Shub e investigación de sus principales características / Yu.D. Vybornova // IN SITU.
Brassard, J. Criptología moderna / J. Brassard. - Moscú: Polimed, 1999 .-- 107 p.
Yu.D. Vybornova, Desarrollo de una función de generación de claves basada en contraseñas como una aplicación de generador Blum-Blum-Shub, nueva técnica, 2017
Turan, M. Recomendación para la derivación de claves basada en contraseñas / M. Turan, E. Barker, W. Burr, L. Chen - NIST, 2010. - 18 p.

Generador Blum-Blum-Shub y su aplicación

Introducción

BBS (Blum-Blum-Shub generator)

BBS

More articles: