Blum Blum Shub 產生器

出自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:23) (編輯) (撤銷)
Ceg (對話 | 貢獻)

 
(1個中途的修訂版本沒有顯示。)
第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
 + 
 +* Blum Blum Shub 演算法與 RSA 公鑰密文非常相似,它們都是通過因式分解大數字的難度來獲得安全性的。因此,如果希望具有與 RSA 相同級別的安全性,選取質數的大小必須和 RSA 密鑰的大小相近。

當前修訂版本

[編輯] 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的因數,求出Bi
   演算法:
   X0=S2mod n
   Xi=(Xi-1)2 mod n
   Bi=Xi mod 2

  • Blum Blum Shub 演算法與 RSA 公鑰密文非常相似,它們都是通過因式分解大數字的難度來獲得安全性的。因此,如果希望具有與 RSA 相同級別的安全性,選取質數的大小必須和 RSA 密鑰的大小相近。