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

《BBS伪随机发生器的改进与应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息与电脑2010年第01期ChinaComputer&Communication计算机工程应用技术BBS伪随机发生器的改进与应用汤永龙吉首大学信息管理与工程学院，湖北张家界427000摘要：传统的BBS随机数生成器是逐个比特的生成器，因此速度比较慢。在本文，我们对传统的BBS生成器进行了改进，得到每次生成多位比特的高速BBS生成器。基于我们的生成器，我们构造了一个高速的概率加密系统。关键词：密码学；BBS随机发生器；概率加密；中图分类号：TP918文献标识码：A文章编号：1003-9767(2010)01-0149-02ImprovedBBSPseudorandomGenera

2、torsanditsApplicationTangYonglongSchoolofInformationManagementandEngineering,JishouUniversity,427000Abstract:TraditionalBBSpseudorandomgeneratorisageneratorinwhichabitcanbegeneratedforeverytime,henceitsefÞciencyislow.Inthispaper,weimprovetraditionalBBSpseudorandomgeneratorandobtainamoreefÞcie

3、ntBBSpseudorandomgeneratorinwhichlotsofbitscanbegeneratedforeverytime.BasedonourBBSpseudorandomgenerator,weconstructaprobabilisticencryptionsystemwithhigherefÞciency.Keywords:Cryptography;BBSpseudorandomgenerator;probabilisticencryption一、引言原来的分段数目个数倍左右。S.Goldwasser和S.Micali于1982年明确提出了概率加密信息的概

4、3．改进的可靠性念,因为概率加密信息不会对信息有任何泄露。但是他们在概率加密改进BBS随机发生器的随机位，选择更多的最低位作为随机位,是信息时所用的密文远远多于明文，其运算复杂度非常大,目前国内外学切实可行的。改进BBS强伪随机发生器和概率加密信息时的安全性都者正在研究如何改进BBS发生器，以期解决概率加密信息时所用的密依赖于对大整数n的因子分解（Theinteger-factorizationproblem），文远远多于明文和加密速度慢的问题。而对大整数n的因子分解，现在是数学上的一个难题,而概率加密本身二、BBS也是随机的。所以改进后也是安全可靠的[4]。1．BBS伪随机发生

5、器四、基于改进的BBS上概率加密体制（1）BBS：Blum与Shub发明了最简单有效的伪随机发生器，称1．概率加密:ShafiGoldwasser和SilvioMicali发明了概率加密（为Blum，Blum和Shub发生器，简称为BBS，有时也称二次剩余发生Probabilisticencryption）的概念[8]，在概率加密中，加密算法是概率器[4]，BBS发生器的理论是必须做模n的二次剩余，其工作原理是：性的而不是确定性的。目的就是对密文或攻击者加密系统不会泄漏原首先找两个大素数p和q，它们满足模n的二次剩余。pq=n，p,q始消息的任何信息。对密文和其他试验明文的所有计

6、算也不给攻击者是私钥，n是公钥，选择另外一个与n互素的随机整数，计算关于对应明文的任何信息。种子：=modn概率加密的原理是：假设密文是C=（M），明文是M，然后开始计算位序列。第i个伪随机位是的最低位，这里:=是密钥。于是modn（2）BBS的优点：BBS随机发生器的优点是不需要为了得到第i位而迭代所有i-1位。如果已知p和q，可以直接计算第i位[1]。同时由此可以看出，很多密文都对应同一明文，反过来，同一明文有BBS随机发生器对左边和右边都是非常安全的,他不能预测序列的前一很多种加密方法，这样概率加密，攻击者不再能用一个明文寻找一个位和后一位，当然更不能预测序列所有位的随机输

7、出，只有知道p和q确定密文，也不能用一个密文确定另外一个明文。这样他即使知道了的人才能知道位序列。明文M，在验证M时，他给它们加密的结果将是完全不同的，，三、改进BBS发生器他不能比较和到底那个正确，所以就不能知道他已经获得的消1．改进的原因:在旧的BBS体制上概率加密（Probabilistic息是否正确。encryption）信息比较慢[2]，所用的密文远远多于明文，其运算复杂2．基于改进的BBS上的概率加密度非常大。基于改进的BBS体制上概率加密消息的原理是：首先找一个与n