DSA变种以及批认证的安全性证明

2020/06/25 密码学

下面给出一个基于标准DSA数字签名算法的变种的形式化安全性证明,同时给出该算法的批量认证算法以及对应的安全性证明。

签名方案的描述与形式化安全性证明

方案中的签名算法是基于DSA数字签名算法的变种,其中包含

  • 系统初始化:随机选择一个大素数\(p\),满足\(2^{L-1}<p<2^L\),\(L\)是\(p\)的比特长度;随机选择一个大素数\(q\),\(q\)是\(p-1\)的大素因子,满足\(2^{N-1}<p<2^N\),其中\(N\)是\(q\)的比特长度;选择一个\(Z_p^*\)上\(q\)阶子群的生成元\(g\),满足\(1<g<p\);选择一个哈希函数\(H:\{0,1\}^*→\{0,1\}^{2K}\),\(K\)是安全参数。

  • 密钥生成算法:选择一个随机数\(x\)作为签名者的私钥,计算出\(y=g^x\) mod \(p\)作为签名者的公钥。随机数\(x\)满足\(1<x<q-1\)。

  • 签名生成算法:对于消息\(m\),签名者选择一个随机数\(k\),满足\(1<k<q-1\)。然后计算

    \[r=g^k\ mod\ p\] \[s=\frac{H(m)+xr}{k}\ mod\ q\]

    生成的签名结果为\((r,s)\)。

  • 验证签名算法:对于消息m与相应的签名\((r,s)\),验证者首先检查签名\((r,s)\)是否满足\(0<r<p\),\(0<s<q\)。如果不满足则对该签名认证不通过。否则检查下面的公式是否成立,如果成立则对该签名认证通过,否则认证不通过。

    \[g^{\frac{H(m)}{s}}y^{\frac{r}{s}}\ mod\ p = r\]

定理:假设\(H\)是一个随机谕言机,如果与方案中相关的离散对数问题是困难的,则该方案是EUF-CMA安全的。

该EUF游戏如下:

  1. 挑战者运行系统初始化算法和密钥生成算法,得到\((p,q,g,y,x)\),选取一个随机的哈希函数\(H\)。敌手\(A\)得到公钥\((p,q,g,y)\)。

  2. 挑战者为敌手\(A\)提供两项模拟算法,分别是返回消息的哈希值以及对消息的签名。当敌手\(A\)请求对消息\(m\)的签名时,挑战者随机选择\(k\in(1,q-1)\),然后向敌手\(A\)返回\(r=g^k\ mod\ p\),\(s=\frac{H(m)+xr}{k}\ mod\ q\)。

  3. 敌手\(A\)输出一个消息-签名组\((m,r,s)\),其中\(A\)在之前的询问中没有请求过消息\(m\)的签名。如果该消息-签名组满足\(g^{\frac{H(m)}{s}}y^{\frac{r}{s}}\ mod\ p = r\),则敌手攻击成功。

下面证明该方案可以归约到离散对数问题。

敌手\(B\)已经获得\((p,q,g,h^{*})\),其中\(h^{*}\)是均匀随机的。敌手\(B\)以\(A\)攻击作为子程序,目标是计算出\(\frac{sk-h^{*}}{r}\ mod\ p\)。如果说敌手\(B\)能够得到某个\((r,s)\),使得\(g^{\frac{h^{*}}{s}}y^{\frac{r}{s}}\ mod\ p=r\),那么有\(\frac{sk-h^{*}}{r}\ mod\ p=x\),即求解出\(y\)在生成元\(g\)的模数\(p\)离散对数。如果说\(h^{*}\)是某个消息的哈希值,那么\((r,s)\)就是这个消息的签名。\((m,r,s)\)是由敌手\(A\)生成的,但是哈希函数是由敌手\(B\)生成的,那么敌手\(B\)可以假设\(H(m)=h^{*}\)。在这个过程中,\(B\)将\(h^{*}\)设定为某个消息\(m\)的哈希函数值,由于不知道\(A\)最终对哪个消息产生伪造的签名,同时也不知道\(A\)生成的随机数\(k\)。因此\(B\)需要对该消息以及随机数\(k\)进行猜测。下面假设\(A\)的第\(j\)次\(H\)询问即是\(A\)最终要伪造的结果。

其中游戏的过程中需要满足几个条件:

  • \(A\)不会发起两次相同的\(H\)询问。

  • 如果\(A\)请求对消息\(m\)的签名,那么它之前已经对\(m\)发起过\(H\)询问。

  • 如果\(A\)输出消息-签名组\((m,r,s)\),那么它之前已经对\(m\)发起过\(H\)询问。

下面是归约的过程。

  1. \(B\)将公开材料\((p,q,g,y)\)发送给\(A\)。假设\(A\)最多进行\(q_H\)次\(H\)询问,\(B\)选择一个随机数\(j\),其中满足\(j\in[1,q_H]\)。\(j\)相当于是\(B\)的一个猜测值,相当于\(A\)的第\(j\)次\(H\)询问即是\(A\)最终的伪造结果。

  2. \(B\)建立一个\(H^{list}\)列表,初始值为空,元素的类型是四元组\((m_i,r_i,s_i,h_i)\),表示\(B\)已经将\(H(m_i)\)设置为\(h^i\),并且\(g^{\frac{h_i}{s_i}}y^{\frac{r_i}{s_i}}\ mod\ p = r_i\)。当\(A\)发起第\(i\)次询问时,\(B\)分两种情况进行回答:

    • 如果\(i=j\),那么返回\(h^{*}\)。

    • 如果\(i\neq j\),那么选择两个随机值\((r_i,s_i)\),满足\(g^{\frac{h_i}{s_i}}y^{\frac{r_i}{s_i}}\ mod\ p = r_i\),并将\(h^i\)作为本次询问的应答,将\((m_i,r_i,s_i,h_i)\)存到\(H^{list}\)列表中。

  3. 当\(A\)请求消息\(m_i\)的签名时,其中\(m_i\)表示\(A\)在第\(i\)次\(H\)询问的询问值。\(B\)分两种情况进行回答:

    • 如果\(i=j\),那么中断。

    • 如果\(i\neq j\),则\(H^{list}\)列表中存在一个四元组\((m_i,r_i,s_i,h_i)\),将其中的\((r_i,s_i)\)返回。

  4. 当\(A\)输出\((m,r,s)\)时,如果\(m_i\neq m\),此时\(B\)中断;如果\(m_i=m\),并且满足\(g^{\frac{h_{*}}{s}}y^{\frac{r}{s}}\ mod\ p = r\),那么\(B\)输出签名\((r,s)\)。

如果说\(B\)的猜测是正确的,并且\(A\)输出一个伪造的签名,那么\(B\)就解决了离散对数问题,因为\(\frac{sk-h^{*}}{r}\ mod\ p=x\),即求解出\(y\)在生成元\(g\)下模数\(p\)的离散对数。\(B\)的成功依赖下面3个事件:

  • \(ε_1\):\(B\)在\(A\)的签名询问中不中断。

  • \(ε_2\):\(A\)输出一个有效的消息-签名组\((m,r,s)\)。

  • \(ε_3\):\(ε_2\)事件发生,并且\(m\)对应的消息签名组中下标满足\(i=j\)。

因为

\[Pr⁡[ε_1]=(1-\frac{1}{q_H})^{q_H}\] \[Pr⁡[ε_2|ε_1]=ϵ(k)\] \[Pr⁡[ε_3|ε_1 ε_2]=Pr⁡[i=j|ε_1ε_2]=\frac{1}{q_H}\]

因此\(B\)的优势为:

\[Pr⁡[ε_1ε_3]=Pr⁡[ε_1]Pr⁡[ε_2|ε_1]Pr⁡[ε_3|ε_1ε_2]=(1-\frac{1}{q_H})^{q_H}\frac{ϵ(k)}{q_H}\]

签名方案中哈希函数的安全性

方案中采用对消息摘要而不是消息本身进行签名的方式,因此Hash函数的安全性也会影响到该方案的安全性。推荐使用SHA-256或者是MD5等安全的哈希函数。下面给出证明,如果方案中采用对消息本身直接进行签名,即\(H(m)=m\),那么该方案是不安全的。

当\(H(m)=m\)时,签名生成算法如下:

\[r=F(g^k)=g^k\ mod\ p\] \[s=\frac{m+xr}{k}\ mod\ q\]

签名的验证算法与上述方案的验证算法一致。

首先考虑比较简单的情况,攻击者构造一个零消息,即消息值\(m=0\),此时攻击者构造出签名\((r,s)\)满足\(r=F(y)\),\(s=F(y)\),该签名是合法的,因为下面等式成立:

\[g^{\frac{H(m)}{s}}y^{\frac{r}{s}}\ mod\ p = g^{\frac{0}{F(y)}}y^{\frac{F(y)}{F(y)}}\ mod\ p = F(y) = r\]

一般的,假设攻击者得到了\((p,q,g,y)\),攻击者的目标是构造出合法签名\((r,s)\)。这个过程如下描述,首先攻击者选择任意两个均匀随机的随机数\(a\),\(b\),然后构造出下列消息-签名组\((m,r,s)\):

\[r=g^{a}y^{b}\ mod\ p\] \[m=rab^{-1}\ mod\ q\] \[s=rb^{-1}\ mod\ q\]

该签名是合法的,因为下面的等式成立:

\[g^{\frac{H(m)}{s}}y^{\frac{r}{s}}\ mod\ p = g^{\frac{rab^{-1}}{rb^{-1}}}y^{\frac{r}{rb^{-1}}}\ mod\ p = g^{a}y^{b}\ mod\ p = r\]

签名方案中随机数k的安全性

在该方案中由于随机数\(k\)与消息\(m\)无关,因此每次签名时,使用随机数\(k\)可以使得对同一消息的签名结果是不同的。但是如果随机数\(k\)的选取存在缺陷,或者使用相同的随机数\(k\)对消息进行签名,那么攻击者有更高的优势恢复出\(k\)。

  1. 如果随机数\(k\)值比较小,根据\(r=g^k\ mod\ p\),攻击者可以使用暴力穷举搜索来求解出\(k\)值。

  2. 如果攻击者获得了两个使用相同的\(k\)值的签名消息,那么可以恢复出\(k\):

    \[k=(s_2-s_1)^{-1}(H(m_2)-H(m_1))\ mod\ q\]

批验证算法的安全性证明

下面给出了该签名方案的批验证算法。

  • \(N\)个签名者分别生成消息\(m_i\)的签名\((r_i,s_i)\)。首先选择一个随机数\(k_i(0<k_i<q)\),计算\(r_i=g^{k_i}\ mod\ p\),\(s_i=k_i^{-1}(H(m_i)+x_ir_i)\ mod\ q\),得到签名\((r_i,s_i)\)。

  • 签名者将\(\{r_i,s_i,m_i\}\)发送给验证者。

  • 验证者收到\(\{r_i,s_i,m_i\},i=1,2,…,n\),首先检查每组签名\((r_i,s_i)\)是否满足\(0<r_i<p\),\(0<s_i<q\)。如果不满足则丢弃第\(i\)组签名,否则选择\(n\)个相互独立的随机数\(b_i,i=1,2,…,n\),检验下式是否成立:

    \[g^{\sum_{i=1}^n \frac{b_iH(m_i)}{s_i}}\prod_{i=1}^n y_i^{\frac{b_ir_i}{s_i}}\ mod\ p=\prod_{i=1}^n r_i^{b_i}\ mod\ p\]

在上述方案中,通过引入随机数\(b_i\)来避免敌手发起共谋攻击,降低了在叠加操作和连乘操作中各个参数之间的关联性。如果没有随机数\(b_i\),敌手可以伪造出两组参数\(\frac{H(m_1)}{s_1}+a\)与\(\frac{H(m_1)}{s_1}-a\),这两组参数对应的签名在单独验证中是不能通过的,但是它们的求和结果能消去随机数\(a\),从而通过批认证算法。

攻击者如果要攻破该批验证算法,需要构造\(n\)组合法签名,相当于求解\(n\)次离散对数问题,这对于攻击者而言是计算上困难的。我们考虑一个特殊情况,即所有的签名者的私钥是相同的,等效于攻击者只需要求解1次离散对数问题。在这种情况下,上述的验证公式变为:

\[g^{\sum_{i=1}^n \frac{b_iH(m_i)}{s_i}}y^{\sum_{i=1}^n \frac{b_ir_i}{s_i}}\ mod\ p=\prod_{i=1}^n r_i^{b_i}\ mod\ p\]

下面给出两个假设并证明它们是等价的。其中假设1是上面验证公式的子问题,如果敌手能满足假设1或者是满足假设2,则表示敌手攻破了该批验证算法。

  1. 假设存在一个高效率的算法\(C(m_1,m_2,p,q,g,y,b,b_1,b_2)=\{s_1,s_2,r_1,r_2\}\),使得下面的式子成立

    \[r_1^br_2^{b_1}≡g^{\frac{bH(m_1)}{s_1}+\frac{b_1H(m_2)}{s_2}}y^{\frac{br_1}{s_1}+\frac{b_1r_2}{s_2}}\ mod\ p\] \[r_1^br_2^{b_2}≡g^{\frac{bH(m_1)}{s_1}+\frac{b_2H(m_2)}{s_2}}y^{\frac{br_1}{s_1}+\frac{b_2r_2}{s_2}}\ mod\ p\]

    其中\(b_1\neq b_2\)。

  2. 假设存在一个高效率的算法可以破解DSA方案。

下面证明假设1和假设2是等价的。

  • 假设2\(→\)假设1:这是显然易见的,因为假设2相当于存在一个高效率的算法可以计算出离散对数,即计算出公钥\(y\)在模\(p\)的离散对数(私钥)\(x\)是计算上高效率的,根据上面DSA的计算过程,假设1中的算法\(C(m_1,m_2,p,q,g,y,b,b_1,b_2)=\{s_1,s_2,r_1,r_2\}\)也是计算上高效率的。

  • 假设1\(→\)假设2。将假设1中的两条式子相除消去\({r_1}^b\)变量,可以得到:

    \[r_2^{b_1-b_2}≡g^{\frac{(b_1-b_2)H(m_2)}{s_2}}y^{\frac{(b_1-b_2)r_2}{s_2}}\ mod\ p\]

    将左右的幂\(b_1-b_2\)消去得到

    \[r_2≡g^{\frac{H(m_2)}{s_2}}y^{\frac{r_2}{s_2}}\ mod\ p\]

    此时求解出\(\{r_2\ mod\ q,s_2,m_2\}\)是对消息\(m_2\)的合法DSA签名。

由于DSA签名方案的安全性归约到计算离散对数的困难问题,因此上述假设1中的算法是计算上困难的,进而得出攻击者要破解批认证算法的优势非常小。

Search

    Table of Contents