现代密码学总结汇总.doc

现代密码学总结
第一讲 绪论
· 密码学是保障信息安全的核心
· 安全服务包括：机密性、完整性、认证性、不可否认性、可用性
· 一个密码体制或密码系统是指由明文（m或p）、密文（c）、密钥（k）、加密算法（E）和解密算法（D）组成的五元组。
· 现代密码学分类：
· 对称密码体制：（又称为秘密密钥密码体制，单钥密码体制或传统密码体制）
密钥完全保密；加解密密钥相同；典型算法：DES、3DES、AES、IDEA、RC4、A5
· 非对称密码体制：（又称为双钥密码体制或公开密钥密码体制）
典型算法：RSA、ECC

第二讲 古典密码学
· 代换密码：古典密码中用到的最基本的处理技巧。将明文中的一个字母由其它字母、数字或符号替代的一种方法。
（1）凯撒密码：c = E(p) = (p + k) mod (26) p = D(c) = (c – k) mod (26)
（2）仿射密码：明文p ∈Z26，密文c ∈Z26 ，密钥k=(a,b) ap+b = c mod (26)
（3）单表代换、多表代换
Hill密码：（多表代换的一种）
——明文p ∈(Z26)m，密文c ∈ (Z26)m ，密钥K ∈{定义在Z26上m*m的可逆矩阵}
——加密 c = p * K mod 26 解密p = c * K-1 mod 26

Vigenere密码：查表解答
（4）转轮密码机：
· 置换密码
·
·
· ：将明文字符按照某种规律重新排列而形成密文的过程
列置换，周期置换
· 密码分析：
· 统计分析法：
移位密码、仿射密码和单表代换密码都没有破坏明文的频率统计规律，可以直接用统计分析法
· 重合指数法

· 完全随机的文本CI=0.0385，一个有意义的英文文本CI=0.065
· 实际使用CI的估计值CI’：L：密文长。 fi：密文符号i发生的数目。

第三讲 密码学基础
第一部分 密码学的信息论基础
· Shannon的保密通信系统模型
· 对称密码体制

· 非对称密码体制

· 一个密码体制是一个六元组：（P, C, K1, K2, E, D )
P--明文空间 C--密文空间 K1 --加密密钥空间
K2 --解密密钥空间E --加密变换 D --解密变换
对任一k∈K1,都能找到k’ ∈K2，使得D k’ (E k (m))=m，mM.
· 熵和无条件保密
· 设随机变量X={xi | i=1,2,…,n}, xi出现的概率为Pr(xi) ≧0, 且 , 则X的不确定性或熵定义为

熵H(X)表示集X中出现一个事件平均所需的信息量(观察前)；或集X中每出现一个事件平均所给出的信息量(观测后).

· 设X={xi|i=1,2,…,n}, xi出现的概率为p(xi) ≥0，且∑i=1,…,n p(xi)=1;
Y={yi|i=1,2,…,m}, yi出现的概率为p(yi) ≥0，且∑i=1,…,m p(yi)=1;
则集X相对于集Y的条件熵定义为

· X视为一个系统的输入空间，Y视为系统的输出空间，通常将条件熵H(X|Y)称作含糊度，X和Y之间的平均互信息定义为：I(X,Y)=H(X)-H(X|Y)
表示X熵减少量。
· 完善保密的（无条件保密的）密码系统（P,C,K,E,D）系统满足 或
第二部分 复杂性理论
· 算法计算复杂性常常用两个变量来度量：时间复杂度（计算复杂度）T和空间复杂度S
· 假设一个算法的计算复杂度为O(nt)，其中t为常数，n为输入问题的长度，则称这算法的复杂度是多项式的。具有多项式时间复杂度的算法为多项式时间算法。
· 如果一个算法的复杂度为O(tf(n))，t为大于1的常数，f（n）是以n为自变量的多项式函数，则称该算法的复杂度是指数的。当f（n）是大于常数而小于线性函数时，称为亚指数时间算法。
· 如果一个判定问题存在解它的多项式时间的算法，则称该问题属于P类.
如果一个判定问题不存在解它的多项式时间的算法，且对于一个解答可以在多项式时间验证其是否正确，则称该问题属于NP类.
第四讲 分组密码
· DES算法
· 整体结构：Feistel结构

· 给定明文，通过一个固定初始置换IP来重排输入明文块P中的比特，得到比特串P0=IP(P)=L0R0，这里L0和R0分别是P0的前32比特和后32比特
· 16轮迭代，密钥生成

按下述规则进行16次迭代，即1≤i≤16
这里 是对应比特的模2加，f是一个函数（称为轮函数）；
16个长度为48比特的子密钥Ki(1≤i≤16)是由密钥k经密钥编排函数计算出来的.
· 对比特串R16L16使用逆置换IP-1得到密文C，即C=IP-1 (R16L16)
· 注意：第十六轮迭代左右两块不交换
· 分组密码的轮函数(f)
· 长度为32比特串Ri-1作为第一输入，以长度为48比特串Ki作为第二个输入，产生长度为32比特的输出
· 扩展置换（E盒）：
32位输入扩展为48位输出：按照8行6列次序排列，从32,1,2……排列，上一行的后两位一次在下一行的起始位置得到重用。
· 密钥加：按位异或加，计算
· S盒代换：DES中唯一的非线性部分
8个S盒。每个S盒输入均为6位，输出为4位。Bj=b1b2b3b4b5b6,
b1b6确定行r的二进制表示, b2b3b4b5确定列c的二进制表示，行列确定唯一长度为4的二进制数字
· P置换：根据固定置换P(*)进行置换
· DES算法的密钥编排算法

· 64比特密钥K，根据固定置换PC-1来处理K得到PC-1（K）=C0D0，C0和D0分别由最前和最后28比特组成（去除8,16,24,32,40,48,56,64这8位奇偶校验位）
· 对1≤i≤16， DES的每一轮中使用K的56比特中的48个比特（压缩方法：删除C中的9,18,22,25位和D中的7,9,15,26位）
· 计算Ci=LSi(Ci-1)和Di=LSi(Di-1)，且Ki=PC-2(CiDi)，LSi表示循环左移两个或一个位置, 具体地, 如果i=1,2,9,16就移一个位置，否则就移两个位置, PC-2是另一个固定的置换。
· DES的解密与加密使用一样的算法，以密文y作为输入，以相反顺序使用密钥编排K16,K15,…,K1，输出的是明文X
· DES算法的扩散
· 两轮扩散：
· 三轮扩散：从LO的一块数据影响开始
· AES算法
· 128位（16个字）输入明文，128位密钥长度，第一次迭代前 明文 密钥
· AES算法整体结构：

· AES算法的轮函数——Rijndael轮函数
1）字节代换（SubByte） 2）行移位（ShiftRow）
3）列混合（MixColumn） 4）密钥加（AddRoundKey）
①字节代换：字节代换是非线形变换，独立地对状态的每个字节进行，代换表（即S-盒）是可逆的

S盒可以由以下两步运算得到：
· 求输入元素在m(x)=x8+x4+x3+x+1 上的逆元；
· 对上步中所求得的逆元进行如下运算

②行移位：行移位是将状态阵列的各行进行循环移位，不同状态行的位移量不同；第0行不移动；第1行左移1字节；第2行左移2字节；第3行左移3字节
· 列混合:

其中：（00000010）*(a7a6a5a4a3a2a1a0)=( a6a5a4a3a2a1a00) ,a7为0;
=( a6a5a4a3a2a1a00) (00011011),a7为1
（00000001）*(a7a6a5a4a3a2a1a0)= (a7a6a5a4a3a2a1a0)
（00000011）*(a7a6a5a4a3a2a1a0)= （00000010）*(a7a6a5a4a3a2a1a0) (a7a6a5a4a3a2a1a0)
· 密钥加:密钥加是将轮密钥简单地与状态进行逐比特异或；
轮密钥由种子密钥通过密钥编排算法得到
注：结尾轮函数将列混合这一步骤去掉
· AES算法的密钥编排算法
· 密钥编排指从种子密钥得到轮密钥的过程，AES的密钥编排由密钥扩展和轮密钥选取两部分组成,基本原则如下:
——轮密钥的总比特数等于轮数加1再乘以分组长度；（（10+1）*128=1408）
——种子密钥被扩展成为扩展密钥
——轮密钥从扩展密钥中取，第1轮轮密钥取扩展密钥的前Nb个字，第2轮轮密钥取接下来的Nb个字
· 密钥扩展：
——每一列的4个字节组成一个字——>
对w数组扩充40个新列，构成总共44列扩展密钥数组，如下产生
（1）如果i不是4的倍数，那么w[i]=w[i-4] w[i-1]
（2）若果i是4的倍数，那么w[i]=w[i-4] T(w[i-1]) T为一个复杂的函数
T函数由三个部分组成：字循环，字节代换和轮常量异或
· 字循环：将1个字中的4个字节循环左移1个字节。即[b0 ,b1,b2,b3]变换成[b1,b2,b3,b4]
· 字节代换：对自循环的结果使用S盒（书上P112表4-15）
· 将前两步的结果同轮常量Rcon[j]进行异或，其中j表示轮数
· 轮密钥的选取

· AES的解密变换
· ByteSub的逆变换由代换表的逆表做字节代换
· 行移位运算的逆变换是循环右移，位移量与左移时相同
· 列混合运算的逆运算是类似的，即每列都用一个特定的多项式d(x)相乘
d(x)=‘0B’x3+‘0D’x2+‘09’x+‘0E’.
· 密钥加运算的逆运算是其自身
· AES算法的扩散
第一轮
第二轮
总体

· 其他典型分组密码——SMS4算法
·

· 128比特明文分为4个32比特字，分别赋值给四个寄存器A、B，C，D（D为最高）.
进行32轮F运算，设每轮输入为寄存器当前状态值 和轮密钥为 ，则轮函数F为：
将寄存器最右边字A的值移出，高三个字顺次右移32位，F函数的输出赋值给最左边的寄存器字D.32轮的输出 进行反序变换R，
然后输出密文.
· 轮函数F 以字为单位进行运算，输入寄存器值 和轮密钥
合成置换T：是一个可逆变换，由非线性变换τ和线性变换L复合而成, 即T(.)=L(τ(.))
非线性变换τ由4个并行的S盒构成
线性变换L：
· 密钥编排算法
· 加密密钥长度为128比特MK
· 轮密钥表示为 ，
· 为系统参数， 为固定参数，用于密钥扩展算法
· 密钥扩展算法：

T’变换与加密算法轮函数中的T基本相同,只将其中的线性变换L修改为

固定参数CKi的取值方法为：设 为 的第j 字节（i=0,1,…,31；j=0,1,2,3,即则
· 分组密码的运行模式
· 为了能在各种场合使用DES，定义了4中DES运行模式：ECB,CBC,CFB,OFB
AES的另外一种运行模式：CTR
· ECB模式
最简单的一种分组密码工作方式。一次处理一个明文分组。

密文块可以分别独立解密，无顺序要求；
密钥相同时，明文中相同的64比特分组产生相同的64比特密文块；
不存在错误传播，一块密文传送错误只导致对应明文解密错误；
主要用于发送少数量的分组数据；
· CBC模式
先对明文分组，一次对一个明文分组加密，加密算法的输入是当前明文分组和前一次密文分组的异或.

在产生第1个密文分组时，需要有一个初始向量IV与第1个明文分组异或；
解密时，IV和解密算法对第1个密文分组的输出进行异或以恢复第1个明文分组；
密钥相同时，明文中相同的64比特分组产生不相同的64比特密文块；
存在错误传播，一块密文传输错误会导致下一块密文解密失败；
· CFB模式

加密：设加密算法的输入是64比特移位寄存器，其初值为某个初始向量IV. 加密算法输出的最左（最高有效位）j比特与明文的第一个单元P1进行异或，产生出密文的第1个单元C1. 传送该单元并将输入寄存器的内容左移j位，用C1补齐最右边（最低有效位）j位. 这一过程继续到明文的所有单元都被加密为止.

解密，将加密算法输出的最左（最高有效位）j比特与密文的相应单元异或，产生明文. 反馈到输入寄存器的值为密文单元
——消息被看作bit流，无须分组填充；适合数据以比特或字节为单位出现标准允许反馈任意比特；
——需要额外的初始向量
——密文块需按顺序逐一解密
——密钥相同时，明文中相同的64比特分组产生不相同的64比特密文块.
——存在错误传播（只传播后面的几块）
· OFB模式
类似于CFB, 不同之处在于OFB模式是将加密算法的输出反馈到移位寄存器，而CFB模式中是将密文单元反馈到移位寄存器

——消息被看作比特流，无须分组填充
——密钥流可以在已知消息之前计算，不需要按顺序解密
——不存在比特错误传播
——发送者和接收者必须保持同步
· CTR模式
消息被看作bit流，无须分组填充；
只使用加密算法，且所有加密都使用同一密钥；
需要额外的初始向量；
密钥相同时，明文中相同的分组产生不相同的密文块；
不存在比特错误传播；
效率，密钥流可以在已知消息之前计算，不需要按顺序解密；
优点：（1）硬件效率高，吞吐量仅受可使用并行数量的限制；
（2）软件效率高，能够并行计算
（3）预处理 （4）随机访问 （5）可证明安全性 （6）简单性

· 查分分析思想
设F为轮函数，共m轮迭代。△P：表明明文P1和P2的差分；设
△R1：表示明文和密钥输入后第i轮输出R1和R2的差分；

· 如果 ，那么，对2t个密钥计算，

· 如果
首先选取多个明文对，使得至少有一对为正确明文对，满足
其次重复猜测搜索密钥 的过程
第五讲 流密码
· 序列密码：又称流密码。指明文消息按字符逐位地加密的一类密码算法。
· 流密码分类：
· 同步序列密码
密钥序列的产生独立于明文消息和密文消息的一类流密码。

OFB模式是同步序列密码的一个例子；
特性：发送方和接收方必须同步；
无错误传播；
优点：容易检测插入、删除、重播等主动攻击；
· 自同步序列密码
密钥序列的产生是密钥及固定大小的以往密文位的函数。

特性：自同步特性；
有限的错误传播；
优点：接收端和发送端不同步，只要接收端能连续地正确地接受到n个密文符号，就能重新建立同步；
· 流密码原理
密钥系列产生器分为驱动部分和组合部分。驱动部分产生控制生成器的状态序列；组合部分对驱动部分的各个输出序列进行非线性组合。驱动器一般利用线性反馈移位寄存器LFSR，特别是利用最长周期或m序列产生器实现；非线性反馈移位寄存器也可作为驱动器。
· 线性反馈移位寄存器
· 反馈移位寄存器(FSR)是由n位的寄存器和反馈函数组成，如下图所示，n位的寄存器中的初始值称为移位寄存器的初态.

工作原理：反馈函数f是n个变元(b1,b2,…,bn)的布尔函数.
· 线性反馈移位寄存器的反馈函数为线性函数
设n级LFSR的输出序列{ai}满足递推关系

这种递推关系可用一个一元高次多项式
表示，称这个多项式为LFSR的特征多项式
· 设 是上的多项式，使的最小的p称为的周期或者阶
· n级LFSR输出的序列的最大周期是2n-1
· 当LFSR的寄存器状态遍历2n 1个非零状态时，序列的周期达到最大2n 1，这种序列被称为m序列
· 若n次不可约多项式p(x)的阶为2n-1，则称p(x)为n次本原多项式
· {ai}是周期为2n 1的m-序列的充要条件是其特征多项式f(x)为n阶本原多项式
· 非线性组合部分
· 滤波生成器又叫前馈生成器，一般由LFSR和滤波（前馈）函数两部分组成. LFSR可以是一个，也可以是几个，它们输出的序列共同作为滤波函数的输入。滤波函数要求具有很好的非线性性质，以增强生成器的抗攻击能力。
Geffe序列发生器: 两个LFSR作为复合器的输人，第三个LFSR控制复合器的输出如果a1, a2, 和a3是三个LFSR的输出，则Geffe发生器的输出表示为：b = (a1 ∧ a2) ⊕( a1 ∧a3) ⊕a3

如果3个LFSR长度分别为n1，n2和n3，线性复杂度为(n2+n3)n1+n3
周期为3个LFSR周期的最小公倍数；如果3个本院反馈多项式的阶数互素，那么发生器的周期是3个LFSR周期之积，即(2n1-1)(2n2-1)(2n3-1)
· 钟控生成器。最简单的钟控生成器是用一个LFSR控制另一个LFSR的时钟脉冲

当LFSR1输出1时，时钟脉冲通过与门使LFSR2进行一次移位，从而生成下一位；当LFSR1输出0时，时钟脉冲无法通过与门使LFSR2移位（走），从而LFSR2重复输出前一位（停）。也称之为走停生成器
· 典型流密码算法
· A5算法
GSM系统主要使用的序列密码加密算法，保护从基站到移动设备传输信息
x、y、z（位置分别为A、B、C的第9、11
、11位）进行钟控，若三个位中间
至少有两个为“1”，则为“1”的寄
存器进行一次进动，而为“0”的不
移。反过来，若三个位中至少有两个
为“0”，则为“0”的寄存器进行一次
移位，而为“1”的不移。这种机制保
证了每次至少有两个LFSR被驱动移位

· RC4算法
典型的基于非线性数组变换的序列密码。使用了一个256字节大小的非线性数据表（简称S表），依据表进行非线性变换，得到密钥流。
包括密钥调度算法（KSA）和伪随机生成算法（PRGA）
第六讲 HASH函数和MAC
· Hash函数的定义：
消息是任意有限长度，哈希值是固定长度。
性质：
· 单向性（抗原像）：对干任意给定的消息，计算其哈希值容易。但是，对于给定的哈希值h，要找到M使得H(M)＝h在计算上是不可行的
· 弱抗碰撞（抗二次原像）：对于给定的消息M1，要发现另一个消息M2，满足H( M1 )＝H(M2)在计算上是不可行的
· 强抗碰撞：找任意一对不同的消息M1，M2 ，使H(M1)＝H(M2 )在计算上是不可行的.
分类：
· 改动检测码MDC——不带密钥的哈希函数，主要用于消息完整性
· 消息认证码MAC——带密钥的哈希函数，主要用于消息源认证和消息完整性
· MD5算法
· 算法过程描述：
· 消息填充
填充一个1和若干个0使其长度模512与448同余；再将消息的真实长度以64比特表示附在填充结果后面，使总长度为512比特的整数倍。
· 初始向量
MD5中有A,B,C和D4个32位的寄存器，最开始存放4个固定的32位的整数参数，即初始链接变量，用于第一轮运算：
A=0x01234567 B=0x89ABCDEF C=0Xfedcba98 D=0x76543210
· 分组处理（迭代压缩）
压缩分为4轮，每轮16步函数运算，共64步；

512bitMi被均分为16个子分组（32bit/组）参与每轮16步函数运算。每步的输入是4个32bit的链接变量和一个32bit的消息子分组，输出为32bit；经过4轮候，得到的4个寄存器值分别于输入链接变量进行模加，即是当前中间散列值。
· 输出散列值128bit
· 步函数

每一轮的16个步函数相同，使用同一个非线性函数；
不同轮的步函数使用的非线性函数不相同；
四个非线性函数：

M[j]：消息分组Mi的第j（0<=j<=15）个32bit子分组。
<<<s：循环左移s位
常数T[i]为
· MD5与MD4
从三轮改为四轮；
增加了一种逻辑运算，第二轮函数从F(x,y,z)=(xΛy) v(xΛz) v(yΛz)改为(xΛz) v(yΛ ┐z)，以消弱对称性；
改变第二轮和第三轮访问消息子分组的顺序，使其形式更不相似；
改变每轮移位量以实现更快的雪崩效应；
每步有唯一的加法常数ti，消除任何输入数据的规律；
每一步与上一步的结果相加，这将引起更快的雪崩效应；
· SHA256算法
· 算法过程描述
· 消息填充
填充一个1和若干个0使其长度模512与448同余；再将消息的真实长度以64比特表示附在填充结果后面，使总长度为512比特的整数倍。
· 初始变量
由前8个素数的平方根的小数部分的前32位(二进制)生成
用8个32bit寄存器ABCDEFGH表示。初始链接变量存入其中

· 压缩函数

64轮运算；512bit分组为单位处理消息
对于64轮中的每一轮的t，使用一个32bit的Wt，其值由当前被处理的512bit消息分组Mi导出；每轮中使用一个附加常数Kt（取前64个素数的立方根的小数部分的二进制表示的前32bit）
· 最后一轮的输出和第一轮的输入模232相加产生Hi
· 输出散列值长度为256比特
· SHA256的轮函数
· 第(i-1)块的输出链接变量a、b、c、d、e、f、g和h分别赋值：
a=H0(i-1) b=H1(i-1) c=H2(i-1) d=H3(i-1)
e=H4(i-1) f=H5(i-1) g=H6(i-1) h=H7(i-1)
· for t=0 to 63:（借助临时寄存器T1和T2）
a=T1+T2,b=a,c=b,d=c,e=(d+T1),f=e,g=f,h=g
其中：Ch(e,f,g)=(eΛf)⊕(非eΛg); Maj(a,b,c)=(aΛb) ⊕(aΛc)⊕(bΛc)
=ROTR2(a)⊕ROTR13(a)⊕ROTR22(a)
=ROTR6(e) ⊕ROTR11(e)⊕ROTR25(e)
且ROTRn(x)/ SHRn(x)表示对32bit变量x循环右移/左移n bit
· 计算第i个Hash值H(i)
H0(i)=a+ H0(i-1) H1(i)=b+ H1(i-1) H2(i)=b+ H2(i-1) H3(i)=c+ H3(i-1)
H4(i)=d+ H4(i-1) H5(i)=e+ H5(i-1) H6(i)=f+ H6(i-1) H7(i)=g+ H7(i-1)
· 32bit的Wt是从512bit消息中导出的，方法如下：

其中（x）= ROTR7(x)⊕ROTR18(x)⊕SHR3(x)
(x)= ROTR17(x) ⊕ROTR19(x) ⊕SHR10(x)
· SHA512和SHA284
· ①SHA512
填充消息M, 将消息填充到1024的整数倍；
将填充消息分割为N个1024比特长的消息块M(1)，M(2)，…，M(N)；
设置初始Hash值H(0)；
迭代压缩，80步；
N次迭代后的输出512比特链接变量作为消息散列值输出；

②SHA284
与SHA512仅有两点不同：
初始Hash值H(0)的设置不同；
输出384比特长的消息摘要；
· 算法过程描述
· 消息填充
填充一个1和若干个0使其长度模1024与896同余；再将消息的真实长度以128比特表示附在填充结果后面，使总长度为1024比特的整数倍。
· 初始变量：
· SHA384初始链接变量
第九个至第十六个素数的平方根小数部分前64位(二进制)生成

· SHA512初始链接变量
前八个素数的平方根的小数部分的前64位(二进制)生成

· SHA384和SHA512的轮函数
· (i-1)次迭代的输出赋值给工作变量a、b、c、d、e、f、g和h；
a=H0(i-1) b=H1(i-1) c=H2(i-1) d=H3(i-1)
e=H4(i-1) f=H5(i-1) g=H6(i-1) h=H7(i-1)
· for t=0 to 79：
a=T1+T2,b=a,c=b,d=c,e=(d+T1),f=e,g=f,h=g

· 计算第i个Hash值H(i)
H0(i)=a+ H0(i-1) H1(i)=b+ H1(i-1) H2(i)=b+ H2(i-1) H3(i)=c+ H3(i-1)
H4(i)=d+ H4(i-1) H5(i)=e+ H5(i-1) H6(i)=f+ H6(i-1) H7(i)=g+ H7(i-1)
· 消息认证
· 消息认证码（MAC）是一种消息认证技术
· 发送方A和接收方B共享密钥K，若A向B发送消息M，则A计算利用C=F (K, M)计算MAC值；然后将原始消息M和C一起发送给接收方。
接收方B对收到的消息M用相同的密钥K进行相同的计算得出新的MAC值C’。并将接收到的C与其计算出的C’进行比较 ，若相等，则：
(1) 接收方可以相信消息未被修改。
(2) 接收方可以确信消息来自真正的发送方。
F是MAC函数，它利用密钥K和任意长度的消息M来生成一个固定长度的短数据块C。
· 攻击目的：
①伪造攻击:攻击者在没有密钥K的情况下，伪造一个未经过认证（M，Mac)对.
存在性伪造: 如果攻击者只能够对一个不由他控制的消息进行伪造，那么这种伪造攻击称为存在性伪造攻击.
选择性伪造: 如果攻击者能够对由他选择的消息进行伪造，那么这种伪造攻击称为选择性伪造攻击.
②密钥恢复攻击:攻击者通过分析一系列（M，Mac）对，找到控制这些（M，Mac）对的密钥.
非自适应选择明文攻击: 敌手在使用Mac设备之前，必须已经选定要测试的消息；
自适应选择明文攻击：敌手可以根据Mac设备的输出，自行选择下一次要测试的消息.
· CBC-MAC
· 填充数据，形成一串n比特组；其次，使用CBC模式加密这些数据；对最后的输出分组进行选择处理和截断（如果m＜n）形成MAC
填充方法：（不知道数据的长度，则应选用填充方法2或3）
方法1：对需要计算MAC的数据的右边填充若干个或零个“0”比特，以便得到一个比特长度是n的整数倍的数据串。
方法2：对需要计算MAC的数据的右边先填充一个“1”比特，然后填充若干个或零个“0”比特，以便得到一个比特长度是n的整数倍的数据串。
方法3：首先对需要计算MAC的数据的右边填充若干个或零个“0”比特，以便得到一个比特长度是n的整数倍的数据串；其次，在所得到的数据串的左边 填充一个n比特组，该组包含了未进行填充的数据的比特长度的二元表示，其左边用“0”补齐。
· n比特数据组D1，D2，……，Dq,计算过程如下：(ek为加密函数)
· 置I1=D1，计算O1=ek(I1)
· 对i=2，3，……，q，完成下列计算：Ii=Di⊕Oi-1 Oi=ek(Ii)
· 对Oq进行选择处理和截断，获得m比特MAC
· 攻击：
· 假定MAC1=ek(D1)，则MAC2是两个分组的消息（D1||D2）的一个合法MAC值，其中，D2=D1 ^MAC1。这种攻击方法称为”cut and paste”攻击。
· 攻击者想伪造消息D的合法MAC。
首先，选择消息D1发送给认证者，认证者返回MAC1=ek(D1)
然后计算D2=MAC1^D，把消息（D1||D2）发送给认证者，认证者返回MAC2=ek(ek(D1)^D2)
则MAC2是消息D的合法MAC值：MAC2=ek(D)
· HAMC
· 使用Hash函数H，K1和K2（K1≠K2）计算MAC=H(K1 ||H (K2||m))，其中K1和K2由同一个密钥K导出
· 工作流程：

· H是hash函数（嵌入的散列函数），K是密钥，K+是K左连填充若干0之后的结果，B表示计算消息摘要时消息分块的字节长度，L表示消息摘要按字节计算的长度，M是消息输入
· ipad表示0x36重复b/8次，opad表示0x5c重复b/8次
· n表示嵌入散列函数产生的散列码长度
· 一般来说K的长度不小于n；如果K大于b，则将其作为散列函数的输入而产生一个n位的密钥
· HMAC(K,M)=H[(K+⊕opad) || H[(K+⊕ipad) ||‖M]]
· 在K的左边加上足够的0以得到B字节的K+；
· 将（1）得到的K+与ipad异或，产生分组S1；
· 将M接在（2）得到的S1后面；
· 将H应用于（3）的结果计算消息摘要；
· K+与opad异或产生b位分组S0；
（6） 将（4）消息摘要接在（5）的S0后面；
（7） 应用H于（6）的结果，输出该函数值HMAC(K,M)
· CCT认证加密标准
· 消息认证方式
· SSL：认证加密
· IPSec：加密认证
· SSH：加密、认证
·
· 先认证后加密：接受方解密和验证程序都完成后才能确定消息是否有效。——具有密文隐藏功能
· 先加密后认证：传送信道不安全，传送信息被篡改（或出现传送错误），接受方在解密运算之前就可以发现，从而减少不必要的解密浪费；——不具有密文隐藏功能

第七讲 公钥密码
· 公钥加密体制的原理：
· 参数生成过程：
接收消息的端系统，产生一对用来加密和解密的密钥——公开钥和秘密钥
· 参数生成满足的要求：
公开密钥(public-key), 可以被任何人知道, 用于加密或验证签名；
私钥(private-key), 只能被消息的接收者或签名者知道,用于解密或签名；
由私钥及公开参数容易计算出公开密钥；
由公钥及公开参数推导私钥是困难的；
· 原理图：

· 单向陷门函数
单向函数：两个集合X、Y之间的一个映射，使得Y中每一元素y都有唯一的一个原像x∈X由x易于计算它的像y，由y计算它的原像x是不可行的
单向陷门函数：该函数是易于计算的，但求它的逆是不可行的，除非再已知某些附加信息。
一族可逆函数fk，满足
① Y=fk(X)易于计算（当k和X已知时）.
· X=f-1k(Y)易于计算（当k和Y已知时）.
· X=f-1k(Y)计算上是不可行的（当Y已知但k未知时）.
· 背包密钥体制
若用f充当加密函数对明文消息m加密:首先将m写成二元表示，再将其分成长为n的分组；然后求每一分组的函数值，以函数值(背包容积)作为密文分组.
· 超递增背包体制
（1）解法：已知s为背包容积，对A从右向左检查每一元素，以确定是否在解中:
· 若s≥an，则an在解中，令xn=1；若s<an，则an不在解中，令xn=0. 然后令

2) 对an-1重复上述过程，一直下去，直到检查出a1是否在解中.
3) 检查结束后得解 x=(x1x2…xn).
若XA=S，则背包问题的解为X；否则原背包问题无解
（2）伪装，防攻击方法：
模数k和乘数t皆取常量，满足k>∑ai，且gcd(t,k)=1，即t在模k下有乘法逆元.
bi≡t·ai mod k, i=1,2,…,n.
得新的背包向量B=(b1,b2,…,bn)，记为 B≡t·A mod k.
用户以B作为自己的公开密钥, t、t-1和k可作为其秘密的陷门信息，即解密密钥.
· 加密运算：对明文分组X=(x1x2…xn)的加密为c=f(x)=B·X≡t·A·X mod k
· 解密运算：首先由s≡t-1 c mod k求出s作为超递增背包向量A的容积，再解背包问题即得x=(x1x2…xn).
· RSA算法
（1）密钥的产生
· 选两个安全的大素数p和q。
· 计算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的欧拉函数值。
· 选一整数e，满足1<e<φ(n)，且gcd(φ(n),e)=1。
· 计算d，满足d·e≡1 mod φ(n),即d是e在模φ(n)下的乘法逆元，因e与φ(n)互素，由模运算可知，它的乘法逆元一定存在。
· 以{e,n}为公开钥,{d,n}为秘密钥。
（2）加密：c≡me mod n
（3）解密：m≡cd mod n
· RSA的计算问题——模指数运算的快速算法
求am可如下进行，m写成二进制表示法：m=bk2k+bk-12k-1+…+b12+b0，所以

· ELGamal算法
（1）密钥的产生
首先选择一素数p,生成元g和小于p的随机数x，计算y≡gx mod p，以(y, g, p)作为公开密钥，x作为秘密密钥.
（2）加密过程
随机选一与p-1互素的整数k，0<=k<=p-1
计算密文对: C = {C1,C2}, 发送给接收者——C1≡gk mod p, C2≡ykM mod p.
（3）解密过程

（4）k永久保存？不能重复使用？
攻击者若已知k，可以计算y^k,然后用C2/y^k就得到明文；
若是k重复使用，则C2/C2’=M/M’,知道其中的一个明文，另一个可求。
· 椭圆曲线密码体制
（1）密码学中通常采用有限域上的椭圆曲线，它指曲线方程定义式中，所有系数都是某一有限域GF(p)中的元素（其中p为一大素数）.其中最为常用的是
y2≡x3+ax+b(mod p) (a,b∈GF(p), 4a3+27b2(mod p)≠0) 定义的曲线.
（2）设P=(x1,y1)，Q=(x2,y2)，P≠-Q，则P+Q=(x3,y3)由以下规则确定：
x3≡λ2-x1-x2(mod p)
y3≡λ(x1-x3)-y1(mod p)
其中，
· 利用椭圆曲线实现ElGamal密码体制
（1）密钥生成：
选取一条椭圆曲线，并得Ep(a,b)，取Ep(a,b)的一个生成元G，Ep(a,b)和G作为公开参数.
用户A选nA作为秘密钥，并以PA=nAG作为公开钥.
（2）加密：
B若想向A发送消息Pm，选取一随机正整数k——Cm={kG, Pm+kPA}
（3）解密：
以密文点对中的第二个点减去用自己的秘密钥与第一个点的倍乘
Pm+kPA-nAkG=Pm+k(nAG)-nAkG=Pm
第八讲 数字签名
· 数字签名的性质：（数据完整性、数据源认证性、数据不可否认性）
① 能够验证签名产生者的身份，以及产生签名的日期和时间.
②能保证被签消息的内容的完整性.
③数字签名可由第三方公开验证，从而能够解决通信双方的上述争议.
· 数字签名
电子签名，是指附加在某一电子文档中的一组特定的符号或代码，它是利用数学方法对该电子文档进行关键信息提取并与用户私有信息进行混合运算而形成的，用于标识签发者的身份以及签发