公钥密码体制中模幂运算方法、设备和服务器

摘要

本发明涉及密码学技术领域，特别是涉及公钥密码体制中模幂运算方法、设备和服务器。所述模幂运算方法，包括：构造随机参数w；选择随机数k；将w和k进行线性运算，得到k’；向服务器发送计算gk′的请求，其中g是公钥密码体制中的生成元；获得服务器计算gk′的计算结果Q′；获取Qw，所述Qw＝gw；将Q’和Qw根据所述线性运算的逆运算进行相应的乘法运算，得到Q。本发明公钥密码体制中的模幂运算方法、设备和服务器，在满足数字签名安全性的条件下，实现了以外包计算的方式将公钥密码体制中的模幂运算安全地交付给云计算服务提供商，借助云计算系统来完成计算密集度高的操作，从而使得数字签名系统可以满足大规模、高并发的要求，并具备动态扩展的特性。

说明书

技术领域

本发明涉及密码学技术领域，特别是涉及公钥密码体制中模幂运算方法、 设备和服务器。

背景技术

数字签名在信息安全，包括身份认证、数据完整性、不可否认性以及匿名 性等方面有重要应用，特别是在大型网络安全通信中的密钥分配、认证及电子 商务系统中具有重要作用。数字签名是实现认证的重要工具，具有很多实际用 途，可以在通信协议中表明用户的身份，也可以用在X.509数字证书中用来证 实该证书是有特定数字认证机构（CA）所签发。

使用数字签名的一般过程包括以下步骤：（1）发送方首先用公开的单向函 数对报文进行一次变换，得到数字签名，然后利用私有密钥对数字签名进行加 密后附在报文之后一同发出。（2）接收方用发送方的公开密钥对数字签名进行 解密变换，得到一个数字签名的明文。（3）接收方将得到的明文通过单向函数 进行计算，同样得到一个数字签名，再将两个数字签名进行对比，如果相同， 则证明签名有效，否则无效。

安全的数字签名必须满足可信、不可伪造、不可复制、不可抵赖，签名的 消息是不可改变等特性，通常依赖于密码算法及协议过程来达到这一目标。如 采用非对称加密算法实现的数字签名技术，常用的是DSA和RSA签名。其中， DSA是Schnorr和ElGamal签名算法的变种，被美国NIST作为数字签名标准 (Digital Signature Standard，简称DSS)。

以下对DSA数字签名算法进行简单介绍。设(p,q,g)是系统公开参数。其中 p是一个长为l比特的大素数(512≤l≤1024且^64|l)；q是一个长为160比特的素数 使得q|(p-1)；而g是乘法群中阶为q的元素。签名者S选取一随机数作 为其秘密秘钥，将y＝g^xmodp公布为其公开秘钥。另外，还假设H(·)是一个公开 的安全Hash函数(比如SHA-1)。

要产生对某个消息的签名时，签名者首先随机选取0＜k＜q，然后利 用其秘密秘钥x按下式计算出签名(M,r,s)：

r＝(g^kmodp)modq，s＝k^-1(H(m)+xr)modq

验证者V可根据以下恒等式是否成立来判定是否为签名者对消息的签名：

$r\equiv \left(g^{H\left(m\right)s^{-1}\mathrm{mod}q}{y}^{{\mathrm{rs}}^{-1}\mathrm{mod}q}\mathrm{mod}p\right)\mathrm{mod}q$

DSA的安全性依赖于计算模数的离散对数的难度，鉴于有限域上计算离散 对数问题的进展，一般认为512比特的DSA算法无法提供长期的安全性，而1024 比特的安全性则值得依赖。在使用相同的模数时，DSA比RSA更慢（两者产生 签名的速度相同，但验证签名时DSA比RSA慢10到40倍）。

DSA数字签名算法中使用的模幂运算计算复杂度高，在执行DSA数字签名 算法的过程中，大部分的时间都将用于执行模幂运算，因此模幂运算的执行效 率是提高系统效能的关键因素。对于本身不具备大规模运算能力的节点（如某 些嵌入式设备），则可能需要将数字签名算法的执行过程外包给所连接的服务网 络。

为了满足大规模、高并发的要求，数字签名系统中需要配置专用的密码运 算设备（俗称“密码机”），并需要实现密码设备的集群，而这些专用设备的价 格相对比较昂贵，并且不利于动态扩展。由于云计算系统是基于主流的通用服 务器硬件来构建，具有海量计算能力、海量存储、动态扩展等技术优势，用来 执行密码学运算的性价比更高。但是，要将密码学运算外包给云计算系统来完 成，则会导致云计算系统获得用户的密码运算的隐私泄露。譬如，数字签名算 法中的私钥及相关参数如果泄露，会给用户带来不可估量的损失。

发明内容

基于此，有必要针对现有技术将密码学运算外包给云计算系统无法保证密 码运算的隐私性的技术问题，提供一种公钥密码体制中的模幂运算方法、设备 和服务器。

一种公钥密码体制中的模幂运算方法，包括：

构造随机参数w；

选择随机数k；

将w和k进行线性运算，得到k’；

向服务器发送计算g^k′的请求，其中g是公钥密码体制中的生成元；

获得服务器计算g^k′的计算结果Q′；

获取Q_w，所述Q_w＝g^w；

将Q’和Q_w根据所述线性运算的逆运算进行相应的乘法运算，得到Q，Q为 所述模幂运算的结果。

在其中一种实施例中，所述线性运算为减法，所述将w和k进行线性运算 具体为：k′＝k-w;

所述线性运算的逆运算为加法，所述将Q’和Q_w根据所述线性运算的逆运算 进行相应的乘法运算具体为：Q＝Q′·Q_w。

在其中一种实施例中，所述参数w的一部分比特位的比特值为0，另外一部 分的比特位的比特值为1，且比特值为1的比特位随机分布。

在其中一种实施例中，所述参数w的构造方法如下：

随机选择m个整数r_i∈{0,2,…,n-1},i＝1,2,…,，以r_i作为权值构造一个n比特 的参数$w=\underset{i}{\Sigma }{2}^{r_i}.$

在其中一种实施例中，所述获取Q_w，具体包括：

预先计算并存储包括有多个倍乘生成元的倍乘生成元对应列表；

从所述倍乘生成元对应列表中，选择所有与参数w中比特值为1的比特位的 位置具有对应关系的倍乘生成元，所述对应关系为：倍乘生成元由2^r与g进行 模幂指数运算得到，所述r与所述比特位的位置相等；

对所有选择的倍乘生成元进行乘法运算得到Q_w。

在其中一种实施例中，所述将w和k进行线性运算包括：从多个线性运算 中随机选择一个线性运算作为隐藏线性运算，将w和k进行所述隐藏线性运算。

在其中一种实施例中：

所述构造随机参数w具体包括：

每间隔预设使用次数，重新构造随机参数w并保存；

所述获取Q_w，具体包括：

如果重新构造随机参数w，则将w与G进行第一运算，得到w与G进行第 一运算的计算结果Q_w并保存，

否则获取预先保存的Q_w。

一种公钥密码体制中的模幂运算的设备，包括：

参数构造模块，用于构造随机参数w；

随机数选择模块，用于选择随机数k；

线性运算模块，用于将w和k进行线性运算，得到k’；

计算请求发送模块，用于向服务器发送计算g^k′的请求，其中g是公钥密码 体制中的生成元；

设备计算结果获取模块，用于获得服务器计算g^k′的计算结果Q′；

设备幂指数运算模块，用于获取Q_w，所述Q_w＝g^w；

设备结果运算模块，用于将Q’和Q_w根据所述线性运算的逆运算进行相应的 乘法运算，得到Q，Q为所述模幂运算的结果。

在其中一种实施例中，所述线性运算为减法，所述线性运算模块，具体用 于计算k′＝k-w;

所述线性运算的逆运算为加法，所述设备结果运算模块，具体用于计算 Q＝Q′·Q_w。

在其中一种实施例中，所述参数w的一部分比特位的比特值为0，另外一部 分的比特位的比特值为1，且比特值为1的比特位随机分布。

在其中一种实施例中，所述参数构造模块，具体用于：

随机选择m个整数r_i∈{0,2,…,n-1},i＝1,2,…，m，以r_i作为权值构造一个n比特 的参数$w=\underset{i}{\Sigma }{2}^{r_i}.$

在其中一种实施例中，所述设备幂指数运算模块，具体用于：

预先计算并存储包括有多个倍乘生成元的倍乘生成元对应列表；

从所述倍乘生成元对应列表中，选择所有与参数w中比特值为1的比特位的 位置具有对应关系的倍乘生成元，所述对应关系为：倍乘生成元由2^r与g进行 模幂指数运算得到，所述r与所述比特位的位置相等；

对所有选择的倍乘生成元进行乘法运算得到Q_w。

在其中一种实施例中，所述线性运算模块，具体用于：从多个线性运算中 随机选择一个线性运算作为隐藏线性运算，将w和k进行所述隐藏线性运算。

在其中一种实施例中：

所述参数构造模块，具体用于：

每间隔预设使用次数，重新构造随机参数w并保存；

所述设备幂指数运算模块，具体用于：

如果重新构造随机参数w，则将w与G进行第一运算，得到w与G进行第 一运算的计算结果Q_w并保存，

否则获取预先保存的Q_w。

一种公钥密码体制中的模幂运算方法，包括：

响应设备发送的计算g^k′的请求，计算Q'＝g^k′，其中g是公钥密码体制中的生 成元，k′为设备所发送的随机数，由设备构造随机参数w和选择随机数k，并将 w和k进行线性运算所得到；

向设备返回Q’，所述Q’用于设备将Q’和Q_w根据所述线性运算的逆运算进 行相应的乘法运算，得到Q，Q为所述模幂运算的结果，其中所述Q_w＝g^w。

在其中一种实施例中，所述响应设备发送的计算g^k′的请求，计算Q'＝g^k′， 具体包括：

将k′展开为多个分段，

向多个运算服务器发送所述分段与生成元g进行模幂运算的请求；

从多个运算服务器中获取所述分段与生成元g进行模幂运算的运算结果；

将多个运算结果进行乘法运算，得到g^k′的计算结果。

在其中一种实施例中，将k′展开为多个分段，具体包括：将k′用权2^v展开 为多个分段，其中v为大于或等于0的整数。

一种公钥密码体制中的模幂运算服务器，包括：

服务器幂指数运算模块，用于响应设备发送的计算g^k′的请求，计算Q'＝g^k′， 其中g是公钥密码体制中的生成元，k′为设备所发送的随机数，由设备构造随机 参数w和选择随机数k，并将w和k进行线性运算所得到；

结果发送模块，用于向设备返回Q’，所述Q’用于设备将Q’和Q_w根据所述 线性运算的逆运算进行相应的乘法运算，得到Q，Q为所述模幂运算的结果， 其中所述Q_w＝g^w。

在其中一种实施例中，所述服务器幂指数运算模块，具体包括：

分段子模块，用于将k′展开为多个分段，

分发子模块，用于向多个运算服务器发送所述分段与生成元g进行模幂运 算的请求；

服务器计算结果获取子模块，用于从多个运算服务器中获取所述分段与生 成元g进行模幂运算的运算结果；

服务器合并结果子模块，用于将多个运算结果进行乘法运算，得到g^k′的计 算结果。

在其中一种实施例中，分段子模块，具体用于：将k′用权2^v展开为多个分 段，其中v为大于或等于0的整数。

要保证数字签名算法的安全性，必须满足两个基本条件：（1）保护用于签 名的私钥d；（2）保证参数k是真随机数，并且不被泄露。在DSA中随机数k与 私钥d有同样的保密要求，因为攻击者获知了随机数k，则可以计算出私钥 x＝r^-1(ks-H(M))modq。因此必须确保随机数k安全地产生、存储、销毁。

在本发明的技术方案中，数字签名使用的私钥d不需要在外包计算过程中使 用，而是仅在设备内部计算最终结果的时候使用，因此满足第1个条件。在外 包计算过程中使用的参数k′并非数字签名时使用的随机数k，而是采用了另一个 随机数w对其进行变换，因此满足第2个条件。

由此可见，尽管在本发明的技术方案中采用了计算外包过程，但是仍然可 以满足数字签名算法的安全性条件。

本发明公钥密码体制中的模幂运算方法、设备和服务器，通过增加构造一 个随机参数w，而交付给服务器计算点乘运算的k’，是将w和k进行线性运算 所得到，能很好地把随机数k隐藏起来，避免了服务器获得用户的随机数。因此， 在满足数字签名安全性的条件下，实现了以外包计算的方式将公钥密码体制中 的模幂运算安全地交付给云计算服务提供商，借助云计算系统来完成计算密集 度高的操作，从而使得数字签名系统可以满足大规模、高并发的要求，并具备 动态扩展的特性。

附图说明

图1为本发明的一种公钥密码体制中的模幂运算的计算方法的工作流程图；

图2为本发明的一种公钥密码体制中的模幂运算的计算方法在计算Q_w＝g^w的工作流程图；

图3为本发明的一种公钥密码体制中的模幂运算的设备的模块方框图；

图4为本发明的一种公钥密码体制中的模幂运算方法的工作流程图；

图5为本发明的一种公钥密码体制中的模幂运算服务器的模块结构图；

图6为本发明的一种公钥密码体制中的模幂运算应用于签名方法的工作流 程图；

图7为本发明的一种公钥密码体制中的模幂运算应用于DSA签名方法的公 钥计算工作流程图；

图8为本发明的一种公钥密码体制中的模幂运算应用于DSA签名方法的签 名工作流程图。

具体实施方式

下面结合附图和具体实施例对本发明做进一步详细的说明。

如图1所示为本发明的一种公钥密码体制中的模幂运算方法的工作流程图。

步骤S101，构造一个随机参数w；

步骤S102，选择随机数k；

步骤S103，将w和k进行线性运算，得到k’=Γ(k,w)；

步骤S104，向服务器发送计算g^k′的请求，其中g是公钥密码体制中的生成 元，即乘法群Z^*_p中阶为q的元素；

步骤S105，获得服务器计算g^k′的计算结果Q′；

步骤S106，获取Q_w，所述Q_w＝g^w；

步骤S107，将Q’和Q_w根据所述线性运算的逆运算进行相应的乘法运算， 得到Q，Q为所述模幂运算的结果。

在步骤S101中，随机参数w的构造，本领域普通技术人员在阅读本专利之 后，可以有多种选择。例如，w为真随机数，分别在多次点乘运算的中与不同的 k执行线性运算。

作为其中一种实施例，所述参数w的一部分比特位的比特值为0，另外一部 分的比特位的比特值为1，且比特值为1的比特位随机分布。构造这样的随机参 数w，当w的大部分比特位都为0时，其计算效率会得到极大的提升。

在其中一个实施例中，所述参数w的构造方法如下：

随机选择m个整数r_i∈{0,2,…,n-1},i＝1,2,…,m，以r_i作为权值构造一个n比特 的参数$w=\underset{i}{\Sigma }{2}^{r_i}.$

在其中一种实施例中，线性运算为减法，其逆运算为加法，在步骤S102具 体为计算k′＝k-w，在步骤S107中，采用乘法运算计算Q＝Q′·Q_w。本实施例的 方法较为简单，本领域普通技术人员在阅读本专利后，也可以选择其他线性运 算方式，例如加法，其逆运算为减法，则步骤S102可以为k′＝k+w，步骤S107 中，可以计算Q＝Q′/Q_w。当然，步骤S102也可以令k′＝k-Aw，其中A为一个 常数，则步骤S106中，可以计算Q＝Q′·Q_w^A。

在其中一种实施例中，步骤S103可以包括：从多个线性运算中随机选择一 个线性运算作为隐藏线性运算，将w和k进行所述隐藏线性运算。

例如，可以令k′＝k-Aw，而A的值每次均随机获取，则每次选择不同的A 值，构成所述的隐藏线性运算。

在其中一种实施例中：

所述步骤S101中，每间隔预设使用次数，重新构造随机参数w并保存；

所述步骤S106：

如果重新构造随机参数w，则将w与G进行第一运算，得到w与G进行第 一运算的计算结果Q_w并保存，

否则获取预先保存的Q_w。

例如，可以在步骤S101中，随机数w可以每N次更换一次，例如，每100 次更换一次，并把步骤S106的计算结果保留，步骤S106仅在w更换的时候重 新计算。由于k是每次运算都会更换，因此，k’仍然是每次运算都会变化，要把 w反向计算出来，需要一定的次数，因此也同样能起到隐藏k的效果。但是由于 Q_w不用频繁计算，因此，也可以提高运算效率。

在其中一个实施例中，点乘运算Q_w＝g^w的计算方法如下：

预先计算并存储包括有多个倍乘生成元的倍乘生成元对应列表；

从所述倍乘生成元对应列表中，选择所有与参数w中比特值为1的比特位的 位置具有对应关系的倍乘生成元，所述对应关系为：倍乘生成元由2^r与g进行 模幂指数运算得到，所述r与所述比特位的位置相等；

对所有选择的倍乘生成元进行乘法运算得到Q_w。

作为一个例子，点乘运算Q＝g^kmodq方法如下：

a)随机选择m个整数r_i∈{0,2,…,n-1},i＝1,2,…,m，以r_i作为权值构造一个n 比特的参数这样得到n比特数值其中只有m个1，并且是随机分布。

b)选择随机数k，计算k′＝k-w。

c)通过外包计算的方式，在云计算服务器集合U＝{U₁,U₂,…,U_c}执行模幂 运算Q′＝g^k′modq＝g^k-wmodq，为了确保隐私性、正确性，可采用安全多方计 算协议。

d)在特定的硬件加速设备执行模幂运算如 果满足m远小于n这个条件，则参数w的大部分比特为零值，其执行效率比 计算点乘运算kG要高得多。

e)计算Q＝Q′·Q_w＝(g^k-w·g^w)modq＝g^kmodq，得到模幂运算的最终结果。

在步骤S105中，需要计算Q_w＝g^wmodq。本领域普通技术人员在阅读本专利 后，可以选择采用其他方式计算，例如通用的模幂分解运算，如下所示：

对于任意整数w＝(w_t-1，…,w₁,w₀)₂，Q_w＝g^wmodq按以下步骤计算：

（a）Q_w←1，G←1；

（b）Forifrom0tot-1do

a)Ifw_i＝1thenQ_w←Q_w·G

b)G←(G·g)modq

（c）输出Q_w。

对于特定的DSA密码体制，其生成元g是固定不变的，在本发明的一个实 施例中，在系统存储空间足够的条件下，可以预先计算并存储 {G,2G,2²G,…,2^n-1G}，从而把模幂指数运算转化为乘法运算来执行，以减少计算 的复杂程度。

如图2所示为本发明的一种公钥密码体制中的模幂运算方法在计算Q_w＝g^w的工作流程图。

步骤S201，从所述倍乘生成元对应列表中，选择所有与参数w中比特值为1 的比特位的位置具有对应关系的倍乘生成元，所述对应关系为：倍乘生成元由2^r 与g进行模幂指数运算得到，所述r与所述比特位的位置相等；

其中，所述幂指数与所述参数w中的比特位的位置对应，即对于任意整数 w＝(w_t-1，…,w₁,w₀)₂，其中w_i对应的倍乘生成元为

步骤S202，对所有选择的倍乘生成元进行乘法运算得到Q_w。

作为一个例子，预先计算并存储对于任意整数 w＝(w_t-1，…,w₁,w₀)₂，G∈E(F_p)，令O表示无穷远点，Q_w＝g^w按以下步骤计算：

（a）Q_w←O；

（b）Forifrom0tot-1do

$\mathrm{If}{w}_i=1\mathrm{then}{Q}_w\leftarrow Q_w·g^{2^i}$

（c）输出Q_w。

如图3所示为本发明的一种公钥密码体制中的模幂运算的设备的模块方框 图，包括：

参数构造模块310，用于构造随机参数w；

随机数选择模块320，用于选择随机数k；

线性运算模块330，用于将w和k进行线性运算，得到k’；

计算请求发送模块340，用于向服务器发送计算g^k′的请求，其中g是公钥密 码体制中的生成元；

设备计算结果获取模块350，用于获得服务器计算g^k′的计算结果Q′；

设备幂指数运算模块360，用于获取Q_w，其中Q_w＝g^w；

设备结果运算模块370，用于将Q’和Q_w根据所述线性运算的逆运算进行相 应的乘法运算，得到Q，Q为所述模幂运算的结果。

在其中一个实施例中，所述线性运算为减法，所述线性运算模块，具体用 于计算k′＝k-w;

所述线性运算的逆运算为加法，所述设备结果运算模块307，具体用于计算 Q＝Q′·Q_w

在其中一个实施例中，所述参数w的一部分比特位的比特值为0，另外一部 分的比特位的比特值为1，且比特值为1的比特位随机分布。

在其中一个实施例中，所述参数构造模块301，具体用于：

随机选择m个整数r_i∈{0,2,…,n-1},i＝1,2,…，m，以r_i作为权值构造一个n比特 的参数$w=\underset{i}{\Sigma }{2}^{r_i}.$

在其中一个实施例中，所述设备幂指数运算模块306，具体用于：

预先计算并存储包括有多个倍乘生成元的倍乘生成元对应列表；

从所述倍乘生成元对应列表中，选择所有与参数w中比特值为1的比特位的 位置具有对应关系的倍乘生成元，所述对应关系为：倍乘生成元由2^r与g进行 模幂指数运算得到，所述r与所述比特位的位置相等；

对所有选择的倍乘生成元进行乘法运算得到Q_w。

运算转换为可并发执行的形式，允许任意多个服务器共同执行这个计算过 程。当然也可以将不同的并发过程外包给不同的云计算服务提供商，然后再形 成外包计算的最终结果。在这种情况下，还可以通过执行安全多方计算协议， 使得单个的云计算服务提供商不能获得计算过程的输入参数、输出结果的信息， 进一步保护随机数k′的隐私性。

如图4所示为一种公钥密码体制中的模幂运算方法的工作流程图，包括：

步骤S401，响应设备发送的计算g^k′的请求，计算Q'＝g^k′，其中g是公钥密 码体制中的生成元，k′为设备所发送的随机数，由设备构造随机参数w和选择 随机数k，并将w和k进行线性运算所得到；

步骤S402，向设备返回Q’，所述Q’用于设备将Q’和Q_w根据所述线性运算 的逆运算进行相应的乘法运算，得到Q，Q为所述模幂运算的结果，其中所述 Q_w＝g^w。

在其中一种实施例中，所述响应设备发送的计算g^k′的请求，计算Q'＝g^k′， 具体包括：

将k′展开为多个分段，

向多个运算服务器发送所述分段与生成元g进行模幂运算的请求；

从多个运算服务器中获取所述分段与生成元g进行模幂运算的运算结果；

将多个运算结果进行乘法运算，得到g^k′的计算结果。

在其中一种实施例中，将k′展开为多个分段，具体包括：将k′用权2^v展开 为多个分段，其中v为大于或等于0的整数。

将模幂运算转换为可并发执行的形式的原理阐述如下：对于n比特任意随机 数k，可用权2^v展开为m个分段，其中为自然数，每个分段的位宽为v比 特：

$k=\underset{i=0}{\overset{m-1}{\Sigma }}{2}^{i·v}{k}_i=2^{(m-1)v}{k}_{m-1}+···+2^v{k}_1+k_0,$

这里，当n不能整除v时，需要通过高位补零的方式将k扩展为n′比特。

从而模幂运算可以表示为以下形式：

$Q=g^k=g^{\underset{i=0}{\overset{m-1}{\Sigma }}\left(2^{i·v}{k}_i\right)}={\left(g^{2^{(m-1)v}}\right)}^{k_{m-1}}······{\left(g^{2^v}\right)}^{k_1}·g^{k_0}\text{.}$

在进行上述变换之后，对于给定的参数m及w，可以预先计算并存储以下中 间结果：

$\{g,g^{2^v},g^{2^{2v}},···,g^{2^{(m-1)v}}\},$

从而将单个模幂运算分解为m个相互独立的模幂运算。

如图5所示为本发明的一种公钥密码体制中的模幂运算服务器的模块结构 图。

一种公钥密码体制中的模幂运算服务器，包括：

服务器幂指数运算模块510，用于响应设备发送的计算g^k′的请求，计算 Q'＝g^k′，其中g是公钥密码体制中的生成元，k′为设备所发送的随机数，由设备 构造随机参数w和选择随机数k，并将w和k进行线性运算所得到；

结果发送模块520，用于向设备返回Q’，所述Q’用于设备将将Q’和Q_w根 据所述线性运算的逆运算进行相应的乘法运算，得到Q，Q为所述模幂运算的 结果。

在其中一个实施例中，所述服务器幂指数运算模块510，具体包括：

分段子模块511，用于将k′展开为多个分段，

分发子模块512，用于向多个运算服务器发送所述分段与生成元g进行模幂 运算的请求；

服务器计算结果获取子模块513，用于从多个运算服务器中获取所述分段与 生成元g进行模幂运算的运算结果；

服务器合并结果子模块514，用于将多个运算结果进行乘法运算，得到g^k′的 计算结果。

在其中一个实施例中，分段子模块511，具体用于：将k′用权2^v展开为多个 分段，其中v为大于或等于0的整数。

本发明的公钥密码体制中的模幂运算方法可以用于多种签名方法。

如图6所示为本发明的一种公钥密码体制中的模幂运算应用于签名方法的 工作流程图。

一种椭圆曲线密码体制中的签名方法，所述方法包括：

步骤S601，构造一个随机参数w；

步骤S602，选择随机数k；

步骤S603，将w和k进行线性运算，得到k’=Γ(k,w)；

步骤S604，向服务器发送计算g^k′的请求，其中g是公钥密码体制中的生成 元，即乘法群中阶为q的元素；

步骤S605，获得服务器计算g^k′的计算结果Q′；

步骤S606，获取Q_w，所述Q_w＝g^w；

步骤S607，将Q’和Q_w根据所述线性运算的逆运算进行相应的乘法运算， 得到Q；

步骤S608，采用Q作为签名参数，进行签名运算

在步骤S601中，随机参数w的构造，本领域普通技术人员在阅读本专利之 后，可以有多种选择。

作为其中一种实施例，所述参数w的一部分比特位的比特值为0，另外一部 分的比特位的比特值为1，且比特值为1的比特位随机分布。构造这样的随机参 数w，当w的大部分比特位都为0时，其计算效率会得到极大的提升；

在其中一种实施例中，线性运算为减法，其逆运算为加法，在步骤S602具 体为计算k′＝k-w，在步骤S607中，采用乘法运算计算Q＝Q′·Q_w。其中，线性 运算也可以为其他方式，例如加法，其逆运算为减法，则步骤S102可以为 k′＝k+w，步骤S106中，可以计算Q＝Q′/Q_w。

作为一个例子，以DSA数字签名算法为例。

如图7所示为本发明的一种公钥密码体制中的模幂运算应用于DSA签名方 法的公钥计算工作流程图。

设(p,q,g)是系统公开参数。其中p是一个长为l比特的大素数(512≤l≤1024且 ^64|l)；q是一个长为160比特的素数使得q|(p-1)；而g是乘法群中阶为q的 元素。另外，还假设H(·)是一个公开的安全Hash函数(比如SHA-1)。签名者S 选取一随机数作为其秘密秘钥，然后计算公钥，执行如下步骤：

步骤S701，随机选择m_x个整数r^x_i∈{0,2,…,n_x-1},i＝1,2,…,m_x，以r^x_i作为权 值构造一个n_x比特的参数这样得到n_x比特数值其中只有m_x个1，并 且是随机分布；

步骤S702，计算x'＝x-w_x；通过外包计算的方式，在云计算服务器集合 U＝{U₁,U₂,…,U_c}执行模幂运算在特定的硬件加速设备执行模幂 运算${Q_w}^x=g^{w_x}=g^{\underset{i}{\Sigma }{2}^{r^{x_i}}}.$

步骤S703，计算$Q_x=Q_x^{\prime }·{Q_w}^x=g^{(x-w_x)}·g^{w_x}=g^{(x-w_x+w_x)}=g^x.$

步骤S704，将Q_x公布为其公开公钥。

如图8所示为本发明的一种公钥密码体制中的模幂运算应用于DSA签名方 法的签名工作流程图。要产生对某个消息的签名时，签名者设备执行如下 步骤：

步骤S801，随机选择m个整数r_i∈{0,2,…,n-1},i＝1,2,…,m，以r_i作为权值构 造一个n比特的参数这样得到n比特数值其中只有m个1，并且是随 机分布；

步骤S802，随机选取0＜k＜q，计算k'＝k-w；通过外包计算的方式，在云 计算服务器集合U＝{U₁,U₂,…,U_c}执行模幂运算Q′＝g^k′＝g^(k-w)；在特定的硬件加速 设备执行模幂运算

步骤S803，计算Q＝Q′·Q_w＝g^(x-w)·g^w＝g^(x-w+w)＝g^x。

步骤S804，令r＝(Qmodp)modq，s＝k^-1(H(M)+xr)modq，得到签名 (M,r,s)。

以上所述实施例仅表达了本发明的几种实施方式，其描述较为具体和详细， 但并不能因此而理解为对本发明专利范围的限制。应当指出的是，对于本领域 的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干变形和 改进，这些都属于本发明的保护范围。因此，本发明专利的保护范围应以所附 权利要求为准。