文档介绍：概述(ɡài shù)
成对密钥的思想：一个(yī ɡè)加密密钥和一个(yī ɡè)解密密钥，而从其中一个(yī ɡè)密钥推导出另外一个(yī ɡè)是不能的。
混合密码系统：对称算法用于加密消息，公开密钥算法用于加密密钥。
结论：公开密钥算法是不安全的，那些被认为是安全的算法中，又有许多是不实用的。
第一页，共33页。
背包(bèibāo)算法
背包问题: 已知M1, M2, …, Mn和S, 求b1,b2,…,bn, bi{0,1}, 使S=b1M1+b2M2+…+bnMn （1：表示物体放入背包，0：表示物体不放入背包）
背包算法的思想: 明文作为背包问题的解, 对应于bi, 密文为重量和。
例：明文：0 1 1 0 1 0
背包：2 5 7 8 13 17
密文：5+7+13=25
算法的关键(guānjiàn)：两个不同的背包问题，一个在线性时间内 求解，一个不能在线性时间内求解。
超递增序列：其中每个元素都大于前面所有元素的和
例：1，3，6，13，27，52……
超递增背包：重量列表为一个超递增序列
第二页，共33页。
超递增背包的解法(jiě fǎ)：对于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}。
第三页，共33页。
加密：将明文分成(fēn chénɡ)长度与背包序列相同的块，计算背包总重量。
例如：背包{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*61 mod 105=9=3+6, 明文为011000
第四页，共33页。
例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被加密(jiā mì)后生成密文C=22，已知系统中模m=50，n=17，试对C解密求出M。
第五页，共33页。
例1：n=31,m=105,秘密密钥为{2，3，6，13，27，52}，公开密钥：{62，93，81，88，102，37}，密文(mì wén)C=280，求明文。
解： n-1=61
C* n-1 mod 105=280*61 mod 105=70
70=2+3+13+52
根据秘密密钥{2，3，6，13，27，52}
明文：110101
第六页，共33页。
例2：设背包公开密钥算法 的公开密钥为向量(xiàngliàng){17，34，2，21，41}，某消息M被加密后生成密文C=22，已知系统中模m=50，n=17，试对C解密求出M。
解：根据公开密钥{17，34，2，21，41}，求秘密密钥
1 * 17 mod 50=17
2 * 17 mod 50=34
6 * 17 mod 50= 2
13*17 mod 50=21
23*17 mod 50=41
秘密密钥为{1，2，6，13，23}
n-1=3, C* n-1 mod 50=22*3 mod 50=16=1+2+13
明文为：11010
第七页，共33页。
实际实现：
元素个数少的背包序列(xùliè)易解，实际的背包应该包括至少250个元素，超递增背包中每项应该有100到200位长，模200至400位长，不易解。
第八页，共33页。
RSA算法(suàn fǎ)
第一个成熟(chéngshú)的公开密钥算法，可以用作加密和数字签名
算法描述：
RSA的安全性基于大整数的因数分解的困难性
首先随机选择两个大素数p和q，计算n = pq
然后随机选择加密密钥e，满足e与(p-1)(q-1)互素。用扩展的Euclid算法计算解密密钥d，使得ed 1 mod (p-1)(q-1)
公开密钥：e和n
秘密密钥：d
加密：C = M