公钥密码学2
（1）主要看的书籍与相关视频：《现代密码学导论：原理与协议》、《Introduction to Modern Cryptography》
（2）具体学习情况如下：
这周的学习有一些收获，也有一些问题还没有解决。有关使用PKCS1 v1.5的填充方式的RSA加密的例子没找到参考的代码，然后安装vs的时候电脑内存不够了，所以还没有实现填充式RSA。
PKCS1 v1.5
用于RSA加密的PKCS1 v1.5编码格式主要用于提供机密性，通常用于分发对称加***。它有
01
01
01和
02
02
02两种模式，分别代表签名和加密。下图是将
m
m
m填充为
x
x
x的过程：
假如
x
x
x是1024比特的RSA**（1024比特=1024/8=128字节），那么，消息
m
m
m的长度$\leq
128
−
11
字
节
。
因
为
，
如
果
B
T
=
02
或
01
，
128-11字节。因为，如果BT=02或01，
128−11字节。因为，如果BT=02或01，r$至少要有8字节长。
攻击：
选择密文攻击安全与选择明文攻击安全的区别就是，前者具有”不可延展性“这一特点。也就是说，如果一个攻击者试图去修改一个指定的密文，其结果要么是一个非法密文，要么是一个和原文没有任何关系的明文的密文。而PKCS #1 v1.5是选择明文攻击安全的，选择密文攻击不安全的，意思就是它具有延展性。
我们都知道这样一个现象：如果服务器接收到一个没有正确解密的密文，它可能会请求重新传输或终止会话，而这两个事件中的任何一个都将在观察到的流量中产生明显的变化。这种攻击已经被证明在各种已部署的协议上实际有效。在PKCS #1 v1.5 加密中，只要攻击者能够将解密成功后的接收者的行为与解密失败后的接收者的行为区分开来，就可以进行攻击。
也就是说，攻击者可以向服务器发送任何密文，并了解底层编码的数据是否以正确的PKCS1 v1.5格式填充（基于是否返回了“错误填充”错误）。这看起来像是毫无意义的信息，但是，它使得对手能够完全恢复其选择的任何密文的原始消息。
Bleichenbacher（布莱申巴赫）的攻击过程：攻击者生成一个随机数 s s s，对获得的密文 c c c进行一个处理： c ′ = s e ⋅ c m o d N = ( s ⋅ x ) e m o d N c'=s^e·c \bmod N=(s·x)^e \bmod N c′=se⋅cmodN=(s⋅x)emodN，然后发送给Web服务器。要求某个 s s s满足服务器解密后发现 s ⋅ x s·x s⋅x以PKCS #1 v1.5格式填充，则解密成功，攻击者可以学习到 x ′ = s ⋅ x m o d N x'=s·x \bmod N x′=s⋅xmodN的前两个字节为 0 x 00 ∣ ∣ 0 x 02 0x00||0x02 0x00∣∣0x02，那么攻击者可以得到 x ′ x' x′的范围是 2 ⋅ 2 8 ( ∣ ∣ N ∣ ∣ − 2 ) ≤ x ⋅ s m o d N < 3 ⋅ 2 8 ( ∣ ∣ N ∣ ∣ − 2 ) 2·2^{8(||N||-2)} \leq x·s \bmod N <3·2^{8(||N||-2)} 2⋅28(∣∣N∣∣−2)≤x⋅smodN<3⋅28(∣∣N∣∣−2)。然后精心挑选某个 s i s_i si（这里看得不是很明白，感觉应该是：每一次的成功挑选，都在缩小 x ′ x' x′可能取值的范围），重复上述过程，直到找到那个 x ′ x' x′，最终就能求出 x = x ′ ⋅ s − 1 m o d N x=x'·s^{-1} \bmod N x=x′⋅s−1modN。
PKCS1 v2.0 ：OAEP（最优非对称加密填充）
PKCS1 v1.5填充的特定弱点是它不是非常冗余，而OAEP使用哈希函数添加了大量的内部冗余。OAEP算法是Feistel网络的一种形式，使用两个哈希函数
G
G
G和
H
H
H，只要它们足够好，RSA-OAEP加密方案就是安全的。
G
:
{
0
,
1
}
k
→
{
0
,
1
}
f
+
k
1
G:\{0,1\}^{k} \rightarrow\{0,1\}^{f+k_1}
G:{0,1}k→{0,1}f+k1
H
:
{
0
,
1
}
f
+
k
1
→
{
0
,
1
}
k
H:\{0,1\}^{f+k_1} \rightarrow \{0,1\}^{k}
H:{0,1}f+k1→{0,1}k
其中，
f
+
k
+
k
1
<
N
f+k+k_1<N
f+k+k1<N
1、对消息 m m m进行OAEP填充：设 m ′ = m ∣ ∣ 00...0 m'=m||00...0 m′=m∣∣00...0，则 s = m ′ ⨁ G ( r ) , t = r ⨁ H ( s ) s=m' \bigoplus G(r),t=r \bigoplus H(s) s=m′⨁G(r),t=r⨁H(s)， s s s的长度对应 m ′ m' m′的长度， t t t的长度对应 r r r的长度，令 x = s ∣ ∣ t x=s||t x=s∣∣t。
2、使用RSA加密： c = x e m o d N c=x^e \bmod N c=xemodN，其中， p k = < N , e > pk=<N,e> pk=<N,e>， s k = < N , d > sk=<N,d> sk=<N,d>。
攻击者如果要恢复 m m m，必须恢复整个 s s s和整个 t t t。由于哈希函数的特性，其输入的一个比特的变化会导致其结果完全不同，所以必须恢复整个 s s s和整个 t t t。在 G G G和 H H H是随机预言机的条件下，RSA-OAEP已被证明是CCA安全的。由此可见，PKCS1 v1.5或者v2.0编码都避免了”教科书式RSA“的确定性，是RSA加密的升华。
数字签名
1、“教科书式RSA”签名方案(实际并不安全)
p
k
=
<
N
,
e
>
pk=<N,e>
pk=<N,e>，
s
k
=
<
N
,
d
>
sk=<N,d>
sk=<N,d>，
m
∈
Z
N
∗
m \in Z_N^*
m∈ZN∗，
σ
∈
Z
N
∗
\sigma \in Z_N^*
σ∈ZN∗
签名：
σ
=
m
d
m
o
d
N
\sigma=m^d \bmod N
σ=mdmodN
验证：
m
=
σ
e
m
o
d
N
m=\sigma^e~mod~~N
m=σe mod N
针对该方案的攻击：
（1）攻击者选择一个任意的
σ
\sigma
σ，计算
m
=
σ
e
m
o
d
N
m=\sigma^e~~mod~~N
m=σe mod N，然后输出（
m
m
m，
σ
\sigma
σ）作为一个伪造签名。
（2）攻击者获取了两个签名（来自同一签名者） σ 1 \sigma_1 σ1（对应 m 1 m_1 m1）， σ 2 \sigma_2 σ2（对应 m 2 m_2 m2），假设攻击者想要伪造一个 m m m关于 p k = < N , e > pk=<N,e> pk=<N,e>的签名，假设 m 2 = m / m 1 m o d N m_2=m/m_1~~mod~~N m2=m/m1 mod N， σ = σ 1 ⋅ σ 2 m o d N \sigma=\sigma_1·\sigma_2~~mod~~N σ=σ1⋅σ2 mod N，则 σ e = ( σ 1 ⋅ σ 2 ) e = ( m 1 d ⋅ m 2 d ) e = m 1 e d ⋅ m 2 e d = m 1 m 2 = m m o d N \sigma^e=(\sigma_1·\sigma_2)^e=(m_1^d·m_2^d)^e=m_1^{ed}·m_2^{ed}=m_1m_2=m~~mod~~N σe=(σ1⋅σ2)e=(m1d⋅m2d)e=m1ed⋅m2ed=m1m2=m mod N
2、“散列后RSA”签名方案（在理想模型下可证明是安全的）
”散列后RSA“签名方案也叫做RSA-FDH签名方案，它的提出就是为了解决方案1中的攻击。它是一种使用RSA和全域哈希的可证明安全盲签名方案。该方案仅仅将明文 m m m进行哈希函数计算，得到的结果再进行其 d d d次方模 N N N的计算。虽说方案2比方案1更加安全一些，至少在针对方案1的一些攻击在方案2中是不可行的。但是只有当 H H H为随机预言机时，该方案是安全的。（签名： σ = H ( m ) d m o d N \sigma=H(m)^d \bmod N σ=H(m)dmodN，验证： H ( m ) = σ e m o d N H(m)=\sigma^e~mod~~N H(m)=σe mod N）
在PKCS1 v2.1中的数字签名方案（RSA-PSS）是RSA-FDH签名方案的变体，消息的签名依赖于一个随机数 s a l t salt salt，由签名者在生成签名时选择的。如果 s a l t salt salt为 N U L L NULL NULL，那构造出来的签名跟RSA-FDH签名类似。
3、Lamport的“一次性签名”方案
一次性签名是最多能签一个消息的签名方案。如果签多个消息，攻击者就可以伪造签名。所以每签一个消息就需要一个新的公私钥对。
对长度为3的消息的签名及验证过程大致如下：在进行签名之前，签名者根据消息的长度，生成一对公私钥对 p k ， s k pk，sk pk，sk，然后进行签名。签名： m = 011 m=011 m=011， s k = ( x 1 , 0 x 2 , 0 x 3 , 0 x 1 , 1 x 2 , 1 x 3 , 1 ) sk=\left(\begin{array}{cc} x_{1,0} & x_{2,0} & x_{3,0} \\ x_{1,1} & x_{2,1} & x_{3,1} \end{array} \right) sk=(x1,0x1,1x2,0x2,1x3,0x3,1)，故 σ = ( x 1 , 0 , x 2 , 1 , x 3 , 1 ) \sigma=(x_{1,0},x_{2,1},x_{3,1}) σ=(x1,0,x2,1,x3,1)。验证： p k = ( y 1 , 0 y 2 , 0 y 3 , 0 y 1 , 1 y 2 , 1 y 3 , 1 ) pk=\left(\begin{array}{cc} y_{1,0} & y_{2,0} & y_{3,0} \\ y_{1,1} & y_{2,1} & y_{3,1} \end{array} \right) pk=(y1,0y1,1y2,0y2,1y3,0y3,1)，如果 H ( x 1 , 0 ) = y 1 , 0 , H ( x 2 , 1 ) = y 2 , 1 , H ( x 3 , 1 ) = y 3 , 1 H(x_{1,0})=y_{1,0},H(x_{2,1})=y_{2,1},H(x_{3,1})=y_{3,1} H(x1,0)=y1,0,H(x2,1)=y2,1,H(x3,1)=y3,1，说明验证成功。
4、基于Chain的签名方案
只能使用给定的 s k sk sk对单个消息进行签名具有一定的局限性。基于Chain的签名方案是一种基于抗冲突哈希函数的方法，它允许签名者对任意多条消息进行签名，代价是维护在每个签名生成后必须更新的状态。
在该方案中，签名者先生成一对公私钥对 ( p k 1 , s k 1 ) (pk_1,sk_1) (pk1,sk1)。在对第一个消息 m 1 m_1 m1进行签名时，先产生一个新的公私钥对 ( p k 2 , s k 2 ) (pk_2,sk_2) (pk2,sk2)（该公私钥对是根据 m 1 m_1 m1独立生成的，类似于一次性签名方案），然后得到 σ 1 = S i g n s k 1 ( m 1 ∣ ∣ p k 2 ) \sigma_1=Sign_{sk_1}(m_1||pk_2) σ1=Signsk1(m1∣∣pk2)，此时输出的签名为 ( p k 2 , σ 1 ) (pk_2,\sigma_1) (pk2,σ1)，签名者添加状态 ( m 1 , p k 2 , s k 2 , σ 1 ) (m_1,pk_2,sk_2,\sigma_1) (m1,pk2,sk2,σ1)为当前状态。
对 m 2 m_2 m2进行签名时，签名者生成一对新的公私钥对 ( p k 3 , s k 3 ) (pk_3,sk_3) (pk3,sk3)，然后得到 σ 2 = S i g n s k 2 ( m 2 ∣ ∣ p k 3 ) \sigma_2=Sign_{sk_2}(m_2||pk_3) σ2=Signsk2(m2∣∣pk3)，此时输出的签名为 ( p k 3 , σ 2 , ( m 1 , p k 2 , σ 1 ) ) (pk_3,\sigma_2,(m_1,pk_2,\sigma_1)) (pk3,σ2,(m1,pk2,σ1))，签名者添加状态为 ( m 2 , p k 3 , s k 3 , σ 3 ) (m_2,pk_3,sk_3,\sigma_3) (m2,pk3,sk3,σ3)。
…
对 m i m_i mi进行签名时，签名者生成一对新的公私钥对 ( p k i + 1 , s k i + 1 ) (pk_{i+1},sk_{i+1}) (pki+1,ski+1)，然后得到 σ i = S i g n s k i ( m i ∣ ∣ p k i + 1 ) \sigma_i=Sign_{sk_i}(m_i||pk_{i+1}) σi=Signski(mi∣∣pki+1)，此时输出签名为 ( p k i + 1 , σ i , { ( m j , p k j + 1 , σ j ) } j = 1 i − 1 ) (pk_{i+1},\sigma_i,\{(m_j,pk_{j+1},\sigma_j)\}_{j=1}^{i-1}) (pki+1,σi,{(mj,pkj+1,σj)}j=1i−1)，签名者状态为 ( m i , p k i + , s k i + 1 , σ i + 1 ) (m_i,pk_{i+},sk_{i+1},\sigma_{i+1}) (mi,pki+,ski+1,σi+1)。
如果要验证
m
=
m
i
m=m_i
m=mi关于公钥
p
k
1
pk_1
pk1的签名
(
p
k
i
+
1
,
σ
i
,
{
(
m
j
,
p
k
j
+
1
,
σ
j
)
}
j
=
1
i
−
1
)
(pk_{i+1},\sigma_i,\{(m_j,pk_{j+1},\sigma_j)\}_{j=1}^{i-1})
(pki+1,σi,{(mj,pkj+1,σj)}j=1i−1)，验证者验证
V
r
f
y
p
k
(
m
j
∣
∣
p
k
j
+
1
,
σ
j
)
=
1
Vrfy_{pk}(m_j||pk_{j+1},\sigma_j)=1
Vrfypk(mj∣∣pkj+1,σj)=1，其中
j
=
1
,
2
,
.
.
.
,
i
j=1,2,...,i
j=1,2,...,i。（图为对
m
=
m
5
m=m_5
m=m5签名后，签名者的状态，对应输出的签名为：
(
p
k
6
,
σ
5
,
(
m
1
,
p
k
2
,
σ
1
)
,
(
m
2
,
p
k
3
,
σ
2
)
,
(
m
3
,
p
k
4
,
σ
3
)
,
(
m
4
,
p
k
5
,
σ
4
)
,
(
m
4
,
p
k
6
,
σ
5
)
)
(pk_6,\sigma_5,(m_1,pk_2,\sigma_1),(m_2,pk_3,\sigma_2),(m_3,pk_4,\sigma_3),(m_4,pk_5,\sigma_4),(m_4,pk_6,\sigma_5))
(pk6,σ5,(m1,pk2,σ1),(m2,pk3,σ2),(m3,pk4,σ3),(m4,pk5,σ4),(m4,pk6,σ5))）
由此可以清晰的看到每一对公私钥对只对一个消息进行签名，基于Chain的签名方案优于一次性签名方案之处在于：其对消息的签名不受公私钥对的数量的限制，需要的时候可以生成新的公私钥对，而一次性签名方案是事先根据消息的数量生成一对公私钥对，如果这时候增加新的消息，就需要生成一个新的公私钥对进行分发。而且，一次性签名方案的公私钥对的长度与消息的数量成线性关系，效率相对低下。
5、基于Tree的签名方案
在该方案中，对 m = m 1 ⋅ m 2 ⋅ m 3 = 101 m=m_1·m_2·m_3=101 m=m1⋅m2⋅m3=101进行签名时，先对 m 1 m_1 m1进行签名，签名者先生成一对公私钥对 ( p k ε , s k ε ) (pk_{\varepsilon},sk_{\varepsilon}) (pkε,skε)，然后继续生成 ( p k 0 , s k 0 ) (pk_0,sk_0) (pk0,sk0)和 ( p k 1 , s k 1 ) (pk_1,sk_1) (pk1,sk1)，签名为 σ ε = S i g n s k ε ( p k 0 ∣ ∣ p k 1 ) \sigma_{\varepsilon}=Sign_{sk_{\varepsilon}}(pk_0||pk_1) σε=Signskε(pk0∣∣pk1)，完整签名为 ( σ ε , p k 0 , p k 1 ) (\sigma_{\varepsilon},pk_0,pk_1) (σε,pk0,pk1)。（ ε \varepsilon ε表示空字符串， p k , s k pk,sk pk,sk的下标表示 m m m的前缀）
对 m 1 m_1 m1进行签名，签名者生成两对新的公私钥对 ( p k 10 , s k 10 ) (pk_{10},sk_{10}) (pk10,sk10)和 ( p k 11 , s k 11 ) (pk_{11},sk_{11}) (pk11,sk11)，其签名为 σ 1 = S i g n s k 1 ( p k 10 ∣ ∣ p k 11 ) \sigma_{1}=Sign_{sk_{1}}(pk_{10}||pk_{11}) σ1=Signsk1(pk10∣∣pk11)，完整签名为 ( ( p k 10 , p k 11 , σ 1 ) , p k 0 , p k 1 , σ ε ) ((pk_{10},pk_{11},\sigma_{1}),pk_0,pk_1,\sigma_{\varepsilon}) ((pk10,pk11,σ1),pk0,pk1,σε)
对 m 2 m_2 m2进行签名，签名者生成两对新的公私钥对 ( p k 100 , s k 100 ) (pk_{100},sk_{100}) (pk100,sk100)和 ( p k 101 , s k 101 ) (pk_{101},sk_{101}) (pk101,sk101)，其签名为 σ 10 = S i g n s k 10 ( p k 100 ∣ ∣ p k 101 ) \sigma_{10}=Sign_{sk_{10}}(pk_{100}||pk_{101}) σ10=Signsk10(pk100∣∣pk101)，完整签名为 ( ( p k 100 , p k 101 , σ 10 ) , ( p k 10 , p k 11 , σ 1 ) , ( p k 0 , p k 1 , σ ε ) ) ((pk_{100},pk_{101},\sigma_{10}),(pk_{10},pk_{11},\sigma_{1}),(pk_0,pk_1,\sigma_{\varepsilon})) ((pk100,pk101,σ10),(pk10,pk11,σ1),(pk0,pk1,σε))
对 m 3 m_3 m3进行签名，其签名为 σ 101 = S i g n s k 101 ( m ) \sigma_{101}=Sign_{sk_{101}}(m) σ101=Signsk101(m)，完整签名为 ( σ 101 , ( p k 100 , p k 101 , σ 10 ) , ( p k 10 , p k 11 , σ 1 ) , ( p k 0 , p k 1 , σ ε ) ) (\sigma_{101},(pk_{100},pk_{101},\sigma_{10}),(pk_{10},pk_{11},\sigma_{1}),(pk_0,pk_1,\sigma_{\varepsilon})) (σ101,(pk100,pk101,σ10),(pk10,pk11,σ1),(pk0,pk1,σε))
验证： V r f y p k 101 ( m , σ 101 ) = 1 Vrfy_{pk_{101}}(m,\sigma_{101})=1 Vrfypk101(m,σ101)=1， V r f y p k 10 ( p k 100 ∣ ∣ p k 101 , σ 10 ) = 1 Vrfy_{pk_{10}}(pk_{100}||pk_{101},\sigma_{10})=1 Vrfypk10(pk100∣∣pk101,σ10)=1， V r f y p k 1 ( p k 10 ∣ ∣ p k 11 , σ 1 ) = 1 Vrfy_{pk_{1}}(pk_{10}||pk_{11},\sigma_{1})=1 Vrfypk1(pk10∣∣pk11,σ1)=1， V r f y p k ε ( p k 0 ∣ ∣ p k 1 , σ ε ) = 1 Vrfy_{pk_{\varepsilon}}(pk_{0}||pk_{1},\sigma_{\varepsilon})=1 Vrfypkε(pk0∣∣pk1,σε)=1
这里有一部分公私钥对没有用到，当下次需要的时候，不必再生成，可直接用。与基于Chain的签名方案相比，本方案只有叶子节点将用于对消息进行签名，内部节点是不需要的。