现代密码学总结讲解.docx

现代密码学总结讲解.docx

《现代密码学总结讲解.docx》由会员分享，可在线阅读，更多相关《现代密码学总结讲解.docx（39页珍藏版）》请在冰点文库上搜索。

现代密码学总结讲解

现代密码学总结

第一讲绪论

∙密码学是保障信息安全的核心

∙安全服务包括：

机密性、完整性、认证性、不可否认性、可用性

∙一个密码体制或密码系统是指由明文（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=cmod（26）

（3）单表代换、多表代换

Hill密码：

（多表代换的一种）

——明文p∈（Z26）m，密文c∈（Z26）m，密钥K∈{定义在Z26上m*m的可逆矩阵}

——加密c=p*Kmod26解密p=c*K-1mod26

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，使得Dk’（Ek（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,…,np（xi）=1;

Y={yi|i=1,2,…,m},yi出现的概率为p（yi）≥0，且∑i=1,…,mp（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的寄存器状态遍历2n1个非零状态时，序列的周期达到最大2n1，这种序列被称为m序列

∙若n次不可约多项式p（x）的阶为2n-1，则称p（x）为n次本原多项式

∙{ai}是周期为2n1的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=0x01234567B=0x89ABCDEFC=0Xfedcba98D=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位

常数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）

∙fort=0to63:

（借助临时寄存器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循环右移/左移nbit

∙计算第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）次迭代的输出