1．概率加密:Shafi Goldwasser 和Silvio Micali发明了概率加密（ Probabilistic encryption）的概念[8]，在概率加密中，加密算法是概率 性的而不是确定性的。目的就是对密文或攻击者加密系统不会泄漏原 始消息的任何信息。对密文和其他试验明文的所有计算也不给攻击者 关于对应明文的任何信息。
关键词：密码学；BBS随机发生器； 概率加密； 中图分类号：TP918 文献标识码：A 文章编号：1003-9767(2010)01-0149-02
Improved BBS Pseudorandom Generators and its Application
Tang Yonglong School of Information Management and Engineering, Jishou University, 427000
mod n),所以有： 文长度）
（t 是明
*基金项目：本文得到湖南省教育厅自然科学基金项目（09C791）的资助 作者简介：汤永龙， 1961-，男。 吉首大学信息管理与工程学院副教授。主要从事数论和密码学研究。
149
计算机工程应用技术
信息与电脑 China Computer&Communication
（2） 用保密位作随机位：使用所有的保密位作为随机位，而不 仅仅是最低位，并且它仍然是随机的。可以使加密速度提高到原来的 随机位数目个数倍左右[5]。
（3）分段加密：可以对明文进行分段加密。使加密速度提高到
原来的分段数目个数倍左右。 3．改进的可靠性 改进BBS随机发生器的随机位，选择更多的最低位作为随机位,是
密信息，与同类加密方法相比较，简化了大量的计算问题，解决了传 统概率加密时密文远远多于明文的复杂度问题和加密信息速度慢的问 题，不失为一个简单实用的加密信息的新公开密钥方法。
参考文献：
[1].S. Godwasser and S. Micali, “Probabilistic Encryption ”Journal of Computer and System Sciences,v,28,n,2,Apr1984,pp270-299
[4]. Kiltz, E.: Chosen-Ciphertext Security from Tag-Based Encryption. In: Halevi, S.,Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 581–600. Springer, Heidelberg(2006)
/* we already know that god(p, q)= =1*/
(void)extended-enclidian (p, q, &a, &b) ;
u = mod exp ((p+1)/4, t, p-1) ;
v = mod exp ((q+1)/4, t, q-1) ;
w = mod exp ( %p, u, p) ;
切实可行的。改进 BBS强伪随机发生器和概率加密信息时的安全性都 依赖于对大整数n的因子分解（The integer -factorization problem）， 而对大整数n的因子分解，现在是数学上的一个难题,而概率加密本身 也是随机的。所以改进后也是安全可靠的[4]。
四、基于改进的BBS上概率加密体制
2．基于改进的BBS上的概率加密 基于改进的BBS体制上概率加密消息的原理是：首先找一个与n
互素的随机数x，利用二次剩余的性质计算： = mod n，用 作为BBS伪随机发生器的种子，并且将发生器的输出作为一个伪随 机序列密码。将发生器的输出与M进行异或，每次是改进后所要求的
位数。发生器的输出位为 ( 是 改进后所选的最低有效位， =
二、BBS
1．BBS伪随机发生器 （1）BBS：Blum与Shub发明了最简单有效的伪随机发生器，称 为 Blum ，Blum 和Shub发生器，简称为BBS，有时也称二次剩余发生 器[4]，BBS发生器的理论是必须做模n的二次剩余，其工作原理是： 首先找两个大素数p和q，它们满足模n的二次剩余。p q = n ，p, q 是私钥，n是公钥，选择另外一个与n互素的随机整数 ，计算
2010年第01期
将最后计算的值 附加在该消息的尾部，这样就完成了概率加密 消息M ，并Biblioteka 在加密过程中没有泄漏任何信息[5]。
3．解密消息M 此概率加密密码体制中，如果知道p和q后，从 中恢复 的程序 如下: int (int p, int q , int n ,int t, int )
int a, b, u, v, w, z ;
三、改进BBS发生器
1．改进的原因:在旧的BBS体制上概率加密（ Probabilistic encryption）信息比较慢[2]，所用的密文远远多于明文，其运算复杂 度非常大 。
2. 改进的方法：（1）增加随机位: 使用每个 更多的最低位作为 随机位， N是 的长度,可以使用 的最低 位作为它的随机位,使 加密速度提高到原来的 倍左右[3] 。
(上接第148页)
方面是空白，集团需求的矿山建设工程的项目管理软件的成功实施将 要填补这一空白。
矿山建设工程的信息化就是要用计算机、通信、自动控制等信 息汇集处理高新技术对传统矿山建设工程技术手段及施工方式进行改 造与提升，促进矿山建设工程技术及施工手段不断完善，使其更加科 学、合理，有效地提高效率，降低成本。矿山建设工程的信息化是矿 山建设市场发展的高级阶段，必定融入现代物流业、电子商务业和信 息产业，从而实现矿山建设工程的高效益、高效率。由于工程项目管 理主要是针对某个具体项目的治理，而集团除了以矿山建设为主的专 业领域，还涉及到房屋建筑工程、市政公用工程、公路、铁路和隧道 等工程，因此必须度身定做一套综合项目管理系统，在信息化建设上 走一条前所未有的道路。
中煤三建的综合项目管理系统建设工程于09年2月启动，根据工 程项目施工管理的实际需求，项目管理系统的涉及模块有：项目注 册、招投标管理、进度管理、质量管理、安全管理、竣工管理、风险 管理、供方评价、项目事务、灵动项目平台和项目经理平台等。
系统实施从基层调研开始，对实际业务流程进行充分的研究和梳 理。将其优化整合后进入系统。试运行时不断修正、完善、磨合，以 求得科学规范符合实际操作的业务流程。在系统正式应用前，集团采 取选择部分典型项目进入系统进行测试的方式。各个单位将具有本专 业典型特点的试点项目部挑选出来，按集团要求进入系统实现信息化 管理。此措施一方面可以检测系统问题，及早对系统问题进行整改， 修正，升级。另一方面可以把试点项目的成功经验复制到本单位各个
[3]. M. Blun and S. Goldwasser, “ An Efficient Probabilistic PublicKey Encryption Scheme Which All Partial Information,” Advances in Cryptology: Proceedings of CRYPTO84, Springer-Verlag, 1985, pp.289-299.
[5]. Paillier, P., Villar, J.L.: Trading One-Wayness Against ChosenCiphertext Security in Factoring-Based Encryption.. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006.LNCS, vol. 4284, pp. 252–266. Springer, Heidelberg (2006)
[2].W.Alexi,B.Z.Chor,O.Goldreich and C.P.Schnorr, “RSA and Rabin Functions: Certain Parts are as Hard as the Whole,” SIAM Journal on Com puting,v,17,n,2,Apr1988,pp.194-209.
z = mod exp ( %q, v, q) ;
retum (b*q*w+a*p*z)% n ; 这样知道 就容易解密了, 只要建立一个相同的BBS随机发生器 和密文异或。只有知道p和q的人才能解密该消息M。同时不需要迭代 所有位。可以直接计算第i位，异或后得出明文[6]。 4. 改进后的复杂度 利用公开密钥n，任何人都可以使用该发生器产生位随机序列， 这就给合法应用此加密系统提供了极大的方便，便于实际应用和推 广。应用时不需要为了得到第i位,而迭代所有i-1位，如果已知 p 和q， 可以直接计算第i位和密文。同时基于改进的BBS发生器体制来概率加
2010年第01期
信息与电脑 China Computer&Communication
计算机工程应用技术
BBS伪随机发生器的改进与应用
汤永龙 吉首大学信息管理与工程学院，湖北 张家界 427000
摘要：传统的BBS随机数生成器是逐个比特的生成器，因此速度比较慢。在本文，我们对传统的BBS生成器进行了改进，得到每次生成多位 比特的高速BBS生成器。基于我们的生成器，我们构造了一个高速的概率加密系统。
[6].Liskov, M.: Constructing an ideal hash function from weak ideal compression functions. In:Biham,E.,Youssef, A.M. (eds.) SAC 2006. LNCS, vol. 4356, pp. 358–375. Springer, Heidelberg (2007)
概率加密的原理是：假设密文是 C = （M），明文是M ， 是密钥。于是
由此可以看出，很多密文都对应同一明文，反过来，同一明文有 很多种加密方法，这样概率加密，攻击者不再能用一个明文寻找一个 确定密文，也不能用一个密文确定另外一个明文。这样他即使知道了