Created: <2020-11-12 Thu>
Last updated: <2020-12-06 Sun>
Shoup's RSA Threshold Signature
1. Threshold Signature 简介
(t,n) 门限签名（Threshold Signature）是指由 n 个成员组成一个签名群体，该群体共同有一对公钥和私钥，群体内大于等于 t 个合法、诚实的成员组合可以代表群体使用该群的私钥进行签名，任何人可利用该群体的公钥进行签名验证。这里 t 是门限值，群体中任何 t−1 个或更少的成员不能代表该群体进行签名，同时任何成员不能假冒其他成员进行签名。
1.1. Multi-Signature VS. Threshold Signature
多重签名（Multi-Signature）和门限签名（Threshold Signature）实现的目标差不多。不过， 多重签名一般是在“应用层”实现的，比如应用层编写代码，只有正确验证 t 个签名后才能执行某个动作；而门限签名则工作在“密码学算法层面”上，而且群体私钥在任何时候都不会完整地出现在任何一个参与方中。
2. Shoup's RSA Threshold Signature
Victor Shoup 于 1999 年在论文 Practical Threshold Signatures 中提出了一种 RSA 门限签名方案。
2.1. RSA 加解密和签名算法回顾
RSA 算法生成公钥和私钥的方法如下：
-
选择两个随机大素数 p 和 q （ p 和 q 是保密的，生成完公钥和私钥后就销毁）
-
计算大素数 p 和 q 的乘积 n=p×q （ n 是公开的）
-
计算 z=(p−1)×(q−1) （ z 是保密的，生成完公钥和私钥后就销毁）
-
随机选择整数 e ，满足 gcd(e,z)=1 ，即 e,z 互素（ e 是公开的）。
-
计算 d ，满足 d×e=1(modz) （ d 是保密的）
完成上面步骤后， (e,n) 就是公钥，而 (d,n) 是私钥。
RSA 算法的加密及解密过程如下：
-
假设明文为 P ，则其对应的密文 C 的计算方法（使用公钥进行加密的过程）为： C=Pe(modn)
-
假设密文为 C ，则其对应的明文 P 的计算方法（使用私钥进行解密的过程）为： P=Cd(modn)
上面介绍的是 RSA 加解密算法。RSA 如何用于签名呢？ 使用私钥对消息摘要进行 RSA 加密操作的过程就是“RSA 签名过程”。 私钥怎么可以用来加密呢（前面介绍过的都是用别人公钥进行加密，用自己私钥进行解密）？RSA 算法的加密操作步骤和解密操作步骤是一样的（只是使用的密钥不同），所以你不用关心到底叫“加密”还是“解密”，只需关心用“公钥”还是“私钥”处理数据。正常的加密解密过程是“先使用公钥操作数据，再使用私钥操作数据”（即 D(E(P))=P ）。RSA 算法还有一个特性就是“先使用私钥操作数据，再使用公钥操作数据”也可以得到原始数据（ E(D(P))=P ），用 RSA 进行数字签名正是利用了 RSA 的这个特性。
设 x 是消息摘要，则签名 y=xd(modn) 就是 x 的签名数据，而验证签名就是检查 x=ye(modn) 是否成立。
2.2. Shoup 的 RSA 门限签名方案
下面不给出证明过程（请参考原始论文），直接描述一下 Shoup 的 RSA 门限签名方案。
2.2.1. 系统初始化
系统中有 l 个参与者，编号分别为 1,2,⋯,l ，而门限值记为 k ，也就是这个门限签名可表示为 (k,l) 。为了和 Shoup 原始论文中的符号一致，这里没有采用本文开头使用的 (t,n) 记号。
选择两个素数 p 和 q ，设 p=2p′+1,q=2q′+1 ，其中 p′,q′ 也都是素数。RSA 模 n=pq ，令 m=p′q′ ，并选择公共一个素数指数 e,e>l 。 RSA 公钥就是 (e,n) 。
选择一个 d ，它要满足 de=1(modm) ，这个 d 就是要分享给 l 个参与者的秘密值。
下面采用 Shamir's Secret Sharing 方法来把 d 分享给 l 个参与者：随机取 k−1 个数 a1,a2,⋯,ak−1 ，构造下面多项式： f(X)=d+a1X+a2X2+⋯+ak−1Xk−1 记 si=f(i)(modm) 其中 i=1,2⋯,l ，这个 si 就是每个参与者得到的“部分秘密”，参与者将使用它生成部分签名。
2.2.2. 生成部分签名
定义 Δ=l! ，消息 M 的摘要为 x=Hash(M) ，对于参与者 i,i=1,2,⋯,l 计算： xi=x2⋅Δ⋅si 这个 xi 就是参与者 i 的部分签名。
2.2.3. 组合部分签名
对于任意大小为 k 的集合 S ， S 是 {1,2,⋯,l} 的子集，定义： λi,jS=Δ⋅∏j′∈S∖ji−j′j−j′ 这个式子是从标准拉格朗日插值公式系数而来，只是多乘以了一个常量 Δ 。
假设我们收集了 k 个成员的“部分签名”，把成员组成的集合记为 S={i1,⋯,ik}⊂{1,2,⋯,l} ，记 ij⊂S,j=1,⋯,k ，用下面方式组合部分签名： w=xi12⋅λ0,i1Sxi22⋅λ0,i2S⋯xij2⋅λ0,ijS⋯xik2⋅λ0,ikS
用下面方式计算最终的组合签名： y=waxb 其中 a 和 b 都是整数，它们由 (4⋅Δ2)⋅a+e⋅b=1 计算而来，由于 e 是素数， 4⋅Δ2 和 e 互素，由 4⋅Δ2 和 e 上的扩展欧几里德算法可以得到满足要求的 a 和 b 。
2.2.4. 签名验证
如果 ye(modn)=x 成立，则通过签名验证，这和常规的 RSA 签名验证逻辑是一样的。
3. 不需要 Trusted Dealer 的 RSA 门限签名方案
前面介绍的 Shoup 的 RSA 门限签名方案在系统初始化阶段需要一个 Trusted Dealer 来分配秘密。论文 Practical Threshold RSA Signatures without a Trusted Dealer, by Ivan Damgård and Maciej Koprowski 给出了不需要 Trusted Dealer 的 RSA 门限签名方案，这里不详细介绍。
4. 参考
Shamir's Secret Sharing
Practical Threshold Signatures
