基于二次剩余构造的盲签名方案

Construction of Blind Signature Scheme Based on Quadratic Residue

摘要: 盲签名是在1982年基于对保护信息的私密性而提出的签名方案，在密码学中占据着重要的地位。本文以二次剩余和整数分解的困难性为理论基础，提出了一种新的盲签名方案。通过利用Hash函数以及盲因子让待签名信息盲化，使签名者不知所签名的具体信息，从而保护了用户信息。同时，还证明了该签名的盲性以及不可伪造性。

Abstract: Blind signature was proposed based on the privacy of protected information in 1982. It plays an important role in cryptography. Based on the difficulty of quadratic residue and integer decompo-sition, a new blind signature scheme is proposed in this paper. By using Hash function and blind factor to blind signature information, it makes the content of the information has not been seen by the signer, thus protecting the user’s information. Meanwhile, it is proved that the signature is blind and cannot be forged.

1. 引言

随着计算机科学技术的发展，电子商务、电子金融等系统得到了广泛的应用，数字签名的问题就显得更加突出、更加重要。1982年Chuam [1] 为实现不可跟踪的支付系统，也就是电子现金，首次提出了盲签名的概念。盲签名与普通签名相比有两个显著特点：第一，签名者不知道所签署的数据内容。第二，在签名被接收者泄漏后，签名者不能追踪签名内容 [2]。为了满足这样的条件，用户首先将待签名的数据进行盲变换，然后把变换后的盲数据发送给签名者，经过签名者签名后再发给用户。用户对签名进行去盲变换，得到的是签名者对原数据的盲签名。

盲签名可以有效地保护用户的隐私，因而被广泛的应用于需要保护个人隐私的地方。文献 [3] 提出了一个基于二次剩余的盲签名方案，但是没有给出它的不可伪造性。文献 [4] 提出了一种基于RSA体制的盲签名，但是计算效率较低。2011年，文献 [5] 提出一种基于Schnorr盲签名的向前安全盲签名方案。之后，文献 [6] 指出文献 [5] 不满足可验证性和不可伪造性，并对其进行改进。本文基于二次剩余提出了一个新的盲签名方案，并且对该方案进行分析，证明了它满足盲性和不可伪造性。

2. 基本定义与相关定理

二次同余式求解问题可以归结到讨论形如 $x^2\equiv a\left(\mathrm{mod}m\right)$ 的同余式，在密码学中应用很广泛，它是本文所构造的概率密码体制的数学理论基础之一。

设n是正整数集， $Z_n=\left\{x|0\le x<n,n\in N\right\}$ ， ${Z^{″}}_n=\left\{x|x\in Z_n,\left(x,n\right)=1\right\}$ 。

定义2.1 [7] ：若 $a\in {Z^{″}}_n$ ，且存在x满足二次同余式 $x^2\equiv a\mathrm{mod}n$ ，则称a为模n的二次同余，称x为模n下a的平方根，模n的所有二次同余的集合记为 $Q_n$ ；若 $a\in {Z^{″}}_n$ 且 $a\notin Q_n$ ，称a为模n非二次同余 ${\bar{Q}}_n$ 。

定义2.2：若 $n=p\cdot q$ ，其中p和q为两个互不相同的素数，并且满足 $p\equiv q\equiv 3\mathrm{mod}4$ ，则称n为Blum数。

定理2.1 [7] ： (欧拉定理)若 $\left(a,n\right)=1$ ，则 $a^{\varphi \left(n\right)}\equiv 1\mathrm{mod}n$ 。

定理2.2 [7] ：(欧拉判别条件)若 $\left(a,p\right)=1$ ，则a是模p的平方剩余的充分必要条件是 $a^{\frac{p-1}{2}}\equiv 1\left(\mathrm{mod}p\right)$ ；而a是模p的平方非剩余的充分必要条件是 $a^{\frac{p-1}{2}}\equiv -1\left(\mathrm{mod}p\right)$ 。

定理2.3 [8] ：设p和q为两个互不相同的素数， $n=p\cdot q$ ，则对任一整数 $a\in Z_n^{\ast }$ ，有 $a\in Q_n$ ，等价于 $a\in Q_p$ 且 $a\in Q_q$ 。

定理2.4 [8] ：p为素数且 $p\equiv 3\mathrm{mod}4$ ， $a\in Q_P$ ( $Q_p$ 为模p的所有二次同余的集合)，则 $x^2\equiv a\mathrm{mod}p$ 在模p下有且仅有两个平方根，分别为 $x\equiv \pm a^{\frac{p+1}{4}}\mathrm{mod}p$ 。

引理1 [8] ：设 $N=p\cdot q$ 为Blum数， $a\in Q_n$ ，则 $a^{\frac{\varphi \left(n\right)}{4}}\equiv 1\mathrm{mod}N$ 。

定理2.5 [8] ：设 $N=p\cdot q$ 为Blum数， $a\in Q_n$ ，则对于 $x^2\equiv a\mathrm{mod}N$ 有：

1) 在模N下有4个平方根。

2) 这4个平方根有且仅有一个属于 $Q_n$ ，且 $x\equiv a^{\frac{\varphi \left(N\right)+4}{8}}\mathrm{mod}N$ 。

定理2.6：设 $N=p\cdot q$ ，其中p和q为两个互不相同的奇素数，则分解N计算上等价于求模N的平方根。

3. 签名与验证过程

3.1. 参数生成阶段

Step1：签名者找出两个较大的素数p、q(不能公开)，使得 $p\equiv q\equiv 3\mathrm{mod}4$ ，同时需要计算Blum数 $N=p\cdot q$ ，将N作为验证密钥，将p、q作为签名密钥。

Step2：签名者选择一个结果为平方项的Hash函数：H： ${\left(0,1\right)}^{\ast }\to Z_N^{\ast }$ 。并计算 $d=\left(N-p-q+5\right)/8$ ，公开(N,H)，保密(d,p,q)。

Step3：对于明文信息 $M=\left(a_0,a_1,\cdots ,a_n\right)$ ，计算 $H\left(a_i\right),i=0,1,\cdots ,n$ ，再选择一个盲因子 $k\in Z_n^{\ast }$ ，计算 $M^{\prime }\equiv k^{2}H\left(a_i\right)\mathrm{mod}N$ ，得到 $M^{\prime }=\left({a^{\prime }}_0,{a^{\prime }}_1,\cdots ,{a^{\prime }}_n\right)$ 。

3.2. 签名过程

Step1：用户选取随机数b， $b\in Z$ ， $x_0\equiv b^2\mathrm{mod}N$ ，并把 $x_0$ 以及待签名信息 $M^{\prime }=\left({a^{\prime }}_0,{a^{\prime }}_1,\cdots ,{a^{\prime }}_n\right)$ 发送给签名者。

Step2：签名者收到用户所发送的信息后，根据d分别做如下计算：

$\begin{array}{l}{x}_1\equiv x_0^d\mathrm{mod}N\\ x_2\equiv x_1^d\mathrm{mod}N\\ ⋮\\ x_{n+1}\equiv x_{n+2}^d\mathrm{mod}N\end{array}$

得到序列 $A=\left(x_1,x_2,\cdots ,x_{n+1}\right)$ 。

Step3：根据待签名信息 $M^{\prime }=\left({a^{\prime }}_0,{a^{\prime }}_1,\cdots ,{a^{\prime }}_n\right)$ ，签名者分别计算： $y_0={a^{\prime }}_0\times x{}_1,y_1={a^{\prime }}_1\times x_2,\cdots ,y_n={a^{\prime }}_n\times x_{n+1}$ ，得到序列。

Step4：签名者得到 $Sign\left(M^{\prime }\right)\equiv Y^d\mathrm{mod}N$ ，并将 $\left(Sign\left(M^{\prime }\right),x_{n+1}\right)$ 发送给用户，用户收到 $\left(Sign\left(M^{\prime }\right),x_{n+1}\right)$ 后，计算 $s\equiv sign\left(M^{\prime }\right)/k\left(\mathrm{mod}N\right)$ ，对M的签名是 $\left(s,M,x_{n+1}\right)$ 。

3.3. 签名验证过程

验证者验证的具体步骤如下：

Step 1：根据 $x_{n+1}$ ，分别计算：

$\begin{array}{l}{x}_{n+1}^2\equiv x_n\mathrm{mod}N\\ x_n^2\equiv x_{n-1}\mathrm{mod}N\\ ⋮\\ x_2^2\equiv x_1\mathrm{mod}N\end{array}$

得到序列 $A=\left(x_1,x_2,\cdots ,x_{n+1}\right)$ ，并计算 $T\equiv H\left(a_i\right)x_{i+1}^2\mathrm{mod}N$ 。

Step 2：验证 $s^2\equiv T\mathrm{mod}N$ 是否成立，如果成立则签名有效；否则签名无效。

4. 签名方案的分析

4.1. 有效性分析

$Y=\left(y_0,y_1,\cdots ,y_n\right)$ ， $y_i={a^{\prime }}_i{x}_{i+1}^2=k^{2}H\left(a_i\right)x_{i+1}^2$ ，。又因为 $T=H\left(a_i\right)x_{i+1}^2$ ，

$Sign\left(M^{\prime }\right)=Y^d\mathrm{mod}N$ ， $s=sign\left(M^{\prime }\right)/k\left(\mathrm{mod}N\right)$ 。验证 $s^2\equiv T\mathrm{mod}N$ ，即 $\frac{Sign{\left(M^{\prime }\right)}^2}{k^2}\equiv H\left(a_i\right)x_{i+1}^2\mathrm{mod}N$ ， $Sign{\left(M^{\prime }\right)}^2\equiv k^{2}H\left(a_i\right)x_{i+1}^2\mathrm{mod}N\equiv Y\mathrm{mod}N$ ，说明签名 $$ 是一个有效签名。

4.2. 盲性

盲性是盲签名的主要安全需要，它可以确保被签名消息的安全性。要证明我们的方案是盲的，只要证明方案中存在随机值，可以在签名过程中有效地保护原信息，使得签名者对所签消息一无所知。由于签名者只知道，而 $M^{\prime }=\left({a^{\prime }}_0,{a^{\prime }}_1,\cdots ,{a^{\prime }}_n\right)$ 是用户经过盲因子盲化之后以及Hash函数计算之后所得的数据，签名者不能从盲化后的消息 $M^{\prime }=\left({a^{\prime }}_0,{a^{\prime }}_1,\cdots ,{a^{\prime }}_n\right)$ 中推出原消息的Hash值 $H\left(M\right)$ ，更不能推出原消息M。所以，这个签名方案是满足盲性的。

4.3. 不可伪造性

攻击者想要通过公开的验证密钥N求出保密的签名密钥p，q是不可行的，因为这是基于大合数分解的困难问题。因此，该方案是可以抵御一般性的伪造攻击。如果攻击者想要伪造签名者对盲化后的 $M^{\prime }=\left({a^{\prime }}_0,{a^{\prime }}_1,\cdots ,{a^{\prime }}_n\right)$ 进行签名，需要先破获 $x_0$ 。其次，攻击者需要求出d，而这是不可行的，因为 $d=\left(N-p-q+5\right)/8$ ，想要求出d，必须要先求出p，q，这仍然是基于大合数分解的困难问题。所以，我们的盲签名方案满足不可伪造性。

4.4. 性能分析

本方案与文献 [3] 的方案同为利用二次剩余进行盲签名，但在签名方式上各不相同，故签名运算所用时间有所差异。在模运算中，模幂、模逆与模乘运算占用了大部分时间，在签名阶段本方案的运算效率高于文献 [3]。而在参数生成阶段时，文献 [3] 需要多次计算Jacobi符号也会花费时间。可以看出就整个签名方案而言，本方案的计算效率更高。

5. 结束语

盲签名因为具有盲性，它使得盲签名能有效地保护用户的隐私，所以在电子商务和电子选举等领域有着广泛的应用 [9]。本文提出一个基于二次剩余的盲签名方案，并证明了这个盲签名方案满足盲性和不可伪造性这两个基本安全需求。