密码学备考知识点复习
前言
就是根据老师给的考察范围来进行一个复习，虽然是开卷考试，但是通过一个有效的复习，可以有效提高在考试中的得分效率，再不济也可以提高在考试中定位课本页数的可能性。
根据老师的给出的考察题目及类型，有五道大题，分别考察RSA、ECC、AES、数字签名以及对涉及多个知识点的综合设计，总体感觉要比上学期的信息安全课程会舒服一点。
MindMap
RSA（20分）
RSA是我们考察的第一题，同时也是三种密码算法加解密最高的一题。
背景
在了解RSA之前，我们需要知道它的一些背景：这是基于大整数素因子分解问题（tps：公钥密码大多数算法都是基于一些数学难题），这个问题顾名思义，其实就是对于一个大整数，我们很难去计算它的 素因子。这个算法之所以叫RSA，就是发明者有三个人，分别为：Rivest、Shamir（就是我们在信息安全中学到的Shamir门限分割）、Adleman。 RSA的基础是数论中的欧拉定理。
欧拉定理
设 a , m ∈ N + , 且 g c d ( a , m ) = 1 , 则 : a φ ( m ) = 1 ( m o d m ) φ ( m ) , 表 示 小 于 m 的 区 间 中 的 正 整 数 和 m 互 素 的 个 数 ， 该 函 数 又 称 为 欧 拉 函 数 。 设a,m \in N^+, 且 gcd(a, m) = 1,\\ 则: a^{\varphi(m)} = 1(modm) \\ \varphi(m), 表示小于m 的区间中的正整数和m互素的个数，该函数又称为欧拉函数。 设a,m∈N+,且gcd(a,m)=1,则:aφ(m)=1(modm)φ(m),表示小于m的区间中的正整数和m互素的个数，该函数又称为欧拉函数。
题型（猜测）
依据课堂上的例题和测验题来看，应该就是考察学生对RSA算法流程的掌握程度，所以大概率就是考察RSA的加解密，当然这个过程其实就是RSA 公钥密码体制的流程。
密钥生成
分5步：
- 选取两个大素数p和q
- 计算n=pxq，φ(n) =（p-1）（q-1），这个φ（n）就是我们上面提到的欧拉函数。
- 选取一个比 φ(n) 小的整数e，e>1，
gcd(φ(n), e) = 1 - 然后求d，d是e关于欧拉函数的逆元。
- 公钥：{e, n}, 私钥：{d, n}
加密
我们设明文M，密文C
C
=
M
e
m
o
d
n
C = M^{e}mod n
C=Memodn
解密
M = C d m o d n M = C^d modn M=Cdmodn
难点——乘法逆元求解
上面的流程的难点就在于逆元的求解，如果到现在还不会乘法逆元的求解，那你急需看下我这个例子。
我们求3 关于 20 的乘法逆元。
辗转相除判断互素
先用欧几里得（辗转相除）
20
=
6
?
3
+
2
3
=
1
?
2
+
1
20 = 6 * 3 + 2 \\ 3 = 1 * 2 + 1
20=6?3+23=1?2+1
当我们求出 余数为1 的时候就可以了，此时我们可以知道 3，20 互素。
接下来求解逆元的过程，有两种思路，利用拓展欧几里得算法，就是逆推相关式子。
拓展欧几里得
3 ? 1 ? 2 = 1 3 ? 1 ? ( 20 ? 6 ? 3 ) = 7 ? 3 ? 20 = 1 3 - 1 * 2 = 1 \\ 3 - 1 * (20 - 6 * 3) = 7 * 3 - 20 = 1 3?1?2=13?1?(20?6?3)=7?3?20=1
所以，3关于20的逆元就是7。
欧拉快速演算
我们先倒写出在辗转相除时得到的商 1，6
如下表，我们将第一行视为x，第二行视为y，第一行前两先空出来，第二行分别为0，1
| 1 | 6 | ||
|---|---|---|---|
| 0 | 1 | 1 | 7 |
从第一行对下来的第二行对应的位置的值为
y
i
=
y
i
?
2
+
y
i
?
1
?
x
i
y_i = y_{i-2} + y_{i - 1}*x_i
yi?=yi?2?+yi?1??xi?
然后要求取出的逆元就是最后一个y的值，当然此时会根据 i 的奇偶性判断，这里规定 i 从1开始
假
设
y
m
为
最
终
的
值
，
d
为
所
求
的
逆
元
d
=
{
y
m
,
m
%
2
=
=
0
?
y
m
,
m
%
2
=
=
1
假设y_m 为最终的值， d为所求的逆元 d = \left\{ \begin{aligned} y_m, \qquad &m \% 2 == 0 \\ -y_m, \qquad &m \%2 ==1 \end{aligned} \right.
假设ym?为最终的值，d为所求的逆元d={ym?,?ym?,?m%2==0m%2==1?
ECC（15分）
椭圆曲线密码体制，简称ECC。它是基于椭圆曲线上的离散对数问题。
椭圆曲线
E : y 2 = x 3 + a x + b E : y ^2 = x^3 + ax + b E:y2=x3+ax+b
上面的方程式其实也可以用来表达（x，y）构成的的集合，特别注意：
如
果
方
程
式
没
有
重
复
的
因
子
，
或
者
4
a
3
+
27
b
2
≠
0
则
E
可
以
为
群
。
如果方程式没有重复的因子，或者4a^3 + 27b^2 \neq 0 \\ 则E可以为群。
如果方程式没有重复的因子，或者4a3+27b2?=0则E可以为群。
无穷远点O
其实就是在讨论椭圆曲线群时，需要引入的一个参考点。
有限域
曲线方程中的所有系数都是在 有限域GF(p)中的元素，p为一大素数。
离散化
密码学中不讨论椭圆曲线的连续性，而是关注离散化后的整数点，即点中的 x，y都是整数。
运算规则
加法规则
-
所 有 点 P ∈ E p , 则 P + O = O + P = P , P + ( ? P ) = 0 所有点P\in E_p, 则P + O = O + P = P, P + (-P) = 0 所有点P∈Ep?,则P+O=O+P=P,P+(?P)=0
-
P = ( x 1 , y 1 ) ∈ E p , Q = ( x 2 , y 2 ) ∈ E p , p ≠ ? Q 则 P + Q = R = ( x 3 , y 3 ) ∈ E p λ = { y 2 ? y 1 x 2 ? x 1 , P ≠ Q 3 x 1 2 + a 2 y 1 , P = Q P=(x_1, y_1) \in E_p, Q=(x_2,y_2)\in E_p, p\neq -Q\\ 则P+Q = R = (x_3, y_3)\in E_p \\ \lambda = \left\{ \begin{aligned} \frac{y_2-y_1}{x_2-x_1}, \qquad &P\neq Q\\ \frac{3x^2_1+a}{2y_1}, \qquad &P=Q \end{aligned} \right. P=(x1?,y1?)∈Ep?,Q=(x2?,y2?)∈Ep?,p?=?Q则P+Q=R=(x3?,y3?)∈Ep?λ=????????x2??x1?y2??y1??,2y1?3x12?+a?,?P?=QP=Q?
-
s, t 为整数
对 所 有 的 点 P ∈ E p , 有 ( s + t ) P = s P + t P 对所有的点P\in E_p, 有 (s+t)P = sP+tP 对所有的点P∈Ep?,有(s+t)P=sP+tP
(其实就是分配律)
乘法规则
-
如果k为整数，
P ∈ E p , 有 k P = P + . . . + P = ∑ i = 1 k P P\in E_p, 有 kP = P+...+P = \sum_{i=1}^{k}{P} P∈Ep?,有kP=P+...+P=i=1∑k?P -
s, t为整数，
s ( t P ) = ( s t ) P s(tP) = (st)P s(tP)=(st)P
椭圆曲线加法交换群（Abel群）
-
? P , Q ∈ E , 有 P + Q = Q + P ∈ E \forall P, Q \in E, 有P +Q = Q+P \in E ?P,Q∈E,有P+Q=Q+P∈E
-
? P ∈ E . 有 P + O = P \forall P \in E. 有 P + O = P ?P∈E.有P+O=P
-
P + ( ? P ) = O P + (-P) = O P+(?P)=O
-
直线L 交 E 于P、Q、R三点（三点未必不同），则
( P + Q ) + R = O (P+Q) +R = O (P+Q)+R=O -
? P , Q , R ∈ E , 有 ( P + Q ) + R = P + ( Q + R ) \forall P,Q,R \in E, 有(P+Q)+R = P + (Q+R) ?P,Q,R∈E,有(P+Q)+R=P+(Q+R)
满足上述性质，加上无穷远点O作为零元，就可以作为 加法交换群（Abel群）
阶
椭圆曲线上的一点P，若存在最小的正整数n，使得nP=O，称n为点P的阶。
题型1 椭圆群的求取
需要我们求取椭圆群的点，做法很简单，我们在 0 到 p-1 的范围内枚举x，带入E的方程式，计算y，当y为整数就是要求取的点，这里没什么技巧分享，我们用一个例子展示。
p=11，a=1，b=2，我们以计算x=1，为例
y
2
=
x
3
+
x
+
2
=
4
∴
y
=
2
,
y
=
?
2
m
o
d
p
=
9
y^2 = x^3+x+2 = 4 \\ \therefore y = 2, \qquad y = -2 mod p = 9
y2=x3+x+2=4∴y=2,y=?2modp=9
如果第一下计算的方程的右边不是一个完全平方数，可以模加p，这里分享一个知识点，加到超过（p-1）^2就不用加了。
题型2 加解密过程
会给出p，a，b，G，k，私钥n。
往往第一步就是计算公钥 P = nG，然后基本上就是密文和明文的过程。
加密
注意：求取的密文是一个点对，
C
1
=
k
G
,
C
2
=
P
m
+
k
P
A
C
m
=
{
C
1
,
C
2
}
C_1 = kG, C_2 = P_m+kP_A \\ C_m =\{C_1, C_2\}
C1?=kG,C2?=Pm?+kPA?Cm?={C1?,C2?}
解密
P m = C 2 ? C 1 = P m + k P A ? k P A P_m = C_2 - C_1 = P_m + kP_A - kP_A Pm?=C2??C1?=Pm?+kPA??kPA?
题型3 DH密钥交换
即利用ECC 实现 Diffle—Hellman 密钥交换。
我觉得可以分为以下步骤进行：公开参数构造，双方选定私钥，并计算公钥，发送，实现共享密钥。
公开参数构造
就是选取p，a，b，G，阶数N。
交换过程
-
A选取私钥nA，nA<n, 计算公钥PA。
-
B同上。
-
A，B发送公钥给彼此，然后再用私钥计算共享密钥
K = n A P B = n A ( n B G ) = n B ( n A G ) ? n B P A K = n_AP_B = n_A(n_BG) = n_B(n_AG) - n_BP_A K=nA?PB?=nA?(nB?G)=nB?(nA?G)?nB?PA?
AES(15分)
如果对这个算法的实现，可以参考我的这篇blog(5条消息) AES-128算法实现（附C++源码）_物联黄同学的博客-CSDN博客_aes128加密算法源码
流程图
密钥拓展
参考下述公式进行密钥拓展
k
e
y
s
[
i
]
=
{
k
e
y
s
[
i
?
1
]
⊕
k
e
y
s
[
i
?
4
]
,
i
%
4
!
=
0
T
(
k
e
y
s
[
i
?
1
]
)
⊕
k
e
y
s
[
i
?
4
]
,
i
%
4
=
=
0
keys[i] = \left\{ \begin{aligned} keys[i - 1] \oplus keys[i - 4], \qquad i \% 4 != 0 \\ T(keys[i-1]) \oplus keys[i - 4], \qquad i \% 4 == 0 \end{aligned} \right.
keys[i]={keys[i?1]⊕keys[i?4],i%4!=0T(keys[i?1])⊕keys[i?4],i%4==0?
行位移没什么知识点，所以不在此阐述。知道从第一行开始，第一行不移位，接下来的每一行比上一行多移动一位。
列混淆
其实就是矩阵乘法运算
轮密钥加
其实就是将在密钥拓展获取的密钥逐论和与状态（明文，密文）异或。
小技巧 xtime函数
函数xtime(x)定义为 上的x·b(x)。其运算如下：若b7 =0，则x·b(x)的结果就是把字节b左移一位；若b7 =1，则结果需异或‘1B’。
解密
解密和加密相反，其实就是将加密的过程反过来，行移位是左移，逆行移位就是右移。逆列混合的变化是
其他的过程参考流程图。
题型（猜测）
AES作为考到唯一一个公钥密码体制，其实主要就是考察学生对这个过程的熟悉和了解程度，所以其实就是照着流程来，然后考虑到计算量，应该只会考察其中的一部分过程，按照测试题来看，列混淆 和 轮密钥加的概率最大。
数字签名（25分）
我超，xdm，25分！和综合设计一个分数，不说了，好吧，必拿下！
背景
就是时代发展的产物，针对电子文档的一种签名确认方法，从而实现对数字对象的 合法化、真实性 的 标记，并提供签名者的承诺。
电子签名实现的就是 数字化文档的 认证性、完整性、不可否认性。
教学内容中有四种，分别是：基于RSA数字签名，基于ElGamal数字签名，Schnorr数字签名、基于ECC数字签名。考察的题目一个会在后三种中出，鉴于ECC会在前面已经出过了，可以重点关注ElGamal，香农数字签名。考察的重点应该在签名和验证的过程描述，以及证明签名算法正确性。
原理图
RSA 数字签名方案
m表示消息，e公钥，d私钥。
签名
-
Hash函数得到消息摘要h(m)
-
签名算法计算签名
s = S i g k ( m ) = h ( m ) d m o d n s =Sig_k(m) = h(m)^dmod n s=Sigk?(m)=h(m)dmodn
验证
-
hash计算摘要。
-
检验等式
h ( m ) m o d n = s e m o d n h(m)mod n = s^e modn h(m)modn=semodn
是否成立，从而验证签名的有效性。
算法正确性证明
s = h ( m ) d m o d n , d ? e = 1 ( m o d φ ( n ) ) ∴ s e m o d n = h ( m ) e d m o d n = h ( m ) k φ ( n ) + 1 m o d n = h ( m ) ? h ( m ) k φ ( n ) m o d n = h ( m ) ? ( h ( m ) φ ( n ) ) k m o d n = h ( m ) s = h(m)^dmodn, \qquad d*e = 1(mod\varphi(n)) \\ \begin{aligned} \therefore s^e mod n &= h(m)^{ed}modn \\ &= h(m)^{k\varphi(n)+1}modn \\ &= h(m) * h(m)^{k\varphi(n)}modn \\ &= h(m)*(h(m)^{\varphi(n)})^k modn \\ &= h(m) \end{aligned} s=h(m)dmodn,d?e=1(modφ(n))∴semodn?=h(m)edmodn=h(m)kφ(n)+1modn=h(m)?h(m)kφ(n)modn=h(m)?(h(m)φ(n))kmodn=h(m)?
其实最后一步，我有点小困惑，根据欧拉定理，h（m）和φ（n）必须互素才行。
Elgamal 签名体制
初始化
选择一个大素数p，Zp为对应的离散对数域，在这个域中求解离散对数困难，在这个域中选择一个生成元g，随机选择x，计算
y
=
g
x
m
o
d
p
y = g^x modp
y=gxmodp
公钥y，g，p，私钥x。
签名
随 机 数 k ∈ R Z p ? r = ( g k m o d p ) s = ( h ( m ) ? x r ) k ? 1 m o d ( p ? 1 ) 随机数k\in_RZ_{p^*} \\ \begin{aligned} r &= (g^k mod p)\\ s &= (h(m)- xr)k^{-1} mod(p-1) \end{aligned} 随机数k∈R?Zp??rs?=(gkmodp)=(h(m)?xr)k?1mod(p?1)?
数字签名为（s, r）。
验证
y r r s = g h ( m ) m o d p y^rr^s = g^{h(m)}modp yrrs=gh(m)modp
正确性证明
∵ r = ( g k m o d p ) , s = ( h ( m ) ? x r ) k ? 1 m o d ( p ? 1 ) ∴ k s = h ( m ) ? x r m o d ( p ? 1 ) g k s = g h ( m ) ? x r m o d p g k s g x r = g h ( m ) m o d p y r r s = g h ( m ) m o d p \because r = (g^k mod p), \qquad s = (h(m) - xr)k^{-1} mod(p-1) \\ \begin{aligned} \therefore ks = h(m) - xr mod(p-1)\\ g^{ks} = g^{h(m)-xr}modp \\ g^{ks}g^{xr} = g^{h(m)}mod p \\ y^rr^s = g^{h(m)}modp \end{aligned} ∵r=(gkmodp),s=(h(m)?xr)k?1mod(p?1)∴ks=h(m)?xrmod(p?1)gks=gh(m)?xrmodpgksgxr=gh(m)modpyrrs=gh(m)modp?
安全性考虑（难点，思考题）
- 不能泄露随机数k——此时计算私钥x就不是离散对数问题了。
- 随机数k不能重复使用——不同的消息重复使用，k会被容易（相较）算出来，从而私钥被计算，同时不符合数字签名的特性。
- 不用hash函数，会收到攻击。
Schnorr 签名
初始化
大素数p，q，生成元g，随机数x
q
∣
(
p
?
1
)
,
g
q
=
1
(
m
o
d
p
)
,
g
∈
Z
q
8
1
<
x
<
q
,
y
=
g
x
m
o
d
p
q | (p-1), g^q = 1(modp), g \in Z_{q^8} \\ 1 < x < q, y = g^xmodp
q∣(p?1),gq=1(modp),g∈Zq8?1<x<q,y=gxmodp
公钥p，q，g，y，私钥x。
签名
选择随机数k
r
=
g
k
m
o
d
p
e
=
H
(
r
,
m
)
s
=
x
e
+
k
m
o
d
q
r = g^k mod p \\ e = H(r, m) \\ s = xe + k mod q
r=gkmodpe=H(r,m)s=xe+kmodq
签名为（e，s）
验证
r 1 = g s y ? e m o d p H ( r 1 , m ) 验 证 H ( r 1 , m ) = e r_1 = g^sy^{-e}modp \\ H(r_1,m)\\ 验证H(r_1, m) = e r1?=gsy?emodpH(r1?,m)验证H(r1?,m)=e
正确性证明
R 1 = s G + H ( m ) P = ( k ? H ( m ) n A ) G + H ( m ) P = k G ? H ( m ) n A G + H ( m ) P = k G = R \begin{aligned} R_1&= sG+H(m)P\\ &= (k-H(m)n_A)G+H(m)P\\ &= kG-H(m)n_AG + H(m)P \\ &= kG \\ &= R \end{aligned} R1??=sG+H(m)P=(k?H(m)nA?)G+H(m)P=kG?H(m)nA?G+H(m)P=kG=R?
和Elgmal性能对比
TE ：幂运算的计算量
TH：哈希计算的计算量
TM：乘积运算的计算量
ECC
初始化参考上面的初始化过程以及ECC加密体制。
签名
R = k G s = k ? H ( m ) ? n A m o d p R = kG\\ s = k-H(m)*n_A mod p R=kGs=k?H(m)?nA?modp
签名值（R,s)
验证
R 1 = s G + H ( m ) P 验 证 等 式 R 1 = R R_1 = sG + H(m)P \\ 验证等式 R_1 = R R1?=sG+H(m)P验证等式R1?=R
正确性证明
R 1 = s G + H ( m ) P = ( k ? H ( m ) n A ) G + H ( m ) P = k G ? H ( m ) n A G + H ( m ) P = k G = R \begin{aligned} R_1&= sG+H(m)P\\ &= (k-H(m)n_A)G+H(m)P\\ &= kG-H(m)n_AG + H(m)P \\ &= kG = R \end{aligned} R1??=sG+H(m)P=(k?H(m)nA?)G+H(m)P=kG?H(m)nA?G+H(m)P=kG=R?
综合设计（看命）
根据所学的可以参考复习流密码和序列密码，以及密钥交换协议，还有各种签名，比如盲签名、群签名和群、环、域等数论知识点等。