现代密码学期末重点（备考ing）

密码学概念

密码技术：把可理解的消息变换成不可理解的消息，同时又可恢复原消息的方法和原理的一门科学或艺术，密码学技术可以使消息的内容对（除发送者和接受者外的）所有人保密

四种密码学攻击方法

唯密文攻击
条件：拥有密文、密码体制和密文信息的一般了解
目的：1.尽可能恢复明文 2.推算密钥破译其他加密消息

已知明文攻击
条件：许多密文，一些明文-密文对
目的：推算密钥->解密使用同一密钥的密文

选择明文攻击
条件：一定的明文-密文对，可使用特定明文加密->产生更多密钥信息
目的:推算密钥或算法（使用同一密钥的密文有通用性）

选择密文攻击
条件：密文和对应解密的明文
目的：密钥和其他密文

什么是公钥密码？

公钥密码学（也叫非对称加密）是一种使用**一对密钥（公钥和私钥）**进行加密和解密的加密方法。
公钥是公开的，任何人都可以使用它加密信息；而私钥是保密的，只有密钥的拥有者才能使用它解密信息。公钥和私钥是数学上配对的，公钥加密的信息只能用对应的私钥解密

什么是对称密码？

加解密都使用同一密钥

什么是无条件密码？

基于信息论的安全性加密方法，即其安全性不依赖于计算的复杂性或破解的难度，而是通过理论证明确保其无法被破解(计算资源再大也无法破解)
例如：

一次性密码本（One-TimePad，OTP）：这是一种典型的无条件加密方法，使用一个与消息等长的随机密钥来加密消息。只要密钥是随机的、一次性使用，并且与消息长度相等，消息就无法被破解，具有无条件安全性。

中国剩余定理（必考）

什么是原根

定义： 对于一个给定的数 n，如果存在一个数 g，使得通过不断地将 g 进行幂运算（即 g 的不同次方）后取模 n，可以生成所有与 n 互质的数（也就是与 n 没有共同因数的数）的集合，那么这个数 g 就被称为 n 的一个原根
应用于： Diffie-Hellman密钥交换 和 ElGamal加密
理解：求模n的原根？
找出一个数g，使得g的幂次方对n取模后的余数覆盖所有与n互素的数（与n互素只需要找齐比n小的那些即可）

例子：找出模 5 的原根首先，我们需要找出所有与5互质的数。由于5是质数，除了1和5本身，所有小于5的数都与5互质。因此，1、2、3、4是与5互质的数。接下来，找一个数 g，使得通过不断计算 g 的幂并取模5，能够生成1、2、3、4这四个数。尝试 g = 2：2¹ mod 5 = 2
2² mod 5 = 4
2³ mod 5 = 8 mod 5 = 3
2⁴ mod 5 = 16 mod 5 = 1
通过这个过程，我们得到的结果是2, 4, 3, 1。这覆盖了所有与5互质的数（1, 2, 3, 4），所以 2 是 5 的一个原根。再尝试 g = 3：3¹ mod 5 = 3
3² mod 5 = 9 mod 5 = 4
3³ mod 5 = 27 mod 5 = 2
3⁴ mod 5 = 81 mod 5 = 1
结果是3, 4, 2, 1，这也覆盖了所有与5互质的数。所以 3 也是 5 的一个原根

什么是阶

定义：对于一个给定的数 g 和模 n，g 的阶是最小的正整数 k，使得 gᵏ ≡ 1 mod n
解释：g 的阶是 g 被不断地乘以自己，直到结果在模 n 下等于 1 所需要的最小幂次 k
判断原根应用：如果一个数的阶等于 φ(n)，那么这个数就是 n 的一个原根
在我们的例子中：
φ(5) = 4
2 的阶是 4，所以 2 是 5 的一个原根。
3 的阶是 4，所以 3 也是 5 的一个原根。
4 的阶是 2，不等于 φ(5)，所以 4 不是 5 的原根

经典密码学

密码体制

密码体制是六元组
变换即置换

什么是列置换？

**列置换密码：**明文遵照密钥的规程按列换位并且按列读出序列得到密文
举例：列置换加密------变换即置换
将明文按行写入矩阵，按列读出矩阵

列置换解密：

分组密码

什么是分组密码
一种对称加密算法 分为多个固定大小块->同一密钥按块加密->分块组成密文
明文分成固定长度的块（通常为128位、64位等），分别对每个块进行加密处理。
每个分组（块）通过相同的密钥进行加密
最终得到的密文是这些分组加密后的结果

分组密码运行模式

分组密码只能处理固定长度的明文分组，而实际的明文长度通常无法整除分组长度，所以需要采用 分组密码工作模式 来处理更复杂的加密需求

ECB电码本模式

ECB(electronic codebook)最简单的运行模式，发送少量分组数据
1.一次对一个64比特长的明文分组加密，
2.每次的加密密钥都相同（因此明文分组相同则密文分组相同），如图4.10所示。
当密钥取定时，对明文的每一个分组，都有一个惟一的密文与之对应。
因此形象地说，可以认为有一个非常大的电码本，对任意一个可能的明文分组，电码本中都有一项对应于它的密文。

CBC密码分组链接模式

让重复明文分组产生不同的密文分组
原理：输入是当前明文分组和前一次密文分组的异或
解密也因此不同：每一个密文分组被解密后，再与前一个密文分组异或得出真正的明文分组
前后关联的链接式加密缺陷：错误传播–某处加密错误后续解密皆错，但解密时仍只有该处出错
适用：
长度大于64比特的消息、用户鉴别

CFB密码反馈模式

原理：加密过程转化为一种流加密模式->前一个密文块的一部分与当前的明文进行异或来加密数据。反馈机制逐步加密数据流而非一次性加密
加解密对称（即加密解密过程相同）
特点：
1.流加密：按字节进行加密（非块），适合比特或字节形式的数据
2.误差传播

OFB输出反馈模式

消息作为比特流
分组加密的输出与被加密的消息相加
比特差错不容易传播

DES

 明文和密文分组长度为64比特
 算法包含两部分：迭代加解密和密钥编排
 Feistel结构（加解密相似）：加密和解密除密钥编排（即密钥自己顺序不同）不同外, 完全相同
（思考：1 为什么解密函数不是逆函数？（因为密钥子集是反向的）2 为什么不用逆函数来解密（解密操作可以使用加密的相同结构，只是需要倒序应用密钥子集））
 密钥长度：56比特（DES的密钥空间：2^{56}），每7比特后为一个奇偶校验位（第8位），共64比特
 轮函数采用混乱和扩散的组合，共16轮（轮次写16，包考的）

DES弱密钥半弱密钥？

必考：弱密钥4个，半弱密钥12个
弱密钥：
EK（m）=Dk(m), 有4个
半弱密钥：
K1不等于K2, 但Ek1(m)=Ek2(m).
至少有12个半弱密钥。
弱密钥：
若密钥 k 使得 加密函数与解密函数一致：Dk§=Ek§对所有明文P成立，即为弱密钥。
解释：明文P+弱密钥k加密=密文Q，则Q+弱密钥k加密=明文P
半弱密钥（成对出现）：
存在一对密钥 𝐾1和 𝐾2 ，使得当一个密钥用于加密时，另一个密钥用于解密，会导致加密和解密结果相同。

重点例子，课堂要求：弄清楚16轮中每一轮的明文与明文是什么（鄙人觉得大概率不会考这么复杂）

IP置换表，初始置换对照下表进行输出。即按照明文第58bit、50bit、42bit的顺序进行输出，该序输出即为置换后的明文

AES（了解）

老登暗示：AES处理单元为字节，DES处理基本单元为bit

前n-1轮的四个变换组：
字节代换->行移位->列混合->行密钥加

Rijindael（该算法确定为AES标准）特点（作为补充）

1. 不属于Feistel结构
2. 加密、解密相似但不对称
3. 分组长度灵活：支持128/32=Nb数据块大小
4. 密钥长度灵活：支持128/192/256(/32=Nk)密钥长度
5. 有较好的数学理论作为基础
6. 结构简单、速度快
7. Rijndael的操作简单，并可抵御时间和能量攻击，
8. 它还有许多未被特别强调的防御性能；
9. Rijndael内在迭代结构显示良好潜能来防御入侵行为。

概念要熟知

列混合？

老登布置过作业 ，解答过程太长，暂时赌他不考
学习这个B站视频

字节代换的作用：是扩散？是混淆？至少20字 （必考）

该题由老登上课暗示
答案（GPT给出）：是混淆作用，字节代换通过使用S盒进行非线性替换，打乱了明文的比特位模式，增强了密码的安全性。
解释：字节代换是通过非线性替换操作（使用S盒）将每个字节替换为另一个字节，从而改变了明文的每个比特位。这种替换操作使得密文与明文之间的关系变得更加复杂，无法直接从密文推断出明文。通过这一过程，原始数据中的模式被打乱，增加了密码系统的复杂性和安全性

AES与DES扩散的区别？至少五条（必考）

该问题由老师上课暗示，极大概率考
AES与DES扩散的区别：（答案暂由GPT生成）
扩散机制：
DES：通过Feistel结构，采用置换和异或操作进行扩散。
AES：通过替代-置换网络（SPN）结构，采用字节替代和列混淆操作进行扩散。
扩散速度：
DES：扩散较慢，需要16轮才能充分扩散。
AES：每轮加密就产生较强的扩散。
扩散范围：
DES：每轮扩散仅影响数据块的一部分。
AES：每轮扩散整个数据块，扩散更广泛。
轮数与扩散强度：
DES：16轮加密才达到较好的扩散效果。
AES：更少的轮数（10、12、14轮）即可实现强扩散。
数学操作：
DES：依赖于S盒和P置换，扩散效果较为简单。
AES：通过字节替代和列混淆的复杂操作实现强扩散。

序列密码

概念：对称加密算法，它通过生成一个伪随机密钥流（Keystream），将该密钥流逐位或逐字节地与明文进行加密（通常使用异或操作 XOR），生成密文

主要特点：

1. 逐位/逐字节加密：
   序列密码按位或按字节处理数据，因此适合实时加密（如音频、视频流）。
2. 伪随机密钥流：通过初始密钥和随机初始化向量（IV）生成一个伪随机的密钥流，该密钥流长度与明文相同。
3. 对称加密：
   加密和解密使用相同的密钥流：密文=明文⊕密钥流
   解密时：明文=密文⊕密钥流
4. 高效性：
   由于只涉及异或操作，计算复杂度较低，适合高速数据加密

多级反馈移位寄存器（序列密码产生密钥流核心部件）

课后作业（师兄说，老登出题的习惯就是偏重课后作业）

线性反馈移位寄存器

当移位寄存器反馈函数为a1、a2、、、an的线性函数时，称之为线性反馈移位寄存器
如：f(a1,a2,…,an)= cna1 + cn-1a2 + … +c1an（其中常数ci=0或1，+是模2加法）

m序列的概念：
只要选择合适的反馈函数便可使序列的周期达到最大值2n-1，周期达到最大值的序列称为m序列。
注意：线性反馈移位寄存器与特征多项式是一一对应的。即线性反馈移位寄存器与特征多项式可互推

线性反馈移位寄存器的破译机制？（应该是做大题）

1. 已知序列分析法
   获取一段足够长的LFSR输出序列（称为已知序列），可以利用LFSR的线性特性恢复其反馈多项式和初始状态
   只需要已知序列的长度 ≥2n，即可完全恢复LFSR
2. 贝鲁克姆普-马西算法（Berlekamp-Massey Algorithm）
3. 穷举法
   如果LFSR的寄存器长度 𝑛较小，攻击者可以通过穷举所有可能的初始状态和反馈多项式进行暴力破解

课后题

该类题目求解见B站视频

伪随机序列发生器怎么产生的？（老登提问）

什么是伪随机序列？
**概念：**如上所提，m序列的周期很长，但是仍然具有周期性。所以不可能是完全随机的（只能要求比周期短的一段泄露时不会泄露更多信息），因此称此序列为伪随机序列。
伪随机序列应满足的条件：
① {ai}的周期相当大。
② {ai}的确定在计算上是容易的。
③ 由密文及相应的明文的部分信息，不能确定整个{ai}。

伪随机序列发生器包括以下结构或算法：

1. 线性反馈移位寄存器（LFSR）
2. 非线性反馈移位寄存器NLFSR（非线性函数或者多个LFSR组合）
3. 基于密码学安全的生成器： 如基于分组密码的AES、DES
4. 以及上述各方法的组合

伪随机序列发生器的破译

1. 已知明文攻击
   已知一部分明文和对应的密文，密钥流=密文⊕明文
2. 相关密钥攻击
   若生成器对类似密钥生成的密钥流有明显的模式或相关性，可分析类似密钥流破译密钥
3. 状态恢复攻击
   恢复伪随机序列发生器的内部状态（如LFSR的内容）

公钥密码学-RSA

RSA算法安全性依赖于一个事实：将两个大素数相乘十分容易，但对其进行整数分解却极为困难

RSA算法

学习这个视频

解密举例（熟悉公式）

RSA加密原理-给个值怎么做？

RSA安全机制（了解）未完善。。

1） 分解模数n：若模数n = pq被分解，则RSA被攻破
因为若p, q已知，则即可计算
φ(n) = (p – 1)(q – 1)。
再根据关系： ed ≡ 1mod φ(n)，即d是e的逆元。
从公开的公钥e求出私钥d，即可解密。
因此，理论上，RSA安全性依赖于整数分解的困难性
2）若从**求φ(n)**入手对RSA进行攻击，它的难度和分解n相当。
已知φ(n)可求秘密素数p、q

公钥密码学–椭圆曲线

椭圆曲线定义
一般考虑椭圆曲线方程可以简化为
y^2 = x ^3 + ax + b，
小白先看这个视频，了解什么是椭圆曲线

椭圆曲线群加法运算

部分特殊运算规则，自行补充（我赌不考，就不赘述了）。

例5.3为老登提示重点例子

ECC椭圆曲线密码体制

安全性依赖：椭圆曲线上的离散对数问题（ECDLP）

例5.7为重点例子（老登留的作业）

明朝著名画家阿邑真迹(ppt 部分数据有误，以真迹为准)