密码分析学
密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照这些法则，变明文为密文，称为加密变换；变密文为明文，称为解密变换。
1977年美国公布实施的数据加密标准DES，标志着密码学发展的革命。
对称密钥密码
对称算法就是加密密钥能够从解密密钥中推算出来，反过来也成立。在大多数对称算法中，加/解密密钥是相同的。这些算法也叫秘密密钥算法或单密钥算法。 对称算法可分为两类。序列密码（流密码）与分组密码。 序列密码（流密码）
序列密码主要应用于军事和外交场合。
序列密码的优点是错误扩展小、速度快、利于同步、安全程度高。
1、伪随机序列发生器是指输入真随机的较短的密钥（种子）通过某种复杂的运算产生大量的伪随机位流。
2、真随机序列从真实世界的自然随机性源产生。如自然界中的抛币。
3、伪随机序列用确定的算法产生，不是真正的随机序列。伪随机序列发生器指使用短的真随机序列（称为种子）x扩展成较长的伪随机序列y。 4、随机数是较短的随机位序列。
分组密码：分组密码是将明文按一定的位长分组，明文组和密钥组的全部经过加密运算得到密文组。 分组密码根据攻击者所掌握的信息，其攻击可分为：唯密文攻击、已知明文攻击、选择明文攻击 攻击的复杂度：
1、数据复杂度:实施该攻击所需输入的数据量 2、处理复杂度:处理这些数据所需要的计算量 分组密码的典型攻击方法： 最可靠的攻击办法:强力攻击
穷尽密钥搜索攻击：唯密文,2k、已知(选择)明文, 2k, k-密钥长度 字典攻击：明密文对编成字典, 2n,n-分组长度
查表攻击：选择明文攻击, 给定明文,用所有的2k个密钥,预计算密文, k-密钥长度
时间存储权衡攻击：选择明文攻击,由穷尽密钥搜索和查表攻击混合而成,它在选择明文攻击中以时间换取空间
最有效的攻击:差分密码分析,通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特.
线性密码分析:本质上是一种已知明文攻击方法,通过寻找一个给定密码算法的有效的线性近似表达式来破译密码系统 、插值攻击方法 、密钥相关攻击 DES
DES利用56比特串长度的密钥K来加密长度为64位的明文，得到长度为64位的密文
DES算法：64位块长度 56位密钥 迭代16轮（前一轮输出是下一轮的输入，经过16轮得到密文） 子密钥48位
初始置换IP和初始逆置换IP—1
DES算法安全性主要在S盒（非线性）、输入32位，扩展输出48位 子密钥每一轮的输出都不一样 输入64比特明文数据 初始置换IP 在密钥控制下 16轮迭代 交换左右32比特 初始逆置换IP-1 输出64比特密文数据 DES算法框图
S—盒：有八个S盒，每一个S盒由6位组成，输入2为输入，4位输出
对每个盒，6比特输入中的第1和第6比特组成的二进制数确定的行，中间4位二进制数用来确定的列。相应行、列位置的十进制数的4位二进制数表示作为输出。例如的输入为101001，则行数和列数的二进制表示分别是11和0100，即第3行和第4列，的第3行和第4列的十进制数为3，用4位二进制数表示为0011，所以的输出为0011。 S -盒的设计原则
S -盒的设计原理没有公开，一些原则如下： 所有S-盒的每一行是0,1,?,15的一个置换；
所有S-盒的输出都不是输入的线性函数或仿射函数；
S-盒的输入改变任意一位都会引起输出中至少两位发生变化； 对于任何输入x（6位），S(x)与S(x⊕001100)至少有两位不同； 对于任何输入x（6位），S(x)与S(x⊕00ef00)不相等，e, f取0或1；
对于任意一个输入位保持不变而其他五位变化时，输出中0和1的数目几乎相等。
子密钥的产生
DES的安全性分析
DES的安全性完全依赖于密钥，与算法本身没有关系。
主要研究内容：密钥的互补性；弱密钥与半弱密钥；密文-明文相关性；密文-密钥相关性；S-盒的设计； 密钥搜索。
弱密钥：由密钥 k 确定的加密函数与解密函数相同，即
。
DES的弱密钥： 如果各轮产生的子密钥一样，则加密函数与解密函数相同。
DES至少有4个弱密钥 ：0101010101010101、1f1f1f1f0e0e0e0e、e0e0e0e0f1f1f1f1、fefefefefefefefe 半弱密钥 ：对于密钥 k ，存在一个不同的密钥 ，满足。
DES的半弱密钥：子密钥生成过程中只能产生两个不同的子密钥或四个不同的子密钥，互为对合。 DES至少有12个半弱密钥。
差分密码分析法，可对DES进行选择明文攻击。线性密码分析比差分密码分析更有效 双重DES (Double DES)
C = EK2(EK1(P)) ? P = DK1(DK2(C))
攻击DES的方法主要有：密钥穷搜索攻击、差分攻击、线性攻击，较有效的方法、相关密钥攻击 分组密码的操作模式
电子密码本ECB 、密码分组链接CBC、密码反馈CFB 、输出反馈OFB 、计数器模式CTR
公钥密码
公开密钥算法中用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来（至少在合理假定的长时间内），所以加密密钥能够公开，每个人都能用加密密钥加密信息，但只有解密密钥的拥有者才能解密信息。又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在提出的。 在公开密钥算法系统中，加密密钥叫做公开密钥（简称公钥），解密密钥叫做秘密密钥（私有密钥，简称私钥）。
公开密钥算法主要用于加密/解密、数字签名、密钥交换。 为什么要设计公钥密码算法？ 密钥分配
保密通信双方需共享密钥，而共享密钥要经常更换
例如：A选择密钥并手工传递给B，第三方C选择密钥分别手工传递给A,B，用A,B原有共享密钥传送新密钥。与A,B分别有共享密钥的第三方C传送新密钥给A和/或B。N个用户集需要N(N-1)/2个共享密钥。
密钥分发中心(Key Distribution Center)
每个用户与KDC有共享密钥(Master Key)、N个用户,KDC只需分发N个Master Key。两个用户间通信用会话密钥(Session Key)、用户必须信任KDC、KDC能解密用户间通信的内容 公开密钥密码的重要特性 加密与解密由不同的密钥完成 加密: m?c: c = EK(m) 解密: c?m: m = DB(c) = DB(EK(m))
知道加密算法,从加密密钥得到解密密钥在计算上是不可行的
两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的) m = DB(EK(m)) = EK(DB(m)) 用公钥密码实现保密
用户拥有密钥对（k,k')公钥k公开，私钥k'保密Alice?Bob：c＝Ek（m）BBob： Dk（c）＝Dk（Ek（m））＝m''BBB
用公钥密码实现认证
用户拥有密钥对（k,k')公钥k公开，私钥k'保密Alice?Bob：c＝Ek（m）'ABob： Dk（c）＝Dk（Ek（m））＝m'AAA
用公钥密码实现保密与认证
用户拥有密钥对（k,k')公钥k公开，私钥k'保密Alice?Bob：c＝Ek（Dk（m））'BABob： Dk（Ek(c)）AB ＝Dk（Ek(c)）AB ＝Dk（Ek'(Ek（Dk（m））)）'ABBA ＝m公钥密钥的应用范围：加密/解密、数字签名(身份鉴别)、密钥交换
公钥密码算法
涉及到各方：发送方、接收方、攻击者 涉及到数据：公钥、私钥、明文、密文 公钥算法的条件：
1、产生一对密钥是计算可行的
2、已知公钥和明文，产生密文是计算可行的 3、接收方利用私钥来解密密文是计算可行的
4、对于攻击者，利用公钥来推断私钥是计算不可行的 5、已知公钥和密文，恢复明文是计算不可行的 6、(可选)加密和解密的顺序可交换 一、背包问题（公钥相关） 背包问题：
已知一长度为B的背包，及长度分别为a1,a2,...,an的n个物品。假定这些物品的半径和背包相同，若从这n个物品中选出若干个正好装满这个背包。现在反过来问：究竟是哪些物品？ 背包问题数学描述
求xi＝0或1，i?1,2,...,n,使其满足：?ai?1nixi?b,
其中a1,a2,...,an和b都是整数背包问题求解：
背包问题属于NP完备类（NP问题中难度最大的一类）对这一问题没有有效算法