于集Y的条件熵定义为
则集X

X视为一个系统的输入空间，Y视为系统的输出空间，通常将条件熵HXY称作含
糊度，X和Y之间的平均互信息定义为：IXYHXHXY
表示X熵减少量。

完善保密的（无条件保密的）密码系统（PCKED）系统满足
或
第二部分复杂性理论
算法计算复杂性常常用两个变量来度量：时间复杂度（计算复杂度）T和空间复杂度S
假设一个算法的计算复杂度为O
t，其中t为常数，
为输入问题的长度，则称这算法的复杂
度是多项式的。具有多项式时间复杂度的算法为多项式时间算法。
如果一个算法的复杂度为Otf
，t为大于1的常数，f（
）是以
为自变量的多项式函数，
则称该算法的复杂度是指数的。当f（
）是大于常数而小于线性函数时，称为亚指数时间算
法。
如果一个判定问题存在解它的多项式时间的算法，则称该问题属于P类
如果一个判定问题不存在解它的多项式时间的算法，且对于一个解答可以在多项式时间验
证其是否正确，则称该问题属于NP类
第四讲分组密码
DES算法

整体结构：Feistel结构
f给定明文，通过一个固定初始置换IP来重排输入明文块P中的比特，得到比特串P0IPPL0R0，这里L0和R0分别是P0的前32比特和后32比特
16轮迭代，密钥生成
LiRi1RiLifRi1Ki按下述规则进行16次迭代，即1≤i≤16
这里是对应比特的模2加，f是一个函数（称为轮函数）；
16个长度为48比特的子密钥Ki1≤i≤16是由密钥k经密钥编排函数计算出来的对比特串R16L16使用逆置换IP1得到密文C，即CIP1R16L16注意：第十六轮迭代左右两块不交换

分组密码的轮函数f
长度为32比特串Ri1作为第一输入，以长度为48比特串Ki作为第二个输入，产生长度
为32比特的输出扩展置换（E盒）：
32位输入扩展为48位输出：按照8行6列次序排列，从3212……排列，上一行的后两位一次在下一行的起始位置得到重用。
ERi1Ki密钥加：按位异或加，计算
S盒代换：DES中唯一的非线性部分8个S盒。每个S盒输入均为6位，输出为4位。Bjb1b2b3b4b5b6b1b6确定行r的二进制表示b2b3b4b5确定列c的二进制表示，行列确定唯一长度为4的二进制数字
P置换：根据固定置换P进行置换
f
DES算法的密钥编排算法
64比特密钥K，根据固定置换PC1来处理K得到PC1（K）C0D0，C0和D0分别由最前
和最后28比特组成（去除816243240485664这8位奇偶校验位）
对1≤i≤16，DES的每一轮中使用K的56比特中的48个比特（压缩方法：删除C中的
9182225位和D中的791526位）
计算CiLSiCi1和DiLSiDir