密码学复习 - LeeHung的博客

第一章：密码体制

密码体质的设计原则：密码系统的安全性不应该取决于不易改变的算法，应该取决于可随时改变的密钥

五元组：M（明文）、C（密文）、K（密钥）、E（加密算法）、D（解密算法）

密码体制分类

🌟对称密码
- 序列密码（流密码）：RC4、A5等
- 分组密码：DES、3DES、AES、IDEA
🌟公钥密码：RSA、ECC、Rabin、Elgamal

对称密码体制优点：

速度快
密钥较短
密文往往与明文长度相同

对称密码体制缺点

密钥分发需要安全通道
密钥量大，难管理
难于解决不可否认问题

公钥密码体制优点：

密钥分发相对简易
密钥简单管理
可以实现数字签名

公钥密码体制缺点：

加解密速度慢
密钥较长
密文长度往往大于明文长度

密码分析

被动攻击与主动攻击：

被冻攻击：对一个保密系统采用截获密文进行分析，如监视、偷听等
主动攻击：非法入侵者主动干扰系统，采用删除、更改、增添、重放等方法向系统加入假消息

破译和攻击密码的主要方法：

穷举攻击法（爆破）
- 变体：字典攻击
统计分析法：根据明文、密文和密钥的统计规律来破译密码
- 适用于对称密码体制
数学分析攻击法：针对加解密算法的数学基础和某些密码学特征，通过数学求解的方法来破译密码
- 适用于公钥密码体制

🌟根据密码分析者对明文、密文等数据资源的掌握程度，可以将密码分析攻击分为以下几种

唯密文攻击（被动）：仅能根据截获的密文进行分析，以得出明文或密钥（如穷举和统计分析）
已知明文攻击（被动）：除了有截获的密文外，还知道一些已知的“明文-密文对”，来破译密码
选择明文攻击（主动）：除得到一些”明文-密文对”外，还可以选择被加密的明文，并获得相应的密文
- 目标：推出用来加密的密钥或者某种算法
- 变体：自适应选择明文攻击
选择密文攻击（主动）：可以选择一些密文，并得到相应的明文
- 目标是推出密钥
- 多用于攻击公钥密码体制
- 变体：自适应选择密文攻击

攻击的复杂性取决于

数据复杂性：攻击所需要的输入数据量
处理复杂性：完成攻击所需要花费的时间
存储需求：所需要的数据存储空间大小

攻击的复杂性取决于以上三个因素的最小复杂度

安全的密码体制特性

密文恢复明文是困难的，即使知道明文空间
从密文获得明文部分信息是困难的
从密文探测出简单有用的事实也是困难的

评价密码体制安全性的途径：

无条件安全性（理论安全性）：分析者有无限计算能力，密码体制也不能被攻破，那么就是无条件安全
计算安全性：攻破一个密码体制最好算法用现在或将来可得到的资源都不能在足够长的时间内破译，该密码体制被认为计算上安全
可证明安全性：可证明安全性只是说明密码体制的安全性与一个问题相关，也成归约安全性

第二章：古典密码

经典密码体制分类：

替换密码/代换密码
- 单表替换密码：用一个符号代替另外一个符号，一一对应
  - 🌟移位代换密码：E_k(i) ＝ i＋k(mod q) ＝ j D_k(j) ＝ j－k (mod q)＝i
    - 凯撒密码
  - 乘数密码：E_k(i) ＝i ∗ k mod q＝j D_k(j)＝j ∗ k^(-1) mod q＝i
  - 🌟仿射密码：以上两个的组合 C＝ k₁∗m＋k₂ mod 26 m＝ (C-k₂)∗k₁^-1 mod 26
- 多表替换面：多个替换包
置换密码/换位密码：对符号重新排序

🌟Playfair密码

思路：双字母转换

密钥：5×5矩阵

比如关键词为 FIVESTARS，将关键词中重复字母去掉，填充矩阵起始部分，之后将26字母中未出现的字母按顺序填充
I 和 J 作为一个字母看待
密钥空间为 25

对每一对明文m1, m2加密如下：

若m1和m2同行，则密文c1和c2分别紧靠m1，m2右端的字母，其中第一列看做最后一列的右方
若m1和m2同列，则密文c1和c2分别是紧靠m1，m2下方的字母，其中第一行看做最后一行的下方
若m1和m2不同行也不同列，则c1和c2是m1，m2确定的矩形的其他两角的字母，并c1和m1，c2和m2同行
若出现重复字母，即m1=m2，则在其中插入字母Q
如明文字母是单数，将Q放在明文的末端

🌟维吉尼亚密码

维吉尼亚方阵为 26×26表，加密过程：先找明文的列，再找密钥的行

安全性能分析步骤：

确定密钥长度d
- Kasiski测试法
- 重合指数法
确定具体的密钥字
- 重合互指法

第三章：序列密码

基本概念：用一个随机序列（密钥流）与明文序列按位叠加产生密文；用同一随机序列与密文序列叠加来恢复明文。

种子密钥通过密钥流发生器得到的密钥流

特点：

加解密只是简单的模二加法运算（异或）
密码安全强度依赖密钥流的安全性

序列密码分类：

同步序列密码：密钥序列的产生独立于明文消息和密文消息
- 无错误传输：一个错误只影响一个符号
- 同步：保持精确，且密钥作用位置相同才能正确解密
🌟自同步序列密码：密钥序列是密钥及固定大学的以为密文的函数（密钥由以往密钥及密文生成）
- 有限错误传播
- 自同步
- 消除明文统计特征

密钥流生成器大都基于移位寄存器FSR

基于移位寄存器的密钥流序列成为移位寄存器序列
通常由线性移位寄存器LFSR和一个非线性组合函数（布尔函数）组成一个密钥流发生器

🌟线性反馈移位寄存器

特点：

非常适合硬件实现
能产生大的周期序列
能产生统计性好的序列
能够应用代数方法分析

定理：n级LFSR产生的序列有最大周期 2ⁿ-1的必要条件是其特征多项式为不可约的

🌟m-序列密码的破译

m-序列（周期为 2ⁿ-1）如果攻击者知道了 2n位明密文对 ，则可确定反馈多项式的系数，从而确定LFSR接下来状态，得到余下的密钥序列

伪随机性测试

扑克牌测试
游程测试
接收20000个二进制位，检验1和0的核数是否大致相等

常见基于LFSR的密钥序列发生器

Geffefasq
钟控发生器
交错停走式发生器
门限发生器

第四章：分组密码

特点：速度快、安全性较高、易于标准化、便于软硬件实现

分组密码设计要求：

分组长度足够大
密钥量足够大
密码变换够复杂
加密和解密运算简单
无数据扩展和压缩

设计思想：扩散和混淆，目的抵抗对密码系统的统计分析

扩散：密钥或明文每一比特变化影响密文许多比特变化（雪崩效应）
混淆：密钥和明文及密文之前依赖关系尽可能复杂，防止统计分析法

🌟数据加密标准DES

算法详解在课程设计中已详细展开，不再累述，这里主要讲述关于考试方面的主要内容

明文分组和密文均为 64bit ，有效密钥为 56bit（另外8比特用于奇偶校验，用于检查密钥 K 在产生和分配及存储过程中可能发生的错误）。由初始置换、16轮迭代、逆初始置换组成

初始置换和逆初始置换：通过置换表置换，没有安全意义，可忽视
16轮迭代：每轮迭代，64位的中间结果分为左右两部分，且作为独立32位数据进行处理。每轮迭代的输入时上轮的结果 L_i-1 和 R_i-1。

加解密过程：

加密函数F

E扩展置换：32bit 扩展为 48bit，每输入分组的4位作为6位输出分组的中间4位，第1位和第6位分别由相邻两个4位分组的最外面两位扩散进入本分组
与子密钥异或：将48位输出与子密钥 K_i 进行异或操作
🌟压缩替换 S-盒：
- 由8个S-盒构成，每个S-盒都是6比特输入，4比特输出
- s_i (h₁h₂h₃h₄h₅h₆) 的值是对应表 s_i 中 (h₁h₆) 行和 (h₂h₃h₄h₅) 列上的值

S-盒设计准则：
- 有良好的非线性性（输出的每个比特与全部输入比特相关）
- 每一行包括所有16种4位二进制
- 两个输入相差1比特时，输出相差2比特等
P-置换：P-置换对8个S-盒的输出进行变换（对表查询变换）

🌟DES轮运算对和性证明

定义 T 是把64位数据的左右两半交换位置

$$
T(L,R)=(R,L)
$$

因为
$$
T^2(L,R)=(L,R)=I
$$
其中 I 为恒等变化，于是
$$
T = T^{-1}
$$
所以 T 变化是对合运算

记 DES 第 i 轮中的主要运算为

$$
F_i(L_{i-1},R_{i-1})=(L_{i-1}\oplus f(R_{i-1},K_i),R_{i-1})\
F_i^2=F_i(L_{i-1}\oplus f(R_{i-1},K_i),R_{i-1})\
=(L_{i-1}\oplus f(R_{i-1},K_i)\oplus f(R_{i-1},K_i),R_{i-1})\
=(L_{i-1},R_{i-1})\
=I
$$

所以
$$
F_i=F_i^{-1}
$$
所以 F_i 变换也是对合变化

结合以上两步，便可构成 DES 的轮运算
$$
H_i=F_iT
$$
因为
$$
(F_iT)(TF_i)=(F_i(TT)F_i)=F_iF_i=I
$$
所以
$$
(F_iT)^{-1}=(TF_i)\
(F_iT)=(TF_i)^{-1}
$$

DES的安全性

主要争论为：

S-盒的设计准则、迭代次数、密钥长度等设计准则
存在弱密钥和半弱密钥
- 弱密钥：初始密钥 K 使得种子秘钥两部分的每一部分的所有位置全为0或1，则经子密钥产生器产生的各个子密钥都相同。这样的密钥共有4个，分别是0000000 0000000、0000000 FFFFFFF、FFFFFFF 0000000、FFFFFFF FFFFFFF
  - E_k (E_k (m)) = m 和 D_k (D_k (m)) = m
- 半弱密钥：把明文加密成相同的密文，即存在两个不同的密钥，使得加密同一明文的到的结果相同。
- 弱密钥占比非常小，对安全性威胁不大
56位密钥无法抵抗穷举攻击
代数结构存在互补对称性：互补性会使DES在选择明文攻击下所需要的工作量减半，仅需要测试 2⁵⁵ 个密钥。

$$
\begin{cases}
c_{1} = E_{k}(m) \
c_{2} = E_{k}(\overline{m})
\end{cases}
$$

由互补性得到
$$
\overline{c_{2}} = E_{\overline{k}}(m)
$$
在穷举密钥 k 时，若输出密文是 c，则加密密钥就是所应用的密钥；若输出密文是 c 的补，则加密密钥就是所用密钥 k 的补

多重DES分析

双重DES：无能抵抗中途相遇攻击

$$
加密：C = E_{K_{2}}(E_{k_{1}}(P)) \
解密：P = D_{K_{1}}(D_{k_{2}}(C)) \
由上可推出\
X = E_{k_{1}}(P) = D_{k_{2}}(C)\
X 为中间值
$$

给定明密文对 (P, C) ，将 P 按所有可能密钥 K₁ 加密，得到结果排列与表 T 中；将 C 用所有可能密钥 K₂ 解密，每解密一次就将解密结果与 T 中的值比较。若有相等，就用刚才测试的两个密钥对 P 加密，若结果为 C 则认定这两个密钥时正确的密钥。

三重DES：有四种方式，分别是 EEE3、EDE3、EEE2、EDE2，其中的数值表示密钥数量

🌟高级加密标准AES

本课程中的AES中运算按字节（8位二进制）定义

一个字节看成优先于上次数小于 8 的多项式

多项式加法：

🌟多项式乘法：有限域 GF(2⁸) 中两个元素的乘法为模 2 元域 GF(2) 上的一个 8 次不可约多项式的多项式乘法。对于 AES，该8次不可约多项式为
$$
m(x)=x^{8}+x^{4}+x^{3}+x+1
$$
用十六进制表示为{9B}

🌟X乘法（乘2情况）：

最高位是 0：直接左移 1 位
最高位是1：左移 1 位后和 00011011 异或

$$
x*B(x)=\begin{cases}(b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}0) &\text{b7=0} \(b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}0)\oplus(00011011)&\text{b7=1}\end{cases}
$$

乘 3 乘法：

3 = (0000 0011)₂ 可以拆分为 (0000 0001)₂ 和 (0000 0010)₂ ，再将两个乘积异或：
$$
(0000 0011)(a_7a_6a_5a_4a_3a_2a_1a_0)\
=[(00000010)\oplus(00000001)](a_7a_6a_5a_4a_3a_2a_1a_0)\
=[(00000010)(a_7a_6a_5a_4a_3a_2a_1a_0)]\oplus(a_7a_6a_5a_4a_3a_2a_1a_0)
$$

AES结构

明文按字节分成列组（共16字节）
128位密钥被扩展成44个字组成的序列 W[ i ]
AES每轮有四个阶段
- 字节代换：S-盒和逆S-盒，简单查表
- 行移位：简单左循环移位操作，状态矩阵中，第 i 行循环左移 i 字节；逆操作则右移
- 🌟列混合：对状态矩阵逐列变换，每列视为有限域 GF(2⁸)上一多项式。列多项式乘以一个固定多项式 c(x)，对应四字节向量为（03 01 01 02），模多项式为（x⁴ + 1）
- 轮密钥加：轮密钥与状态按比特逐位异或
每个阶段可逆，解密的一轮就是加密的逆执行
加解密的最后一阶段（第10轮）只有三个阶段（没有列混合）

密钥扩展

将初始 128 位密钥，输入一个 4x4 矩阵，4 列依次为 w[ 0 ]、w[ 1 ]、w[ 2 ]、w[ 3 ]，接着对 w 数组扩充到 40 个新列，总共构成 44 列，采用以下递归方式构成
$$
w[i] =\left{
\begin{array}{}
w[i-4]\oplus w[i-1] & \text{i不是4的倍数}\
w[i-4]\oplus T(w[i-1]) & \text{i是4的倍数}
\end{array}
\right.
$$
T 是一个复杂函数，有字循环，字代替和轮常量异或三个组成部分，其中引用了S-盒。

IDEA和SMS4

IDEA分组大小为64位，密钥为 128 位；它的种子密钥为 128 位。在加密中，由8轮和随后的一个输出变换组成。共用 52 组 16 位的子密钥，子密钥主要通过初始密钥移位得到。
SMS4，分组长度 128 比特，密钥长度 128 比特，加解密采用32轮非线性迭代，加解密轮密钥顺序相反。

🌟分组密码工作模式

电码本模式（ECB）

相同明文分组加密成相同的密文分组，明文分成 64 的分组进行加密，不足 64 位时进行填充

特点

简易，可并行计算，速度快
相同密钥作用下，相同明文加密产生相同密文，暴露明文特征
密文块缺乏相关，易受替换、重复等攻击

密码分组链接模式（CBC）

加密输入是当前明文分组和前一密文分组的异或，形成一条链。密文组不仅与当前明文组有关，且通过反馈以前的明文组有关

🌟CBC的传播错误：

明文有一分组有错，会使以后的密文组都收到影响，但经过解密，除原来有误的一组外，其后各组明文都正确恢复
传送过程中某组密文出错时，则该组恢复的明文和下一组恢复数据出错，再后面的组不受影响

密码反馈模式（CFB）

输入是 64 比特的移位寄存器，初值为初始向量 IV，输出最左边 j 比特与明文第一个单元 P₁ 进行异或，产生密文的第一个单元 C₁ 。然后将移位寄存器左移 j 位，并将 C₁ 送入移位寄存器的最右边 j 位，直至所有单元被加密

优点：自同步能力强，可处理任意长度消息

缺点：

明文某一组中有错，使以后的密文组都受影响，但经解密后，除原有误的一组外，其后各组都正确地恢复
密文里的一位错误会引起明文的一个单独错误，此错误进入移位寄存器，导致密文成为无用信息，直到该错误从移位寄存器中移出

输出反馈模式（OFB）：

反馈模式结构与CFB结构类似，不同在于

OFB模式将加密算法的输出反馈到移位寄存器

特点：

可加密任意长度数据，没有错误传播，适用于加密冗余度较大的数据，但对密文的篡改难以检测

计数器模式（CTR）：
$$
加密：c_i = m_i \oplus E_k(CTR+i) (i = 1,2,…,n) \
解密：m_i = c_i \oplus E_k(CTR+i) (i=1,2,…,n)
$$
CTR表示计数器初值

特点：

随机访问特性：可随机对任一个密文分组解密，且与其他密文无关
高效率：能并行处理
可处理任意长度数据，仅涉及加密运算，不用实现解密算法

第五章：哈希函数

哈希函数：将任意长的消息 M 变换为较短的、固定长度的值 H(M) 的不可逆的单选密码体制，其中 H(M) 称为消息摘要，又称数字指纹

基本特征：

算法公开，无需密钥
数据压缩
易于计算
🌟单向性（抗原像性）：给定消息的散列值 h(m) ，要得到消息 m 在计算上不可行

Hash 函数安全性要求：

抗弱碰撞性：给定消息 m ，寻找与 m 不同的消息 m’ ，使得 h(m) = h(m’) 在计算上不可行
抗强碰撞性：寻找两个不同消息 m 和 m’，使得 h(m) = h(m’) 在计算上不可行

MD5

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

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

SHA1

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

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

🌟数据填充

填充一个 “1” 和若干个 “0” 使消息长度模 512 与 448 同余。
将原始消息长度以 64 比特表示附加在填充结果后面，使得消息长度恰好为 512 比特整数倍
512 比特按 32 比特分为 16 组
若原消息长度刚好满足这个条件，则再填充 512 位（1 个 1 和 511 个 0）。

例题：给定一个三个 8 位 ASCII 字符组成的消息 “abc” ，总长度为 l = 24 位

第六章：公钥密码

单向陷门函数 f ：

给出 f 定义域中的任意元素 x，计算 f(x) 是容易的
给出 y = f(x) 中的 y，计算 x：
- 若知道 f 结合进去的信息（陷门，也称密钥），则 x 容易计算
- 若不知道该陷门信息，则 x 难以计算

公钥密码应满足：

解密算法 D 与加密算法 E 互逆，对于所有明文都有

$$
D(E(M,K_e),K_d) = M
$$

由 K_e 求出 K_d 在计算上不可行
算法 E 和 D 都是高效的

优点：

密钥分发简单
需保密的密钥量少
可满足互不相识的人之间私人对话的保密性
可实现数字签名和认证功能

相对于对称密码的不足

密码算法较慢
提供更多信息对算法进行攻击
数据扩展
建立在特定的数学难题上，这种困难性只是一种设想

🌟RSA

🌟RSA算法描述：

密钥生成
- 选择两个大素数 p 和 q，（p ≠ q，需保密）
- 计算 n = p x q，φ(n) = (p-1) × (q-1)
- 选择整数 e 使 (φ(n), e) = 1, 1 < e < φ(n)
- 计算 d，使得 d = e^-1 mod φ(n)
- 得到：公钥为 {e，n}；私钥为 {d}
加密（用e，n）：明文 M < n，密文 C = M^e (mod n)
解密（用d，n）：密文 C，明文 M = C^d (mod n)

计算时，求 d 时，使用欧几里得扩展算法列表运算

正确性验证(欧拉定理)：
$$
C^d \mod n=(M^e)^d \mod n\=M^{ed} \mod n\=M\mod n
$$

🌟RSA的攻击

同模攻击：

假设 m 是明文，两用户的公钥分别是 e₁ 和 e₂ ，且 ( e₁ ,e₂ ) = 1，共同模数 N ，两密文为
$$
c_1 \equiv m^{e_1}\mod N\
c_2 \equiv m^{e_2}\mod N
$$
攻击者知道 N, e₁ , e₂, c₁ 和 c₂，可如下恢复明文 m

( e₁ ,e₂ ) = 1，由欧几里得算法可找出 r, s 满足 re₁ + se₂ = 1。假定 r 是负数，那么
$$
(c_1^{-1})^{-r}c_2^s=m^{re_1+se_2}\equiv m\mod N
$$
无需密钥 d，就可得到明文 m

防御：使用 RSA 公钥密码的通信中，不同用户的密钥不能有相同的模值

低加密指数攻击：

小的公钥可加快加密速度，但过小公钥易受攻击

三个用户都使用 3 作为公钥，对同一明文 m 加密
$$
c_1\equiv m^e \mod n_1\
c_2\equiv m^e \mod n_2\
c_3\equiv m^e \mod n_3
$$
运用中国剩余定理，在 e = 3 时，可以得到
$$
c_x\equiv m^3\mod n_1n_2n_3
$$
所以
$$
m=\sqrt[3]{c_x}
$$
防御：对短消息，用随机数填充以保证
$$
m^e\mod n\neq m^e
$$
从而杜绝低加密指数攻击

🌟ElGamal

🌟ElGamal算法描述：

密钥的生成
- 选取大素数 p、g ∈ Z_p^* 是一个生成元，p、g 作为系统参数所有用户共享
- 每个用户 U 都随机挑选整数 x，2 ≤ x ≤ p-2，计算
$$
y=g^x\mod p
$$
- y 作为用户 U 的公钥，x 作为用户 U 的私钥
加密
- 用户 A 把明文编码为一个 0 ~ p-1 之间的整数 m
- A 挑选一个秘密随机数 r （2 ≤ r ≤ p-2）
  $$
  c_1=g^r\mod p \
  c_2 = m*y^r\mod p
  $$
- A 把二元组（c1, c2）作为密文传送给用户 B。
解密
- B 收到密文二元组后，做解密计算
  $$
  m=c_2*(c_1^x)^{-1}\mod p
  $$

算法正确性验证：
$$
c_2(c_1^x)^{-1}\mod p=(y^rm)(g^{rx})^{-1} \mod p \
=(g^{xr}m)g^{-rx}\mod p \
=m\mod p
$$

ps: 安全性分析 8 考

第七章：数字签名

数字签名的目的：保证信息的完整性和真实性

完善的签名方案应满足的条件：

不可否认性
不可伪造性
公正的仲裁

🌟RSA数字签名方案

签名算法如下：

生成密钥（与加密系统一样）
签名过程 (d, n)：

用户 A 对消息 M ∈ Z_n 进行签名，计算
$$
S = Sig(H(M)) = H(M)^d \mod n
$$
并将 S 附在消息 M 后，发送
验证过程 (e, n)：

给定 (M, S) ，Ver(M, S)为真，则下式成立
$$
H(M) = S^e \mod n
$$
正确性

因为
$$
s\equiv h(m)^d\mod n\
de \equiv 1\mod \varphi(n)\
\varphi(n)=(p-1)(q-1)
$$
所以
$$
s^e\equiv h(m)^{ed}\equiv h(m)^{k\varphi(n)+1}\equiv h(m)h(m)^{k\varphi(n)}\
\equiv h(m)[h(m)^{\varphi(n)}]^k\equiv h(m)\mod n
$$

安全性

如果不加 Hash 函数，直接对消息进行签名

一般攻击：

攻击者任选一个数据 Y，用 A 的公钥计算 X = Y^e mod n，便可以用 Y 伪造 A 对消息 X 的签名
$$
Y = X^d \mod n
$$
利用已有签名进行攻击:

如果消息 M₁、M₂ 的签名分别是 S₁、S₂，则任何指导 M₁、M₂ ，S₁、S₂ 的人可以伪造对消息 M₁、M₂ 的签名 S₁、S₂，因为
$$
Sig(M_1,M_2) = Sig(M_1)Sig(M_2)
$$
利用签名获得明文:

截获 C＝M^e mod n，选择随机数 r，计算
$$
x = r^e \mod n\
y = xC\mod n
$$
设法让发送者对 y 签名，获得
$$
S = y^d\mod n
$$
攻击者计算
$$
r^{-1}S\mod n=r^{-1}y^d\mod n\
=r^{-1}x^dC^d\mod n=C^d\mod n=M
$$

其中 H(M) 的另外一个作用就是可以加快签名速度。

🌟ElGamal数字签名方案

签名算法如下：

系统初始化：选择大素数 p，选择生成元 g ∈ Z_p^* 和随机数 x ∈ _RZ_p。

公钥 (p, g, y)，私钥为 x (1 ≤ x ≤ p-1)，其中
$$
y=g^x\mod p
$$
签名过程：给定消息 M，签名者如下计算
- 选择随机数 k ∈ Z_p^*，且 k 与 (p-1) 互素
- 计算 M 的哈希值 H(M) ，计算
  $$
  r = g^k\mod p\
  s=(H(M)-xr)k^{-1}(\mod p-1)
  $$
- 将 (r, s) 作为签名，与 M 一起发送给接收方
签名验证
- 计算消息 M 哈希值 H(M)
- 验证公式
  $$
  y^rr^s=g^{H(M)}\mod p
  $$
  成立则认为 (r, s)为有效签名，否则认为签名是伪造的
正确性
$$
ks\equiv h(m)-xr\mod (p-1)\
g^{ks}\equiv g^{h(m)-xr}\mod p\
g^{ks}g^{xr}\equiv g^{h(m)}\mod p\
y^rr^s=g^{H(m)}\mod p
$$

安全性：

非确定性数字签名算法，同一消息 M 的签名依赖于随机数 k
安全性基于有限域上计算离散对数的困难性（DLP）

实际中常用本原元 α 生成一个阶为素数的子群，所有元素都是本原元，不存在子群，从而抵抗这种攻击。
随机数 k 不能泄露（已知 k 可以计算 x ）
随机数 k 不能被重复使用（泄露 x ）

设 k 用来对两个不同消息签名，则 r 相同。签名分别为 (r, s₁), (r, s₂)。因为
$$
s_1\equiv [h(m_1)-xr]k^{-1}\mod (p-1)\
s_2\equiv [h(m_2)-xr]k^{-1}\mod (p-1)\
(s_1-s_2)k\equiv [h(m_1)-h(m_2)]\mod (p-1)
$$
因为消息 m₁，m₂ 不同，他们所以签名不同的概率很大，则
$$
k\equiv h(m_1)-h(m_2)^{-1}\mod (p-1)
$$
之后可以将 k 代入上面两式来计算私钥
$$
x\equiv \frac{h(m_1)-s_1k}{r}\mod p-1
$$
哈希函数的应用

如果未使用 Hash 函数则易受到攻击。攻击者选取任一整数对 (u, v)，满足
$$
gcd(v, p-1)=1
$$
计算
$$
r\equiv g^uy^v\mod p\
s\equiv -rv^{-1}\mod (p-1)\
m\equiv su\mod p
$$
则消息 m 及其签名 (r, s) 可以被验证者接受，即攻击者成功进行存在性伪造。因为
$$
y^rr^s\equiv y^r(g^ug^v)^s\equiv y^{r+w}g^{us}\equiv g^m\mod p
$$
又因为
$$
g^m\equiv g^{su}\mod p
$$
也就是说，签名 (r, s) 使等式
$$
y^rr^s=g^{m}\mod p
$$
成立

所以使用 Hash 函数能够有效提高 ElGamal 数字签名方案安全性。

Schnorr签名体制

签名算法如下：

系统初始化：p、q 大素数，选择生成元 g ∈ Z_p^* ，且
$$
g^q\equiv 1\mod q\ne 1
$$
选择随机数 1 < x < q，计算
$$
y\equiv g^x\mod p
$$
公钥为（p, q, g, y），私钥为（ x ）
签名算法

签名者选取随机数 k，1 ≤ k ≤ q-1，计算
$$
r\equiv g^k\mod p\
e= h(m,r)\
s\equiv (xe+k)\mod q
$$
计算得签名 (e, s)，其中 h 为安全的 Hash 函数
验证算法

收到消息 m 和签名 (e, s)，计算
$$
r_1\equiv g^sy^{-e}\mod p
$$
验证
$$
e=h(m,r_1)
$$
等式成立则签名有效；否则无效
正确性

因为
$$
r\equiv g^k\mod p\
e= h(m,r)\
s\equiv (xe+k)\mod q
$$
所以
$$
r_1\equiv g^sy^{-e}\equiv g^sg^{-xe}\equiv g^{s-xe}\
\equiv g^{xe+k-xe}\equiv g^k\equiv r\mod p
$$
因此
$$
h(m, r_1)=h(m,r)=e
$$

安全性：

Schnorr数字签名方案中 g 为 Z_p^* 的 q 阶子群的生成元，较 Elgamal 签名方案的生成元阶为 p-1。所以从穷尽搜索签名者密钥的角度，Elgamal 签名安全性更高。除此之外，安全性与 Elgamal 签名方案相同。

试卷题型

计算题（60分）

6道或8道

分析题（20分）

4个小题

综合题（20分）

3个小题或2个小题