2024-07-12 2024-07-12 7719 字 16 分钟

- 数字签名

#include <iostream>
using namespace std;
int main(){
    cout << "你可以在这里编写，测试代码!" << endl;
    cout << "目前只支持c++,java和python!" << endl;
    cout << "点击右上角切换语言!" << endl;
    return 0;
}

群签名

概念

群签名是这样一个数字签名：在一个群签名的方案中，一个群体中的任意一个成员可以代表这个群体对消息进行签名，并且其他人可以使用群公钥对这个签名进行公开验证。在验证时，验证者只能验证签名是来自这个群组的，但是无法知道到底是群中的哪个成员对消息进行了签名。

在群签名中，存在一个群管理员，该管理员可以通过对签名进行操作得到签名者的真实身份。

形式化定义

一个群签名通常包含下面几个步骤：
创建：一个用以产生群公钥和私钥的概率多项式时间算法。
加入：一个用户和群管理员之间的使用户成为群管理员的交互式协议。执行该协议可以产生群员的私钥和成员证书，并使群管理员得到群成员的私有密钥。
签名：一个概率算法，当输入一个消息和一个群成员的私钥后，输出对消息的签名。
验证：一个概率算法，当输入一个群成员的签名和群公钥后，可以判断签名是否属于这个群。
打开：一个在给定一个签名及群私钥的条件下确认签名人的合法身份的算法。

群签名的性质

早期的群签名存在公钥大小随群成员数量线性增长的情况，随着群签名的发展，现在的群签名方案一般具有以下特点：

公钥大小和签名大小固定，与群成员的数量无关；
实现了对群成员的动态管理，允许用户再需要的时候动态的加入群组，或者允许群管理员动态的对群成员进行撤销。
一些群签名方案实现了 Opener 和 Manager 分离，使得 Manager 管理群成员的加入和离开，Opener负责揭露恶意群成员的真实身份，解除其匿名性，实现有条件的隐私保护。

在群签名中，常见的实现群组成员撤销的机制有以下几种：
① 组管理员更新组公钥，并将其发送给为被撤销的用户
② 使用累加器：它可以高效的队组成员进行撤销和加入
③ 签名者在签署消息，或根据组的变化更新自己的密钥时，需要提供合格的成员资格证明。常见的方法是把非法用户的 id 放入黑名单，使得在更新密钥的时候，黑名单内的用户证书将面临除零异常，从而导致其无法更新证书。
④ 验证者本地撤销：GM发现恶意用户的签名之后，将签名者的身份发给签名的验证者。这种撤销方式只有验证者拥有撤销列表。

基于RSA的群签名

系统初始化

群管理员选择RSA的公钥（n，e）
群管理员选择生成元为 g 的循环群 G，G 的阶为 n
选择一个 $a\in Z_n^* $，这里 a 对于 n 的两个素数因子 p ，q 都有较大的乘法阶
选择密钥长度的上界 λ ，和一个常数 ε ，其中 ε 1
该群的公共参数为 params = {n，e，G，g，a，λ，ε}

成员加入

假设Alice想要加入这个群组，她和群管理员进行以下交互：

Alice 执行：

选择一个私钥 x 并计算 $y = a^x (mod\ n)$ 和 $z = g^y$（z作为成员密钥）

然后Alice发送 y，z 和自己对 z 的签名给群管理员GM，并使用知识签名证明自己知道满足$y=a^x(mod\ n)$的 x 。

GM 执行：

GM验证y和z的合法性，验证知识签名从而确定Alice是知道 x 的。

GM保留（y，z）用于日后打开群签名。

GM生成Alice的群成员证书$v = (y + 1) ^ {1/e}\ (mod\ n)$, 并将 v 发送给Alice。

Alice 执行：

Alice可以通过计算验证 v 的正确性。如果验证通过，则Alice 存储这个证书，用于后续生成群签名。

成员生成群签名

随机选择 $r∈Z_n^*$并计算$\widetilde{g}=g^r$
计算$\widetilde{z}=\widetilde{g}^{\ y}(mod \ n)$
计算$v_1$ = SKLOGLOG[ $x:\widetilde{z}=\widetilde{g}^{α^x}$ ]
计算$v_2$ = SKROOTLOG[ $v:\widetilde{z}\widetilde{g}=\widetilde{g}^{v^e}$ ]
群签名的结果为$sig={\widetilde{g}, \widetilde{z}, v_1, v_2}$

群签名的验证

验证 $v_1$ 即可证明签名者知道私钥 x, 同时验证者可以据此得知 $\widetilde{z}$ 的结果形如 $\widetilde{g}^{α^x}$ 。因此，我们可以得知 $\widetilde{z}\widetilde{g}$ 的结果是性心如 $\widetilde{g}^{\ a^x+1}$ 的形式。

用知识证明验证$v_2$时可知：$\widetilde{z}\widetilde{g}$ 的形式是 $\widetilde{g}^{\ a^x+1}$ 验证 $v_2$ 如果成功，证明 Alice 知道 $a^x+1$ 的 e 次根，即 $(a^x+1)^{1/e}=v$ 这意味着 Alice 知道秘钥x和她的成员密钥的成员证书 v。

综上：只要验证了上述群签名就能验证签名 sig 确实来自这个群组的某个成员。（上述验证中验证了签名者群成员证书v的合法性）

打开群签名

当遇到特殊情况时，需要知道签名者的真实身份，这是群管理员可以做到这一点：由于$\widetilde{z}=\widetilde{g}^{\ y}(mod \ n)$，且GM存储了每个群成员的（y，z）。所以，GM遍历所有的 y ，如果满足上述等式，就能找到签名者的真实身份。

参考文献：

97年发表的论文《 Efficient Group Signature Schemes for Large Groups 》
CSDN：https://blog.csdn.net/zhang_hui_cs/article/details/8965338

群签名开山作：

这是第一篇介绍群签名的论文中提出的方案【一共提出了四个方案，这是其中的一个方案】

预备知识

零知识证明：

也就是 P 向 V 证明自己知道一个秘密值$s_i$,，满足：$s_i=m^{s_i}\ (mod\ p) 且 g^{s_i}∈{k_j\ |\ j∈Γ }$ 在证明过程中，$p,g,h,S,Γ$是公开的。其中，p是一个大素数，$g,h∈Z_p^*$ 。S是群签名，$Γ$ 表示群成员的索引集合。

具体签名过程

假设 p 是一个大素数，$g,h\in Z_p^* $, 群公钥为 $gpk={k_1,k_2,…,k_n}$ ，假设用户 i 想对消息 m 进行签名：

说明：

如果证明者P不知道$s_i$那么他不能计算出 $t_3+s_i$;因为b=0时，验证者可以通过验证保证$y=m^{t_3}$的成立，而$S=m^{s_i}$是公开的，故$yS=m^{t_3+s_i}$，故P必须知道$s_i$并给出$t_3+s_i$才能完成b=1时的验证
第二个等式中，由于$k_i=g^{s_i}$是公开的，由于等式化简过程中，将$g^{s_i}$化简为了$(g/m)^{s_i}*m^{s_i}$,这必须保证$k_i=g^{s_i}$中的$s_i$与$S=m^{s_i}$中使用的$s_{s_i}$相等. 这就保证了群签名S中的秘密值确实来自某个群成员公钥对应的私钥.
置换$τ$是用来隐藏群成员的真实身份的. 由于验证的时候使用的是置换后的群成员索引,因此证明者不能知道群成员在公钥集合中的真实索引.

ACJT群签名方案

ACJT算法在2000年提出

预备知识

知识签名:

知识签名，=：非交互式的零知识证明。
Elgamal加密：

方案详情

参数设置

创建：

群管理员执行：【QR(n)是一个阶为$p’q’$的循环群】

加入：

用户执行：【区间 ]a,b[ 表示出去a,b以外的值】

注意：

由于p,q是保密的，只有群管理员知道，因此敌手不能自己伪造$A_i$,因为敌手求不出$e_i$在(p-1)(q-1)下的逆元$1/e_i$.

关于$u,v,w$的证明之中，前两个证明保证了$x_i$的计算过程是正确的. 第三个等式则证明了$C_1$的计算过程是正确的.

因为:令$u=α_i\tilde{x_i}+β_i \ mod\ 2^{λ_2}\ ;则 C_2/a^{2^{λ_1}}=g^u$;上述等式如果成立,显然$x_i$是以正确的方法计算得到的.

因为:

如果$C_1$是正确计算的,即 $C_1=g^{\tilde{x_i}}h^{\tilde{r}}$ ; $C_1^{α_i}g^{β_i}=g^{α_i\tilde{x_i}+β_i}h^{\tilde{r}α_i}$

由于$x_i=2^{λ_1}+u$;而$α_i\tilde{x_i}+β_i=v*2^{λ_2}+u$(其中v是一个整数)

所以 $ C_1^{α_i} g^{β_i} = g^{α_i \tilde{x_i} + β_i} h^{\tilde{r} α_i } = g^{ v\cdot 2^{λ_2} + u}\cdot h^{\tilde{r}α_i} = g^u\cdot (g^{2^{λ_2}})^vh^{\tilde{r}α_i}$

令 $w={\tilde{r}α_i}$则有:$C_1^{α_i}g^{β_i}=g^u(g^{2^{λ_2}})^vh^w$

如果上述$C_1$不是正确计算的,那么就无法证明上述的等式成立.

综上所述,如果上述给出的知识签名都是正确的，那么$x_i$的计算就是按照协议进行的。

我的疑问:

这里Join’阶段给出的群成员证书是由随机数构造而成的,如果用户自己选择一堆随机数按照上述格式伪造一个证书,岂不是可以伪造组成员进行签名.

签名：群成员执行：

注意：

这里$(T_1,T_2)$相当于对$A_i$做ElGamal加密，打开就是进行ElGamal解密。
这里的$(d_1,d_2,d_3,d_4)$和对应的$(s_1,s_2,s_3,s_4)$相当于知识签名。

验签：

打开：

群管理员执行：

ElGamal算法解密得到身份信息。用知识签名证明自己确实是群管理员GM，即我知道群私钥x，满足$x=log_gy=log_{T_2}(T_1/A_i\ mod\ n)$【防止其它人假装自己是GM，因为没有群私钥的人无法打开签名，获取签名者的身份】

参考文献

原论文:

A Practical and Provably SecureCoalition-Resistant Group Signature Scheme

BBS群签名算法

预备知识

线性加密(LE):

决策线性问题(DLP)产生了线性加密(LE)方案,它是ElGamal加密的自然扩展。与ElGamal加密不同，线性加密即使在存在ddh决定算法的组中也是安全的。在此方案中，用户的公钥是一个三组生成器$u, v, h∈G_1$;她的私钥是指数$x, y∈Z_p$，使得$u^x = v^y = h$。要对消息$M∈G_1$进行加密:
- 随机选择$a, b∈Zp$, 并计算输出三元组 $(u^a, v^b, M·h^{a+b})$。
- 为从加密$(T_1, T_2, T_3)$中恢复消息M，用户计算$M=T_3/(T_1^x·T_2^y)$。
通过对ElGamal安全性证明的自然扩展，假设Decision-LA成立，LE在语义上是安全的，不会受到选择明文攻击.

方案详情：

方案思路总览：

GM首先生成群签名中需要用到的参数，其中包括一个秘密参数$\gamma$，这个参数用来为群成员颁发证书。
当用户想要加入一个群组的时候，GM用$\gamma$为其生成一个群成员证书$(A_i,x_i)$
用户进行签名的时候，证明自己知道群成员证书【】，并用GM的公钥使用用LE加密将自己的身份加密【GM可用私钥解密】

正确性证明

验签过程需要验证下面五个等式

分别对其正确性进行证明如下：

关于方案的说明：

$π_i$表示的是一个非交互式的零知识证明，他的具体说明。原论文中有，见参考文献

这里BBS签名实际上就是一个零知识证明，证明签名者拥有$(A,x)$满足$A^{γ+x}=g_1$

也即是证明签名者拥有$(A,x)$满足$e(A,wg_1^x)=e(g_1,g_2)$

在不知道$\gamma$的情况下，伪造$(A,x)$满足$A=g_1^{1/{r+x}}$在计算上是不可行的。故，验证了上述零知识证明就相当验证了签名者拥有群成员证书。

这里的${R_1,R_2,R_3,R_4,R_5,}$以及${S_α,S_β,S_x,S_{δ_1},S_{δ_2}}$的计算过程实际上就是将构造的Sigma协议经过Fait-Shamir启发式得到的非交互式零知识证明。

这里${R_1,R_2}$证明了签名者知道${T_1,T_2}$中的$\alpha,\beta$；

而${R_4,R_5}$保证了${\delta_1,\delta_2}$是按照正确的方式计算出来的；

它们与$R_3$配合证明了存在$(A,x)$满足$A^{r+x}=g_1$

参考文献 BBS签名原论文：

《Short Group Signatures》

BBS签名的Go语言实现：

https://blog.csdn.net/Gassuih/article/details/117417328

CL签名方案

三个版本

作者在论文中循序渐进的提出CL签名方案，前两个方案是为第三个方案做铺垫的。这里第一个版本和第二个版本是第三个版本的特例

第一个版本的CL签名:【记作CL01】

参数生成:
- 通过安全参数生成公共参数:$Params={q,G_1,G_2,e,g_1,g_2,e}$
- 其中$G_1=<g_1>,G_2=<g_2>$是阶为 q 的,循环群, $e:G_1×G_1→G_2$双线性映射.
密钥生成:
- 选择$x∈_RZ_q^* \ ;\ y∈_RZ_q^* $计算$X=g_1^x\ ;\ Y=g_1^y$ ; 则私钥为$(x,y)$公钥为$(X,Y)$
签名:
- 对于消息m , 签名者执行以下步骤对消息进行签名.
- 选择$a∈_RG$ ; 计算$\sigma=(a,a^y,a^{x+mxy})$
验签:
- 给定消息 m 的签名 σ 和签名者的公钥,对签名进行验证,如果签名正确,返回Yes,否则返回NO
- 检验: $\begin{align} e(a,Y)\overset{?}{=}e(g_1,b) \ \ \ \ ;\ \ \ e(X,a)e(X,b)^m\overset{?}{=}e(g_1,c) \end{align}$ 都成立,返回yes
说明:
- 事实上,签名者不需要知道消息m也能对消息m进行签名. 例如: V给签名者S一个$M=g^m$; 则签名者S可以通过下面的式子计算签名: $\sigma=(a,a^y,a^xM^{rxy})$
- 容易看出,上述方式计算出的签名和正常计算得到的签名是完全一样的,区别在于用上述方法生成签名不需要知道消息m. 类似于盲签名.
- 在构造群签名时,为了加入一个组，一个新成员将选择一个秘密m，例如向GM提供$g^m$，证明对m的了解，并获得成员证书(a, b, c)。如果用户使用相同的秘密m成为多个组的成员，不同组的组管理员可以发现他们正在与同一个用户交谈。当两个组管理器使用相同的生成元g时,该用户在两个群中的证书完全相同,这很容易看出. 但是，即使一个GM使用生成元g，而另一个GM使用生成元h，这也是正确的: 因为在双线性配对的组中，决策的Diffie-Hellman问题很容易:

     - 对于用户给出的$g^m$和$h^m$两个组管理员通过比较$e(g^m,h) = e(g,h)^m = e(g,h^m)$可以得出用户为同一个人.

第二个签名:【记作CL02】

说明:

事实上,签名者不需要知道消息m也能对消息m进行签名. 例如: V给签名者S一个$M=g^mZ^r$; 则签名者S可以通过下面的式子计算签名: $\sigma=(a,A=a^z,b=a^y,B=A^y,c=a^xM^{αxy})$
容易看出,上述方式计算出的签名和正常计算得到的签名是完全一样的,区别在于用上述方法生成签名不需要知道消息m. 类似于盲签名.
在这种签名中,敌手在不知道消息m的情况下,可以直接向喻言机请求M的签名,从而伪造签名.,尽管他不知道如何用g和Z去表示M. 为了防止这种预测,可以使用一个零知识证明向签名方证明自己知道如何用g和Z去表示M也就是知道$M=g^mZ^r$中的m和r .

第三个签名:【记作CL03】

说明: 上面两个签名都是这一个签名的特殊形式, 该签名需要说明的地方与上一个签名类似,这里不再赘述. 唯一的区别是,这里给出的零知识证明不同.

注意:

CL组签名方案【记作CL04】

方案思路总览：

GM首先生成签名需要用到的各种参数；

成员在加入组时从组管理器获得关于成员公钥【P】的证书【a,b,c】

成员想要代表组签名时，她①用GM的公钥【$PK_R$】加密她的成员资格公钥【P】，然后②签名者证明她拥有加密的成员资格公钥上的证书【a,b,c】，并且③用户知道它对应的私钥【k】。

Join阶段：

用户选择一个私钥 k ,计算成员公钥 P 并将其向=发给 GM 进行注册，以申请加入群组。GM用自己的私钥对秘密值 P 进行签名得到$(a,b,c)$发给用户，用户将该签名作为群成员证书。

签名阶段：

隐藏的$(c_1,c_2,c_3,c_4)$【①用GM的公钥【$PK_R$】加密她的成员资格公钥【P】】

使用ElGamal加密的方式对群成员的身份进行加密得到$(c_1,c_2,c_3)$，

使用$c_4$生成$(c_1,c_2,c_3)$的承诺，保证$(c_1,c_2,c_3)$的正确性。

盲化的群成员证书$(a’,b’,c’)$【②签名者证明她拥有加密的成员资格公钥上的证书【a,b,c】】

用户使用随机数对自己的证书$(a,b,c)$进行盲化得到$(a’,b’,c’)$，防止暴露自己的证书

这里$c’$的产生方式中多了一个随机数 r ,

零知识证明$Σ$中，证明了以下事情：

其中$c_3=y_1^ug^k\ \ \ (g=e(P,g_1))$的证明，证明了【③用户知道它对应的私钥【k】】

ElGamal加密中使用的随机数是用户自己选的。

方案A【CL01】的验签需判断两个双线性映射，零知识证明中包含了一个双线性映射的判断。

方案详情:

注意:

这里$\mathcal{P}$是组成员的身份,而$(C_1,C_3)$实际上是用ElGamal加密算法对$\mathcal{P}c_2^{x_2}$进行了加密,如下:$(C_1,C_3)=(g_2^u,\mathcal{P}y_1^u) =(g_2^u,\mathcal{P}(g_2^{x_1}h^{x_2})^u) =(g_2^u,\mathcal{P}(g_2^{x_1})^u(h^u)^{x_2})) =(g_2^u,\mathcal{P}c_2^{x_2}(g_2^{x_1})^u)$

由于GM知道群私钥$(x_1,x_2)$,因此可以解密得到群成员的身份$\mathcal{P}$

参考文献 CL原论文：

《Signature Schemes and Anonymous Credentials from Bilinear Maps》

参考地址：

基于PS签名的群签名方案

可撤销的动态群签名

该群签名方案根据PS签名和ELGamal签名组合设计而成，具有签名短，计算开销小，可撤销群成员等优点。但是群成员的撤销时静态的撤销。

静态撤销是指，每次撤销之后需要重新生成群内的公共信息

动态撤销是指，撤销群成员不需要重新生成群内的公共信息

PS签名类似于CL签名中提出的第一个签名。

预备知识：

签名方案如下：

说明：

Issue阶段中，GM将用户的私钥 usk 作为PS签名中的消息 m 进行签名，得到$(A,B)=(\sigma_1,\sigma_2)$作为改用户加入群时GM为其颁发的群成员证书。【GM为用户的 usk 颁发了证书】

Sign 阶段中，作者提出的方案主要证明了两件事

① 证明【自己拥有群成员证书】、具体过程中对自己的群成员证书进行了随机化，以达到匿名的效果。

$T_0,T_1$使用随机数对证书$(A,B)$进行了随机化，保证证书不会暴露。

$T_2$保证了用户确实知道群证书中的私钥，从而证明了自己确实是群成员。

② 证明【ElGaml加密的公钥upk 所对应的私钥usk】正是【GM颁发过证书中的私钥usk】。

$R_0,R_1,R_2$作为零知识证明，证明了ElGamal加密的公钥确实是群成员证书中的私钥对应的公钥，并且证明了作者知道ElGamal加密中使用的随机数。

Verify阶段中，只需要验证上面的零知识证明即可。

具体方案：

群成员的撤销操作：

可批量验证的群签名

预备知识，

PS签名。【见二、1.1节】

具体方案：

说明：

实际上，打开的过程就是ElGamal的解密过程。

首先根据ElGamal加密算法解密得到$\hat{f}$,

然后计算计算出$\tau=e(g,\hat{f})$，

根据 τ 即可在注册表中查找到签名信息$reg_i$

打开完成后，Opener生成一个打开的证明。任何人都能根据这个证明验证打开的合法性。

优缺点：

优点：

本文提出的方案中，签名和验证签名花费的时间很少，

本签名方案的签名大小很小，

本签名方案实现了CCA匿名性，并且支持批量验证

缺点

但是加入群组花费的时间很多。

打开签名的时间随群成员数量的增涨呈线性增长。

总结：

因此适用于群组成员流动性不大的场景之中。在这种场景可以最大化的利用本签名方案的优势。

思考:

如果将ElGamal加密放在签名中产生，这样打开签名的时间复杂度可以降低到$O(1)$

用数字签名对 τ 进行签名的意义不大，不如直接将 f 存储在$reg_i$之中。

【但是这样就不能实现Judge功能了】

基于ECDSA的群签名方案、

参考文献：

https://www.hanspub.org/journal/PaperInformation.aspx?paperID=43012&btwaf=22311340

← 环签名

数据库原理 →