基于多变量排列难题和超对数难题的数字签名方法

摘要

基于多变量排列难题和超对数难题的数字签名方法，属于密码技术和计算机技术领域；包括密钥生成、数字签名和身份验证三个部分；其用户拥有两个密钥，即一个私钥和一个公钥，且从公钥不能推导出私钥；发送方的私钥用于生成文件或消息的签名码，发送方的公钥用于接收方验证相应文件或消息的签名码；该方法能有效抵御已有分析手段的攻击，具有模数小、计算速度快、技术可以公开等特点，可用于手机、计算机和通信网络中任何文件、数据的签名与验证，以及电子政务、电子商务中的身份认证与内容确认。

说明书

(一)技术领域

公开密钥数字签名方法(简称公钥数字签名方法或签名方法)属于密码技术和计算机技术领域，是信息安全的核心技术之一。

(二)背景技术

密码技术的发展经历了古典密码技术、对称密码技术和公钥密码技术三个阶段。1976年，美国学者Diffie和Hellman提出公钥密码体制的思想，标志着公钥密码技术的来临。目前，普遍使用的数字签名技术有RSA方案、Rabin方案和ElGamal方案(参见《应用密码学》，美国Bruce Schneier著，吴世忠、祝世雄等译，机械工业出版社，2000年1月，第334-342页)。为了提高安全性，ElGamal方案常在椭圆曲线上实现，此时，它叫ECC(Elliptic CurveCryptography)方案。另外，还有一个DSA(Digital Signature Algorithm)签名方案，它是ElGamal签名方案的改进。

RSA、Rabin和ElGamal等方案都是美国人发明的。它们的安全性基于大数难于计算的复杂性，即在有限的时间和资源内，对大数进行因式分解或离散对数求解几乎是不可能的。但是，随着计算机运算速度的提高，它们的安全参数不得不变得越来越大，极大地浪费了存储空间和降低了签名效率。

(三)发明内容

本发明是对“REESSE1公钥密码体制”(《计算机工程与科学》，2003(10)，pp.13-16)中签名方案的一个根本性的革新。

数字签名技术用于计算机网络和通信网络中双方身份的认证、传输内容的不可抵赖性、以及电子商务、金融交易和文件签发中身份的鉴别与确认。

本发明希望我们国家在公钥加密与数字签名领域能够拥有自己的核心技术，以确保国家的信息安全、经济安全和主权安全，同时提高我国防范金融欺诈、证书欺诈和票据欺诈的技术手段。

限于篇幅，本节内容略去了对有关性质和结论的证明，如果需要补上，我们将立即呈交。

3.1两个基本概念

3.1.1互素序列的定义与性质

定义1：如果A₁、A₂、...、A_n是n个两两不同的整数，满足附带i≠j，或者gcd(A_i，A_j)＝1；或者gcd(A_i，A_j)≠1，但对任意k≠i、j，且那么，这些整数被称为互素序列，记为{A₁，A₂，...，A_n}，简记为{A_i}。

在本文中，我们要求每个A_i＞0，且带i≠j，有gcd(A_i，A_j)＝1。

性质1：对于任意正整数m≤n，如果从互素序列{A_i}中随机选取m个元素，并构造子集{Ax₁，Ax₂，...，Ax_m}，那么互素子集积

G＝|Ax₁|×|Ax₂|×...×|Ax_m|

被唯一地确定，即从G到{Ax₁，Ax₂，...，Ax_m}的映射是一对一的。

这里，|Ax_i|表示数Ax_i的绝对值，i＝1，2，...，m。

3.1.2杠杆函数

在本发明中，仍需要用到杠杆函数的概念。设l(.)是由整数到整数的单射函数，其定义域为{1，2，...，n}，值域为{5，6，...，M-1}，这里M为模数。

在“REESSE1公钥密码体制”一文中，我们论述了：当从公钥推导私钥时，需考虑{l(i)}的全排列数n！，这意味着，当n足够大时，穷举{l(i)}的全排列在多项式时间内是不可行的；但从私钥恢复明文或进行数字签名时只需考虑{l(i)}的累加和，使得解密或签名在关于n的多项式时间内可行。因此，{l(i)}是“公开”一端计算量大，“私有”一端计算量小。故我们称具有上述特征的l(.)为杠杆函数。

注意：在本文中，{A_i}是序列{A₁，A₂，...，A_n}的简写，{C_i}是序列{C₁，C₂，...，C_n}的简写。{l(i)}是n个杠杆函数值{l(1)，l(2)，...，l(n)}的简写。另外，在本文中，乘法“A×B”有时简写成“AB”，“mod”代表求余，“gcd”代表最大公约数，“←”代表赋值，“≡”表示两边对M求余相等，表示x不能整除y，“||x||”代表x mod M的阶，代表比特的求反运算，“∈”表示左边变量的值属于某个区间或集合。n≥80为一个正整数，Hash为一个单向散列函数。

3.2数字签名的技术方案

本发明是一种基于多变量排列难题和超对数难题的公钥数字签名方法，简称REESSE1+数字签名方法，根据该方法，可制造数字签名芯片，或开发数字签名软件等。因此，本发明是一种生产数字签名产品所必须遵循的基本原理与技术方案，而不是物理产品本身。

本数字签名方案，由密钥生成、数字签名和身份验证等三部分组成。

3.2.1数字签名与身份验证操作

假设用户U欲通过网络向用户V发送一个具有自己数字签名的文件或消息F，其操作过程如下：

密钥生成：首先，用户U应该去第三方权威机构即CA数字证书中心(CertificateAuthentication)领取由密钥生成部件输出的一对私钥(Private Key)与公钥(Public Key)，私钥必须由U自己保管，不得外泄；公钥则允许以公钥证书的形式向外界公开发放，以便于验证。

数字签名操作：用户U在运行数字签名部件的机器上用自己的私钥对文件或消息F进行签名，得到签名码，并把文件F连同签名码发送给用户V。

身份验证操作：用户V从CA中心获得用户U的公钥证书，在运行身份验证部件的机器上对接收到的文件F和其签名码进行验证，以鉴定签名码是否为用户U所为、文件F在传输过程中是否已被修改。

3.2.2密钥生成

密钥生成部分供CA认证中心使用，用来产生一对用户的私钥和公钥。

假设S、T、是两两互素的整数，其中且非大，其实现方法是：

(1)随机产生互素序列{A₁，A₂，...，A_n}，计算

(2)找到一个正素数M使得gcd(S，M-1)＝1和

(3)随机选择W、δ∈(1，M)，其中δ满足

(4)产生两两不同的值l(1)，l(2)，...，l(n)∈{5，7，...，2n+3}

(5)计算$\alpha \leftarrow {\delta }^{({\delta }^n+\delta W^{n-1})T}\mathrm{mod}M,\beta \leftarrow {\delta }^{W^{n}T}\mathrm{mod}M,$

l(1)←(WG^δ)^-S(αδ^-1)mod M

(6)计算序列{C₁，C₂，...，C_n|C_i←(A_iW^l(i))^δmod M}

最后，用户以({A_i}、{l(i)}、W、δ、作为私钥，以({C_i}α、β)作为公钥，S、T、M共用。

3.2.3数字签名

发送方即签名方以自己的私钥({A_i}、{l(i)}、W、δ、作为签名密钥。设F为待签文件或消息。

(1)令消息摘要H＝Hash(F)，其二进制形式为b₁b₂...b_n

(2)计算$k_1\leftarrow \delta {\Sigma }_{i=1}^n{b}_{i}l\left(i\right)\mathrm{mod}(M-1),$$G_0\leftarrow {\left({\Pi }_{i=1}^n{A}_i^{⫬b_i}\right)}^{\delta }\mathrm{mod}M$

(3)选择a＜M-1，使得

其中

(4)计算$R\leftarrow {\left(Q{\delta }^{-1}l{\left(1\right)}^{-1}\right)}^{S^{-1}}{G}_0^{-1}\mathrm{mod}M,\bar{U}\leftarrow {\left(R{W}^{k_1-1}\right)}^Q\mathrm{mod}M,$

$\xi \leftarrow {\Sigma }_{i=0}^{n-1}{\left(\mathrm{\delta Q}\right)}^{n-1-i}{\left(\mathrm{HW}\right)}^i\mathrm{mod}(M-1)$

(5)任选使得

其中$U\leftarrow \bar{U}{\hat{g}}^r\mathrm{mod}M$

(6)若转至(5)

算法执行后，得到数字签名码(Q、U)，其可随文件F一起发送给验证者。

根据双同余定理，在签名中，无需V≡(R^-1WG₁)^QUδ^λ(mod M)，其中λ满足λS≡((WQ)^n-1+ζ+rUS)(δQ-HW)(mod M-1)，这表明

双同余定理：设M为素数，s、t满足gcd(s，t)＝1为常数，则联立方程x^s≡a(mod M)、x^t≡b(mod M)有唯一解的充要条件是a^t≡b^s(mod M)。

3.2.4身份验证

接收方以发送方的公开密钥({C_i}、α、β)作为验证密钥。设F为待签文件或消息，(Q、U)为其签名码。

(1)令消息摘要H＝Hash(F)，其二进制形式为b₁b₂...b_n

(2)计算$\hat{G}\leftarrow {\Pi }_{i-1}^n{C}_i^{b_i}\mathrm{mod}M$

(3)计算$X\leftarrow {\left(\alpha Q^{-1}\right)}^{\mathrm{QUT}}{\alpha }^{Q^n}\mathrm{mod}M,$

和$Y\leftarrow {\left({\hat{G}}^Q{U}^{-1}\right)}^{\mathrm{UST}}{\beta }^{H{Q}^{n-1}+H^n}\mathrm{mod}M$

(4)若X≡Y，则签名者身份有效且F未被修改，

否则，签名者身份无效或F在传输中已被修改

算法执行后，可以达到鉴别签名真伪、防发送者抵赖和抗攻击者修改的目的。

下面证明：若(Q、U)是一个真实的签名码，则有X≡Y(mod M)。

从3.2.2节知：$\alpha \equiv {\delta }^{({\delta }^n+\delta W^{n-1})T}\equiv \mathrm{\delta l}\left(1\right){\left(W{G}^{\delta }\right)}^S\left(\mathrm{mod}M\right)$和$\beta \equiv {\delta }^{W^{n}T}\left(\mathrm{mod}M\right).$

从3.2.3节知：Q≡(RG₀)^S(δl(1))(mod M)和G^δ≡G₀G₁(mod M)。

令V≡(R^-1W G₁)^QUδ^λ(mod M)。

因为λ满足

λS≡((WQ)^n-1+ξ+rUS)(δQ-HW)(mod M-1)，

可以令这里k是一个整数，那么

移项得

因此，有

又

移项得

因此

根据双同余定理，有

即$X\equiv {\left({\hat{G}}^Q{U}^{-1}\right)}^{\mathrm{UST}}{\beta }^{{\mathrm{HQ}}^{n-1}+H^n}\equiv Y\left(\mathrm{mod}M\right).$

3.3本数字签名方法的安全性

分析表明，基于多变量排列难题和超对数难题的公钥数字签名方法具有相当高的安全性，能满足实际应用的需要。

在下面的讨论中，令M为素常数，y、C_i为常数，x、A_i、W、δ、l(i)为未知量。

离散对数难题：从y≡g^x(mod M)求x被称为离散对数难题(参见《应用密码学》中ElGamal签名方案)。

多变量排列难题：从C_i≡(A_iW^l(i))^δ(mod M)求A_i、W、δ、l(i)被称之为多变量排列难题，它保证了私钥的安全性。

通过归约方法知，从C_i推导A_i、W、δ、l(i)是比求离散对数更为困难的。

超对数难题：从y≡x^x(mod M)求x被称之为超对数难题，它保证了签名码的安全性。

通过归方约法知，从y≡x^x(mod M)求解x是比从y≡g^x(mod M)求解x更为困难的。

3.4优点和积极效果

3.4.1安全性较高

在目前所用的RSA、ElGamal等数字签名方案中，利用了大数难于计算的问题，随着计算机速度的提高，它们的安全性和效率将受到影响。而本数字签名方法是利用了超对数难题y≡x^x(mod M)以及多变量排列难题C_i≡(A_iW^l(i))δ(mod M)，只是在被穷举攻击时才考虑计算机的运算速度，所以，具备更高的安全性。

3.4.2运算速度较快

在本数字签名方法中，无论是签名还是验证，主要涉及素域上的模乘运算和模幂运算。由于模数M较小且模幂运算的个数非常有限，因此，运算速度将会较快。

3.4.3对国家安全有利

互联网是一种开放网，任何人在网上利用一定的工具就可以截获和修改被传输的信息，因此，在网上传输的信息必须进行加密和签名。由于我国政府、国防、金融、税务等重要部门业已使用互联网作为通信工具，所以，信息安全关系到国家安全和经济安全。但是，泱泱一个大国的信息安全不能建立在外来的密码算法基础之上，因此，研究我们自己的公开密钥加密与签名算法显得势在必行和具有重大意义。

(四)具体实施方式

基于多变量排列难题和超对数难题的公钥数字签名方法的特点是它能够让每一用户得到两个密钥，一个密钥可以公开，一个密钥只能私人拥有。这样，就不会担心密钥在传递过程中泄密了。当约定通信双方在网上传输信息时，发送者使用自己的私钥对文件或消息进行数字签名，接收者收到文件和签名码后使用发送者的公钥对其进行验证。

每个用户可以到指定的CA数字证书中心取得两个密钥。CA中心是对用户进行登记、对密钥进行产生、分发和管理的一个机构。它的主要职能是利用密钥生成方法产生用户的一对公钥与私钥。

本数字签名方法可以用逻辑电路芯片或程序语言来实现，并形成相应的硬件或软件产品，它包括三部分：①根据3.2.2节的密钥生成方法开发出芯片或软件，由CA数字证书中心使用；②根据3.2.3节的数字签名方法开发出芯片或软件，由签名用户使用；③根据3.2.4节的身份验证方法开发出芯片或软件，由验证用户使用。