《密码学》复习笔记 | ComyDream Studio

与命运博弈。

本文为信息安全专业《密码学》课程的复习笔记。

攻击方法

唯密文攻击（Ciphertext Only Attack，COA）：仅持有密文。

已知明文攻击：（Known Plaintext Attack，KPA）：掌握了一些明密文对。

选择明文攻击（Chosen Plaintext Attack，CPA）：截获加密机。

选择密文攻击（Chosen Ciphertext Attack，CCA）：截获解密机。

古典密码

大写字母A~Z和小写字母a~z分别对应数字0~25（考试会给出表格）。

重点是置换密码：

1. 单表：加法、乘法、仿射
2. 多表：Playfair、Vigenere

安全性分析（包括抗暴力破解强度，即密钥空间大小）

分组密码

DES

算法过程

计算：S盒

查表，最高位和最低位对应行号，中间位对应列号。

安全性

互补性

弱密钥

双重、三重DES分析（加密的强度：密钥空间）

AES

算法过程（加密/解密）

解密是加密的逆过程。

计算

字节上的计算。

字节代换（S 盒）

简单的查表。

逆：也是查表。

行移位

简单的移位。

第0行不变，第1行左移1个字节，第2行左移2个字节，第3行左移3个字节。

逆：变成右移。

列混合

这应该是 AES 考察的重中之重。

加法：异或

乘法两种方法：

1. 用定义
2. 用简便方法（乘2情况下）
   • 最高位是0：直接左移1位。
   • 最高位是1：左移1位后和 00011011 异或。

乘3情况：(00000011=00000010⊕00000001)

逆：太难，不要求掌握。

轮密钥加

逐位异或。

密钥扩展

看了下书，宛若没学2333。

128 位密钥形成4个4字节组成的（32位）字：$w[0],w[1],w[2],w[3]$ ，这是初始密钥加用到的。

扩充40个新列，以如下算法生成：

1. 若 $i$ 不是4的倍数，那么 $w[i] = w[i-4]⊕w[i-1]$ 。
2. 若 $i$ 是4的倍数，那么 $w[i] = w[i-4]⊕T(w[i-1])$ 。

其中，$T()$ 是一个很复杂的函数，定义如下：

1. 字循环：循环左移一个字节，即有 $[b_0,b_1,b_2,b_3]\rightarrow [b_1,b_2,b_3,b_4]$ 。
2. 字节代换：用字节代换中的 S 盒，直接查表。
3. 轮常量异或。

工作模式

根据加密图画出解密图。

根据图写出算法。

错误传播分析。

1. 电子密码本模式（ECB）
2. 密码分组链接模式（CBC）
3. 密码反馈模式（CFB）
4. 输出反馈模式（OFB）
5. 计数器模式（CTR）

流密码

给定初始状态，写出输出序列。线性反馈移位寄存器（LFSR）。

周期、游程分析。

本原多项式、m序列。

哈希函数

不要求掌握完整算法。

因为不考记忆算法，后面的也很难算，能考的或许只有数据填充（99.9%考）。

本身含义、安全性分析（碰撞性）。

基本概念

Hash 函数是密码学的一个重要分支，是将任意长度的输入变换为固定长度的输出的不可逆的单向密码体制。

性质

1. 任意长度输入。
2. 固定长度输出。
3. 对于任意给定的消息 $x$ ，计算 $H(x)$ 比较容易，硬件软件均可实现。
4. 单向性（抗原像性）：从散列值 $h=H(m)$ 推回消息 $m$ 在计算上不可行。
5. 抗弱碰撞性：对任意给定的消息 $x$ ，找到 $y≠x$ 且 $H(x)=H(y)$ 在计算上不可行。
6. 抗强碰撞性：找到任何满足 $H(x)=H(y)$ 的两个不同消息 $x,y$ 在计算上不可行。

数据填充

填充一个1和若干个0，使得消息长度模 512 与 448 同余。

特别注意：若原消息长度刚好满足这个条件，则再填充 512 位（1 个 1 和 511 个 0）。

填充完后再把原始消息长度以 64 比特表示附加在后面。

这样，最终消息长度恰好为 512 的整数倍。

MD5

分组长度为 512 比特，最终输出 128 位（即 16 字节，32 个十六进制位）的消息摘要。

过程为 4 轮，每轮 16 步，共 64 步。

SHA1

最终输出 160 位（即 20 字节，40 个十六进制位）的消息摘要。（因此比 MD5 抗穷举能力更强）

过程为 4 轮，每轮 20 步，共 80 步。

看到后面的步骤，心中呐喊：打扰了。

公钥密码

相当于单向陷门函数，陷门是私钥。

RSA

算法流程（加密、解密）

计算

给出 $p,q,e$ 求 $d$

$$n = p\cdot q\\ φ(n)=(p-1)\cdot (q-1)\\ d\equiv e^{-1}\pmod {φ(n)}$$

加密：给出 $m$ 求 $c$

$$c\equiv m^e\pmod n$$

解密：给出 $c$ 求 $m$

$$m\equiv c^d\pmod n$$

安全性分析

正确性验证

1. $(m,e)=1$
2. $(m,e)≠1$

攻击与防范（肯定考）

共模攻击

低指数攻击

ElGamal

不考安全性分析。

加密解密算法（必须记住）

计算

正确性验证

数字签名

签名用私钥，验证用公钥。

RSA

ElGamal（如果考会给出算法）

特殊：盲签名

安全性分析

若不加 Hash 会怎么样？（没有Hash函数有什么缺点？）

可以伪造签名。

看P246 6.

正确性分析

密码协议

联系《密码学课程设计》的综合实验。

对称密码用到的密钥用公钥密码体制传输。

1. Alice 用 Bob 的公钥加密对称密码的密钥，发送给 Bob 。
2. Bob 用自己的私钥解密，得到密钥。

给出具体密码协议，分析合理性，验证可靠性，证明安全性。

综合，会涉及到前面学的。

一些题目

仿射密码

题目

若 $c_i=E(m_i)=(11\cdot m_i+6)\mod 26$：

1. 若明文为 $cumt$ ，请计算相应的密文。
2. 写出解密变换。
3. 若密文文 $cumt$，请计算相应的明文。

解答

字母-数字对应表：（考试会给出）

A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

由 $c_i=E(m_i)=(11\cdot m_i+6)\mod 26$

$c$ 对应 2，对应密文为 2，对应 $c$；

$u$ 对应 20，对应密文为 18，对应 $s$；

$m$ 对应12，对应密文为 8，对应 $i$ ；

$t$ 对应 19，对应密文为 1，对应 $b$ 。

故 $cumt$ 对应的密文为 $csib$ 。

$$∵ 11^{-1}\equiv 19\pmod {26}\\ ∴ 解密变换为m_i=[19\cdot (y-6)]\mod 26$$

RSA

题目

RSA 加密算法是当前使用最为广泛的公钥加密算法。假设消息接收方选择 $p=43,q=59,e=13$ ，请回答以下问题：

1. 发送方预加密消息 $224$ 并发送给接收方，请计算密文。
2. 请计算解密方的解密密钥 $d$。
3. 若收到的密文为 $803$ ，请计算相应的明文。

解答

$$n=p\cdot q=43\cdot 59=2537\\ φ(n)=(p-1)\cdot(q-1)=42\cdot 58=2436\\ c\equiv m^e\equiv 224^{13}\equiv 1692\pmod n\\ ∴密文为1692$$

使用扩展 Euclid 算法求模逆：

$j$	$s_{j-1}$	$t_{j-1}$	$q_j$	$r_j$
-2				2436
-1	1	0		13
0	0	1	187	5
1	1	-187	2	3
2	-2	375	1	2
3	3	-562	1	1
4	-5	937	2	0

使用 Python 验算：

$$∴d\equiv e^{-1}\equiv 937\pmod {φ(n)}$$

若收到密文为 $803$ 则：

$$m\equiv c^d\equiv 803^{937}\equiv 1727\pmod n$$

即明文为 $1727$ 。

External Links

Cryptography Course Review Note - 3ND

本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明来自 ComyDream 。
本文链接：http://comydream.github.io/2019/01/04/cryptography-review/