密码学|整理

第一章 计算机与网络安全概念·

信息安全三要素（CIA）：

• 机密性
  • 数据保密性：隐私或者秘密数据不向非授权者泄露、也不被他们使用
  • 隐私性：个人能够控制和确定自身相关的哪些信息可以被收集、保存、公开及向谁公开
• 完整性
  • 数据完整性：信息和程序只能以特定的方式进行改变
  • 系统完整性：系统以一种正常的方式执行预定的功能，免于被非法的操控
• 可用性

攻击方式有两种：主动攻击和被动攻击。

• 被动攻击：窃听，不影响正常的通信，不对信息进行任何修改，以获取信息为目的。

  被动攻击分为：信息内容的泄露、流量分析。

• 主动攻击：对数据流进行篡改，或者产生假的信息。

  主动攻击包括：

  • 拒绝服务：对系统可用性进行攻击。
  • 消息修改：修改消息内容、延迟传输、修改消息顺序等。破坏完整性。
  • 伪装：假装成其他实体。对真实性进行攻击。
  • 重放：将截获的信息再次发送。

安全服务：对系统资源进行特殊保护的处理或者通信服务。

1. 数据保密性：防止消息内容泄露，被窃听。防止被动攻击
2. 认证：保证通信的真实性。包括单向通信和双向通信
3. 数据完整性：保证所接受的信息是未经修改或重放的，还能用于对一定程度损坏的数据的恢复。
4. **不可否认性：**接收者能证明消息的真实来源，发送者能证实接收者已经接受了消息
5. 访问控制：检查用户是否对某一资源有访问权。实现方式是认证

第三章 传统加密技术·

• 基于密码分析的攻击：
  1. 唯密文攻击
  2. 已知明文攻击：已知多个明文-密文对
  3. 选择明文攻击：由破译者选择的明文信息及其密文
  4. 选择密文攻击：由破译者选择的密文信息及其明文
  5. 选择文本攻击：选择明文+密文攻击

代替技术·

1. 凯撒密码
   • 字母表位移k位
   • 共有26种可能的密钥，25种有效
2. 采样密码（乘法密码）
   • 明文字母表每隔k位取出一个
   • 要求密钥k与26互素，有 ${\phi}(q)-1$ 个可用密钥
   • 加密： $C=(mk)\ mod\ 26$
   • 解密： $p = (k^{-1}C)\ mod \ 26$
3. 仿射代替密码
   • 加法和乘法结合
   • q=26时，共26*12 - 1 = 311 个可用密码（减去的是不变的变换）
   • 加密：$E_k(m)=mk_1+k_0 mod q$
   • 解密： $D_k(c)=k_1^{-1}(c-k_0) mod q$
4. 单表代替密码：
   • 随机映射
   • 密钥数目：$26!$
   • 缺陷：密文字母带有明文的统计特性，明文中一个元素仅影响密文中一个元素
   • 语言的统计特性：
     • 单字母：极大概率：e，大概率字母：tao，较大概率：inshr
     • 多字母
     • 单词特性
   • 单表代替密码之所以容易被攻击，是因为每个密文字母都是用同一个代替密表加密而成的，相同的密文字母对应着相同的明文字母。实际上只是改变字母的名称。
5. Playfair 密码
   • 多字母代替密码，5*5矩阵，先填充密钥单词，再填充剩下的。I=J
   • 加密：明文两个字母一组，如果两个字母相同则在中间插入一个填充字母。同行：循环向右，同列：循环向下，对角线：另一对角线，按加密两字母的行排序
   • 优点：安全性优于单表代替密码，使用频率分析困难
6. Hill密码
   • 多字母代替密码，利用矩阵 $K$
   • 加密： $C=PK\ mod\ 26$
   • 解密： $P = (CK^{-1})\ mod \ 26$
   • 优点：完全隐藏了单字母的频率特性，可以抵抗唯密文攻击
   • 容易被已知明文攻击破解

多表代替技术·

1. 多表代替：对每位明文采用不同的单表代替。当明文和密钥一样长时成为一次一密密码。
2. 维吉尼亚密码：
   • 26*26表格，行和列均为a-z，表内为每行以a.b.c…z开头的凯撒密码
3. 博福特密码：
   • 加密：$\begin{aligned}&c_i=k_i-p_i\mod26\end{aligned}$
   • 解密：$p_i=k_i-c_i\mod26$
4. 弗纳姆Vernam密码：
   • 与密钥诸位异或
5. 一次一密：
   • 在Vernam密码中，如果采用的密钥不重复就是一次一密体制
   • 在理论上不可被破解，但是在实际上不可行
6. 多表代替密码的破译：
   • 对于周期多表代替密码，可以转换成多组单表代替密码进行破译

第四章 分组密码和数据加密标准·

1. 代替：元素被唯一地替换成对应的密文元素

   置换：没有元素被添加、删除、替换，只是顺序发生了改变

   混淆：是密文和加密密钥之间关系变得复杂，以阻止攻击者发现密钥。

   扩散：每个密文字母尽可能受多个明文数字的影响，使得明文的统计特性消散在密文中。

2. 乘积密码：在单个加密机制中依次使用两个或两个以上不同类型的基本密码，所得结果的密码强度将强于每个单个密码的强度。

3. Feistel密码是一种特殊的SP网络，交替使用代替和置换，增强密码的扩散和混淆性能。

4. Feistel密码的结构：加密和解密完全相同

数据加密标准(DES)·

1. DES使用56比特的密钥加密64位的明文，得到64位的密文。

2. 算法的实现过程:

   (1)初始置换IP

   (2)16轮迭代运算：$L_i=R_{i-1},R_i=L_{i-1}\oplus F(R_{i-1},k_i)$，子密钥$k_i$长48位

   迭代运算过程包含4步： --32bit–> 扩展置换E --48bit–> 与子密钥异或 --48bit–> S盒代替 --32bit–> 置换运算P --32bit–>

   

   (3)逆置换$IP^{-1}$

3. DES攻击，强力攻击$2^{55}$是平均尝试次数，差分攻击$2^{47}$是选择明文攻击

4. S盒是DES中唯一的非线性计算，提供了密码算法所必须的混淆作用。而线性的置换，通常是起扩散的作

   用。

5. 雪崩效应：明文或密钥的一点小的变动都引起密文的较大变化。P置换的目的是提供雪崩效应。

6. 弱密钥：初始密钥产生的16个子密钥相同。

   半弱密钥：存在不相等的 $k,k^{'}$，使得$DES_k(m)=DES_{k^{\prime}}(m)$。DES一共有6对半弱密钥。

7. 差分密码攻击：通过比较两个已知明文差异的明密文对，在使用相同子密钥的情况下搜索密文中的已知差异。

8. 线性密码分析：基于找到DES中进行变换的线性近似，可以在有2^47个已知明文的情况下破译DES密钥，但实践中仍不可行。

9. 分组密码的整体结构：Feistel结构和SP网络

10. SP网络结构：每一轮中，轮输入首先被一个由子密钥控制的可逆函数S（混淆）作用，然后再对所得结果用置换（或可逆线性变换）P（扩散）作用。SP网络结构可以更快的扩散，但加解密通常不相似。

第六章 高级加密标准·

高级加密标准(AES)·

1. Rijndael是一个迭代型分组密码，其分组长度和密钥长度都可变，可以为128比特、192比特、256比特。Rijndael使用非线性结构的S-boxes，能抵抗所有已知的攻击。Rijndael中轮函数由3层不同的可逆均匀变换组成，分别为线性混合层、非线性层、密钥加层。

   在第一轮之前使用一个初始密钥加层，目的是：使加解密相似、对安全性无意义、有利于差分分析。

2. AES是一个迭代型分组密码，其分组长度固定为128 比特，密钥长度则可以是128，192或256比特，迭代轮数分别为10、12、14

3. AES流程：

DES中的元素	实现的效果 (扩散/混淆)	AES中的对应元素
f 函数的输入与子密钥相异或	混淆	轮密钥加
f 函数的输出与分组左边的部分相异或	扩散	列混淆
f函数中的 S 盒	混淆	字节代替
P 置换	扩散	行移位
交换一个分组的两半部分	扩散	无此元素： 第一，行移位起到了行内元素的扩散效果，列混淆起到了列中元素的扩散效果。 第二，交换分组两半是Fesitel结构所必需的，而AES采用的是SPN网络。

第八章 伪随机数的产生和流密码·

伪随机数的产生原则·

1. 随机数序列需要满足两个特征：随机性和不可预测性
2. 伪随机数：使用算法生成随机数，由伪随机数发生器（PRNGs）产生
   • 伪随机数发生器（PRNG）：生产不限长度的位流，通常作为对称流密码的输入。
   • 伪随机函数（PRF）：用于产生固定长度的伪随机数串。如对称加密的时变值。PRF的输出常为种子加一些上下文相关的特定值。

伪随机数发生器·

1. 线性同余发生器
2. BBS发生器

流密码·

1. 伪随机数发生器的输出称为密钥流，密钥流和明文流的每一个字节进行按位异或运算，得到一个密文字节。密码系统的安全性取决于密钥流的性能。
2. 流密码类似于一次一密，但是一次一密使用的是真正的随机数流。
3. 一次一密密码：密钥流是完全随机序列，且密钥不重用。一次一密在唯密文攻击条件下是理论保密的，这是唯一一个能被证明是无条件安全的密码。
4. 流密码可以分为：同步流密码和自同步流密码

线性反馈移位寄存器 LFSR·

第九章 公钥密码与 RSA·

OAEP–最优非对称加密填充

RSA-OAEP可抗击适应性选择密文攻击

第十章 其他密码体制·

Rabin密码体制·

1. Rabin密码体制已被证明对该体制的破译与分解大整数是等价的

2. 不以一一对应的单向陷门函数为基础，对同一密文，可能有两个以上对应的明文

3. 密钥生成算法：

   选择两个大素数pq满足 $p\equiv q\equiv3\ mod \ 4$，计算 $n=pq$

   n为公钥，p,q为私钥

4. 加密：$c=m^2\ mod\ n$

5. 解密：求解 $x^2=c\ mod \ n$ ，由CRT知该方程等价于解方程组：

   $\left\{\begin{aligned}x^2&&\equiv c&&mod&&p\\x^2&&\equiv c&&mod&&q\end{aligned}\right.$

   每个方程都有两个解，因此可以得到四个可能的解，即每一密文对应的明文不惟一。

   为了有效确定明文，可在m中加入某些双方商定的信息，如日期、发送者的ID等。

Diffie-Hellman密钥交换·

1. Diffie-Hellman算法可以用于密钥分配，但是不能用于加密或解密信息。

2. 安全性依赖于有限域上计算离散对数非常困难。

3. 算法流程：

   1. AB协商一个大素数p和本原根a，a和p公开
   2. A产生随机数x，计算 $X = a^x\ mod\ p$，X发给B
   3. B产生随机数y，计算 $Y = a^y\ mod\ p$，Y发给A
   4. A计算 $k=Y^x \ mod \ p$
   5. B计算$k=X^y \ mod \ p$

4. Diffie-Hellman密钥交换容易受到中间人攻击，原因是Diffie-Hellman密钥交换不认证对方。

5. 改进的Diffie-Hellman密钥交换算法：

   

ElGamal密码体制·

1. 双钥密码体制，用于加密和签名

2. 安全性基于求解离散对数问题的困难性。

3. 密钥生成算法：

   ① 选取一个足够大的素数q，在 $Z^*_p$ 上选取一个本原元a

   ② 随机选取一个整数 $X_A$，并计算 $Y_A=a^{X_A}mod \ q$

   ③ 公钥为 $(q,a,Y_A)$，私钥为 $(X_A)$

4. 加密：

   ① 消息 $M$ 。以分组密码序列的方式来发送信息，每个分组的信息大小不超过q。

   ② 选择任意整数 $k\in Z_{q-1}$

   ③ 一次性密钥 $K=(Y_A)^k$ mod $q$

   ④得到密文对：

   $C_1= a^k\textit{ mod }q\\C_2= KM\textit{ mod }q$

5. 解密：$M=C_2(C_1^{X_A})^{-1}\:mod\:q$

ECC·

1. 基于椭圆曲线数学的一种公钥密码的方法。
2. 椭圆曲线上的公钥密码体制的优点：速度快、密钥短、存储空间和传输带宽占用较少，安全性高，灵活性好。
3. 基于椭圆曲线离散对数问题的困难性
4. ECC要求最小密钥长度160位

第十一章 密码学Hash函数·

SHA1、SHA2都是迭代结构。Keccak被选为SHA-3，采用了创新的“海绵引擎”散列消息文本。

哈希函数在密码学中的应用：消息认证码、数字签名、伪随机数发生器、一次性口令等

第一类生日攻击：

• 问题：H有n个可能的输出，$H(x)$是一个特定的输出，对H取k个输入，至少有一个输入y使得$H(y)=H(x)$时，k有多大？

• y取k个随机值得到函数的k个输出中至少有一个等于$H(x)$的概率为：

  $1-(1-1/n)^k\approx1-(1-k/n)=k/n$。若概率等于0.5,则$k=n/2$。当输出长为m比特时，$k=2^{m-1}$

第二类生日攻击：

• 寻找函数H的具有相同输出的两个任意输入

• 设哈希函数输出长度为m比特，H的k个随机输入中至少有两个产生相同输出的概率大于0.5,则：

  $k\approx\sqrt{2^m}=2^{\frac m2}$

第十二章 消息认证码·

1. 公钥加密：先签名再加密：提供保密性和认证性
2. 消息认证码MAC：是指消息被一密钥控制的公开函数作用后产生的、用作认证符的、固定长度的数值。
3. MAC是实现有效、安全可靠数字签字和认证的重要工具，是安全认证协议中的重要模块。
4. MAC算法不要求可逆性，是带有密钥的Hash函数。但是也不是加密函数，因为MAC算法不要求可逆性，与加密函数相比，MAC函数更不容易被攻破。
5. MAC的构造：
   • 用hash函数构造MAC
   • 用分组密码构造MAC
   • 用伪随机算法构造MAC
6. HMAC能提供：
   • 消息完整性认证
   • 信源身份认证

第十三章 数字签名·

ElGamal签名·

1. 随机数k不能泄露且不能被重复使用，否则x有可能被算出
2. 存在ElGamal数字签名的变形在某些假设下，能被证明在选择消息攻击下是安全的

Schnorr数字签名·

ECDSA·

SM2·

椭圆曲线： $y^2=x^3+ax+b$

第十四章 密钥的管理和分发·

公钥基础设施（PKI）·

1. 为管理公钥（生成、认证、存储、安装），须建立一套公钥基础设施（PKI，Public Key Infrastructure），PKI的基本组成元素是证书颁发机构（CA，Certificate Authority）。
2. PKI主要完成的工作为：
   1. 为用户生成一对密钥（公开密钥，私有密钥），并通过一定的途径分发给用户。
   2. CA为用户签发数字证书，形成用户的公开密钥信息，并通过一定的途径分发给用户。
   3. 对用户证书的有效性进行验证。
   4. 对用户的数字证书进行管理。这些管理包括有效证书的公布、撤销证书的公布、证书归档等。
3. PKI包含五个关键元素：
   1. 端实体：一个在公钥数字证书作用范围中被认证的实体。
   2. 签证机构CA：证书和证书撤销列表的发行人。
   3. 注册机构RA：可选元素，承担一些签证机构（CA）的管理任务。
   4. 证书撤销列表发布点：可选元素，CA可通过它来发布证书撤销列表（CRL）。
   5. 证书存取库：必备元素，提供存取数字证书和证书撤销列表的方法。