Blum Blum Shub 產生器
出自KMU Wiki
(修訂版本間差異)
| 在2008年4月28日 (一) 12:18所做的修訂版本 (編輯) Ceg (對話 | 貢獻) ←上一個 |
當前修訂版本 (2008年4月28日 (一) 12:23) (編輯) (撤銷) Ceg (對話 | 貢獻) |
||
| 第14行： | 第14行： | ||
| 再選定一個與n互質的亂數s，使p,q都不是s的因數，求出B<sub>i</sub><br> 演算法：<br> X<sub>0</sub>=S<sup>2</sup>mod n<br> X<sub>i</sub>=(X<sub>i</sub>-1)2 mod n<br> B<sub>i</sub>=X<sub>i</sub> mod 2 | 再選定一個與n互質的亂數s，使p,q都不是s的因數，求出B<sub>i</sub><br> 演算法：<br> X<sub>0</sub>=S<sup>2</sup>mod n<br> X<sub>i</sub>=(X<sub>i</sub>-1)2 mod n<br> 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 密鑰的大小相近。
