👩🏻‍💼 👨🏽‍🏫 ☎️ Blum-Blum-Shub generator and its application ➿ 🧞 💛

Introduction

Currently, random numbers are used in various fields of science. For example, to simulate various real processes, it is often necessary to take into account not only the behavior of the investigated quantity, but also the influence of various unpredictable phenomena. In addition, some methods for analyzing experimental data also use random numbers. In game theory, chance also plays a big role. And of course in cryptography. Many encryption or electronic signature algorithms use random numbers.

But how do you get a random number? In nature, there are many different random phenomena, on the basis of which generators were invented. Hardware random number generators can be based on macroscopic random processes using items such as a coin, dice, or roulette wheel. But such generators are very slow and not suitable for solving problems. To obtain random numbers faster, physical phenomena of a quantum nature, such as noise in electrical circuits, can be used. But the main disadvantage of hardware random number generators is their unreliability associated with frequent malfunctions. To avoid unreliability, they began to use pre-obtained tables of random numbers. However, they also had a big drawback - they took up a lot of memory.

Since neither the hardware method nor the tables of random numbers satisfied the need for fast and reliable obtaining of random numbers, scientists began to look for algorithmic methods for obtaining random numbers. It is obvious that the sequence obtained as a result of such methods is no longer random, since it is completely determined by a certain formula and initial data. But if the initial value is kept secret, and the algorithm is resistant (an algorithm is considered resistant if a successful attack on which requires the attacker to have an unattainable amount of computing resources), then the results that the generator produces will be unpredictable. Such an algorithm for obtaining a sequence of numbers, the properties of which approximate a sequence of random numbers, is called a pseudo-random number generator.

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

, , , , . - C. $2 ^ {Salt \ _ Length}$ , 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 and S. Micali. Probabilistic encryption and how to play mental poker keeping secret all partial information. In Proc. 14th ACM Symp. on Theory of Computing, pages 365–377, San Francisco, 1982. ACM.
Vybornova, Yu.D. Implementation of the Blum-Blum-Shub generator and the study of its main characteristics / Yu.D. Vybornova // IN SITU.
Brassard, J. Modern cryptology / J. Brassard. - Moscow: Polimed, 1999 .-- 107 p.
Yu.D. Vybornova, Development of a Password-Based Key Generation Function as a Blum-Blum-Shub Generator Application, New Technique, 2017
Turan, M. Recommendation for password-based key derivation / M. Turan, E. Barker, W. Burr, L. Chen - NIST, 2010. - 18 p.

Blum-Blum-Shub generator and its application

Introduction

BBS (Blum-Blum-Shub generator)

BBS

More articles: