👩🏿‍🎨 😀 🙋 Générateur Blum-Blum-Shub et son application 😏 🚵🏼 🦍

introduction

Actuellement, des nombres aléatoires sont utilisés dans divers domaines scientifiques. Par exemple, pour simuler divers processus réels, il est souvent nécessaire de prendre en compte non seulement le comportement de la grandeur étudiée, mais aussi l'influence de divers phénomènes imprévisibles. En outre, certaines méthodes d'analyse des données expérimentales utilisent également des nombres aléatoires. Dans la théorie des jeux, le hasard joue également un rôle important. Et bien sûr en cryptographie. De nombreux algorithmes de cryptage ou de signature électronique utilisent des nombres aléatoires.

Mais comment obtenir un nombre aléatoire? Dans la nature, il existe de nombreux phénomènes aléatoires différents, sur la base desquels les générateurs ont été inventés. Les générateurs de nombres aléatoires matériels peuvent être basés sur des processus aléatoires macroscopiques utilisant des éléments tels qu'une pièce de monnaie, des dés ou une roue de roulette. Mais ces générateurs sont très lents et ne conviennent pas pour résoudre des problèmes. Pour obtenir des nombres aléatoires plus rapidement, des phénomènes physiques de nature quantique, tels que le bruit dans les circuits électriques, peuvent être utilisés. Mais le principal inconvénient des générateurs de nombres aléatoires matériels est leur manque de fiabilité associé à des dysfonctionnements fréquents. Pour éviter le manque de fiabilité, ils ont commencé à utiliser des tableaux pré-obtenus de nombres aléatoires. Cependant, ils avaient aussi un gros inconvénient - ils prenaient beaucoup de mémoire.

Comme ni la méthode matérielle ni les tables de nombres aléatoires ne répondaient au besoin d'obtention rapide et fiable de nombres aléatoires, les scientifiques ont commencé à rechercher des méthodes algorithmiques pour obtenir des nombres aléatoires. Il est évident que la séquence obtenue grâce à de telles méthodes n'est plus aléatoire, car elle est complètement déterminée par une certaine formule et des données initiales. Mais si la valeur initiale est gardée secrète et que l'algorithme est résistant (un algorithme est considéré comme résistant si une attaque réussie nécessite que l'attaquant dispose d'une quantité de ressources de calcul inaccessible), alors les résultats que le générateur produit seront imprévisibles. Un tel algorithme pour obtenir une séquence de nombres, dont les propriétés se rapprochent d'une séquence de nombres aléatoires, est appelé générateur de nombres pseudo-aléatoires.

- 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 \ dans 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 \ dans 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 \ _ Longueur)$

, , , , . - C. $2 ^ {Sel \ _ Longueur}$ , 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 et S. Micali. Chiffrement probabiliste et comment jouer au poker mental en gardant secrètes toutes les informations partielles. Dans Proc. 14e ACM Symp. on Theory of Computing, pages 365–377, San Francisco, 1982. ACM.
Vybornova, Yu.D. Implémentation du générateur Blum-Blum-Shub et étude de ses principales caractéristiques / Yu.D. Vybornova // IN SITU.
Brassard, J. Cryptologie moderne / J. Brassard. - Moscou: Polimed, 1999 .-- 107 p.
Yu.D. Vybornova, Développement d'une fonction de génération de clé basée sur un mot de passe en tant qu'application de générateur Blum-Blum-Shub, Nouvelle technique, 2017
Turan, M. Recommandation pour la dérivation de clé basée sur un mot de passe / M. Turan, E. Barker, W. Burr, L. Chen - NIST, 2010. - 18 p.

Générateur Blum-Blum-Shub et son application

introduction

BBS (Blum-Blum-Shub generator)

BBS

More articles: