出自KMU Wiki

在2008年4月28日 (一) 12:16所做的修訂版本 (編輯) Ceg (對話 | 貢獻) (新頁面: = Blum Blum Shub (BBS)產生器: = &nbsp; * 密碼學上的<u>安全虛擬隨機位元產生器</u>(cryptographically secure pseudorandom bit generator, CSPRBG) 。 * CSPRBG是一種...) ←上一個		在2008年4月28日 (一) 12:18所做的修訂版本 (編輯) (撤銷) Ceg (對話 | 貢獻) 下一個→
第13行：		第13行：
	* 取兩大質數 p,q<br>p,q除以4都要餘3&nbsp;，令n=p*q		* 取兩大質數 p,q<br>p,q除以4都要餘3&nbsp;，令n=p*q
-	&nbsp;&nbsp; 再選定一個與n互質的亂數s，使p,q都不是s的因數，求出Bi<br>&nbsp;&nbsp; 演算法：<br>&nbsp;&nbsp; X0=S2 mod n<br>&nbsp;&nbsp; Xi=(Xi-1)2 mod n<br>&nbsp;&nbsp; Bi=Xi mod 2	+	&nbsp;&nbsp; 再選定一個與n互質的亂數s，使p,q都不是s的因數，求出B<sub>i</sub><br>&nbsp;&nbsp; 演算法：<br>&nbsp;&nbsp; X<sub>0</sub>=S<sup>2</sup>mod n<br>&nbsp;&nbsp; X<sub>i</sub>=(X<sub>i</sub>-1)2 mod n<br>&nbsp;&nbsp; B<sub>i</sub>=X<sub>i</sub> mod 2

---

在2008年4月28日 (一) 12:18所做的修訂版本

Blum Blum Shub (BBS)產生器:

 

• 密碼學上的安全虛擬隨機位元產生器(cryptographically secure pseudorandom bit generator, CSPRBG) 。

• CSPRBG是一種可以通過「後續位元測試」的產生器。

• 如果一個虛擬隨機位元產生器可以通過後續位元測試的話，表示我們無法找到一個多項式時間的演算法，其從前面的k個位元來猜出第k+1個位元的機率會遠大過1/2。

• 安全性建立在對n做因數分解的困難度。
  

• 取兩大質數 p,q
  p,q除以4都要餘3 ，令n=p*q

   再選定一個與n互質的亂數s，使p,q都不是s的因數，求出B_i
   演算法：
   X₀=S²mod n
   X_i=(X_i-1)2 mod n
   B_i=X_i mod 2