但是，如果序列a1,a2,...,an是超递增序列：ai??aj?1i?1j(i?2,3,...,n)
背包问题有多项式解法超递增序列背包问题求解方法 例:n已知序列a1,a2,...,an是超递增序列：1,2,4,8,...,2求 x1?2x2?4x3?8x4?16x5?32x6?43背包问题的解思路：xi取值只可能为0或者1；如果为0，表示不能装入对应的物体，否则可以装入。
(1)对于体积为32的物体，因为32<43，所以x6?（可以选）1
2）带入x1?2x2?4x3?8x4?16x5?32x6?43：x1?2x2?4x3?8x4?16x5?11
3）因为11?16,所以有x5?（不能选）0
4）带入x1?2x2?4x3?8x4?16x5?11：x1?2x2?4x3?8x4?11
5）继续上述过程，可得：x1＝x2＝x4＝x6＝1x3＝x5＝0
RSA密码系统
其安全性是建立在因式分解的困难性上。
已知n，求p和q使得n=pq是NP完全问题。 算法概要：
1、Bob选择保密的素数p和q，并计算n=pq； 2、Bob通过gcd(e,(p-1)(q-1))=1来选择e； 3、Bob通过de≡1(mod(p-1)(q-1))来计算d；
4、Bob将n和e设为公开的，p、q、d设为秘密的；
5、Alice将m加密为c ≡me(mod n)，并将c发送给Bob； 6、Bob通过计算m ≡cd(mod n)解密。 例1
选择两个素数: p=17 & q=11 计算 n = pq =17×11=187 计算 ?(n)=(p–1)(q-1) =16×10=160 选择 e : gcd(e,160)=1; 其中e=7
计算d: de=1 mod 160 且d < 160 ，则 d=23 （因为23×7=161= 10×160+1） 公布公钥KU={7,187} 保存私钥KR={23,17,11}
如果待加密的消息 M = 88 (注意： 88<187) 加密：C = 887 mod 187 = 11 解密:M = 1123 mod 187 = 88 例2
思
（（（（1、Bob选择 p=885320693， q=238855417， 则可以计算n=p*q=211463707796206571，设加密系数为 e=9007，将n和e发送给Alice。
2、假设Alice传递的信息是cat。令a=01 c=03 t=20，则cat=030120=30120。
Alice计算： c ≡me ≡301209007≡113535859035722866(mod n) 她将c传给Bob。 4、Bob已知p和q的值，他用扩展欧几里德算法计算d：de ≡1(mod(p-1)(q-1))，得到d=116402471153538991 然后Bob计算：cd ≡ 113535859035722866116402471153538991≡30120(mod n)由此他可以得到最初的信息。 加密和解密 （1）密钥生成
1）任选一个大素数p，使得p-1有大的素因子； 2）任选一个mod p的本原根g 3）公布p和g。
使用者任选一私钥x∈Zp，并计算公钥y=gx mod p. 加密程序：m为明文
1）任选一个随机数r ∈Zp，满足Gcd(r,p-1)=1并计算c1=gr mod p; c2=m×yr mod p密文为（ c1， c2 ） 解密程序：1）计算w=(c1x)-1 mod p;：2）计算明文m=c2×w mod p。 RSA 主要问题之一：为了保证必要的安全强度，其密钥必须很长 ECC的优势：在同等安全强度下，ECC所需密钥比RSA短 ECC（椭圆曲线密码体制）加密/解密实现 Alice->Bob
Step 1：Bob选择Ep(a，b)的元素G，使得G的阶n是一个大素数,秘密选择整数k.计算P=kG,公开(p，a，b，G，P)，保密k。其中Kb＝kG为Bob公钥，Kb‘＝k为Bob私钥 Step 2：将消息m编码为x-y形式的点Pm
Step 3：Alice随机选择一个正整数r，对Pm产生密文Cm＝{rG，Pm＋rKb} Step 4：Bob解密
Cm-Kb’(rG)=Pm+rKb-krG=Pm+r(kG)-rkG=Pm 示例：
Alice->Bob(示例）
Step 1：Bob选择E88331(3，45)，G＝(4,11), Bob私钥Kb‘＝K=3, Bob公布公钥Kb＝(413,1808) Step 2： Pm=(5,1734) Step 3：Alice随机选择一个正整数r=8，对Pm产生密文:Cm＝{rG，Pm＋rKb}={(5415,6321),(6626,3576)} Step 4：Bob解密Kb’(rG)=3(5415,6321)=(673,146)；Cm -Kb’(rG)=(6626,3576)-(673,146)=(5,1734) 对称密钥密码系统只有一个密钥，同样的密钥加密和解密
公钥密码系统有2个密钥，其中一个密钥可以公开即公钥，用公钥加密，用私钥解密。 对称密钥速度快，不需公钥基础设施 2、公钥可实现数字签名，实现不可否认性 公钥基础设施：信任模型、垄断模式、寡头模式
其他密码学知识
不知道密码，可能入侵密码系统 不知道密钥，仍然可能入侵密码系统
被动攻击：截获密文，分析推断出明文的攻击。
主动攻击：向系统注入假信息（串扰、删除、增添、篡改、伪造等）手段的攻击。 唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击
OSI网络模型：应用层、表示层、会话层、传输层、网络层、数据链路层、物理层 信息安全的需求：保密性、可用性、完整性、不可否认性 CIA：机密性、完整性、可用性
哈希函数
散列函数 (Hash Function)是一个公开的函数，它将任意长的信息映射成一个固定长度的信息。
Hash函数H一般满足以下几个基本要求：
（1）输入x可以为任意长度；输出数据串长度固定；
（2）正向计算容易，即给定任何x，容易算出H(x)；反向计算困难，即给出一Hash值h，很难找出一特定输入x，使h=H(x)； （3）抗冲突性（抗碰撞性），包括两个含义，一是给出一消息x，找出一消息y使H(x)=H(y)是计算上不可行的（弱抗冲突），二是找出任意两条消息x、y，使H(x)=H(y)也是计算上不可行的（强抗冲突）。 常用的散列函数有：消息摘要4（MD4）算法、消息摘要5（MD5）算法、安全散列函数（SHA）。 （被王小云攻破）。
输入：任意长度的消息报文 M 、 输出：一个固定长度的散列码值 H(M) 、是报文中所有比特的函数值、单向函数 根据是否使用密钥
1、带秘密密钥的Hash函数:消息的散列值由只有通信双方知道的秘密密钥K来控制。此时，散列值称作MAC。
2、不带秘密密钥的Hash函数：消息的散列值的产生无需使用密钥。此时，散列值称作MDC。 Hash函数需满足以下条件： 输入x可以为任意长度，输出为固定长度；正向计算容易，反向计算困难；抗冲突性(无冲突性） 成熟的Hash Function
MD5： 输入：消息长度任意 输出：128位 SHA-1: 输入：消息长度<264 输出：160位
密码学哈希函数特性：可压缩性、高效性、单向性、弱的抗碰撞性、强的抗碰撞性 Hash函数密钥必须是其他DES算法的2倍以上 设置密码哈希函数的准则：蝴蝶效应（雪崩效应） HMAC 消息认证代码
消息认证码：使用一个密钥生成一个固定大小的短数据块，并将该数据块加载到消息后面，称MAC（或密码校验和）MAC＝Ck（M）MAC函数类似于加密函数，但不需要可逆性。因此在数学上比加密算法被攻击的弱点要少。
密码学哈希函数常用算法： 哈希函数的基本用法（a）：提供认证 提供保密
哈希函数的基本用法（b）：提供认证
哈希函数的基本用法（c）：提供认证
哈希函数的基本用法(d)：提供认证、提供保密
哈希函数的基本用法（e）提供认证
哈希函数的基本用法（f）提供认证 、提供保密
数字签名：Digital Signature
传统签名的基本特点
签名是可信的：能与被签的文件在物理上不可分割 签名是不可抵赖的：签名者不能否认自己的签名
签名不能被伪造：除了合法者外，其他任何人不能伪造其签名
签名是不可复制的：对一个消息的签名不能通过复制的方式变为另外一个消息的签名 签名是不可改变的：经签名的消息不能被篡改 容易被验证
数字签名是传统签名的数字化 能与所签文件“绑定” 签名者不能否认自己的签名 容易被自动验证 签名不能被伪造
数字签名五元组(P,A,K,S,V) P是所有消息组成的有限集
A是所有可能的签名组成的有限集 K是所有可能的密钥组成的有限集 S签名算法 V验证算法
分类：直接数字签名方案、基于仲裁的数字签名方案