当前位置: 首页 > article >正文

现代密码学总结(下篇)

密钥管理与公钥变革

Needham-Schroeder协议

(对称)
在这里插入图片描述
在这里插入图片描述

1978年提出, 非安全网络环境下, 借助可信第三方利用对称
密码技术分配会话密钥
假设A和B分别与信任权威T建立了一个共享的静态密钥Kat和Kbt

Diffie-Hellman (-Merkle) KE 协议

在这里插入图片描述

安全定义:
在这里插入图片描述
如果DDH问题对于群 G 是困难的,那么DiffieHellman密钥交换协议在窃听者存在的情况下是安全的

中间人攻击

在这里插入图片描述

公钥加密

发送方使用公钥对消息进行加密;接收方使用私钥解密生成的密文。
优势:

  • 公钥加密(在某种程度上)解决了密钥分发问题,因为通信各方不需要在通信之前秘密地共享密钥。即使双方之间的所有通信都被监控,双方也可以秘密通信。

  • 当单个接收方与N个发送方通信时,接收方存储单个私钥sk要比共享、存储和管理N不同的对称密钥(即每个发送方一个)方便得多。

缺点:

  • 公钥加密方案允许任何人充当发送者,这可能是一个缺点,因为接收方可能只想接收特定发送者的消息。

  • 主要缺点是公钥加密大约比对称加密2到3个数量级。

选择明文安全

定义 11.1 一个公钥加密方案是一个PPT算法的三元组 (Gen, EncDec) 使得:

  1. 密   钥   生   成   算   法   Gen将   安   全   参   数   1 n \textbf{密 钥 生 成 算 法 Gen将 安 全 参 数 }1^n       Gen     1n作为输入,并输出一对密
    钥 ( p k , s k ) (公钥暗含了消息空间 M ) 。 \begin{aligned}\text{钥}(pk,sk)\text{(公钥暗含了消息空间}\mathcal{M})。\end{aligned} (pk,sk)(公钥暗含了消息空间M)
  2. 加   密   算   法   Enc将   公   钥   p k \textbf{加 密 算 法 Enc将 公 钥 }pk     Enc   pk和某个消息空间中的消息 m m m作为输入,输出一个密文 c c c,我们将其写作 c ← E n c p k ( m ) c\leftarrow\mathsf{Enc}_{pk}(m) cEncpk(m)。(我们也经常写作 c ← c\leftarrow c E n c ( m , p k ) )。 \begin{aligned}\mathsf{Enc}(m,pk)\text{)。}\end{aligned} Enc(m,pk))
  3. 确定性解密算法Dec以私钥 s k sk sk和密文 c c c作为输入,输出消息 m m m或特殊符号 ⊥ \bot 表示失败。我们将其写作 m : = m: = m:= D e c s k ( c ) Dec_{sk}( c) Decsk(c)。(我们通常也写作 m : = m:= m:=Dec ( c , s k ) (c,sk) (c,sk))。
  • 加密算法可以是确定性的,也可以是概率性的。

  • 解密算法可能是完全正确的(从未失败),也可能以可忽略的概率失败。

  • 如果一个公钥加密方案在窃听者的存在下具有不可区分加密,那么它是IND-CPA安全的。

  • 没有公钥加密方案是具有完善保密性的。

  • 没有确定性的公钥加密方案是IND-CPA安全的。

  • 如果公钥加密方案Π是IND-CPA安全的,那么它对于多消息加密也具有不可区分加密

  • Π与Π’在这里插入图片描述

选择密文攻击安全在这里插入图片描述一个公钥加密方案 Π = ( \Pi=( Π=(Gen,Enc,Dec)在选择密文攻击下具有不可区分加密(或是 CCA-安全的)如果对于所有PPT敌手 A \mathcal{A} A都存在一个可忽略函数 negl 使得

Pr ⁡ [ P u b K A , Π сса ( n ) = 1 ] ≤ 1 / 2 + n e g l ( n ) . \Pr[\mathsf{PubK}_{\mathcal{A},\Pi}^\text{сса}{(n)}=1]\leq1/2+\mathsf{negl}(n). Pr[PubKA,Πсса(n)=1]1/2+negl(n).

KEM

一个密钥封装机制 (KEM)是一个PPT算法的三元组 (Gen
Encaps, Decaps) 使得:

  1. 密   钥   生   成   算   法   Gen以   安   全   参   数   1 n \textbf{密 钥 生 成 算 法 Gen以 安 全 参 数 1}^n       Gen     1n为输入,输出一对密钥 ( p k , s k ) (pk,sk) (pk,sk)
    (密钥的长度至少为 n , n n,n n,n可由 p k pk pk确定)。
  2. 封   装   算   法   Encaps将   公   钥   p k \textbf{封 装 算 法 Encaps将 公 钥 }pk     Encaps   pk和安全参数1 n ^n n作为输入,输出一个密文 c c c和一个密钥 k ∈ { 0 , 1 } p ( n ) k\in\{0,1\}^p(n) k{0,1}p(n),其中 p p p是密钥长度。我们将其写作 ( c , k ) ← (c,k)\leftarrow (c,k)Encaps p k ( 1 n ) _pk(1^n) pk(1n)(或 ( c , k ) ← (c,k)\leftarrow (c,k)Encaps ( 1 n , p k ) ) (1^n,pk)) (1n,pk))
  3. 确定性解封装算法Decaps以私钥 s k sk sk和密文 c c c为输入,输出密钥 k k k或表示失败的特殊符号 ⊥ \bot 。我们将其写作 k : =   Decaps s k ( c ) k:=\textbf{ Decaps}_{sk}(c) k:= Decapssk(c)(或 k : = k:= k:= D e c a p s ( s k , c ) \mathsf{Decaps}(sk,c) Decaps(sk,c))。
    在这里插入图片描述

混合加密Hybrid encryption

给定一个KEM和一个DEM(对称加密方案),我们可以很容易构造一个混合加密方案。 在实际中,这种方案明显比只使用PKE方案更有效(当加密消息需要调用多个PKE时)
在这里插入图片描述
Π = ( \Pi=( Π=(Gen, Encaps, Decaps) 是密钥长度为 n n n的KEM, Π ′ = ( G e n ′ , E n c ′ , D e c ′ ) \Pi^{\prime}=(\mathrm{Gen}^{\prime},\mathrm{Enc}^{\prime},\mathrm{Dec}^{\prime}) Π=(Gen,Enc,Dec)是对称加密方案(DEM)。我们构造一个公钥加密方案 Π h y = ( G e n h y , E n c h y \Pi^hy=(\mathrm{Gen}^{hy},\mathrm{Enc}^{hy} Πhy=(Genhy,Enchy,Dec h y ) ^hy) hy)如下: - Gen h y ^hy hy:输入1 n ^n n,输出 ( p k , s k ) ← (pk,sk)\leftarrow (pk,sk)Gen ( 1 n ) (1^n) (1n)

  • Enc h y ^{hy} hy:输入一个公钥 p k pk pk和一个消息 m ∈ { 0 , 1 } ∗ m\in\{0,1\}^* m{0,1},运行:
    ∙ \bullet 计算 ( c , k ) ← (c,k)\leftarrow (c,k)Encaps p k ( 1 n ) _pk(1^n) pk(1n)
    ∙ \bullet 计算 c ′ ← E n c k ′ ( m ) c^\prime\leftarrow\mathrm{Enc}_k^{'}(m) cEnck(m)
    ·输出密文 ( c , c ′ ) (c,c^\prime) (c,c)

  • Dec h y ^hy hy:输入私钥 s k sk sk和密文 ( c , c ′ ) (c,c^\prime) (c,c),运行:
    ∙ \bullet 计算 k : = k: = k:=D e c a p s s k ( c ) ecaps_sk( c) ecapssk(c) ∙ \bullet 输出消息 m : = m: = m:=D e c k ′ ( c ′ ) ec_k^\prime ( c^{\prime }) eck(c)

如果Π是CPA-安全的KEM,Π’是存在窃听者情况下具有不可区分加密的对称加密方案,那么Πhy是一个CPA-安全的公钥加密方案。

如果Π是CCA-安全的KEM,Π′是CCA-安全的对称加密方案,则Πhy是CCA-安全的公钥加密方案。

ElGamal

在这里插入图片描述
∙ \bullet Gen ( 1 n ) (1^n) (1n): 运行 ( G , q , g ) ← G ( 1 n ) (G,q,g)\leftarrow\mathbb{G}(1^n) (G,q,g)G(1n), 选择 $x\xleftarrow{$}\mathbb{Z}_q$, 计算 y : = g x y:=g^x y:=gx 并输出 ( s k , p k ) : = ( ( G , q , g , x ) , ( G , q , g , y ) ) . (sk,pk):=((G,q,g,x),(G,q,g,y)). (sk,pk):=((G,q,g,x),(G,q,g,y)).
∙ \bullet Enc ( m , p k ) (m,pk) (m,pk): 输入 m ∈ G m\in G mG p k = ( G , q , g , y ) pk=(G,q,g,y) pk=(G,q,g,y), 选择 $r\xleftarrow{$}\mathbb{Z}_q$, 计算 并输出 C : = ( g r , m ⋅ y r ) . C:=(g^r,m\cdot y^r). C:=(gr,myr).
∙ \bullet Dec ( C , s k ) (C,sk) (C,sk): 输入 C = ( C 1 , C 2 ) C=(C_1,C_2) C=(C1,C2) s k = ( G , q , g , x ) sk=(G,q,g,x) sk=(G,q,g,x), 计算 并输出 m : = C 2 ⋅ ( C 1 x ) − 1 . m:=C_2\cdot(C_1^x)^{-1}. m:=C2(C1x)1.

· 正确性:

C 2 ⋅ ( C 1 x ) − 1 = m ⋅ y r ⋅ ( ( g r ) x ) − 1 = m ⋅ y r ⋅ ( y r ) − 1 = m ⋅ 1 = m . C_2\cdot(C_1^x)^{-1}=m\cdot y^r\cdot((g^r)^x)^{-1}=m\cdot y^r\cdot(y^r)^{-1}=m\cdot1=m. C2(C1x)1=myr((gr)x)1=myr(yr)1=m1=m.

DDH问题相对于 g g g是困难的,如果对于所有的PPT算法 A \mathcal{A} A有一个可忽略函数使得 P r [ A ( G , q , g , g x , g r , g z ) = 1 ] − P r [ A ( G , q , g , g x , g r , g x r ) = 1 ] \begin{aligned}\mathsf{Pr}[\mathcal{A}(G,q,g,g^x,g^r,g^z)=1]-\mathsf{Pr}[\mathcal{A}(G,q,g,g^x,g^r,g^{xr})=1]\end{aligned} Pr[A(G,q,g,gx,gr,gz)=1]Pr[A(G,q,g,gx,gr,gxr)=1]
≤ \leq negl ( n ) (n) (n),
其中, x , r , z ∈ Z q x,r,z\in\mathbb{Z}_q x,r,zZq是均匀一致选取的。

RSA

(普通RSA)
∙ \bullet Gen():生成 RSA 参数。
输入 1 n ^n n,输出 N N N, N N N是两个 n n n-比特素数 p p p q q q的乘积;随机选择 e e e,其中 1 < e < ϕ ( N ) <e<\phi(N) <e<ϕ(N) g c d ( e , ϕ ( N ) ) = 1 ; gcd(e,\phi(N))=1; gcd(e,ϕ(N))=1;计算 d d d满足 e d = 1 m o d    ϕ ( N ) . ed=1\mod\phi(N). ed=1modϕ(N).
p k = ( N , e ) ,   s k = ( d ) pk=(N,e),\:sk=(d) pk=(N,e),sk=(d)
∙ \bullet Enc ( p k , m ) : ( 1 ) c = m e ( pk, m) \nobreak {: } ( 1) \textit{c}= m^e (pk,m):(1)c=me mod N N N
(2)输出 c c c
∙ \bullet Dec ( s k , c ) (sk,c) (sk,c):输出 m : = c d m:=c^d m:=cd mod N . N. N.

证明:由加密过程知 c = m e m o d    N c=m^e\mod N c=memodN,所以
c d c^d cd mod N = m e d N=m^ed N=med mod N = m k ϕ ( N ) + 1 N=m^k\phi(N)+1 N=mkϕ(N)+1 mod N N N

分两种情况:

1 ◯ m \textcircled{1}m 1m N N N互素,则由Euler定理得

m ϕ ( N ) = 1 m o d    N , m k ϕ ( N ) = 1 m o d    N , m k ϕ ( N ) + 1 = m m o d    N по  d \begin{aligned}\\&m^{\phi(N)}=1\mod N,\\&m^{k\phi(N)}=1\mod N,\\&m^{k\phi(N)+1}=m\mod N\\&\quad\text{по }d\end{aligned} mϕ(N)=1modN,mkϕ(N)=1modN,mkϕ(N)+1=mmodNпо d

c d m o d    N = m . c^d\mod N=m. cdmodN=m.
② g c d ( m , N ) ≠ 1 , 不妨设  m = t p 。 由  g c d ( m , q ) = 1 及Euler定理得  m ϕ ( q ) = 1 m o d q , 所以  m k ϕ ( q ) = 1 m o d q , [ m k ϕ ( q ) ] ϕ ( p ) = 1 m o d q , m k ϕ ( N ) = 1 m o d q 因此存在一整数  r ,使得  m k ϕ ( N ) = 1 + r q ,两边同乘 以 m = t p  得 m k ϕ ( N ) + 1 = m + r t p q = m + r t N , 所以 m k ϕ ( N ) + 1 = m m o d N ,即 c d m o d N = m 。 \begin{aligned} & ②gcd(m,N)\neq1,\text{不妨设 }m=tp\mathrm{。} \\ & \text{由 }gcd(m,q)=1\text{及Euler定理得 }m^{\phi(q)}=1{\mathrm{mod}}q, \\ & \text{所以 }m^{k\phi(q)}=1{\mathrm{mod}}q, \\ & [m^{k\phi(q)}]^{\phi(p)}=1{\mathrm{mod}}q, \\ & m^{k\phi(N)}=1{\mathrm{mod}}q \\ & \text{因此存在一整数 }r\text{,使得 }m^{k\phi(N)}=1+rq\text{,两边同乘} \\ & \text{以}m=tp\text{ 得} \\ & m^{k\phi(N)+1}=m+rtpq=m+rtN, \\ & \text{所以}m^{k\phi(N)+1}=m{\mathrm{mod}}N\text{,即}c^d{\mathrm{mod}}N=m\mathrm{。} \end{aligned} gcd(m,N)=1,不妨设 m=tp gcd(m,q)=1Euler定理得 mϕ(q)=1modq,所以 mkϕ(q)=1modq,[mkϕ(q)]ϕ(p)=1modq,mkϕ(N)=1modq因此存在一整数 r,使得 mkϕ(N)=1+rq,两边同乘m=tp mkϕ(N)+1=m+rtpq=m+rtN,所以mkϕ(N)+1=mmodN,cdmodN=m

攻击
普通RSA加密是确定性的,因此无法到达CPA安全。

对于恢复 m m m的二次改进(quadratic improvement)。
使用小的 e e e加密短消息。加密部分已知的消息。

加密相关消息。

c 1 = m e c_{1}=m^{e} c1=me mod N , c 2 = ( m + δ ) e N,c_2=(m+\delta)^{e} N,c2=(m+δ)e mod N . N. N.
窃听者可以定义 f 1 ( x ) = d e f x e − c 1 f_1(x)\stackrel{def}{=}x^e-c_1 f1(x)=defxec1 f 2 ( x ) = d e f ( x + δ ) e − c 2 f_2(x)\stackrel{def}{=}(x+\delta)^e-c_2 f2(x)=def(x+δ)ec2
(modulo N ) . N). N).
x = m x=m x=m是两个多项式的根 (modulo N ) , ( x − m ) N),(x-m) N),(xm)是两个多项式的因式。如果 f 1 ( x ) f_1(x) f1(x) f 2 ( x ) f_2(x) f2(x) (作为 Z N ∗ \mathbb{Z}_N^* ZN上的多项式)的最大公因式是线性的,那么将会泄露 m m m。最大公因式可以在poly ( ∣ ∣ N ∣ ∣ , e ) (||N||,e) (∣∣N∣∣,e)时间内计算出来,这种攻击对于小的 e e e是可行的。
2.
向多个接收者发送相同的消息。
发送方将同一消息加密后发送给给多个接收方。
e = 3 , m e=3,m e=3,m使用三个不同的公钥加密 p k 1 = ( N 1 , 3 ) pk_1=(N_1,3) pk1=(N1,3),
p k 2 = ( N 2 , 3 ) pk_{2}= ( N_{2}, 3) pk2=(N2,3), p k 3 = ( N 3 , 3 ) . pk_{3}= ( N_{3}, 3) . pk3=(N3,3).假设对于不同的 i , j i,j i,j,
gcd ⁡ ( N i , N j ) = 1. \gcd(N_i,N_j)=1. gcd(Ni,Nj)=1.窃听者可以得到
c 1 = m 3 c_1=m^3 c1=m3 mod N 1 , c 2 = m 3 N_1,c_2=m^3 N1,c2=m3 mod N 2 , c 3 = m 3 N_2,c_3=m^3 N2,c3=m3 mod N 3 . N_3. N3. Let N ∗ = N 1 N 2 N 3 . N^*=N_1N_2N_3. N=N1N2N3.存在唯一的非负整数 c ^ < N ∗ \hat{c}<N^* c^<N使得 c ^ = c 1 \hat{c}=c_1 c^=c1 mod N 1 = c 2 N_1=c_2 N1=c2 mod N 2 = c 3 N_2=c_3 N2=c3 mod N 3 . N_3. N3.
可以计算 m 3 = c ^ . ( m 3 < N ∗  因为  m 3 < min ⁡ { N 1 , N 2 , N 3 } ) m^3=\hat{c}.\left(m^3<N^*\text{ 因为 }m^3<\min\left\{N_1,N_2,N_3\right\}\right) m3=c^.(m3<N 因为 m3<min{N1,N2,N3})
3.共模攻击
在实现RSA时,为方便起见,可能给每一用户相同的模数 N N N,
虽然加解密密钥不同,然而这样做是不行的。
设两个用户的公钥分别为 e 1 e_1 e1 e 2 e_2 e2,且 e 1 e_1 e1 e 2 e_2 e2互素,明文消息
m m m,密文分别是

c 1 = m e 1 m o d    N , c 2 = m e 2 m o d    N c_1=m^{e_1}\mod N,c_2=m^{e_2}\mod N c1=me1modN,c2=me2modN
敌手截获 c 1 和 c 2 后,可如下恢复 m 。用扩展的Euclid算法求出 \begin{aligned}\text{敌手截获}c_1\text{和}c_2\text{后,可如下恢复}m\text{。用扩展的Euclid算法求出}\end{aligned} 敌手截获c1c2后,可如下恢复m。用扩展的Euclid算法求出
满足 r e 1 + s e 2 = 1 re_1+se_2=1 re1+se2=1的两个整数 r r r s s s,由此
c 1 r c 2 s = m r e 1 + s e 2 = m m o d N c_1^rc_2^s= m^{re_1+ se_2}= m\allowbreak {\mathrm{mod}}N c1rc2s=mre1+se2=mmodN

永远不要使用“教科书式的”RSA!

RSAES-OAEP

![在
RSA是陷门置换(trapdoor permutation) ⇒RSA-OAEP是CCA安全的,当 H, G 是 随机函数 在实际中:使用 SHA-256 实例化 H 和 G
过程:
在这里插入图片描述

n n n 是 RSA 模数的位数, k 0 k_0 k0 k 1 k_1 k1是协议中的固定整数,
m m m n − k 0 − k 1 n-k_0-k_1 nk0k1位长的明文消息, G G G H H H 是Hash函数, ⊕ \oplus

是异或运算。
编码过程包括如下步骤:

1.用 k 1 k_1 k1位长的 0 将消息 m m m填充至 n − k 0 n-k_0 nk0位的长度。

2.随机生成 k 0 k_0 k0位长的串 r r r

3.用 G G G k 0 k_0 k0位长的 r r r扩展至 n − k 0 n-k_0 nk0位长。

  1. X X X = m 00 ⋯ 0 ⊕ m00\cdots 0\oplus m000 G ( r ) G( r) G(r)

5. H H H n − k 0 n-k_0 nk0位长的 X X X缩短至 k 0 k_0 k0位长。

6. Y 6. Y 6.Y = r r r ⊕ \oplus H ( X ) H( X) H(X)

7.输出为 X ∣ ∣ Y X||Y X∣∣Y, X X X 为最左边的块, Y Y Y 为最右边的块。

加密:随后可以使用 RSA 加密编码的消息,使用 OAEP 可以避免 RSA 的确定性。解码过程包括如下步骤:

  • 恢复随机串 r r r Y ⊕ H ( X ) Y \oplus H(X) YH(X)
  • 恢复消息 m 0 … 0 m_0 \ldots 0 m00 X ⊕ G ( r ) X \oplus G(r) XG(r)

数字签名

可以看作公钥环境下MAC,具有公共可验证性。
完整性保护:可以检测到对签名消息的任何修改
来源认证性:识别签名消息的发送者
不可否认性:签名者不能否认已签署(发送)过的消息。
安全性(直观):对于未由私钥持有者签名的消息,应该很难找到一个签名

一个数字签名方案是一个PPT算法的三元组(Gen、Sig、Vrfy) 使得:
·密钥生成算法Gen以安全参数1 n ^n n为输入,输出一对密钥 ( p k , s k ) ( pk, sk) (pk,sk) ( 我 们 假 设 p k pk pk s k sk sk的 长 度 为 n n n, 并 且 n n n可 以从 p k pk pk s k sk sk推断出来)。
·签名算法Sig将私钥 s k sk sk和来自某个消息空间 M \mathcal{M} M的消息 m m m作为输入,输出签名 σ \sigma σ,我们将其写作 σ \sigma σ ← \leftarrow Sig ⁡ s k ( m ) \operatorname{Sig}_{sk}(m) Sigsk(m)
∙ \bullet 确定性验证算法Vrfy将公钥 p k pk pk、消息 m m m和签名 σ \sigma σ作为输 入输出 b , b = 1 表示签名有效, b = 0 表示无效。我 们将其写作 b : = Vrfy p k ( m , σ ) 。 \begin{array}{c}\text{入输出}b,b=1\text{表示签名有效,}b=0\text{表示无效。我}\\\text{们将其写作}b:=\text{Vrfy}_{pk}(m,\sigma)\mathrm{。}\end{array} 入输出b,b=1表示签名有效,b=0表示无效。我们将其写作b:=Vrfypk(m,σ)
( p k , s k ) ← (pk,sk)\leftarrow (pk,sk)Gen ( 1 n ) ,   我   们   有   ( 1^n) \textbf{, 我 们 有 } (1n)   
Vrfy p k ( m , S i g s k ( m ) ) = 1 \text{Vrfy}_{pk}(m,\mathbf{Sig}_{sk}(m))=1 Vrfypk(m,Sigsk(m))=1,
对于任意消息 m ∈ M . m\in\mathcal{M}. mM.

• 可能是确定性的或者是概率的
• 可能是有状态的,也可能是无状态的(后者是标准的)
确定性验证算法可能是完全正确的(从未失败)或可能以可忽略的概率失败。

威胁模型(逐渐增强):

  • 无消息攻击(No-message attack,NMA): 敌手只能知道公钥
  • 随机消息攻击(Random message attack,RMA): 敌手可以获取随机消息的签名(不受敌手控制)。
  • 非适应性选择消息攻击(Non-adaptive chosen messageattack,naCMA): 敌手确定一个想要获得签名的消息列表(在他知道公钥之前)。
  • 选择消息攻击(Chosen message attack,CMA): 敌手可以适应性地要求对其选择的消息进行签名

敌手的目标(难度降低)

  • 无条件伪造(Universal forgery,UF): 给定敌手一个目标,敌手需要为其输出有效的签名
  • 存在性伪造(Existential forgery,EF): 敌手为其选择的消息输出签名。

EUF-CMA: 选择消息攻击下的存在不可伪造性

在这里插入图片描述

教科书式RSA签名

KeyGen: 输入 1 n ^n n,随机选择 n n n-比特的素数 p , q p,q p,q,令 N = p q N=pq N=pq,

选择 e e e使得 gcd ( e , ϕ ( N ) ) = 1 (e,\phi(N))=1 (e,ϕ(N))=1,计算 d : = e − 1 d:=e^-1 d:=e1 mod ϕ ( N ) \phi(N) ϕ(N),

输出 ( s k , p k ) : = ( ( d , N ) , ( e , N ) ) . (sk,pk):=((d,N),(e,N)). (sk,pk):=((d,N),(e,N)).

Sig: 输入 m ∈ Z N ∗ m\in\mathbb{Z}_N^* mZN s k = ( d , N ) sk=(d,N) sk=(d,N),计算并输出 σ = m d \sigma=m^d σ=md mod

N . N. N.

Vrfy: 输入公钥 p k = ( e , N ) pk=(e,N) pk=(e,N),消息 m ∈ Z N ∗ m\in\mathbb{Z}_N^* mZN和签名 σ ∈ Z N ∗ \sigma\in\mathbb{Z}_N^* σZN,
输出 1 当且仅当 m : = σ e m:=\sigma^e m:=σe mod N . N. N.
攻击:

无消息(No-message)攻击

1.输出伪造 ( m ∗ , σ ∗ ) : = ( 1 , 1 ) . (m^*,\sigma^*):=(1,1). (m,σ):=(1,1).是有效的因为 1 d = 1 1^d=1 1d=1 mod N . N. N.
2.选择 σ ∈ Z N ∗ \sigma\in\mathbb{Z}_N^* σZN并计算 m : = σ e m:=\sigma^e m:=σe mod N . N. N.

E U F − C M A \mathsf{EUF-CMA} EUFCMA攻击

∙ \bullet 请求消息 m 1 , m 2 ∈ Z N ∗ m_1,m_2\in\mathbb{Z}_N^* m1,m2ZN的签名 σ 1 , σ 2 \sigma_1,\sigma_2 σ1,σ2 for m 1 , m 2 ∈ Z N ∗ m_1,m_2\in\mathbb{Z}_N^* m1,m2ZN并输
( m ⋆ , σ ⋆ ) : = ( m 1 ⋅ m 2 (m^\star,\sigma^\star):=(m_1\cdot m_2 (m,σ):=(m1m2 mod N , σ 1 ⋅ σ 2 N,\sigma_1\cdot\sigma_2 N,σ1σ2 mod N ) . N). N). 即使是安全的,消息空间是 Z N ∗ \mathbb{Z}_N^* ZN也是不可取的!

扩展消息空间:
分块签名
• 考虑 m := (m1, …, mn),mi ∈ M 并计算 σ := (σ1, …, σn).
• 需要注意避免混合-匹配(mix-and-match)攻击(块重新排
序,交换来自不同签名的块等)。
• 对于长消息效率低(每个块调用一次方案)。
先哈希再签名(Hash-and-Sign)
• 在签名之前,使用哈希函数H将任意长的消息压缩为固定
长度的字符串。
• H的取值范围需要与签名方案的消息空间兼容。

RSA-FDH

GenRSA与前面的章节一样,构造签名方案如下: ∙ Gen: 输入  1 n , 运行 GenRSA ( 1 n )  计算  ( N , e , d ) .  公钥 是 < N , e > ,  私钥是 < N , d > . 作为密钥生成的一部分,函数 H : { 0 , 1 } ∗ → Z N ∗ 是指 定的,但我们将其隐式地保留。 ∙  Sign: 输入私钥 < N , d > 和消息  m ∈ { 0 , 1 } ∗ ,计算 σ : = [ H ( m ) d   m o d   N ] . ∙  Vrfy: 输入公钥  < N , e > , 消息  m  和签名  σ , 输出  1  当 且仅当  σ e = ⁡ ⁡ ? H ( m )   m o d   N . \begin{aligned} & \\ & \text{GenRSA与前面的章节一样,构造签名方案如下:} \\ & \bullet\text{Gen: 输入 }1^n,\text{运行 GenRSA}(1^n)\text{ 计算 }(N,e,d).\text{ 公钥} \\ & \text{是}<N,e>,\text{ 私钥是}<N,d>. \\ & \text{作为密钥生成的一部分,函数}H:\{0,1\}^*\to Z_N^*\text{是指} \\ & \text{定的,但我们将其隐式地保留。} \\ & \bullet\text{ Sign: 输入私钥}<N,d>\text{和消息 }m\in\{0,1\}^*\text{,计算} \\ & \sigma:=[H(m)^d\mathrm{~mod~}N]. \\ & \bullet\text{ Vrfy: 输入公钥 }<N,e>,\text{消息 }m\text{ 和签名 }\sigma,\text{输出 }1\text{ 当} \\ & \text{且仅当 }\sigma^e\overset{?}{\operatorname*{\operatorname*{=}}}H(m)\mathrm{~mod~}N. \end{aligned} GenRSA与前面的章节一样,构造签名方案如下:Gen: 输入 1n,运行 GenRSA(1n) 计算 (N,e,d). 公钥<N,e>, 私钥是<N,d>.作为密钥生成的一部分,函数H:{0,1}ZN是指定的,但我们将其隐式地保留。 Sign: 输入私钥<N,d>和消息 m{0,1},计算σ:=[H(m)d mod N]. Vrfy: 输入公钥 <N,e>,消息 m 和签名 σ,输出 1 且仅当 σe=?H(m) mod N.

RSA假设

Schnorr 签名

∙ \bullet KeyGen: 运行 G ( 1 n ) \mathcal{G}(1^n) G(1n)得到 ( G , q , g ) (G,q,g) (G,q,g).选择 x ← s Z q x\leftarrow^s\mathbb{Z}_q xsZq并计算 y : = y:= y:= g x g^x gx.私钥为 x x x,对应的公钥是 ( G , q , g , y ) (G,q,g,y) (G,q,g,y).作为密钥生成的一部分,确定哈希函数 H : { 0 , 1 } ∗ → Z q . H:\{0,1\}^*\to\mathbb{Z}_q. H:{0,1}Zq.
∙ \bullet Sign: 输入私钥 x x x和消息 m ∈ { 0 , 1 } ∗ m\in\{0,1\}^* m{0,1},选择 k ← s Z q k\leftarrow^{\mathfrak{s}}\mathbb{Z}_q ksZq并计算 I : = g k I:=g^k I:=gk.计算 r : = H ( I , m ) r:=H(I,m) r:=H(I,m) s : = r x + k s:=rx+k s:=rx+k mod q . q. q.输出签名 σ : = ( r , s ) . \sigma:=(r,s). σ:=(r,s).
∙ \bullet Vrfy: 输入公钥 ( G , q , g , y ) (G,q,g,y) (G,q,g,y),消息 m ∈ { 0 , 1 } ∗ m\in\{0,1\}^* m{0,1}和签名 σ = ( r , s ) \sigma=(r,s) σ=(r,s)
计算 I : = g s ⋅ y − r I:=g^s\cdot y^{-r} I:=gsyr并输出 1 如果 H ( I , m ) = r . H(I,m)=r. H(I,m)=r.
正确性: g s ⋅ y − r = g r x + k ⋅ g − x r = g k = I g^s\cdot y^{-r}=g^{rx+k}\cdot g^{-xr}=g^k=I gsyr=grx+kgxr=gk=I
在这里插入图片描述

如果离散对数问题相对于G是困难的,而H是随机预言机,那么Schnorr签名方案是EUF-CMA安全的。

DSA/ECDSA

∙ \bullet KeyGen:运行 G ( 1 n ) \mathcal{G}(1^n) G(1n)得到 ( G , q , g ) . (G,q,g). (G,q,g).选取$x\leftarrow$\mathbb{Z}_q$并设置$y:=gx.$ 私钥为 x x x,对应的公钥为 ( G , q , g , y ) . (G,q,g,y). (G,q,g,y).作为密钥生成的一部分,确定两个哈希函数 H : { 0 , 1 } ∗ → Z q H:\{0,1\}^*\to\mathbb{Z}_q H:{0,1}Zq F : G → Z q . F:G\to\mathbb{Z}_q. F:GZq.
∙ \bullet Sign: 输入私钥 x x x和消息 m ∈ { 0 , 1 } ∗ m\in\{0,1\}^* m{0,1},选取$k\leftarrow^{$}\mathbb{Z}_q 并设置 并设置 并设置r:=$ F ( g k ) . F(g^{k}). F(gk).计算 s : = k − 1 ( H ( m ) + r x ) s:=k^{-1}(H(m)+rx) s:=k1(H(m)+rx) mod q ( q( q(如果 r = 0 r=0 r=0 k = 0 k=0 k=0或r s = 0 s=0 s=0,那么重新选择 k ) . k). k).输出签名 σ : = ( r , s ) . \sigma:=(r,s). σ:=(r,s).
∙ Vrfy:   输   入   公   钥   ( G , q , g , y ) \bullet \textbf{Vrfy: 输 入 公 钥 }( G, q, g, y) Vrfy:     (G,q,g,y),消 息 m ∈ { 0 , 1 } ∗ m\in \{ 0, 1\} ^* m{0,1} 和 签 名 σ = ( r , s ) \sigma = ( r, s) σ=(r,s), 其 中 r , s ≠ 0 m o d q r, s\neq 0\allowbreak {\mathrm{mod}}q r,s=0modq,计 算 u = s − 1 m o d q u= s^{- 1}\allowbreak {\mathrm{mod}}q u=s1modq 并 输 出 1 如 果 r = r= r= F ( a H ( m ) u , r u ) F(a^{H(m)u},ru) F(aH(m)u,ru)
F ( g H ( m ) u y r u ) . F(g^{H(m)u}y^{ru}). F(gH(m)uyru).

在这里插入图片描述

∙ \bullet DSA 适
用于 Z p ∗ \mathbb{Z}_p^* Zp的素数q阶子群且 F ( I ) = I F(I)=I F(I)=I mod q . q. q.
∙ \bullet ECDSA 适用于椭圆曲线. E ( Z p ) E(\mathbb{Z}_p) E(Zp)的素数q阶子群且 I = ( x , y ) , F ( I ) = x I=(x,y),F(I)=x I=(x,y),F(I)=x
mod q q q
·如果 H H H F F F被模拟为随机预言机,EUF-CMA安全性可在DL假设下得
到证明。但对于上述这些的具体形式,尚无可证明安全。

其他

  • Nyberg-Rueppel签名方案是一个具有消息恢复功能的数字签
    名方案, 即验证算法不需要输入原始消息, 原始消息可以从
    签名自身恢复出来, 适合短消息的签名。
  • 基于大整数分解问题的数字签名
    Feige-Fiat-Shamir签名方案—参数与密钥生成
  • 盲签名
    盲签名允许使用者获得一个消息的签名, 而签名者既不知道该消息的内容,也不知道该消息的签名
  • 群签名允许一个群体中的任意一个成员以匿名的方式代表整个
    群体对消息进行签名。
  • 代理签名方案中, 允许一个原始签名者把他的签名权力委托给一
    个称为代理签名者的人, 然后代理签名者就可以代表原始签名者进行签名。

证书

后续更新

————————————————————————————————
致谢:感谢张源老师一学期的教学


http://www.kler.cn/a/448279.html

相关文章:

  • vsCode怎么使用vue指令快捷生成代码
  • 【定理证明工具调研】Coq, Isabelle and Lean.
  • Redisson锁简单使用
  • 电商项目-网站首页高可用(二)
  • Leaflet的zoom层级-天地图层级之间的关系
  • P1305 新二叉树
  • Golang中的Map是怎么遍历的
  • 面试题整理9----谈谈对k8s的理解1
  • Rocky Linux 9安装RabbitMQ
  • 设计模式之结构型
  • 【ArcGIS Pro微课1000例】0064:栅格目录、栅格数据集、镶嵌数据集
  • 怎样在html中异步加载js文件,以避免js文件太大而影响页面打开速度?
  • 【Tomcat运行startup.bat闪退】
  • Connecting to Oracle 11g Database in Python
  • 1.gitlab 服务器搭建流程
  • 在 Django 中使用 SMTP 发送邮件是一个常见的需求
  • Python——turtle库(海龟绘图)介绍与使用
  • javaEE-多线程编程-3
  • EdgeX Core Service 核心服务之 Core Command 命令
  • Redis梳理
  • 计算机视觉目标检测——DETR(End-to-End Object Detection with Transformers)
  • 自然语言处理学什么
  • 前端开放性技术面试—面试题
  • 虚拟世界中的社交互动:Facebook在元宇宙中的发展路径
  • CNN分类-卷积神经网络(Convolutional Neural Network)
  • 【C语言】倒序输出