CTF-All-In-One

CRYPT-6 数字签名

author : Odyssey@cyberpeace

目录

6.1 数字签名概念 6.2 RSA数字签名体制 6.3 ElGamal数字签名体制
6.4 其它数字签名方案 6.5 数字签名标准 6.6 应用

6.1 数字签名概念

6.1 数字签名概念

6.1 数字签名概念

6.1.1 数字签名的基本概念

一个数字签名体制是一个满足以下条件的五元组: $(M,S,K,sig,ver)$

6.1.1 数字签名的基本概念

手写签名与数字签名的区别

签名算法进行分类

6.1.2 数字签名的基本构造方法

利用Hash函数和加密算法可以构造有效的数字签名方案。

  1. 基于Hash函数和对称密码算法构造数字签名方案

  1. 基于Hash函数和公钥密码算法构造数字签名

具有保密作用的数字签名 公钥密码体制：$S_K$是发送方的私钥，$P_K$是发送方的公钥， $E_1$和$D_1$分别是加密算法与解密算法。 对称密码体制密钥：K是双方公用密钥，$E_2$和$D_2$分别是对应的加密算法和解密算法。

6.1.3 数字签名的安全需求

数字签名的攻击模型

攻击者对数字签名系统的攻击目的

Hash函数与数字签名的安全性

使用唯密钥攻击的存在性伪造 当签名算法遭到唯密钥攻击时, 即攻击者E拥有签名者A的公钥K.E就可能对一个随机的散列值z伪造签名$y=sig_k(z)$. 此时, 如果Hash函数h不是单向的,则E可能找到一个消息x，使得$z=h(x)$.所以E能够成功伪造一个签名(x, y).为了阻止这种攻击, 必须要求Hash函数h是单向的.

6.2 RSA数字签名体制

利用RSA加密算法构造的数字签名称为RAS数字签名体制。

6.2.1 RSA数字签名算法描述

  1. 密钥生成算法
    • 选取两个大素数p，q，计算 $n=p\times q,\varphi(n)=(p-1)\times (q-1)$
    • 任选整数e，满足： $0< e <\varphi(n)$，且$gcd(e ,\varphi(n))=1$
    • 用扩展Euclidean算法求e模(n)的逆d，即 $e\times d=1\space mod\space \varphi(n)$
    • 签名者的公钥: {$n,e$}，私钥:{ $p,q,d$}。
  2. 签名算法 设消息为x，则x的RAS签名是 $y=x^d\space mod\space n$
  3. 验证算法 当接收方收到签名（x，y）后，计算 $x’=y^e\space mod\space n$ 如果$x= x’$，则y是x的RAS签名

6.2.2 RSA数字签名的安全性

  1. 一般攻击
    • 攻击方法: 设n与e为用户A的公钥，攻击者首先随意选择一个数据y，并用A的公钥计算 $x=y^e\space mod\space n$ 于是可以伪造A的一个RSA数字签名（x，y）。因为 $x^d=(y^e)^d=y^{ed}=y\space mod \space n$ 所以用户A对x的RSA数字签名是y。
    • 这种攻击实际上成功的概率是不高的 因为对于选择的数据y，得到的x=ye mod n具有正确语义的概率是很低的。
    • 抵抗措施
      • 仔细设计数据格式
      • 对数据的Hash值进行签名
  2. 选择消息攻击
    • 攻击方法：假设攻击者E想伪造消息x的签名，他容易找到两个数据$x_1$和$x_2$，使得 $x=x_1\times x_2 \space mod \space n$ 攻击者E设法让用户A分别对x1和x2 进行签名，得到 $y_1=x_1^d\space mod\space n$，$y_2=x_2^d\space mod \space n$ 然后E可以计算 $y=y_1\times y_2=x_1^d\times x_2^d=(x_1\times x_2)^d=x^d\space mod \space n$ 于是攻击者E得到了用户A对消息x的RSA数字签名y
    • 抵抗措施
    • 用户不要轻易地对其他人提供的随机数据进行签名
    • 对数据的Hash值进行签名
  3. 利用签名进行攻击从而获得明文
    • 攻击方法 假设攻击者E已截获了秘文$c=x^e \space mod\space n$，他想求出明文x。于是，他选择一个小的随机数r，并计算 $s=r^e\space mod\space n$ $l=s\times c\space mod\space n$ $t=r^{-1}\space mod\space n$ 因为s=re,所以sd=( re)d= mod n，r=sd mod n.然后E 设法让签名者对l签名. 于是E又获得k=ld mod n. 攻击者E再计算： $t\times k=r^{-1}\times l^d=r^{-1}\times s^d\times c^d=r^{-1}\times r\times c^d=x \space mod \space n$

于是，获得了密文x。

  1. 对先加密后签名方案的攻击
    • 攻击方法 假设签名者A采用先加密后签名的方案把消息x发送给接收者B ,则他先用B的公开密钥$e_B$对x加密, 然后用自己的私钥dA签名.设A的模数为nA,B的模数为nB.于是A发送给B的数据为: $(x^{e_B}\space mod\space n_B)^{d_A}\space mod \space n_A$ 如果B是不诚实的,那么B可能伪造A的签名.例如,假设B想抵赖收到A发的消息x, 慌称收到的是x1.因为nB是B的模数,所以B知道nB的分解,于是能够计算模nB的离散对数.即他能找到k满足: $(x_1)^k=x\space mod \space n_B$ 然后，B再公布他的新公开密钥为keB。现在B宣布他收到的消息是$x_1$，而不是$x$。

由于下式成立，所以A无法争辩。 $(x_1^{ke_B}\space mod\space n_B)^{d_A}\space mod\space n_A=(x^{e_B}\space mod\space n_B)^{d_A}\space mod\space n_A$

6.3 ElGamal数字签名体制

6.3.1 ElGamal签名算法描述

  1. 参数生成算法
    • 选取一个大素数$p,g\in Z_p^*$是一个本原元，p和g是系统公开参数。
    • 任选整数x，满足：1≤x≤p-2。计算 $y=g^x\space mod\space p$ 签名者的公钥为y，私钥为x。

  2. 签名算法 设$M\in Z_p^{}$为待签名的消息。签名者随机选择一个秘密整数k，1≤k≤p-2，计算 $r=g^k\space mod\space p$ $s=(M-x\times r)k^{-1}\space mod\space(p-1)$ 签名者对M的ElGamal签名为: $sig(M)=(r,s)\in Z_P^{}\times Z_{p-1}^{*}$ 签名者将数据(M,(r,s))发送给接收者

  3. 验证算法 接收方收到签名(M, (r,s)) 后，验证 $y^r\times r^s=g^M\space mod\space p$ 是否成立，如果等号成立，则确认(r, s)是M的有效签名。
    • 有效性证明 因为：$s=(M-x\times r)k^{-1}\space mod\space (p-1)$ 所以：$k\times s+x\times r=M\space mod\space (p-1)$ 因此，如果（r，s）是M的正确签名，则一定有 $y^r\times r^s=g^{xr}\times g^{ks}=g^{xr+ks}=g^M\space mod\space p$

ElGamal数字签名是一个随机的数字签名体制 例如：设p=11，g=2是$Z_{11}^*$的本原元。选取私钥为x=8， 计算公钥 $y=g^x\space mod \space p=2^8\space mod\space 11=3$ 设签名者A要对消息M=5进行签名。签名者A首先秘密选取一个整数k=9，计算 $r=g^k\space mod\space p=2^9\space mod \space 11=6$ $s=(M-x\times r)k^{-1}\space mod(p-1)=(5-8\times 6)\times 9^{-1}\space mod\space 10=3$ 签名者A对$M=5$的ElGamal签名为（6, 3）。 接收者B可以对消息M=5的签名（6, 3）进行验证。 因为：$3^6\times 6^3=2^5\space mod\space 11$

6.3.2 ElGamal数字签名的安全性

ElGamal数字签名算法的实现

ElGamal数字签名体制的参数p

不知道私钥的攻击

假设攻击者E不知道私钥$x$，要想伪造消息M的签名(r,s), 则E可能使用的攻击方式有：

由于： $ \begin{aligned} y^r\times r^s&=y^r\times(g^i\times y^j)^{-rj^{-1}} \ &=y^r\times g^{-irj^{-1}}\times y^{-r} \ &=g^{-irj^{-1}} \&=g^{M}\space mod\space p \end{aligned} $ 成立，所以(r, s) 是消息M的有效签名 该攻击方法属于存在性伪造。因此，在使用ElGamal数字签名方案时，不要直接对消息进行签名，而应该对消息的Hash值进行签名。

例6.3

设p=467，g=2是$Z_{467}^*$的本原元，签名者公钥y=132。攻击者选择整数i=99，j=1.79，计算 $j^{-1}=179^{-1}\space mod \space 466=151$ $r=2^{99}\times 132^{179}\space mod\space 467=117$ $s=-117\times 151\space mod \space 466=41$ $M=-117\times 99\times 151\space mod\space 466=331$

由于： $y^r\times r^s=132^{117}\times 117^{41}=303\space mod\space 467$ $g^{M}=2^{331}=303\space mod\space 467$ 所以（117,41）是消息M=331的有效签名

假设攻击者E知道(r, s)是消息M的签名,则E可利用它来伪造其它消息的签名. 选择整数$l,i,j,0\leq l,i,j\leq p-2,gcd(lr-js,p-1)=1$，计算 $u=r^l\times g^i\times y^j\space mod\space p$ $v=s\times u\times (l\times r-j\times s)^{-1}\space mod\space (p-1)$ $W=u\times (l\times M+i\times s)\times (l\times r-j\times s)^{-1}\space mod\space (p-1)$

由于$y^r\times r^s=g^M\space mod\space p $，所以

$ \begin{aligned} r^s&=y^{-r}\times g^M\space mod\space p
&=y^u\times (r^l\times g^i\times y^j)^{su(lr-js)^{-1}}
&=y^{u+jsu(lr-js)^{-1}}\times r^{hsu(lr-js)^{-1}\times g^{isu(lr-js)^{-1}}}
&=y^{u+jsu(lr-js)^{-1}-rlu(lr-js)^{-1}}\times g^{isu(lr-js)^{-1}+Mu(lr-js)^{-1}}
&=y^{u(l-(lr-js)(lr-js)^{-1})}\times g^{(is+lM)u(lr-js)^{-1}}
&=g^w\space mod \space p \end{aligned} $

可见$(u, v)$是消息$W$的有效签名。

使用ElGamal数字签名方案的安全措施

6.3.3 ElGamal签名体制的变形

ElGamal数字签名算法有多种变形

6.4 其它数字签名方案

6.4.1 Fiat-Shamir数字签名

签名算法：

为了对消息m进行签名,用户A执行以下步骤：

  1. 随机选取一个正整数t。
  2. 在1和n之间随机选取t个正整数rj (j =1,2,…,t)，并计算 $R_j=r_j^2\space mod\space n\space (j=1,2,…,t)$
  3. 计算Hash函数值h (m|| R1|| R2||…|| Rt)，依次取出其前$k\times t$个比特值，记为 $b_{ij}(i=1,2,…,k;j=1,2,…,t)$
  4. 计算：$s_j=r_j\prod_{i=1}^{k} x_{i}^{b_{ij}}\space mod\space n\space (j=1,2,…,t) $ 用户A对消息m的数字签名为： ${b_{ij}},{s_j}(i=1,2,…,k;j=1,2,…,t)$ 签名者将数据$(m,{b_{ij}},{s_j})$发送给接收者B

验证算法：

接收方B收到签名数据$(m,{b_{ij}},{s_j})$后, 按以下步骤进行验证：

  1. 利用A的公钥计算：$R_j^{‘}=s_j^2\prod^{k}{i=1}y_i^{b{ij}}\space mod\space n\space (j=1,2,…,t)$
  2. 计算Hash函数值：$h(m   R_1^{‘}   R_2^{‘}   …   R_t^{‘})$，依次取出其前$k\times t$个比特值，记为：$b_{ij}^{‘}(i=1,2,…,k;j=1,2,…,t)$
  3. 比较等式：$b_{ij}=b_{ij}^{‘}(i=1,2,…,k;j=1,2,,…,t)$ 是否成立。如果$k\times t$个等式全部成立，则数字签名有效。否则，数字签名无效。

该验证算法的正确性

当数据传输正确时，有 得到：$h(m||R_1^||R_2||…||R_k)=h(m||R_1^{‘}||R_2^{‘}||…||R_k^{‘})$ 并且：$b_{ij}=b_{ij}^{‘}(i=1,2,…,k;j=1,2,,…,t)$

例6.4

设n=35，k=4，用户A的4个公钥为：$y_1 =4$，$y_2 =11$，$y_3 =16$，$y_4 =29$。则A的4个私钥为： 取$t=1$,$r_1=16$，计算：$R_1=r_1^{2}=16^2=11\space mod\space 35$ 为了简化，设$h(m||R_1)=R_1=11=1011$。即有： $b_{11}=1,b_{21}=0,b_{31}=1,b_{41}=1$ $s_1=r_1\prod_{i=1}^{4}x_i^{b_{ij}}\space mod\space n=16\times 3^1\times 9^0\times 9^1\times 8^1=26\space mod\space 35$ 数字签名为（{1,0,1,1}, {26}）

设n=35，k=4，用户A的4个公钥为：$y_1 =4$，$y_2 =11$，$y_3 =16$，$y_4 =29$。数字签名为（{1,0,1,1}, {26}）。 接收方验证方法如下。由于：$R_1^{‘}=s_1^2\prod_{i=1}^{4}y_i^{b_{ij}}=26^2\times 4^1\times 11^0\times 16^1\times 29^1\space mod\space 35=11=R_1\space mod\space 35$ 所以数字签名有效。

6.4.2 一次性数字签名

6.4.3 Lamport一次性数字签名

密钥生成：

已知单向函数$f:Y→Z$

签名算法 设消息$x=(x_k x_{k-1}…x_2 x_1)$是二进制串，则对消息x的签名为：{$u_i=y_{i,j}|1\leq i\leq k,x_i=j$} 验证算法 若${f(u_i)|1\leq i\leq k}$包含在公钥中，则签名是合法的。

6.4.4 Bos-Chaum 一次性数字签名

Bos-Chaum一次性签名方案的签名比Lamport方案的签名短。设A={1，2，…，2n}是2n元集合，B是A的所有n元子集构成的集合，则有$|B|=C_{2n}^n$。定义Bos-Chaum签名方案使用的单射函数为：$\varphi:{0,1}^k→B$ 它把长为k的字符串映射到A的n元子集，这里$2^k\leq C_{2n}^n$

6.4.4 Bos-Chaum 一次性数字签名

  1. 密钥生成 设 f:Y→Z是单向函数，取$y1,y2,…,y2n\in Y$作为私钥，$z_1,z_2,…,z_2n\in Z$作为公钥，其中$f(y_i)=z_i(1\leq i\leq 2n)$。
  2. 签名算法 设消息$x=(x_kx_{k-1}…x_2x_1)_2$是二进制串，则对消息x的签名为： {$a_1,a_2,…,a_n$}$=$${y_j|j\in \varphi (x)}$。
  3. 验证算法 计算集合$C={f(a_i),1\leq i\leq n}$和$\varphi (x)$。如果$C={z_j|j\in \varphi (x)}$，则{$a_1,a_2,…,a_n$}是对$x$的合法签名。

6.4.4 Bos-Chaum 一次性数字签名

由于f是单向函数，对手不可能伪造消息的Bos-Chaum签名。 如果使用Bos-Chaum方案签了两个消息，则对手容易伪造Bos-Chaum签名。 例如，令n=4，容易计算出$\varphi (110010)={2,4,6,8},\varphi (010011)={2,3,4,7}$。已知对110010的Bos-Chaum签名为${y_2,y_4,y_6,y_8}$，对010011的Bos-Chaum签名为${y_2,y_3,y_4,y_7}$，容易得到对111100的Bos-Chaum签名为${y_2,y_4,y_7,y_8}$。所以该签名方案是一次性签名方案。

6.4.5 不可否认数字签名

对于以前讨论的数字签名，任何人都可以对签名进行验证。但在某些特殊应用条件下，需要在签名者参加的情况下才能进行验证。具有这种性质的数字签名称为不可否认签名方案(undeniable signature scheme)。它们可以应用在如下场合：

Chaum和van Antwerpen在1989年提出的不可否认数字签名方案

密钥生成

随机选择素数$q,p=2q+1$。在$Z_p^{*}$中取q阶元$a(\neq1)$。从Euler准则知$a$是模$p$的二次剩余组成的。 选择秘密指数$1\leq x\leq p-1$，计算$y=a ^x\space mod \space p$。 公布公钥$(p,a,y)$，秘密保存私钥$x$。

签名算法

对消息m的签名是: $s=m^x\space mod\space p$。

验证协议

假设签名者A想否认一个“由签名生成算法构造出来的”合法签名，其方式有：

  1. 拒绝参与验证协议；
  2. 错误地执行验证协议；
  3. 即使验证协议成功，也断言签名是伪造的。

对于前者很明显，而后两种情况难以防范。使用“否认协议”（disavowal protocol）能够确定是签名者A试图否认一个由签名算法得出的签名，还是签名本身是伪造的。否认协议由两遍验证协议组成。

否认协议

否则计算：$C=(wa^{-x_2})^{x_1’}\space mod\space p,C’=(w’a^{-x’_2})^{x_1}\space mod\space p$

进行一致性检验，若$C=C’$，则s是对m的伪造签名；若$C\neq C’$，则s是对m的合法签名，签名者试图否认。

否认协议的性质

6.4.6 盲签名

盲签名过程

6.4.7 基于RSA公钥密码系统的Chaum盲签名

Chaum提出的盲签名方案是基于RSA公钥密码系统

密钥生成

盲签名协议

设需签名的消息为m

盲签名验证算法

验证$m=s^{b_s}\space mod\space n_B$。若成立，则接受s是对m的签名，否则拒绝

6.4.8 基于离散对数问题的盲签名

密钥生成

签名者选择两个大素数p，q，q (p-1)，在$Z_p^$上离散对数问题是难解问题。a是$Z_p^{}$的q阶元。选取私钥$x$，令$y=a^x\space mod\space p,(p,q,a,y)$为公钥。

盲签名协议

设A需签名的消息为m，盲签名由签名者B开始

盲签名验证算法

验证$a^s\equiv y^rr^m\space mod \space p$，若成立，则接受(r,s)是对m的签名；否则拒绝。

6.5 数字签名标准

数字签名标准（DSS: Digital Signature Standard）由美国国家标准技术研究所（NIST）于1991年提出，并于1994年正式成为美国联邦信息处理标准（FIPS PUB186），这标志着数字签名已得到政府的支持。DSS使用的签名算法称为数字签名算法（DSA: Digital Signature Algorithm）。2000年1月美国政府将RSA和椭圆曲线密码引入数字签名标准DSS，进一步丰富了DSS的算法。目前，DSS的应用已十分广泛，并被多个国际标准化组织采纳作为标准。美国的一些州已经通过相关法律，正式承认数字签名的法律意义。这是数字签名得到法律支持的重要标志。

6.5.1 美国数字签名标准

算法参数 DSA使用的参数如下

签名算法

设SHA是一个安全hash函数

验证算法

6.6 应用

手写签名可以用来签合同，那么数字签名可以用来干什么呢？

6.6.1 网站认证

最常见的用处就是用来认证一个网站的身份。 比如我打开百度，百度是怎么保证显示在我眼前的网页就一定是百度生成的，不是其他人修改的呢？就是借助数字签名来实现的。

用IE浏览器打开百度，点击地址栏旁边的小锁，再点击查看证书，就可以看到百度主页的数字签名证书了。所谓证书，其实是对公钥的封装，在公钥的基础上添加了诸如颁发者之类的信息。

6.6.2 代码签名

如果Windows上的可执行程序程序来源于正规公司，那么通常它会有代码签名，用于确保其来源可靠且未被篡改。以QQ为例，它的数字签名是这样的。

如果某个程序没有数字签名，那么它的安全性往往就没有保证，如果它有数字签名，但是显示“此数字前面无效”，那么这个程序要么被篡改了要么损坏了，不管哪种可能都不应该尝试执行它。

6.6.3 比特币

比特币是一种完全匿名的数字货币，它的身份认证是基于ECDSA。比特币的账户地址就是对公钥计算摘要得到的，向全世界公布。而确认你是账户拥有者的唯一办法就是看你有没有账户对应的私钥。对于比特币中的任意一个交易记录，只有当其中付款方的签名是有效的，它才是有效的。如果账户私钥丢失，那么你将永远地失去里面的钱；一旦被黑客盗取，里面的钱就完全归黑客所有。

6.6.4 电子邮件

This site is open source. Improve this page.