[计算机软件及应用]5公开密钥算法.ppt

《[计算机软件及应用]5公开密钥算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5公开密钥算法概述背包算法RSA算法其他公开密钥算法公开密钥数字签名算法身份验证体制密钥交换算法5.1概述成对密钥的思想：一个加密密钥和一个解密密钥，而从其中一个密钥推导出另外一个是不能的。混合密码系统：对称算法用于加密消息，公开密钥算法用于加密密钥。结论：公开密钥算法是不安全的，那些被认为是安全的算法中，又有许多是不实用的。5.2背包算法背包问题:已知M1,M2,…,Mn和S,求b1,b2,…,bn,bi{0,1},使S=b1M1+b2M2+…+bnMn（1：表示物体放入背包，0：表示物体不放

2、入背包）背包算法的思想:明文作为背包问题的解,对应于bi,密文为重量和。例：明文：011010背包：25781317密文：5+7+13=25算法的关键：两个不同的背包问题，一个在线性时间内求解，一个不能在线性时间内求解。超递增序列：其中每个元素都大于前面所有元素的和例：1，3，6，13，27，52……超递增背包：重量列表为一个超递增序列超递增背包的解法：对于i=n,n-1,…,1bi=0当1当秘密密钥：超递增背包问题的重量序列公开密钥：有相同解的一个一般背包问题的重量序列从秘密密钥建立公开密钥：选

3、择一个超递增序列作为秘密密钥，如：{2，3，6，13，27，52}；将其中每个值都乘以一个数n，对m求余，例如：n=31,m=105；得到的序列作为公开密钥：{62，93，81，88，102，37}。加密：将明文分成长度与背包序列相同的块，计算背包总重量。例如：背包{62，93，81，88，102，37}，明文011000，密文为：93+81=174解密：先计算n-1，为n关于模m的乘法逆元。将密文的值与n-1模m相乘用秘密的背包求解，得到明文例：n=31,m=105,n-1=61,174*61m

4、od105=9=3+6,明文为011000例1：n=31,m=105,秘密密钥为{2，3，6，13，27，52}，公开密钥：{62，93，81，88，102，37}，密文C=280，求明文。例2：设背包公开密钥算法的公开密钥为向量{17，34，2，21，41}，某消息M被加密后生成密文C=22，已知系统中模m=50，n=17，试对C解密求出M。例1：n=31,m=105,秘密密钥为{2，3，6，13，27，52}，公开密钥：{62，93，81，88，102，37}，密文C=280，求明文。解：n-

5、1=61C*n-1mod105=280*61mod105=7070=2+3+13+52根据秘密密钥{2，3，6，13，27，52}明文：110101例2：设背包公开密钥算法的公开密钥为向量{17，34，2，21，41}，某消息M被加密后生成密文C=22，已知系统中模m=50，n=17，试对C解密求出M。解：根据公开密钥{17，34，2，21，41}，求秘密密钥1*17mod50=172*17mod50=346*17mod50=213*17mod50=2123*17mod50=41秘密密钥为{1，2

6、，6，13，23}n-1=3,C*n-1mod50=22*3mod50=16=1+2+13明文为：11010实际实现：元素个数少的背包序列易解，实际的背包应该包括至少250个元素，超递增背包中每项应该有100到200位长，模200至400位长，不易解。5.3RSA算法第一个成熟的公开密钥算法，可以用作加密和数字签名算法描述：RSA的安全性基于大整数的因数分解的困难性首先随机选择两个大素数p和q，计算n=pq然后随机选择加密密钥e，满足e与(p-1)(q-1)互素。用扩展的Euclid算法计算解密密

7、钥d，使得ed1mod(p-1)(q-1)公开密钥：e和n秘密密钥：d加密：C=Memodn解密：M=Cdmodn例：已知n=3337,e=79，M=6882326879666683求C=？解：n=pq=3337=47*71p=47q=71(p-1)(q-1)=46*70=3220d=e-1mod3220=79-1mod3220=1019将明文3位一组，m1=688,m2=232,m3=687,m4=966,m5=668,m6=003加密：c1=m1emodn=68879mod3337=1570

8、同理：c2=2756，c3=2091，c4=2276，c5=2423，c6=158C=15702756209122762423158解密：m1=c1dmodn=15701019mod3337=688RSA算法用于数字签名：(见148页7.1.6)签名：S=MdmodnM:要签名的消息验证签名：M=Semodne:公开密钥d:秘密密钥5.4其他公开密钥算法Rabin体制：安全性基于求模一个合数的平方根的困难性，等价于因数分解。ElGamal：安全性基于有限域内计算离散对数的困难性。数