👈🏽 🌝 👶🏽 Blum-Blum-Shubジェネレーターとそのアプリケーション 🧒🏻 🙏🏽 🧓🏼

前書き

現在、ランダムな数字はさまざまな科学分野で使用されています。たとえば、さまざまな実際のプロセスをシミュレートするには、調査対象の量の動作だけでなく、さまざまな予測できない現象の影響も考慮する必要があることがよくあります。さらに、実験データを分析するためのいくつかの方法もランダムな数を使用します。ゲーム理論では、チャンスも大きな役割を果たします。そしてもちろん、暗号化において。多くの暗号化または電子署名アルゴリズムはランダムな番号を使用します。

しかし、どのようにしてランダムな番号を取得しますか？自然界には、ジェネレーターが発明されたことに基づいて、多くの異なるランダムな現象があります。ハードウェアランダムナンバージェネレーターは、コイン、ダイス、ルーレットホイールなどのアイテムを使用した巨視的なランダムプロセスに基づくことができます。しかし、そのようなジェネレーターは非常に遅く、問題の解決には適していません。ランダムな数値をより速く取得するために、電気回路のノイズなど、量子的な性質の物理的現象を使用できます。しかし、ハードウェア乱数ジェネレータの主な欠点は、頻繁な誤動作に関連する信頼性の低さです。信頼性の欠如を避けるために、彼らは事前に入手したランダムな数字の表を使い始めました。ただし、大きな欠点もありました。多くのメモリを消費していました。

ハードウェア法もランダム数の表もランダム数の高速で信頼性の高い取得の必要性を満たさなかったため、科学者はランダム数を取得するためのアルゴリズム的方法を探し始めました。このような方法の結果として得られたシーケンスは、特定の式と初期データによって完全に決定されるため、もはやランダムではないことは明らかです。ただし、初期値が秘密にされており、アルゴリズムが耐性がある場合（攻撃が成功すると、攻撃者が到達不可能な量のコンピューティングリソースを必要とする場合、アルゴリズムは耐性があると見なされます）、ジェネレーターが生成する結果は予測できません。一連の数を取得するためのこのようなアルゴリズムは、その特性が一連のランダムな数に近似するものであり、疑似ランダム数ジェネレーターと呼ばれます。

- 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 \同等の25 \ mod \ 133$ . : $x_1 = 25 ^ 2 \同等の93 \ mod \ 133$ $b_1 = 93 \同等の1 \ mod \ 2$ , $x_2 = 93 ^ 2 \同等の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 \同等の123 \ mod \ 133$ $b_4 = 123 \ equiv 1 \ mod \ 2$

1,0,0,1.

, BBS, , $\ラムダ（\ラムダ（x））$ , $\ラムダ（n）= \ {\ min {m}：a ^ m \ equiv 1 \ mod n \}$ - .

BBS , n .

i- , x_0 , n, $\ラムダ（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 \ _長さ）$

, , , , . - C. $2 ^ {塩\ _長さ}$ , 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.ゴールドワッサーとS.ミカリ。確率的暗号化と、すべての部分的な情報を秘密にしてメンタルポーカーをプレイする方法。Proc。14番目のACM症状。コンピューティングの理論、365〜377ページ、サンフランシスコ、1982年。ACM。
Vybornova、Yu.D。Blum-Blum-Shubジェネレーターの実装とその主な特性の研究/Yu.D。Vybornova // INSITU。
ブラザード、J。モダンクリプトロジー/ J。ブラザード。-モスクワ：ポリメッド、1999年。--107ページ。
Yu.D. Vybornova、Blum-Blum-Shubジェネレータアプリケーションとしてのパスワードベースのキー生成機能の開発、新しい手法、2017年
Turan、M。パスワードベースのキー導出に関する推奨事項/ M. Turan、E。Barker、W。Burr、L。Chen-NIST、2010年。-18ページ。

Blum-Blum-Shubジェネレーターとそのアプリケーション

前書き

BBS (Blum-Blum-Shub generator)

BBS

More articles: