🔶 😼 👧🏻 Blum-Blum-Shub-Generator und seine Anwendung 👵🏻 💪 👩🏼‍🏭

Einführung

Derzeit werden Zufallszahlen in verschiedenen Bereichen der Wissenschaft verwendet. Um beispielsweise verschiedene reale Prozesse zu simulieren, muss häufig nicht nur das Verhalten der untersuchten Größe berücksichtigt werden, sondern auch der Einfluss verschiedener unvorhersehbarer Phänomene. Darüber hinaus verwenden einige Methoden zur Analyse experimenteller Daten auch Zufallszahlen. In der Spieltheorie spielt auch der Zufall eine große Rolle. Und natürlich in der Kryptographie. Viele Verschlüsselungs- oder elektronische Signaturalgorithmen verwenden Zufallszahlen.

Aber wie bekommt man eine Zufallszahl? In der Natur gibt es viele verschiedene zufällige Phänomene, auf deren Grundlage Generatoren erfunden wurden. Hardware-Zufallszahlengeneratoren können auf makroskopischen Zufallsprozessen basieren, bei denen Elemente wie Münzen, Würfel oder Roulette verwendet werden. Solche Generatoren sind jedoch sehr langsam und nicht zur Lösung von Problemen geeignet. Um Zufallszahlen schneller zu erhalten, können quantenphysikalische Phänomene wie Rauschen in elektrischen Schaltkreisen verwendet werden. Der Hauptnachteil von Hardware-Zufallszahlengeneratoren ist jedoch ihre Unzuverlässigkeit, die mit häufigen Fehlfunktionen verbunden ist. Um Unzuverlässigkeit zu vermeiden, begannen sie, vorab erhaltene Tabellen mit Zufallszahlen zu verwenden. Sie hatten jedoch auch einen großen Nachteil - sie nahmen viel Speicher in Anspruch.

Da weder die Hardwaremethode noch die Tabellen mit Zufallszahlen die Notwendigkeit einer schnellen und zuverlässigen Ermittlung von Zufallszahlen erfüllten, begannen die Wissenschaftler, nach algorithmischen Methoden zur Ermittlung von Zufallszahlen zu suchen. Offensichtlich ist die als Ergebnis solcher Verfahren erhaltene Sequenz nicht länger zufällig, da sie vollständig durch eine bestimmte Formel und Anfangsdaten bestimmt wird. Wenn der Anfangswert jedoch geheim gehalten wird und der Algorithmus resistent ist (ein Algorithmus gilt als resistent, wenn bei einem erfolgreichen Angriff der Angreifer über eine unerreichbare Menge an Rechenressourcen verfügen muss), sind die vom Generator erzeugten Ergebnisse unvorhersehbar. Ein solcher Algorithmus zum Erhalten einer Folge von Zahlen, deren Eigenschaften sich einer Folge von Zufallszahlen annähern, wird als Pseudozufallszahlengenerator bezeichnet.

- 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 \ in 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 \ äquiv 25 \ mod \ 133$ . : $x_1 = 25 ^ 2 \ equiv 93 \ mod \ 133$ $b_1 = 93 \ äquiv. 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 \ äquiv 1 \ mod n \}$ - .

BBS , n .

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

BBS

, , .

BBS , :

, $x \ in 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 \ _ Länge)$

, , , , . - C. $2 ^ {Salz \ _ Länge}$ , 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 und S. Micali. Probabilistische Verschlüsselung und wie man mental Poker spielt, wobei alle Teilinformationen geheim gehalten werden. In Proc. 14. ACM Symp. on Theory of Computing, Seiten 365–377, San Francisco, 1982. ACM.
Vybornova, Yu.D. Implementierung des Blum-Blum-Shub-Generators und Untersuchung seiner Hauptmerkmale / Yu.D. Vybornova // IN SITU.
Brassard, J. Moderne Kryptologie / J. Brassard. - Moskau: Polimed, 1999. - 107 S.
Yu.D. Vybornova, Entwicklung einer passwortbasierten Schlüsselgenerierungsfunktion als Blum-Blum-Shub-Generatoranwendung, Neue Technik, 2017
Turan, M. Empfehlung für die passwortbasierte Schlüsselableitung / M. Turan, E. Barker, W. Burr, L. Chen - NIST, 2010. - 18 S.

Blum-Blum-Shub-Generator und seine Anwendung

Einführung

BBS (Blum-Blum-Shub generator)

BBS

More articles: