2024-07-12 2024-07-12 2663 字 6 分钟

- 数字签名

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

环签名

环签名概述

环签名(ring signature)是一种数字签名方案，最初由Rivest等人提出，环签名可以看成一种简化的群签名, 环签名中只有环成员没有管理者, 不需要环成员间的合作。【在群签名中需要事先生成一个群，随后用户才能加入该群，从而代表该群进行签名】

环签名的定义

假定有 n 个用户，每一个用户拥有一个公钥和与之对应的私钥。环签名是一个能够实现签名者无条件匿名的签名方案，它主要由下述算法组成：

Gen：概率多项式时间(PPT)算法，输入安全参数 k 后输出公私钥对。这里假定Gen为每个用户产生一个公私钥对，并且不同用户的公私钥可能来自不同的公钥体制，如RSA或者DL。

Sign：一个PPT算法，在输入消息 m 和 n 个环成员的公钥 L={y1 , ⋯ , yn}以及其中一个成员的私钥 xs 后，对消息 m 产生一个签名 R，其中 R 中的某个参数根据一定的规则呈环状。

Verify：一个确定性算法，在输入(m,R)后，若 R 为m 的环签名则算法输出“True”，否则算法输出“False”。

环签名因为其签名隐含的某个参数按照一定的规则组成环状而得名。而在之后提出的许多方案中不要求签名的构成结构成环形，只要签名的形成满足自发性、匿名性和群特性，也称之为环签名。

环签名的性质：

正确性：如果按照正确的签名步骤对消息进行签名，并且在传播过程中签名没被篡改，那么环签名满足签名验证等式。

无条件匿名性：攻击者即使非法获取了所有可能签名者的私钥，他能确定出真正的签名者的概率不超过1/n这里n为所有可能签名者的个数。

不可伪造性：外部攻击在不知道任何成员私钥的情况下，即使能从一个产生环签名的随机预言者那里得到任何消息m的签名，他成功伪造一个合法签名的概率也是可以忽略的。

环签名与群签名的比较：

相同点：

都实现了匿名性。

在群签名中，签名者代表这个群进行签名，任何人都可以使用群公钥对这个签名进行验证。在验证过程中，验证者只知道签名者来自这个群，但是不知道签名者是群中的哪一个成员。

在环签名中，签名者代表这个环进行签名，任何人都可以对这个环签名进行验证，在验证过程中，验证者只知道签名者来自这个环，但是不知道签名者具体是环中的哪一个成员。

不同点：

匿名性不同：

群签名实现了有条件的隐私保护，群管理员可以从群签名中找出签名者的真实身份。

环签名是无条件的匿名性。没有任何人可以去除环签名的匿名性。

创建签名的难度方法不同：

用户想要代表某个群对某个消息进行签名，必须由群管理员完成群的【创建】，然后用户【加入】该群后才能进行。

环签名中，用户可以将自己的身份添加到他选择的任何其他用户集合中，并在这个集合上生成一个环签名，该签名只显示出签名者属于该集合，而不暴露其他信息。特别是，未签名的成员甚至可能完全不知道他们参与了这样的签名。 ○ 签名长度不同： ■ 群签名的长度很多都是固定的，与群成员的个数无关 ■ 环签名中，大多数的环签名方案中，签名的长度随环成员个数的增加而增加。

环签名方案

基于RSA的环签名方案【历史上第一个环签名方案】

假设环签名中有n个人，则一个真实用户的签名泄露自己身份的概率是$1 / n$，为了简单起见，下面令n = 5 来举例说明RSA环签名方案。假设有5个用户，分别为1,2,3,4,5，且用户3要对消息m进行签名，则：

密钥生成Gen

为五个用户分别生成RSA公私钥对【（$e_i,n_i$）,（$d_i,n_i$）】。（ i = 1,2,3,4,5 ）

签名Sign

签名需要用到一个对称加密算法，这里使用AES算法。环签名的计算过程如下：

为了简化上述过程，不妨设有一个操作$R_i(c_i)$定义为：$R_i(c_i)$=$c_{i+1}$，其中$x_i$为随机数。则RSA环签名计算过程如下：

$y_i=RSA_Enc_{pk_i}(x_i)=x_i^{e_i}\ mod \ n_i$

$z_{i+1}=c_i \oplus y_i $

$c_{i+1}=AES_Enc_{key}(z_{i+1})$

为了展示计算过程，上述操作表示为：$R_i(c_i)=c_{i+1}$ - - - - - 【$x_i,y_i,z_{i+1},c_{i+1}$】通过上述符号假设，上述的计算过程可以简化为：签名者【用户3】选择随机数$c_4$，然后依次计算： $$R_4(c_4)=c_5 —-【x_4, y_4, z_{5}, c_{5}】$$ $$R_5(c_5)=c_1 —-【x_5, y_5, z_{1}, c_{1}】$$ $$R_1(c_1)=c_2 —-【x_1, y_1, z_{2}, c_{2}】$$ $$R_2(c_2)=c_3 —-【x_2, y_2, z_{3}, c_{3}】$$ $$R_3(c_3)’=c_4’ —-【x_3’, y_3’, z_{4}’, c_{4}’】$$

分析

上面计算的$R_3(c_3)’$=【$x_3’, y_3’, z_{4}’, c_{4}’$】中，$c_4’$满足$c_4’=c_4$的概率可以忽略不计，因为上述等式成立的概率仅为为$1/2^{256}$（因为AES加密的输出是256比特）

为了使其相等，令$c_4‘=c_4$，反向计算出$z_4$, 然后异或计算出$y_3$，随后【用户3】可以使用自己的私钥（$d_3, n_3$）解密$y_3$得到$x_3$；

将$R_3(c_3)’=c_4’$—-【$x_3’, y_3’, z_{4}’, c_{4}’$】替换为$R_3(c_3)=c_4$—-【$x_3, y_3, z_{4}, c_{4}$】; 这样即可得到环签名$σ={(e_1, n_1), (e_2, n_2), (e_3, n_3), (e_4, n_4), (e_5, n_5), c_1, x_1, x_2, x_3, x_4, x_5}$。

上述签名者【用户3】通过将正向运算替换为反向运算，得到了一个$x_3$，从而得到了环签名 σ 。环签名的计算过程正好形成一个环，如下图：

Verify：

验证者计算： $$R_1(c_1)=c_2 —-【x_1, y_1, z_{2}, c_{2}】$$ $$R_2(c_2)=c_3 —-【x_2, y_2, z_{3}, c_{3}】$$ $$R_3(c_3)=c_4 —-【x_3, y_3, z_{4}, c_{4}】$$ $$R_4(c_4)=c_5 —-【x_4, y_4, z_{5}, c_{5}】$$ $$R_5(c_5)=c_1’ —-【x_5, y_5, z_{1}, c_{1}】$$ 检查 $c_1’=c_1$是否成立，如果成立，输出True ，否则输出 False 这里的解密的实质就是等式$R_5(R_4(R_3(R_2(R_1(c_1)))))=c_1$成立。

参考文献：