文档介绍：:一个加密密钥和一个解密密钥,而从其中一个密钥推导出另外一个是不能的。混合密码系统:对称算法用于加密消息,公开密钥算法用于加密密钥。结论:公开密钥算法是不安全的,那些被认为是安全的算法中,又有许多是不实用的。:已知M1,M2,…,Mn和S,求b1,b2,…,bn,bi{0,1},使S=b1M1+b2M2+…+bnMn(1:表示物体放入背包,0:表示物体不放入背包)背包算法的思想:明文作为背包问题的解,对应于bi,密文为重量和。例:明文:011010背包:25781317密文:5+7+13=25算法的关键:两个不同的背包问题,一个在线性时间内求解,一个不能在线性时间内求解。超递增序列:其中每个元素都大于前面所有元素的和例:1,3,6,13,27,52……超递增背包:重量列表为一个超递增序列超递增背包的解法:对于i=n,n-1,…,1 bi=0当1当秘密密钥:超递增背包问题的重量序列公开密钥:有相同解的一个一般背包问题的重量序列从秘密密钥建立公开密钥:选择一个超递增序列作为秘密密钥,如:{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*61mod105=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-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,13,23}n-1=3,C*n-1mod50=22*3mod50=16=1+2+13明文为:11010实际实现:元素个数少的背包序列易解,实际的背包应该包括至少250个元素,超递增背包中每项应该有100到200位长,模200至400位长,不易解。,可以用作加密和数字签名算法描述:RSA的安全性基于大整数的因数分解的困难性首先随机选择两个大素数p和q,计算n=pq然后随机选择加密密钥e,满足e与(p-1)(q-1)互素。用扩展的Euclid算法计算解密密钥d,使得ed1mod(p-1)(q-1)公开密钥:e和n秘密密钥:d加密:C=Memodn解密:M=Cdmodn