6.7-其他几种公钥密码体制t

《6.7-其他几种公钥密码体制t》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章第六章公开密钥密码体制公开密钥密码体制第七节其他几种公钥密码体制1第六章第六章公开密钥密码体制公开密钥密码体制McElicce公钥体制1978年McElicce研究出了一种基于代数编码理论的公开密钥体制.该体制依赖于一类称作Goppa码的纠错编码的存在性,其基本思想是构造一个Goppa码并将其伪装成普通的线性码.2第六章第六章公开密钥密码体制公开密钥密码体制解Goppa码有一种快速算法,但是,要在线性二进制码中找到一种给定大小的代码字则是一个NP完全问题.直到目前为止,仍然认为这种密码体制是安全的.3第六章第六章公开

2、密钥密码体制公开密钥密码体制概率加密公钥体制一般地,公钥密码的一个明文对应于一个密文,因而密码分析者可以对密文进行选择明文攻击,这种攻击对低熵明文空间非常有效.这种明文唯一确定密文的密码体制称为确定性密码体制.4第六章第六章公开密钥密码体制公开密钥密码体制为了消除确定性密码体制的这种缺陷,1982年,美国加州大学伯克利分校的S.MicaliS.Golwasser,提出了一种概率加密方法(简称为GM方法).5第六章第六章公开密钥密码体制公开密钥密码体制概率加密方法是采用概率算法对明文进行变换,因而,加密每一个明文字符可能有许

3、多不同的密文.所以,不可能测试出一个给定的密文是否是某个特定的明文加密而成的.概率加密的目的是要使得敌手在多项式时间内不能从密文获得有关明文的任何信息.这个目的可通过在公钥体制中使用概率加密算法来实现.6第六章第六章公开密钥密码体制公开密钥密码体制NTRU公钥密码体制NTRU(NumberTheoryResearchUnit)公钥密码体制是在90年代中期,由数学家小组JeffreyHoffstein,JillPipher和JosephSilverman研制的.Hoffstein博士首先在CRTPTO’96会议上提出并命名了

4、NTRU加密算法.7第六章第六章公开密钥密码体制公开密钥密码体制NTRU被接受为IEEEP1363标准,被标准化在文档WorkingGroupforStandardsInPublic-KeyCryptography中.8第六章第六章公开密钥密码体制公开密钥密码体制NTRU算法使用多项式代数及两个不同数的模.它的安全性基于多项式、不同模混合运算的相互作用,也依赖于最大格及寻找最短向量的困难性.NTRU加密、解密一个长度N的信息分组需要O(N2)次操作.RSA需要O(N3)次操作,所以,NTRU比RSA至少快100倍.9第六章

5、第六章公开密钥密码体制公开密钥密码体制背包公钥密码体制1978年,Merkle和Hellman首先提出了一个现在称为MH背包体制(knapsacksystem)的公钥密码体制.虽然它和其几个变形在20世纪80年代初被Shamir等人破译了,但是,它的思想和有关理论首先揭示了公钥密码算法的本质,所以仍然具有深刻的理论研究价值.10第六章第六章公开密钥密码体制公开密钥密码体制已知向量A=(a,a,…,a),a为整数.给定向量x12ni=(x,x,…,x),x∈{0,1},求12nin,x∈{0,1}sa=∑xiiii=1容易,

6、但已知A和s,求x使上式成立却非常困难.称此问题为背包问题或子集和问题,A为背包向量.11第六章第六章公开密钥密码体制公开密钥密码体制定义6.7若背包向量满足i−1aaij>∑,i=2,...,nj=1则称A为简单背包向量,相应的背包为简单背包.12第六章第六章公开密钥密码体制公开密钥密码体制简单背包容易求解.这是因为给定A和s后,容易证明⎧xs=1⇔≥ann⎨⎩xs=0⇔

7、放入背包,若能放入,令相应n的x为1,否则,令相应的x为0.再从s中减去xannnn后求x,方法与上相同.以此类推,直到求出xn-11为止.14第六章第六章公开密钥密码体制公开密钥密码体制"贪心"算法(简称GRA算法)如下:ProcedureGRAinputa,a,…,a;s12nfori=ndownto1doifs≥athenx←1,s←s−a;iiielsex←0;iendreturnx,x,…,x12n15第六章第六章公开密钥密码体制公开密钥密码体制利用解简单背包容易,解一般背包困难这一事实,Merkle和Hellm

8、an设计了如下的公钥密码体制.Merkle-Hellman公钥体制(简称M-H体制)构造如下:16第六章第六章公开密钥密码体制公开密钥密码体制n(1)每个用户随机选择一个简单背包向量{}aii=1,模n数为M>∑,Zai*中一对互逆元w和w-1.Mi=1(2)计算b≡wa(modM),i=1,2,...