陕西理工学院毕业论文（设计）
receiverUR. The receiver computes
hk?H(Ck), Tk*?Dkefkhkmn(modn), mk*?H(M,Tk*).
UR verifies the the signature validity by comparing mk*with mk.The final multisignature
is (Tk,mk,Dk,fk).
2 Cryptanalysis of Zhang et a.l’s Sequential Multisignature Scheme
When the receiver UR uses the signature (Tk,mk,Dk,fk), he should convince the third party that it was correctly signed by the k signers. The third party computes hk?H(Ck) and Tk*?Dkefkhkmn(modn), and verifies the validity of the multisignature by judging
whether equation mk*?H(M,Tk* ）holds or not.
The signature is verified by using only the Uk’s public key instead of the public key of k signers.Hence, the third party can not distinguish whether the signature is signed by k signers or only by the kth signer. If the signer wants to convince the third party, he must use all signers’public key to verify the multisignature. Although
fk?h1m1h2m2...hkmkcan be calculated in public to show that the multisignature is signed by
the k signers, but the verifier has to know all the k partial signatures, which violates the definition of sequential multisignature. The computation amount of verification increases linearly with the number of signers. Therefore, we propose an improved scheme here in after to solve this problem based on the schemes in R efs. [2, 5, 6, 7]. 3 Improved Sequential Multisignature Scheme Based on RSA 3. 1 Initialization phase
eSigner U1 selects a random number rcomputes T1?rsends T1 1(1?r1?n), 1(modn),and
to theU2. Similarly, every signer Ui(1?i?k)selects a random number ri(1?ri?n), computes Ti?Ti?1rieand sends Tito signer Ui?1. At last, Uk computes Tk?Tk?1rk2(modn), and sends Tk to receiver UR.Then, UR computes m=H (M, Tk)and publishes m.
3. 2 Generating partial signature of sequential multisignature
Step 1 Signer U1 uses the random number r1 and computes D1?r1s1(modn). Because U1 has sent T1 to the signer U2 in initialization phase, he only sends
mD1 to U2 now.
U2 computes h1?H(C1) and T1*?D1eh1m(modn),and verifies (T1,D1) by
第32页 共41页
陕西理工学院毕业论文（设计）
comparing T1* with T1. The partial signature of U1 is right if T1*equals T1. Otherwise, it is wrong, and U2 requires U1 to resign until the partial signature satisfies the verification equation.
Step 2 Assuming that the (i-1)th signature is right (1 msignature as Di?Di?1rsii(modn). Then Ui sends the partial signature (Ti,Di)to the signer Ui?1. Ui?1 computes h1?H(C1), h2?H(C2),...,hi?H(Ci),and Ti*?Die(h1h2...hi)m(modn). Ui?1 verifies the validity of (Ti,Di) by comparing Ti* with Ti. Step 3 Signer Ui?1 creates the next partial signature. The above process is repeated untill signer Uk creates the last partial signature Dk and sends it to the multisignature receiver UR. UR computes h1?H(C1), h2?H(C2),...,hk?H(Ck), and Tk*?Dke(h1h2...hi)m(modn). UR verifies the validity of (Tk,Dk) by comparing Tk*with Tk. The final multisignature signed by k signers is (Tk,Dk,m). 3. 3 Testifying validity Anyone can verify the validity of the multisignature by computing Tk*and comparingTk*with Tk. If Tk* equals Tk, the multisignature signed by the k signers is right. Proof From the sequential signature process, it is known that ?k?eeTk?Tk?1rk?TT12...Tk?1?(r1r2...rk)???rj?(modn) ?j?1?eDk?Dk?1rksk?(rs)(r2s2)...(rksk)??rjsjm(modn) mm11mmj?1kWhen the receiver or the third party verifies the multisignature, he computes ?k??k?kem?k?*emmmTk?Dk(h1h2...hk)???rjsj?(h1h2...hk)???rj?(?sj)??hj?(modn) ?j?1??j?1?j?1?j?1?Because sj?hjThen ?deem(modn),we have sje?(hj?d)e?(hjed)?1?hj?1(modn)。 第33页 共41页 陕西理工学院毕业论文（设计） ?k??k?* Tk???rj???hj??j?1??j?1?e?m?k??k???hj????rj?(modn) ?j?1??j?1?meThe multisignature is right if and only if Tk* equals Tk. 4 Security Analysis Zhang et a.l[2] analyzed the security of their original scheme in detail Here, we only analyze the security related to the modified part. (1) The verifier knows the signer of the multisignature. In the improved scheme, the certificate of each signer Ui has been published, and the verifier must use h1,h2,?, hi to compute Ti* for verification, so he can distinguish whether the signature is signed by k signers or only by the kth signer. (2) The publication of Ti in initialization phase is secure. In Zhang et a.l’s original scheme, Ti is translated sequentially between signers. Here,Tiis computed in initialization phase. Even an attacker knows Ti and can compute the value of rie, but he can not get ri from Ti. (3) The multisignature can resist forgery attack. If the attacker wants to forge the partial signature of Ui, he must forge a valid (T'i,D'i) satisfying the verification formula. However, Ti is published in initialization phase and can not be forged, so he must make a D'i that satisfies the formula Ti*?(D'i)e(h1h2...hi)m(modn). That is a difficult problem based on factorization of a big integer. (4) All signers must follow the specified order .A next signer Ui (i=2,?,k)verifies the partial signature through the value of Ti?1,which is generated in initialization phase. Any signature disorder of individual signers will results in the process interruption of Creating multisignature. For example, if the signer Uicreated the partial signature Ti before he receives the signature Ti?1,then Ti*≠Ti will occur to the subsequent verification phase and the process of creating the multisignature stops. 5 Performance Analysis Define symbols Tm, Teand Th as the time costs of modular multiplication, modular 第34页 共41页 陕西理工学院毕业论文（设计） exponentiation and hash operation, respectively. In our scheme, the average computation time for verifying the previous partial signature is 2Te?of h1 till hi and their product which costs n(Tm?Th)2, but the computation n(Tm?Th)2, can be done by pre-calculation; the computation time for partial signature is 2Te?3Tm.The computation costs for both signature and verification are less than those in Zhang eta.l’s scheme; therefore our scheme is more efficient. 6 Conclusion We pointed out a defect of Zhang eta.l’s sequential multisignature scheme based on RSA; that is, a verifier can not distinguish whether the signature is signed by a group of signers or only by the last signer of the group. To overcome the defect we proposed an improved scheme, in which the verifier can know the signature is generated by which signers. The proposed scheme does not increase the amount of computation and communication; its security is based on the difficulty of factoring a large integer. Performance analysis and security analysis show that the proposed scheme is more secure and efficient than the original scheme. 中文翻译 密码分析和基于RSA多重数字签名方案的改进 (粟 栗 , 崔国华 , 陈 晶 , 袁 隽) 中国华中科技大学,计算机科学与技术学院,武汉430074 摘要: 张等人提出了基于RSA序贯多重签名方案. 该方案具有低运算、低通信费用优点等等. 然而，我们发现一个问题,在他们的方案中核查不能区分多重签名签署是由签名组中所有的签名者所签署还是由最后一位签名者签署.因此,由最后一位签名者所做的单一签署可以作为整组签署成员所做的多重签署。本文提出一个改进方案，可以克服这个缺陷。在新的方案中，所有签名者的身份信息被添加在这个多重签署中，并且会在核查阶段显示，以确保核查时能知道签署是由哪些签名者产生的。性能分析表明，这个新的方案在签署和核查阶段需要的计算都比原来的方案少。此外，每一部分的签名是基于签名者的身份证书，这使得该计划更安全。 引言 多重签名是由一组签名者所产生的联合签名。该集团的安全政策，需要多重要签署的所有组成员的知识的多重私人钥匙。数字多重签署应该有几个基本属性：（1）多重签署是由多组成员用多个 第35页 共41页 陕西理工学院毕业论文（设计） 私钥的知识产生的；（2）多重签署在不知道每个签署者的公钥的情况下可以很容易的通过该组的公钥进行核查。（3）在没有所有组成员的合作下，计算产生该组签署的可行性。 2003年，张等人提出了一种基于RSA的序列多重签名方案。其中所有的签名使用一个共同的模量。该计划的优点是低的计算和通信费用，并能抵抗伪造和联军攻击。攻破这个系统的困难性相当于将一个大整数分解为两个大素数因子。 然而，我们对张等人加密方案进行分析，发现一个严重的问题。这个问题就是：一个多重签署可以由最后的签名者的公钥来进行核查，而不是多重签署组的公钥。结果使核查者不能区分签署是由一组签署者签署还是仅由最后一个签署者签署，这就违背了连续多重签署的基本属性【1，3】。因此，在这章中，我们提出一种改进的方案来克服这个缺陷，以使核查者能够确认签名是由谁产生的。性能和安全性分析表明，新的方案不仅保留了原来方案的优点，同时也符合了多重的定义，并且更加安全。 1. 张等人的连续多重签名方案的回顾 1.1 系统初始化 首先，信托中心选择两个大素数p和q，并且计算RSA算法的模n=pq。然后，信托中心选择一个随机数e作为公钥，它满足gcd(e,?(n))=1,这儿的gcd(·)是最大公约数函数， ?(n)=(p-1)(q-1)， and 1 Ci是公开的，且将要被签名的信息是M。 对每个签名者Ui，信托中心计算hi?H(Ci)和si?hi?d(modn)， 并且通过一个安全渠道发送那个证书(Ci,si)给每个签名者，这儿的H(·)是保密散列函数，这会产生一个固定长度的身份信息的凭证，是私钥签字。然后，相应的签字确认证书的有效性，在持有公式的情况下，通过公式，并保持作为密钥。 1．2 生成部分连续多重签名 作为新一代的准备部分签名，信托中心通过签名者的身份信息(C1,C2,...,Ck)发布签名的顺序。 步骤 1：签名者U1选择一个随机数r1(1?r1?n)并且计算T1?H(M,T1), 1?r1(modn), meD1?r1s1m1(modn), f1?1,这儿的T1是U1的委托事项；m1绑定那些委托事项，并且明文通过散 列函数；(D1, f1)就是m1的签名。 然后，签名者U1发送部分的签名(T1,m1,D1,f1)给签名者U2. 步骤2：通过类推，如果(i-1)次部分签字是正确的，tUi (2?i ii Ti?Ti?1ri(modn),mi?H(M,Ti),Di?Di?1rsii(modn),fi?fi?1hi(modn). emm第36页 共41页