密码学教程 课件全套 毛明 -1-古典密码 -6-密码协议

密码学

引子什么是密码学？（与其他课程的关系？）加解密古典密码对称密码序列密码分组密码利用关于有限的整数的数学认证对称密码如何建立共享密钥？公钥加密公钥密码数字签名Hash函数身份认证协议利用更多的数学，主要是：数论网络化的环境、更一般/复杂的功能：安全多方计算密码协议密钥管理协议身份认证协议秘密共享协议安全多方计算协议

课程安排48

学时理论；

9

学时实验；----共57学时

第一章

古典密码6学时

1．1置换密码与代替密码1．2统计攻击1．3一次一密与迭代密码

1.4相关数学概念和算法

第二章

序列密码

10学时

2．1概述

2．2线性反馈移位寄存器

2．3

m序列及其性质

2．4对偶移位寄存器第三章

分组密码10学时

3．1概述

3．2DES算法

3．3AES算法3.4SM4算法3.5分组密码的工作模式2．5B-M算法

2.6非线性组合与算法举例第四章

Hash函数

6

学时

4．1概述

4．2SHA-1和SHA-2

4．3SHA-3

4.4我国商密标准SM3

4.5MAC和认证加密

第五章

公钥密码

10

学时

5．1概述

5．2RSA加密方案

5.3ElGamal加密方案

5.4椭圆曲线上加密方案

5.

5数字签名

5.6SM2

5.

7*后量子密码第六章

密码协议

6

学时

6．1概述

6．2密钥协商协议

6．3秘密共享协议

6．4身份认证协议

6.

5安全多方计算教材：毛明，李梦东主编，《密码学教程》，

机械工业出版社，2024年。

参考书：A.Menezes等著，胡磊等译，《应用密码学手册》(1996年)，电子工业出版社，2005。D.Stinson著，冯登国译，《密码学原理与实践》（第二版），电子工业出版社，2003年。

陈鲁生，《现代密码学》，科学出版社，2004年。杨波，《现代密码学》，清华大学出版社，2003。考核方式：

平时成绩40%：期末考试60%。平时成绩考核方式（按照百分制）：

作业50%：五次作业，每次10分；

实验30%：三次实验，每次10分；

其他20%：回答问题等表现情况。第一章古典密码

1．1置换密码与代替密码

1．2统计攻击

1．3一次一密和乘积密码1．4相关数学概念和算法

密码技术源远流长:

1．1置换密码与代替密码自从有了战争，就有了密码；烽火台、、、在不安全的信道传递保密信息。例题：(置换密码)栅栏密码（美国南北战争时期）：1234567891011atcaegtoorwtaktihtmro3597682111410ceotgotawarkirthmat*to竖写横读atcaegtoorwtaktihtmroceotgotawarkirthmat*to

attackateighttomorrow还可以写出多行的形式：123456acetmwtkitotagorathmo古希腊的斯巴达密码棒：acetmwtkitotagorathmo置换（Permutation）：一个有限集合S上的一一对应映射。

逆置换：输出变输入，按列调整第一行为自然顺序：

30个元素的置换表：

为了安全，置换表一般需要很大；另一方面为了方便记忆和存储，置换表都有一些规律；还可以构造多个置换表：置换1置换2置换1置换2置换1置换2希腊时代的恺撒密码，将英文字母移位一个固定的值。

明文字母a

b

c

d

e

f

g

h

i

j

k

l

m密文字母DE

F

G

H

I

J

K

LM

N

O

P明文字母n

o

p

q

r

s

t

u

v

w

x

y

z密文字母Q

R

S

T

U

VW

X

Y

Z

A

B

C例题：（代替密码）

attackateighttomorrow

DWWDFNDWHLJKWWRPRUURZ明文字母a

b

c

d

e

f

g

h

i

j

k

l

m01

2

3

4

5

6

7

89101112明文字母n

o

p

q

r

s

t

u

v

w

x

y

z13141516171819202122232425

加法密码：从运算上代替密码可分为（等）：乘法密码：仿射密码：

置换（换位）密码：打乱明文各字母的顺序。代替（换元）密码：将明文字母用密文字母代替；单表古典密码：始终采用同一个明密对照表的加密；多表古典密码：

变化使用多个明密对照表的加密。例题：Viginere密码（多表代替，1523-1596）明文：vigenerecipher密钥：camelcamelcame--密文：XISIYGRQGTRHQY（见下页表。把所有移位都列出来。）

杰弗逊“轮子密码”：

美国总统托马斯.杰弗逊于1790年左右发明的一个器

械密码。这种设备是后来的机械和机电密码机的基础。机电式密码：电报和加解密做在一起，即密码电报；多表代替汉字密码：每个汉字编写为一串十进制数字（密码本）恩格尼玛密码机

1．2

统计攻击英文单个字母的统计特性单表代替不能掩盖统计特性：

还有字母串的分布：2字母串分布、3字母串分布

attackateighttomorrow

DWWDFNDWHLJKWWRPRUURZ针对单表代替的攻击：（1）截获一定数量密文，统计各个字母出现频次；（2）将出现频次高的密文字母，猜测为明文字母

d、t、a等；（3）猜测其他字母；

（4）反复验证。

例题：

任选两个字母，相同的概率。

粗糙度假设-检验攻击方（Adversary）防守方（Defender）

防守强度攻击强度

密码学（Cryptology）包括：

密码编码学（Cryptography）----设计

密码分析学（Cryptanalysis）----破译

1．3一次一密和迭代密码Vernam密码：

尽可能增加表的长度（很长的密钥流），

而加密就是简单加法，解密就是减法。（1）将明文转为二进制串；

（2）产生与明文一样长的随机二进制串（密钥）；

（3）明文与密钥逐比特异或（模2加）；

（4）解密时密文再与同样的密钥逐比特异或。序列密码的萌芽乘积密码：

将置换与代替结合使用，并进行多轮。

S盒：代替(substitute);

P盒：置换(Permutation)分组密码的萌芽公开1949年，香农发表：

“CommunicationTheoryofSecrecySystems”，

定义理论安全性，提出扩散和混淆的乘积方法。

信源信道信宿干扰通信的任务是把信息有效地、可靠地传递到信宿。

手段是编码（coding）。

平均每个符号的信息量

X是信源;

Y是信宿

含义：损失熵等于明文熵，

信宿端从密文得不到明文的任何信息；

明文信息“皆损失在信道中”；

（皆被加密过程所掩盖。）

含义：密钥熵（不确定性）大于等于明文熵，

密钥信息要能够掩盖住明文信息；

熵越大，用于表示信息的符号长度越长，

即密钥长度要大于等于明文长度。密码体制(模型)：明文空间M：所有明文构成的集合密文空间C：所有密文构成的集合密钥空间K：所有密钥构成的集合加密算法Ek：由k确定的加密算法解密算法Dk：由k确定的解密算法

从空间中随机选取OneTimePad:一次一密（1）密钥与明文一样长；（2）密钥必须是真随机的；（3）密钥只能对一个密文进行加密。

可证明了这一体制是无条件安全的。但只具有理论价值，实际中：（1）难以做到密钥与明文一样长；

（3）真随机的密钥难以实现；

（4）每次更换密钥，效率太低。发展为现代序列密码可通过以下手段达到计算安全性：扩散(diffusion)：明文与密文的关系尽量混乱；混淆(confusion)：密钥与密文之间的关系尽量混乱。理论安全：不泄漏任何信息，不依赖敌手的计算能力。计算安全：计算上困难的，依赖于敌手的计算能力。实际中：置换（P盒）实现扩散；代替（S盒）实现混淆。

二者乘积并多次迭代可达到足够的安全性。发展为现代分组密码攻击=计算困难问题1977年，数据加密标准DES算法被公布；

DES----DataEncryptionStandard

乘积密码的典范；现代分组密码的第一标准。加解密算法公开保密的只有密钥处理二进制数据1976年，Diffe和Hellman提出公钥密码思想；

解决对称密码中建立和管理密钥的问题；

加密用公钥，解密用私钥。私钥还可以数字签名。箱子变邮筒密码学新方向!密码学加密：实现保密性认证：实现认证性1978年，出现第一个公钥加密算法：RSA。因此：加密算法分为对称加密、非对称加密；对称加密又分序列密码和分组密码两种类型；认证技术主要有：数字签名、Hash函数和认证协议。构成密码学的主要(基本)内容!计算机内部处理的是二进制串：

二进制串（0和1组成的串）不仅可以表示数，

还可以表示各种符号等其他数据。

比特（bit：binarydigit）：

每位二进制串中的符号称为1比特（bit）；

不论是1还是0，都算1比特。（信息的单位）

ASCII码（American

Standard

CodeofInformationInterchange）：

128个常用符号编码为128个整数（对应二进制串），

扩展的ASCII码表示另外附加128个符号。将键盘符号转变为二进制码

编码译码加密解密认证认证信源信道信宿噪声网络（安全）信息处理系统：从功能上看：

从内容上看：

保密性

认证性

安全多方计算

对称密码

公钥密码杂凑函数

密码协议安全性定义、设计（编码）、实现和分析（攻击）(含身份认证)可视为三个发展阶段模运算的性质：

同余运算的性质：

1．4相关数学概念和算法加法群：（additivegroup）集合上定义一种运算（+），有单位元，都有逆元。

二种运算！

＋0100111001000101

＋01234001234112340223401334012440123×123411234224133314244321都有加法逆元即负元

＋012345001234511234502234501334501244501235501234×12345112345224024330303442042554321整数集合模素数p构成剩余类域Zp；整数集合模合数n构成剩余类环Zn。有限域有限环无限的代数结构：Z：整数环；Q：有理数域；

R：实数域；C：复数域。

两种运算都构成群（并有分配律）的就是域例题：

商辗转剩余361241221200结论：公因子是每个余数的因子；

每个余数都可以写成输入二数的线性组合。商辗转剩余268321211剩余表示为36和24的和36的系数24的系数1236-1*241-1024-2*12=24-2*（36-1*24）=（-2）*36+3*24-23剩余表示为26和3的和26的系数3的系数226-8*31-813-1*2=3-1*（26-8*3）=（-1）*26+9*3-19

求乘法逆：扩展的欧几里得算法。辗转26108301121-81-19

古典密码中的Hill

密码：如何计算逆矩阵？利用初等行变换利用伴随矩阵注意是mod26运算！

例题：维数可以增加可采用下面模逆算法：i026101211012241-2313-25413-7

习题一：（可选择教材中习题。）第一章古典密码

至此结束！第二章序列密码

2．1概述

2．2线性反馈移位寄存器

2．3m序列及其性质2．4对偶移位寄存器2．5

B-M算法2．6非线性组合与算法举例

2.1概述序列密码将明文编码为比特串:

同时产生与明文相同长度的密钥流:

或者GF(p)效仿一次一密加密方式：

（1）密钥和明文长度相同；

（2）每次加密采用不同的密钥；

（3）密钥是随机的。古典密码中的

Vernam密码（1917年）：

但密钥如何实现？伪随机数发生器：产生性能接近随机的二进制序列。种子密钥序列密码主要任务：设计安全的伪随机密钥产生器。对KG（KeyGenerator）的基本要求：（1）密钥量大；（2）极大周期；（3）理想分布；（4）非线性度大；（5）推测K是计算不可行的。KG非线性移位寄存器（NFSR：Non-linearFeedbackShiftRegister）

－－－－M序列（周期最大）线性反馈移位寄存器（LFSR：Linear

FeedbackShiftRegister）

－－－－m序列（周期最大）线性移位寄存器的非线性组合（实用的）序列密码与分组密码的比较：（1）序列密码：

处理速度快，实时性好；

适用于军事、外交等保密系统。

但是适应性差，需要密钥同步。（2）分组密码：

不需密钥同步，较强的适应性；适宜作为加密标准。

但是加密速度稍慢，错误易扩散和传播。

(但比公钥密码快得多，软件上约100倍。)2．2线性反馈移位寄存器1.反馈移位寄存器KG！

例题-1：初始状态：s0＝101f10110111111011011011移位寄存器的一个状态（开始时为初始状态）：反馈函数

反馈寄存器的状态序列：必然是周期的！因为状态有限，进入一个相同状态后则重复。当触发脉冲到来时，寄存器状态移位更新为一个新状态。

例题-1的输出序列：10111011…..完整的状态图：如何使状态都在一个圈里？这样周期最大。2.线性移位寄存器-LFSR(Fibonacci-LFSRs)反馈函数为线性函数（否则为非线性反馈移位寄存器）

称为结构常数。

结构常数反序是为了将来有理表示方便（不必求互反多项式）。例题-2：

这是一个4阶线性反馈移位寄存器：4-LFSR。

布尔函数！f110001000011000110001101111010110100001000

初始状态记为：

最重要的关系！结构常数不动

可以划出相应的状态转移图。

图形和公式是对应的

上例中：反馈函数为,

初始状态:(1000)，输出序列:(1000110)

，周期为7初始状态:(0010)，输出序列:(0010111)

，周期为7

初始状态:(0110)，输出序列:(0110100)

，周期为7

第三个初态！第一个初态！第二个初态！

反馈函数为：初始状态:(1000)，输出序列:(100010011010111)

，周期为

初始状态:(0110)，输出序列:(011010111100010)

，周期为

的序列称为n阶m序列。另一：f110001000010000100001001110011000110001101111010f111010110101001011110111001111111110111100111000110001续前：第二个初态！第一个初态！只要进入，就得循环！

结论：（1）n-LFSR的结构由其结构常数唯一确定；（2）n-LFSR的结构常数与反馈函数互相唯一确定；（3）n-LFSR序列由其结构常数和初态唯一确定；（4）一个n-LFSR可以产生个不同序列；（5）一个n-LFSR的序列的最大周期是。关键问题：如何产生m序列？LFSR的联接多项式为本原多项式。f(x)称为线性移位寄存器的联接多项式或生成多项式。

3.LFSR的有理表示

a(x)称为序列的形式幂级数或生成函数。--S(f(x))LFSR的有理表示：其中g(x)是次数小于n的多项式：a(x):表示输出序列f(x)：表示结构常数g(x)：与初态、结构常数相关

序列空间定理-1：n-LFSR有理表示中g(x)的次数小于n。证明：因为迭代关系：

LFSR:g(x)的系数和结构常数与初态都有关系。DSR

：g(x)的系数就是初态。（后面讲）

当初结构常数序号与寄存器序号反向，就是为了此处。

另一简单方法求g(x)：

消最低项的长除法可求a(x)：2.3、m序列及其性质1.如何构造m序列例题-4：

设的有理表示为，求其序列表示。解：通过消最低项的多项式除法，得到：

升幂排列消最低项另一种方法：定理-2：周期为p的序列的（非最简）有理表示为：证明：

所以：分子多项式的系数（含常数项）为一个周期；分母二项式的次数为周期。

例题-5：求产生序列（100111）∞的最短的LFSR。

多项式的辗转相除法阶数最少！最简有理表示

任何一个（周期）序列都可以表示为：

此即研究多项式形式的原因

定理-3：当f(x)为本原多项式，产生的序列为m序列。

nFeedbackpolynomialPeriod23374155316637127不止一个！是一个本原多项式。初态为(10101)，求序列的表示。例题-6：两种基本方法：（1）画出结构图，进行迭代，得到状态图。（2）求出有理表示，进行长除法，得到一个周期。（1010111011000111110011010010000）∞设一个序列的联接多项式为

随机性如何？m序列的取样:设

是Fq上的一个周期序列s

是一个正整数，令：称为序列的s采样。定理-4：若是周期为p的m序列，则

2.m序列的伪随机性形如的子序列段称为一个长为k的1游程；形如的子序列段称为一个长为k的0游程。

（1）分布特性：（2）相关特性：随机性的三个特性：s是序列的长度

（3）游程特性：0游程

证明：将游程数目转化为状态的数目。

状态最终都会出现在序列中！一个周期序列圈m序列特点：每个非零状态都出现，且只

出现一次！状态都在序列中！

序列圈中，长为i的1游程总会体现为：存在以下形式的状态(一一对应！)在序列圈上数游程个数，都是从011…10开始。即使在******中也有，以后也会被数到，没有遗漏。输出序列的圈

看序列图上的状态，游程最终要显示在序列圈上。输出序列的圈所以当游程个数为现在只剩下的游程个数：n长的1游程有1个，

因为在状态圈中，有一个全1状态：111….1；没有n长的0游程，因为没有全0状态；n-1长的0游程有1个；所以共有游程：不可能有n+1的1游程：不会有n-1长的1游程：因为不可能有两个全1状态，且相连；因为以下三个状态是相连的：（否则全1状态不会出现。）且每个状态在状态圈中，只出现一次；所以011..11与11..110不会连着出现（连着才会出现n-1长的1游程）。m序列特点：一个周期内,每个非零状态都出现，且只

出现一次！（3）相关系数的证明:

任意5级m序列的周期环上，有个0，有16个1。

＝1111100110’1001000010’1011101100’0……，是由本原多项式产生，所以是5级m序列。其周期中，15个0，16个1。游程总数：长为1的1/0游程：长为2的1/0游程：长为3的1/0游程：长为4的0游程一个，长为5的1游程一个。算游程时首尾相接例题-7：

LFSR（DSR:DualShiftRegisters）DSR2．4对偶移位寄存器LFSR：也称FibonacciLFSRsDSR：也称GaloisLFSRs

DSR的特点：DSR也是LFSR，这样称呼只是为了区别开1.DSR的状态转换（或称迭代过程）

例题-8：4－DSR

序列为：（1101000）

开始循环11000111010011111110000010001000100状态不是每位都输出初态为（1110）时，序列为（1000110）

相同的联接多项式4-LFSR

但是：如果上例的LFSR的初态是1101，

输出序列为：（1101000）

，

与初态为1000的DSR输出序列相同。因此相同的结构常数，DSR和LFSR可产生相同序列。2.DSR的有理表示a(x):表示输出序列f(x)：表示结构常数g(x)：表示初态！DSR也具有有理表示：一方面：利用DSR的递推公式所以输出序列为

定理-6：DSR序列的有理表示中：证明：其系数就是DSR的初态：另一方面：利用消最低项方法有理表示等式的两边相同，得证。

由此可得到DSR的设计思路

例题-9：解：（1）LFSR的结构常数为（0,1,0,1）

初态为（0,1,0,0）。（2）DSR的结构常数为(0,1,0,1)，结构图即

或者：所以DSR和LFSR是等效的。

总结：4.当链接多项式f(x)为本原多项式时，产生m序列。

2.对于LFSR，g(x)的系数由初态和结构常数确定；

对于DSR，g(x)的系数即为初态；产生同一序列（具有相同有理表示），LFSR和DSR

的初态不同；另外：有理表示还可以扩展为假分式的情况，例如：

对应的LFSR的图示为：(退化的7-LFSR)

非周期部分的位数有3位，对应的退化寄存器个数为3。线性复杂度：生成序列所需最小的LFSR寄存器个数。本例中，序列的线性复杂度=4+3。2.5B-M算法线性反馈移位寄存器虽然易于实现，但是不安全的，如果知道两个周期，就能通过B-M算法解出生成多项式。已知阶数B-M算法不需任何前提，求出序列段的线性综合解：是一种迭代算法：阶数对于n阶线性移位寄存器，已知2n序列段，通过解方程组，可以求得对应的结构常数还可用于循环码译码等。还有Berlekamp算法：用于分解多项式。B-M（Berlekamp–Massey）算法：

迭代型求解序列生成多项式的算法。（且不必事先知道寄存器阶数）未知阶数规定：f(x)=1表示0阶线性移位寄存器的联接多项式，（长度为n的全零序列由0阶线性移位寄存器产生。）

且记计算对于，重复第二步和第三步N次，即可求出若（a）如果（b）否则，存在（3）若，取逐次试验联接多项式的方法！输出：<1+x3+x4,4>同一行中最后才算dn！d=1才算m！写在fn+1的上一行例10：输入S8=10101111

当前结构常数：当前状态

逐一试验上题的解释：（上述过程熟练以后，仅用表格形式做即可！）

例题-11：输入：S10=0001101111

注意：

SN是N长的序列，B-M算法仅保证产生这N长序列。如果序列是周期的，例如则需要计算2个周期的序列，才能保证综合解产生的序列是周期的。序列的线性复杂度：（可见前面71页）

产生该序列的最短LFSR的阶数。对于输入序列，用BM算法得到的f(x)的次数就是其线性复杂度。解决线性反馈不安全性有两种方式：非线性反馈：大M序列线性反馈的非线性综合非线性反馈移位寄存器：反馈函数是非线性的布尔函数；但实现和分析上较为复杂。1.非线性综合2.6非线性综合与算法举例对一个或多个线性移位寄存器进行非线性综合可获得安全性能良好的非线性序列。有几类：

非线性综合：非线性滤波生成器非线性综合生成器

LFSR2LFSR1钟控方式：f1f2LFSR1LFSRncz

带记忆组合生成器

A5序列密码算法使欧洲GSM标准中规定的加密算法，用于数字蜂窝电话加密，现已被基于分组方式的取代。2.A5算法19阶、22阶、23阶。19+22+23=64bit

3.ZUC算法（我国商密标准算法）比特重组32bit寄存器两次使用2个8*8的S盒32bit寄存器

习题二：（可选择教材中习题。）第二章序列密码至此结束！第三章分组密码

3.1概述

3.2DES（数据加密标准）3.3AES（高级加密标准）

3.4SM4（我国商用分组算法）

3.5分组密码的工作模式3.1概述为了克服统计分析，可以采用扩散和混淆两种基本方式。扩散：就是使明文的每一位影响密文中的许多位，这样可以隐蔽明文的统计特性。

混淆：密文的每一位受密钥尽可能多位的影响。

使密文和密钥关系复杂，从而统计分析更加困难。

换位变换可以实现有效的扩散，打乱明文字母之间、

字母组合之间的统计关系。

代替变换(非线性的)可以达到比较好的混淆效果。

不论是数、还是其它信息，经过编码后都变为二进制串，可称之为数据。如果对其加密，数据就是明文：11001011’10110010’

01101010’11101011’……..分组密码的加密是每次对一段明文进行加密，类似古典密码的多表密码：

……..每个明文段叫作一个明文分组，对应密文叫作密文分组。明文分组密钥密文分组En明文分组密钥密文分组De01…1101…P盒－permutationbox;S盒－substitutionbox。SP结构（替代－置换网络）：每轮处理整个分组明文，加解密算法不同。分组密码的整体结构有两种基本类型：（迭代类型）Feistel结构：每轮处理一半明文，加解密算法相同。DES是Feistel结构的代表；AES是SP结构的一个代表。乘积密码系统是S盒与P盒变换的组合，两者结合得到的密码系统比单独一种更强。这一方式成为数据加密标准DataEncryptionStandard(DES)的基础。

Feistel结构SP结构En

分组密码：

多次迭代一个轮函数，同时处理一组明文段。

密钥长度固定，且对不同明文段保持不变。序列密码：

产生（伪）随机的密钥流，每次处理一个明文字母。

加密过程简单，但需要密文与密钥同步。分组密码适用性更广，易于标准化；序列密码主要用于保密性，速度更快，可实时通信。

3.2DES（数据加密标准）DES（DataEncryptionStandard）从1977年提出（原计划用10年）到1997年被认为不安全，经历了20多年，是分组密码设计的一个典范。

一、DES的加解密过程

明文分组：64bit(即64位二进制串)密文分组：64bit密钥：64bit，其中8bit为校验位，实际56bit轮数：

16轮（圈）加密函数：8个6-4S盒；P置换。整体结构：FeistelLRLRLRIP-1IP16轮64bit64bit算法：整体结构步(轮)函数密钥扩展密钥扩展ffDES整体结构：32Bit！32Bit！64Bit！48Bit！一共16轮！64bit！注意：最后一轮不交换！DES的加密函数f：8个不同的6-4S盒！48bit！48bit！32bit！4×8=32bit查表！扩展并置换查表：输入6比特的首尾2位确定行，中间4位确定列，交叉处为输出。密钥扩展：64bit输入密钥！56bit－去掉8、16等8个监督位56bit48bit28bit循环移位，1、2、9、16轮左移1位，其它轮左移2位!Feistel结构：记住这个特点即可！！加密解密密钥反序L在右侧加两次，消掉！明文

M(8bit)IPT0(4bit)T1(4bit)f(T1,K1)T1(4bit)T2(4bit)IP-1密文组C(8bit)密钥K(8bit)P1C0(4bit)D0(4bit)4-置换Qf(T2,K2)T3(4bit)T2(4bit)4-置换RC1(4bit)D1(4bit)4-置换Q-14-置换R-1P2K1(6bit)C2(4bit)D2(4bit)P2K2(6bit)小DES（1）如果密钥扩展过程中，

P1=(41768253)，

P2=(571842)，Q=(3142)，R=(4312)，

输入主密钥为K=11001010，

求经密钥扩展后的K1和K2。（2）如果IP=(86421357)，

f函数如左图所示，

两个S盒见下页。S1P=(3,1,2,4)f(T,K)(4bit)K(6bit)E=(4,1,2,2,3,4)T(4bit)T’(6bit)Z2(3bit)Z1(3bit)S2U2(2bit)U1(2bit)(第1bit决定行,第2、3bit决定列)解：（1）经置换，C1D1=10010101，经P2得K1=001110C2D2=01100110，经P2得K2=010001。S101230301211320S201230213013021若已知明文01011100，在密钥K下得到的密文是什么？

并通过解密得到原明文验证加密的正确性。（2）T1=0010，T1’=000010，Z1=001，Z2=100U1=00，U2=11，f(T1,K1)=1001，T2=1110；T2’=011110，Z1=001，Z2=111，U1=00，U2=01，f(T2,K2)=0001，T3=0011，T4=1110，1111100001011100(86421357)01110010F

0010

1110

(54637281)

11111000

11001010(41768253)01100110(3142)F

0011

1110

(4312)10010101(2413)(3421)P200111001100110P2

010001

二、DES的特点

除密钥顺序之外，加密和解密步骤完全相同；

主要的批评：密钥太短，迭代次数可能太少，

S盒可能存在不安全隐患。

差分分析：通过分析明文对的差值（异或）对密文对的差值的影响来恢复某些密钥比特。

穷举攻击：现在人们利用网络计算可以在20多小时破译56位的DES。DES已变得不安全了。

线性分析：一种已知明文攻击，它试图建立起明文、密文和密钥之间的一组近似线性方程。

三、多重DES

为了提高安全性，防止穷举攻击，DES还有多重形式。

双重DES：

但存在中间相遇攻击：（已知一对明密文）穷举k2！穷举k1！

三重DES：

中间一层用解密形式是为了可以利用三重DES对单重DES加密的密文进行解密(

k1=k2或k2=k3)。DESk1mDESk2－1DESk3cDESk1－1DESk2DESk3－13.3AES（高级加密标准）

1997年美国国家标准技术研究所（NIST）征集AES(AdvancedEncryptionStandard)。

要求：（1）比三重DES快且至少与它一样安全；（2）分组长度为128bit；

密钥长为128bit，192bit和256bit；（3）算法要能抵抗已知的密码分析方法，无明显漏洞；（4）算法实现要有效率，有一定的灵活性（适应不同的环境），软硬件两种方法实现。15种算法参加第一轮评选，5种进入第二轮：

RC6、Rijndael、Serpent、Twofish、Mars2000年获胜者是Rijndael算法，是比利时密码设计者所作。

一、AES的加解密过程明文分组：128bit密文分组：128bit密钥：128、192、256bit轮数：10、12、14轮（圈）加密函数：8-8的S盒、P（行移位、列混合）密钥生成：扩展、递归总体结构：SP结构

10-14轮128bit128bit16个字节SP结构

AES是面向字节的算法：字节为最小单位进行处理。输入明文分组：128bit=16×8bit＝16个字节，排成4×4的字节数组，称为状态矩阵（StateMatrix）

按列排！轮函数就是对这个数组进行变换。乘以常数字（4字节）AES解密过程：加密过程的逆过程，需要相应的逆变换。

AddRoundKey：将每一轮的密钥与状态矩阵直接异或；

InvSubBytes：逆字节替代变换，需要8-8的逆s盒。InvShiftRows：逆行移位变换；InvMixColumns：逆列混合变换；

AES密钥扩展过程：

产生各轮子密钥，主密钥直接作为开始的轮密钥，

后面的由前面轮密钥字，经S盒等运算递归产生。

4个字节为1个字

AES中的列混合：AES是面向字节的算法——字节的运算！以下介绍字节替代和列混合这两个部件的实现原理二、AES中的运算

0000——0x00110——0x61100——0xC0001——0x10111——0x71101——0xD0010——0x21000——0x81110——0xE0011——0x31001——0x91111——0xF0100——0x41010——0xA0101——0x51011——0xB11000001——C1AES是面向字节的算法，最小单位是字节(Byte)。一个字节可用二位十六进制数表示。二进制串常表示为十六进制任意分组表示为128bit的二进制串，分为12个字节，每个字节表示为2位十六进制（省略0x），例如：

AES对此字节矩阵的处理即是对字节的运算，需要将所有字节组成的集合变为代数结构（可以加减乘除）。

仿照对“数”的处理，将这些数据视为“数”00000000=0x0000000001=0x01-----00001111=0x0F-----11111111=0xFF加、减、乘、除——域！运算结果还在此域中S盒——字节除法列混合——字节乘法1、中的运算（字节运算）

中一共有个元素，可以有多种方式表示，AES中用多项式表示（以便能进行乘/除运算）。

一个字节8bit：

对应多项式：

一个字节8比特，可以看作中的一个元素。例题：0x57即01010111，对应多项式：

对于域的加法就是多项式对应项相加，系数模二加：

‘57’

‘83’

01010111

10000011＝11010100‘D4’AES中两个字节相加的含义！对于域的减法，就是加上减法逆（就是本身）。对于域的乘法，要模一个8次既约多项式m(x)，AES中选取的

例题：‘57’·‘83’

对应：

二进制表示：01010111•10000011＝11000001十六进制表示：57•83＝c1AES中两个字节相乘的含义！

分配律！

复杂运算化简为简单运算的迭代都是乘x

乘一个x，相当于字节中的1左移1位

06=00000110=00000100+00000010=02+04

将一个字节表示为只有一个1的字节之和，而只有一个1的字节都是不断乘x得到的。

xtime()运算：x

b(x)

更高次的乘法可以通过重复使用xtime（）实现。

(1)如果，则xtime()运算就是左移一位，后补零；如果，则xtime()左移一位，后补零，再异或1b。

xtime()算法：例题：57

13=01010111

00010011

“13”=

00010011

=

00000001

+00000010

+00010000因此13=“01”+

“02”+

“10”字节13是16进制，不是十进制，十进制数对应19。

57

02=xtime(57)=xtime(01010111)=ae57

04=xtime(ae)=xtime(10101110)=4757

08=xtime(47)=xtime(01000111)=8e57

10=xtime(8e)=xtime(10001110)=0757

13=57

(01⊕02⊕10)

=57⊕ae⊕07=fe对于域的除法，也就乘以除数的乘法逆。一般地，可以利用多项式的扩展欧几里得算法求乘法逆。

例题：求多项式模的逆元。验证：表示为输入的线性组合两边模M(x),可得逆元。因为：或者采用以下迭代算法：每次剩余可表示为n与u的代数和。

注意顺序AES中规定：

53的字节代替。二进制为01010011，表示的域元素为例题：表示为二进制为11001010。

逆元为，

所以53代替为11101101，即“ed”。

注意顺序！2、系数在的多项式运算（字运算）

这时元素用多项式表示，就是系数在中的小于4次的多项式。

加法就是多项式对应项的系数相加，因此也就是中元素相加，即逐位模二加。

列混合是字的运算

AES中两个字相加的含义！乘法是多项式相乘后，模一个4次多项式，

AES中两个字相乘的含义！不是既约的：(01+01=00)

都成为四项之和为了进行解密，a(x)应当有逆。AES中的列混合：MDS码，最佳扩散性；重量轻，计算简单

例题：

AES列混合的性质：

混合前后两列的四个字节之和保持不变。

三、AES的特点

结构简单，适应性强；加解密结构相同，但是解密使用加密的逆模块；逆S盒逆S盒对于AES的攻击：主要利用AES代数结构的特点。

积分分析：通过预测几轮之后的积分值来猜测密钥。

代数攻击：用某种代数方程系统描述S盒。

侧信道攻击：加密中间过程电磁泄漏可能暴露密钥信息。

（sidechannelattack）（差分能量攻击）

AES的设计能够抵御已有的线性分析和差分分析；采用较大的S盒，并且能进行代数上的定义，而不像DES的S盒是“随机”代替（不易判断安全性）。宽轨迹策略Feistel结构SP结构En

3.4SM4（我国商用密码算法）SM4是2006年我国公布的商用分组密码算法。特点：分组长度和密钥长度都是128比特；加密算法和密钥扩展都是32轮非线性迭代；采用一个8*8的S盒；采用32bit的异或和移位运算L；结构为非对称的Feistel；加解密算法相同，只是轮密钥顺序颠倒。Electronic-CodeBook(ECB)：电码本模式Cipher-BlockChaining(CBC)：密码分组链接模式CipherFeedBack(CFB)：密码反馈模式OutputFeedBack(OFB)：输出反馈模式

为了防止攻击，分组密码需要有一定的工作模式。CFB和OFB两种模式：可利用分组密码实现流密码！3.5分组密码工作模式

（另外新的还有：计数器模式、加密认证模式等）这些模式适用于各种分组密码，以下仅以DES为例。DESDESm1c1km2c26464kDESkcnmnDES-1DES-1c1m1kc2m26464kDES-1kmncnECB模式（electroniccodebook）相同明文产生相同密文！以DES为例但这种模式存在以下问题：

相同明文对应相同密文。CBC

模式(cipherblockchaining)DESDESm1c1km2c2kDESkcnmn初始矢量Cn-1DES-1DES-1c1m1kc2m2cn-1初始向量kDES-1kmncn64-j位j位j位64-j位DES64-j位j位

DESj位64-j位j位64-j位

64-j位j位DESm1c1k移位寄存器jm2c26464jkkmncnCFB模式(cipherfeedback)64-j位j位j位64-j位DES64-j位j位

DESj位64-j位j位64-j位

64-j位j位DESm1c1k移位寄存器m2c26464kkmncnCn-1解密模式也用DES加密64-j位j位j位64-j位DES64-j位j位

DESj位64-j位j位64-j位

64-j位j位DESm1c1k移位寄存器jm2c26464jkkmncnOFB

模式(outputfeedback)密文错误不会传播！64-j位j位j位64-j位DES64-j位j位

DESj位64-j位j位64-j位

64-j位j位DESm1c1k移位寄存器m2c26464kkmncn计数器模式：DES

DES

DES

习题

三：（可选择教材习题。）第三章分组密码至此结束！第四章杂凑函数

4.1

概述

4.2SHA-1和SHA-2

4.3SHA-34.4我国商密标准SM3

4.

5

MAC和认证加密

4.1概述认证（authentication）：

采取一些措施保证实体（entity）是他们所宣称那些

人，或消息不被非法者修改。

两类基本认证：

身份认证（identificationorentityauthentication）

双方在线、实时，例如电话；消息认证（messageauthentication；或

数据源认证dataoriginauthentication)

单向、可延时，例如E-mail。数据完整性（DataIntegrity）：

保证消息的不被修改（但不含数据源合法性）。实现数据完整性：

应用抗碰撞的杂凑函数，检查摘要值。实现消息认证：

消息认证=完整性+数据源认证

采用：有密钥的杂凑函数（消息认证码-MAC）；

数字签名等。另外：在数字签名中：

用杂凑函数将消息进行压缩后，对摘要值签名；在随机数产生器中：

用杂凑函数的摘要值作为随机数；因此，杂凑函数是密码学中最常用的部件之一。实现区块链的基本工具！杂凑函数（算法）：

将任意长输入的消息压缩为短的摘要值。有密钥的杂凑函数（MAC：MessageAuthenticationCode）有两个输入：密钥和消息。给定消息，只有知道密钥的人可计算MAC。

无密钥的杂凑函数（MDC：ModificationDetectionCode）只有一个输入即消息。

给定消息，任何人都可计算hash值；一般，将无密钥的杂凑函数就叫做杂凑函数；而将有密钥的杂凑函数叫做消息认证码MAC。杂凑函数的安全性：

抗原象性(pre-imageresistance):

由y=h(x)计算x是计算困难的；yxxx’yyx’x

生日问题：最少多少人中有人生日相同，概率大于50%？

不相同的迭代结构＋压缩函数杂凑函数的构造：最常见的Merkle-Damgard(MD)迭代结构利用分组密码工作模式-构造杂凑函数：利用分组密码的密码分组链接模式CBC和密码反馈模

式CFB。Ekx1y1kx2y2kkH（x1..xn)yn初始矢量EkEkCBCCFBx1y1kx2kkH（x1..xn)xn初始矢量EkEky2Ek直接构造f函数：采用类似分组密码的基本部件和基本运算，构造伪随机函数（避免分组密码中不必要的密钥扩展过程）。利用模运算构造f函数：采用第五章介绍的公钥密码的方法，从单向函数设计压缩函数。MASH-1国际标准，采用模平方运算；利用格计算问题设计的SWIFFT算法；利用纠错码设计的FSB算法；虽然具有较好的理论基础，但实现效率仍有差距。SHA-1和SHA-2是美国（NIST）杂凑函数标准算法。（SHA：StandardHashAlgorithm）

4.2

SHA-1和SHA-2这是一系列杂凑函数MD4、MD5的发展，共同特点是：采用简单的运算多次迭代构造压缩函数。

被攻破的MD4、MD5的轮函数

轮常数消息子块每个512比特消息块分为16个32bit的消息字，经扩展，形成80个（步）的消息字；最后将输入链接值反馈到输出，保证压缩函数单向性。

2002年美国NIST根据实际情况，增加了Hash算法

输出长度，形成SHA-256、SHA-384、SHA-512，

这些算法统称为SHA-2。2004年又提出SHA-224。SHA-2：SHA-256的输出为256bit，链接值分为8个字，压缩函数整体迭代64步，没有明显的轮界限。

SHA－256步运算SHA-224：

与SHA-256初始值不同；

输出从256bit左端截取224bit。SHA-512：

每个字64bit，链接值为512bit；

消息分块为1024bit；迭代89步；SHA-384：

与SHA-512初始值不同；

输出从512bit左端截取384bit。名称输出长度消息块长度字长度轮数*每轮步数SHA-1160512324*20SHA-224/256224/256512321*64SHA-384/512384/5121024641*80我们国家商密标准杂凑函数是SM3关于MD-5、SHA-1的攻击

关于MD结构的攻击2004年，A.Joux提出了多碰撞攻击，已知碰撞时

找到多碰撞很容易；2005年，J.Keley等提出长消息的第二原像攻击，

降低了复杂度，但需要较长的消息；2006年，J.Kelsey等提出了Herding攻击，已知碰

撞时产生有意义的第二原像。第一阶段：（2007年）在全世界征集了51个算法；第二阶段：（2010年）剩余14个算法；第三阶段：（2011年）剩余5个算法；(BLAKE、Groestl、JH、Keccak、Skein)2012年10月初

最终获胜者是Keccak。美国NIST关于SHA-3的征集活动：

4.3

SHA-3Keccak：整体结构为Sponge结构，好处是输出任意长；结构具有一定的可证明安全性。1600bit置换1600bit状态，外部状态r长度，内部状态为c长度；初始值为全0，排列为5*5*64的三维