两个基于RSA的特殊数字签名方案

作者：蒋俊锋

来源：《电脑知识与技术》2008年第35期

        摘要：介绍了数字签名背景、签名的形式化描述以及两个特殊的数字签名方案。对如何用RSA实现盲签名和多重数字签名方案进行了研究，分析了两种具体方案实现的安全性。最后总结了这两种特殊数字签名实现过程中算法设计的优劣。

        关键词：数字签名；RSA；盲签名；多重签名

        中图分类号：TP316文献标识码：A文章编号：1009-3044(2008)35-2095-02

        Two RSA-based Special Digital Signature Schemes

        JIANG Jun-feng

        (Engineering of Information Hohai University,Changzhou 213022,China)

        Abstract: The background, the formal definition and some special form of digital signature are firstly introduced.The research of how to realize the blind signature and the multisignature with RSA signature scheme are carried out secondly. The virtue and shortcoming of the two realized special digital signature schemes and the research to be continued are lastly put forward.

        Key words: digital signature;RSA;blind signature;multisignature

        1 引言

        1.1 背景

        签名一直被作为一种证明签名者身份的标识,它表明签名人看过乃至同意文件的内容。签名人作出签名后将无法否认，并要为自己的签名负责。随着密码学的发展，数字签名(digital signature)克服了手写签名的缺点。数字签名[1]具有签名可信性、不可抵赖性、不可复制性、不可伪造性和数据完整性的优点。2004年8月我国正式颁布了《中华人民共和国电子签名法》，确立了数字签名在我国的法律效力和地位。

        1.2 数字签名的形式化定义

        签名[2]是一个满足一下两个条件的概率多项式时间算法的三元组(G,S,V)。

        1) 当输入1n时，算法G(调用密钥生成器)输出一对比特串。

        2) 对G(1n)值域中的每一对(s,v),以及每个α∈{0,1}*,算法S(签名)和V(验证)满足：Pr[V(v, α,S(s, α)=1)]=1

        这里的概率定义在算法S和V的所有内部掷币值上的。S(s, α)称为签名密钥对文档α产生的签名，当V(v, α,β)=1时称β是α对应与验证密钥v的有效签名。

        数字签名主要基于公钥算法。其中RSA基于大整数难以分解为两个素数的乘积。特点是算法简单和安全。RSA是目前使用比较普遍的数字签名算法。ISO/IEC 9796和ANSI X9.30-199X已将RSA作为建议数字签字标准算法。在制定的标准中，PKCS#1是一种采用杂凑算法(如MD2或MD5等)和RSA相结合的公钥密码标准。

        1.3 几种特殊的数字签名

        人们根据不同的应用背景和签名目的，研究出了几种特殊的签名方案：盲签名方案，多重签名方案，代理签名方案,群签名方案等等。

        盲签名方案(Blind-signature Scheme)是由D.Chaum[3]与1982年最先提出的。某人对一个文件签字，但又不让他知道文件内容，这点使盲签名应用在许多领域，比如电子投票系统，电子拍卖系统和电子现金系统。

        一般的数字签名是由单个用户完成的，而由多人参与对同一文件进行的签名方案，称为多重签名方案(Multisignature Scheme)。多重签名方案是D. Chaum 和E.van Heyst[4]于1991 年提出的。根据签名过程的不同，多重数字签名可分为有序多重数字签名方案和广播多重数字签名方案。

        2 方案实现

        2.1 盲签名方案

        下面介绍用RSA实现的盲签名方案。整个过程分为：密钥建立与管理、消息盲化、签名、消息解盲和签名验证。

        2.1.1 盲签名过程

        1) 密钥的建立与管理

        设有参与盲签名的人分别是A和B，A知道消息M,让B进行盲签名。首先建立RSA密钥，任意选取两个大素数p及q ,计算n = pq。φ(n)为n的欧拉函数。任意选择一个整数e, 使得(e,φ(n))=1,计算d (1

        2) 消息盲化

        A进行对消息M盲化:选用盲因子k,1

        3) 签名过程：A把盲化过的消息t发送给B，B对t进行RSA签名,计算S(t) = td = (Mke)d (mod n)

        4) 消息解盲: B将签名S(t)传送给A。A通过下面的运算获得B对消息M的直接RSA签名。

        Sig = S(t)/k≡ td/k≡ Md (mod n)

        对上步等式的证明：td≡(Mke)d≡Mdk(mod n)⇒td/k≡Mdk/k≡Md(mod n)。

        5) 签名验证：A利用B公布的(e,n)对消息进行验证。

        M'=Sige(mod n)

        若M'=M，则验证通过，否则验证失败。

        2.1.2 盲签名方案的安全性分析

        匿名性和不可伪造性：B在获取了t=Mke (mod n)，B不知道盲因子k，所以B在多项式时间内无法推出M的值。这种盲化方法具有匿名性。B签名后如果被攻击者截取，因为攻击者不知道B的私钥d，所以也无法伪造签名Sig。

        2.2 多重签名方案

        下面介绍基于RSA的有序多重签名方案。整个过程分为：密钥建立与管理、多重签名、部分签名多重验证和签名验证。

        2.2.1 多重签名过程

        1)用户密钥建立和管理

        设有参与多重签名的人分别是U1，U2,…,Un。他们都使用RSA密码进行签名。首先建立RSA密钥，任意选取两个大素数pi及qi ,计算ni = piqi。任意选择一个整数ei ,使得(ei,φ(ni))=1,计算di (1

        2) 有序多重签名

        签名者U1 对M的散列值进行签名,计算m=H (M), S1≡(m)d1(mod n1)。U1把签名结果S1传递给下一个签名者U2 , U2首先验证签名S1的正确性,验证如下:

        计算m'(S1)e1(mod n1)以及m =H (M)，如果m′ =m说明签名正确，否则，签名不正确。

        当验证部分签名通过后, U2 签名如下:S2≡(S1)d1(mod n2)然后U2把S2传递给U3,U3首先验证签名S2的正确性。同样首先计算m'≡[(S2)e2(mod n2)]e1(mod n1), 如果m′ =m说明签名正确,否则,签名不正确。

        依次类推，当签名者Ui(1≤i

        3) 验证多重签名：

        计算m'≡(((Sn)en(mod nn))en-1(mod nn-1)…)e1(mod n1)和m=H (M )

        如果m′=m，说明签名正确,否则签名不正确。

        2.2.2 多重签名方案的安全性分析

        1) 签名可信性：对于最终的签名Sn，其他人接收到最终签名的过程中，攻击者有可能窃取并对其进行篡改。但是其他人都可以利用公布的(en,nn)来验证签名Sn的正确性；对于部分签名Si(1≤i

        2) 不可伪造性：对于最终的签名Sn，攻击者截取进行冒充签名是不可能的，因为攻击者不知道dn。对于部分签名Si(1≤i

        3) 防止收到已知签名攻击(know-signature attack)：文献[1]中提到，克服已知签名攻击的有效方法是选择安全Hash函数对签名的消息做Hash变换，然后再对变换后的消息摘要进行签名。因此在多重签名方案中，在签名之前现对消息M做了Hash变换，所以这个方案可以有效防止收到已知签名攻击。

        3 小结 

        文章使用RSA分别实现了盲签名和有序多重签名。通过安全性分析，盲签名方案具有匿名性和不可伪造性。在实现盲签名时没有使用哈希函数，对于短消息适用并且签名速度快。但是对于长消息签名速度比较慢，RSA是幂模运算，当底数M很大时，运算量很大。下面要做的工作是考虑如何把签名和摘要结合起来。

        多重签名具有可信性、不可伪造性和防止收到已知签名攻击。由于多重签名中产生的密钥对较多，密钥的产生、发放和管理等操作比较繁琐。应该用数字证书来管理多重签名每个用户的公钥和密钥。

        参考文献：

        [1] 徐茂智,游林.信息安全与密码学[M].北京:清华大学出版社,2007.

        [2] Goldreich O.密码学基础[M].2卷.北京:人民邮电出版社,2005.

        [3] Chaum D.Blind signature for untraceable payments[A].Proc.Crypto'82[C].New York:Plenum Press,1983:199-203.

        [4] Harn I,Keisler T.New scheme for Digital Multisignature[J].Electronic Letters,19,25(15):1002-1003.