BBS伪随机发生器的改进与应用

1、2010年第01期计算机工程应用技术信息与电脑China Computer&Communication一、引言S. Goldwasser 和S. Micali 于1982年明确提出了概率加密信息的概念, 因为概率加密信息不会对信息有任何泄露。但是他们在概率加密信息时所用的密文远远多于明文,其运算复杂度非常大,目前国内外学者正在研究如何改进BBS 发生器,以期解决概率加密信息时所用的密文远远多于明文和加密速度慢的问题。二、BBS1.BBS 伪随机发生器(1BBS :Blum 与Shub 发明了最简单有效的伪随机发生器,称为 Blum ,Blum 和Shub 发生器,简称为BBS ,有时也

2、称二次剩余发生器4,BBS 发生器的理论是必须做模n 的二次剩余,其工作原理是:首先找两个大素数p 和q ,它们满足模n 的二次剩余。p q = n ,p, q是私钥,n 是公钥,选择另外一个与n互素的随机整数,计算种子: = mod n 然后开始计算位序列。第i个伪随机位是的最低位,这里:= mod n (2BBS 的优点:BBS 随机发生器的优点是不需要为了得到第i 位而迭代所有i-1位。如果已知 p 和q ,可以直接计算第i 位1。同时BBS 随机发生器对左边和右边都是非常安全的,他不能预测序列的前一位和后一位,当然更不能预测序列所有位的随机输出,只有知道p 和q 的人才能知道位序列。三

3、、改进BBS发生器 1.改进的原因:在旧的BBS 体制上概率加密( Probabilistic encryption 信息比较慢2,所用的密文远远多于明文,其运算复杂度非常大 。2. 改进的方法:(1增加随机位: 使用每个更多的最低位作为随机位, N是的长度,可以使用的最低位作为它的随机位,使 加密速度提高到原来的倍左右3 。 (2 用保密位作随机位:使用所有的保密位作为随机位,而不仅仅是最低位,并且它仍然是随机的。可以使加密速度提高到原来的随机位数目个数倍左右5。(3分段加密:可以对明文进行分段加密。使加密速度提高到原来的分段数目个数倍左右。3.改进的可靠性改进BBS 随机发生器的随机位,选

4、择更多的最低位作为随机位,是切实可行的。改进 BBS 强伪随机发生器和概率加密信息时的安全性都依赖于对大整数n 的因子分解(The integer -factorization problem ,而对大整数n 的因子分解,现在是数学上的一个难题,而概率加密本身也是随机的。所以改进后也是安全可靠的4。四、基于改进的BBS上概率加密体制1.概率加密:Shafi Goldwasser 和Silvio Micali 发明了概率加密( Probabilistic encryption 的概念8,在概率加密中,加密算法是概率性的而不是确定性的。目的就是对密文或攻击者加密系统不会泄漏原始消息的任何信息。对密

5、文和其他试验明文的所有计算也不给攻击者关于对应明文的任何信息。概率加密的原理是:假设密文是C =(M ,明文是M,是密钥。于是由此可以看出,很多密文都对应同一明文,反过来,同一明文有很多种加密方法,这样概率加密,攻击者不再能用一个明文寻找一个确定密文,也不能用一个密文确定另外一个明文。这样他即使知道了明文M ,在验证M时,他给它们加密的结果将是完全不同的,他不能比较和到底那个正确,所以就不能知道他已经获得的消息是否正确。2.基于改进的BBS 上的概率加密基于改进的BBS 体制上概率加密消息的原理是:首先找一个与n 互素的随机数x,利用二次剩余的性质计算:= mod n,用作为BBS 伪随机发生

6、器的种子,并且将发生器的输出作为一个伪随机序列密码。将发生器的输出与M 进行异或,每次是改进后所要求的位数。发生器的输出位为(是改进后所选的最低有效位,= mod n,所以有:(t 是明文长度BBS伪随机发生器的改进与应用汤永龙 吉首大学信息管理与工程学院,湖北 张家界 427000摘要:传统的BBS 随机数生成器是逐个比特的生成器,因此速度比较慢。在本文,我们对传统的BBS 生成器进行了改进,得到每次生成多位比特的高速BBS 生成器。基于我们的生成器,我们构造了一个高速的概率加密系统。关键词:密码学;BBS 随机发生器; 概率加密;中图分类号:TP918 文献标识码:A 文章编号:1003-

7、9767(201001-0149-02Improved BBS Pseudorandom Generators and its ApplicationTang Yonglong School of Information Management and Engineering, Jishou University, 427000Abstract: Traditional BBS pseudorandom generator is a generator in which a bit can be generated for every time, hence its ef ciency is l

8、ow. In this paper, we improve traditional BBS pseudorandom generator and obtain a more ef cient BBS pseudorandom generator in which lots of bits can be generated for every time. Based on our BBS pseudorandom generator, we construct a probabilistic encryption system with higher ef ciency.Keywords: Cr

9、yptography; BBS pseudorandom generator; probabilistic encryption *基金项目:本文得到湖南省教育厅自然科学基金项目(09C791的资助作者简介:汤永龙, 1961-,男。 吉首大学信息管理与工程学院副教授。主要从事数论和密码学研究。2010年第01期计算机工程应用技术信息与电脑China Computer&Communication将最后计算的值附加在该消息的尾部,这样就完成了概率加密消息M ,并且在加密过程中没有泄漏任何信息5。 3.解密消息M此概率加密密码体制中,如果知道p 和q后,从中恢复的程序如下: int(int

10、 p, int q , int n ,int t, int int a, b, u, v, w, z ; /* we already know that god(p, q= =1*/ (voidextended-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 ; z = mod exp ( %q, v, q ; retum (b*q*w+a*p*z% n ;这样知道就容易解密了, 只要建立一个相同的BBS 随机发生

11、器 和密文异或。只有知道p 和q 的人才能解密该消息M 。同时不需要迭代所有位。可以直接计算第i 位,异或后得出明文6。4. 改进后的复杂度利用公开密钥n ,任何人都可以使用该发生器产生位随机序列,这就给合法应用此加密系统提供了极大的方便,便于实际应用和推广。应用时不需要为了得到第i 位,而迭代所有i-1位,如果已知 p 和q ,可以直接计算第i 位和密文。同时基于改进的BBS 发生器体制来概率加密信息,与同类加密方法相比较,简化了大量的计算问题,解决了传统概率加密时密文远远多于明文的复杂度问题和加密信息速度慢的问题,不失为一个简单实用的加密信息的新公开密钥方法。参考文献:1.S. Godwa

12、sser and S. Micali, “Probabilistic Encryption ”Journal of Computer and System Sciences,v,28,n,2,Apr1984,pp270-2992.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.3. M. Blun and S.

13、 Goldwasser, “ An Efficient Probabilistic Public-Key Encryption Scheme Which All Partial Information,” Advances in Cryptology: Proceedings of CRYPTO84, Springer-Verlag, 1985, pp.289-299.4. Kiltz, E.: Chosen-Ciphertext Security from Tag-Based Encryption. In: Halevi, S.,Rabin, T. (eds. TCC 2006. LNCS,

14、 vol. 3876, pp. 581600. Springer, Heidelberg(20065. Paillier, P., Villar, J.L.: Trading One-Wayness Against Chosen-Ciphertext Security in Factoring-Based Encryption. In: Lai, X., Chen, K. (eds. ASIACRYPT 2006.LNCS, vol. 4284, pp. 252266. Springer, Heidelberg (20066.Liskov, M.: Constructing an ideal

15、hash function from weak ideal compression functions. In:Biham,E.,Youssef, A.M. (eds. SAC 2006. LNCS, vol. 4356, pp. 358375. Springer, Heidelberg (2007方面是空白,集团需求的矿山建设工程的项目管理软件的成功实施将要填补这一空白。矿山建设工程的信息化就是要用计算机、通信、自动控制等信息汇集处理高新技术对传统矿山建设工程技术手段及施工方式进行改造与提升,促进矿山建设工程技术及施工手段不断完善,使其更加科学、合理,有效地提高效率,降低成本。矿山建设工程的

16、信息化是矿山建设市场发展的高级阶段,必定融入现代物流业、电子商务业和信息产业,从而实现矿山建设工程的高效益、高效率。由于工程项目管理主要是针对某个具体项目的治理,而集团除了以矿山建设为主的专业领域,还涉及到房屋建筑工程、市政公用工程、公路、铁路和隧道等工程,因此必须度身定做一套综合项目管理系统,在信息化建设上走一条前所未有的道路。中煤三建的综合项目管理系统建设工程于09年2月启动,根据工程项目施工管理的实际需求,项目管理系统的涉及模块有:项目注册、招投标管理、进度管理、质量管理、安全管理、竣工管理、风险管理、供方评价、项目事务、灵动项目平台和项目经理平台等。系统实施从基层调研开始,对实际业务流

17、程进行充分的研究和梳理。将其优化整合后进入系统。试运行时不断修正、完善、磨合,以求得科学规范符合实际操作的业务流程。在系统正式应用前,集团采取选择部分典型项目进入系统进行测试的方式。各个单位将具有本专业典型特点的试点项目部挑选出来,按集团要求进入系统实现信息化管理。此措施一方面可以检测系统问题,及早对系统问题进行整改,修正,升级。另一方面可以把试点项目的成功经验复制到本单位各个项目部,以逐步实现集团信息化的全面覆盖。目前为止,集团已经按计划完成了80个试点项目的基础数据录入,为下一步系统的正式应用做好了充分的准备。2.4 应用集成系统随着集团信息化建设的不断深入,集团必须从整体来考虑企业的整个信息系统,并且根据实际需要,对各个应用系统进行总体规划,建设一个合适的集成平台,把企业各个信息系统有机的集成起来。应用集成系统便是采用相关技术将集团门户系统与内部管理系统连接,实现对企业信息流和资金流等系统的信息集成。开放式的企业应用集成是企业提高自身效率和市场