CN1282325C - 能快速解密的密码系统与方法 - Google Patents

Abstract

一种通过利用Zn*的某些子群来改进RSA算法的解密速度的密码系统。该密码系统采用基于Zn*的子群中的取幂的新的陷门置换族。

Description

能快速解密的密码系统与方法

技术领域

本发明涉及密码系统、计算机及计算机实现的执行加密与解密运算的方法。更具体地，本发明涉及改进执行解密运算的速度的密码系统。

背景技术

公开密钥密码术是在用其它方法则不安全的通信信道上安全地传输报文的广为使用的方法。公开密钥密码术采用了不对称的密钥对。“不对称”密码密钥对包含两个独立的密钥，第一密钥以一种方式操作数据而第二密钥将操作后的数据转换回其原始形式。这两个密钥是基于其中的一个密钥不能从另一个密钥计算出(至少在任何合理的时间量中)的数学关系的。

密码密钥对可用于不同功能，诸如加密、解密、数字签名、签名检验及鉴定。作为实例，采用不对称密钥对的加密与解密可表示如下：

                        E_Kpub(M)＝C

                        D_Kpri(C)＝M

其中“E_Kpub”为使用公开密钥“Kpub”将明文报文“M”加密成密文“C”的加密函数，而“D_Kpri”则为使用秘密密钥“Kpri”的解密函数。其逆亦真，由于能用秘密密钥“签名”报文并用公开密钥检验签名。

在公开密钥系统中，公开密钥是分配给其它方的而秘密密钥是保密的。不对称公开与秘密密钥保证两种结果。第一，只有秘密密钥的持有者能解密用对应的公开密钥加密的报文。第二，如果另一方用公开密钥解密报文，该方能保证该报文是用秘密密钥加密的并从而推测源自该秘密密钥的持有者。

最知名与最广为使用的不对称密码为用其建立者Rivest、Shamir与Adleman命名的RSA密码学密码。原始RSA密码系统描述在以RivestShamir与Adleman的名义的1983年9月20日公布的名为“密码通信系统与方法”的美国专利4,405,829中。通过引用结合该专利作为背景信息。

加密与解密的RSA密码给出如下：

RSA加密：C＝M^e mod n

RSA解密： $M=C^{1/e\mathrm{mod}(p_1-1)(p_2-1)}\mathrm{mod}n$

其中p₁与p₂为素数，n为形式n＝p₁p₂的合数，而e则为与(p₁-1)(p₂-1)互素的数。

运算“mod”为“模缩减”运算，或简单地说“模”运算，这是大整数算术的普通运算。模运算是算术运算，其结果为除法运算的余数。表示成“A mod B”，其中A为以某一基写出的数而B为“模”。A modB的结果为A除以模B的余数。作为简单的示例，模运算17mod3得出结果2，因为17除以3得出余数2。因为它产生余数，模运算通常也称作“除法余数”运算。

对于传统RSA密码学，解密比加密慢得多。这一差别是由于RAS密码需要比加密同一报文更多的计算来解密同一报文中这一事实。在一些环境中这一差别是不利的。例如，在客户服务器的范围之中，客户机与服务器通常互相交换加密的报文。单个客户机通常享有充分时间与资源来加密报文。不幸的是，服务器并不享受这种奢侈品并有时可能受到其快速解密进入的报文的限制，尤其是在高级客户机请求量的时段中。

从而，存在着改进RAS算法中的解密速度的要求。

发明内容

本发明提供在第一与第二计算单元之间的网络上发送报文的系统中的一种方法，包括下述步骤：

(a)在第一计算单元上将报文M加密成密文C，其中密文C包含值V及值W，如下：

(1)值V为数x的函数V＝x^e，其中e为整数且x如下：

x＝g^R mod n，其中：(i)n为数n＝p₁p₂，其中p₁与p₂为素数且p₁＝r₁q₁+1及p₂＝r₂q₂+1，其中r₁与r₂为随机数且q₁与q₂为素数；

(ii)R为与随机数r₁与r₂无关地选取的随机数；及

(iii)g为形式 $g=r_3^{(p_1-1)(p_2-1)/q_1{q}_2}\mathrm{mod}n$ 的数，其中r₃为与随机数r₁，r₂及R无关地选取的随机数；

(2)值W为值h(x)与报文M的函数，值h(x)为数x的单向函数的结果；

(b)将密文C从第一计算单元发送到第二计算单元；以及

(c)在第二计算单元上解密密文C来再生报文M，其中M为值W与值h(x)的函数且x是作为 $x=V^{(1/e)\mathrm{mod}{q}_1{q}_2}\mathrm{mod}n$ 导出的。

本发明还提供一种能使包含处理模块的计算机将数字报文信号M加密成具有V和W两个分量的数字密文信号C的方法，其中：n为形式n＝p₁p₂的数，其中p₁与p₂为素数；p₁＝r₁q₁+1且p₂＝r₂q₂+1，其中r₁与r₂为随机数且q₁与q₂为素数；及

g为形式 $g=r_3^{(p_1-1)(p_2-1)/\left(q_1{q}_2\right)}\mathrm{mod}n$ 的数，其中r₃为与随机数r₁与r₂无关地选取的随机数；

该方法包括下述步骤：由该处理模块计算数x＝g^R mod n，其中R为与随机数r₁、r₂与r₃无关地选取的随机数；由该处理模块按照数x的函数计算数字分量V；由该处理模块按照单向函数h变换数x产生值h(x)；以及由该处理模块按照值h(x)的函数编码该数字报文信号M，以产生该数字分量W；以及通过组合数字分量V和W而形成该数字密文信号C。

本发明还提供一种能使包含处理模块的计算机将具有V和W两分量的数字密文信号C解密成数字报文信号M的方法，其中：n为形式n＝p₁p₂的数，其中p₁与p₂为素数；p₁＝r₁g₁+1及p₂＝r₂q₂+1，其中r₁与r₂为随机数且q₁与g₂为素数；该方法包括下述步骤：

由该处理模块从数字分量V中复原数X，其中 $X=V^{(1/e)\mathrm{mod}q1q2}\mathrm{mod}n;$ 按照单向函数h，由该处理模块变换数X以产生值h(X)；以及按照值h(X)的函数和该数字分量W，由该处理模块解码该数字密文信号C来恢复数字报文信号M。

本发明还提供在第一与第二计算单元之间的网络上发送报文的系统中的一种方法，包括下述步骤：

(a)在第一计算单元上将报文M加密成密文C，其中该密文C包含值V与值W，如下：

(1)值V为数x的函数V＝x^e，其中e为选自前b个奇素数的整数，而x如下：x＝g^R mod n，其中：

(i)n为数n＝p₁p₂，其中p₁与p₂为素数且p₁＝r₁q₁+1及p₂＝r₂q₂+1，其中q₁与q₂为素数且r₁与r₂为不被前b个奇数素数除尽的随机数；

(ii)R为与随机数r₁与r₂无关地选取的随机数；及

(iii)g为形式 $g=r_3^{(p_1-1)(p_2-1)/\left(q_1{q}_2\right)}\mathrm{mod}n$ 的数，其中r₃为与随机数r₁、r₂及R无关地选取的随机数；

(2)值W为值h(x)与报文M的函数，值h(x)为数x的单向函数的结果；

(b)将密文C从第一计算单元发送到第二计算单元；以及

(C)在第二计算单元上解密密文C来再生报文M，其中M为值W与值h(x)的函数且x是作为 $x=V^{(1/e)\mathrm{mod}{q}_1{q}_2}\mathrm{mod}n$ 导出的。

本发明还提供一种在通信信道上发送报文的系统，包括：

将报文M变换成密文C并在通信信道上传输该密文C的编码器，其中该密文C包含值V与值W，如下：

(1)值V为数x的函数V＝X^e，其中e为整数而x如下：x＝g^R mod n，其中：

(i)n为数＝p₁p₂，其中p₁与p₂为素数且p₁=r₁q₁+1及p₂＝r₂q₂+1，其中r₁与r₂为随机数，而q₁与q₂为素数；

(ii)R为与随机数r₁与r₂无关地选取的随机数；及

(iii)g为形式 $g=r_3^{(p_1-1)(p_2-1)\left(q_1{q}_2\right)}\mathrm{mod}n$ 的数，其中r₃为与随机数r₁、r₂及R无关地选取的随机数；

(2)值W为值h(x)与报文M的函数，值h(x)为数x的单向函数的结果；

以及被耦合以从通信信道接收密文C及值V并将密文C变换回报文M的解码器，其中M为值W与值h(x)的函数且x是作为 $x=V^{(1/e)\mathrm{mod}q1q2}\mathrm{mod}n$ 导出的。

本发明还提供一种用于在通信信道上发送报文的系统，包括：

将报文M变换成密文C及在通信信道上传输密文C的编码器，其中密文C包含如下的值V与值W：

(1)值V为数x的函数V＝x^e，其中e为选自前b个奇素数的整数，而x如下：x＝g^R mod n，其中：

(i)n为数n＝p₁p₂，其中p₁与p₂为素数且p₁＝r₁q₁+1及p₂＝r₂q₂+1，其中q₁与q₂为素数及r₁与r₂为不能被前b个奇素数除尽的随机数；

(ii)R为与随机数r₁与r₂无关地选取的随机数；及

(iii)g为形式 $g=r_3^{(p_1-1)(p_2-1)/\left(q_1{q}_2\right)}\mathrm{mod}n$ 的数，其中r₃为与随机数r₁、r₂及R无关地选取的随机数；

(2)值W为数值h(x)与报文M的函数，值h(x)为数x的单向函数的结果；

被耦合以从通信信道接收报文C与值V并将密文C变换回报文M的解码器，其中M为值W及值h(x)的函数而x是作为 $x=V^{(1/e)\mathrm{mod}{q}_1{q}_2}\mathrm{mod}n$ 导出的。

本发明提供一种用于密码系统的编码器，其中：

n为形式n＝p₁p₂的数，其中p₁与p₂为素数；

p₁＝r₁q₁+1及p₂＝r₂q₂+1，其中r₁与r₂为随机数且q₁与q₂为素数；及

g为形式 $g=r_3^{(p_1-1)(p_2-1)/\left(q_1{q}_2\right)}\mathrm{mod}n$ 的数，其中r₃为与随机数r₁与r₂无关地选取的随机数；

该编码器包括：用于计算数x＝g^R mod n的装置，其中R为与随机数r₁、r₂及r₃无关地选取的随机数；用于按照单向函数h变换数x来产生值h(x)的装置；以及用按照值h(x)的函数编码报文M的装置。

本发明还提供一种用于密码系统的解码器，其中：n为形式n＝p₁p₂的数，其中p₁与p₂为素数；

p₁＝r₁q₁+1及P₂＝r₂q₂+1，其中r₁与r₂为随机数且q₁与q₂为素数；

g为形式 $g=r_3^{(p_1-1)(p_2-1)/\left(q_1{q}_2\right)}\mathrm{mod}n$ 的数，其中r₃为与随机数r₁与r₂无关地选取的随机数；x为形式x＝g^R mod n的数，其中R为与随机数r₁、r₂与r₃无关地选取的随机数；e为整数；V为形式V＝x^e的值；及

W为从报文M与值h(x)的函数导出的值，其中h(x)为单向函数h的结果；

该解码器包括：

用于接收值V与W的装置；

用于从值V复原数x的装置，其中 $x=V^{(1/e)\mathrm{mod}{q}_1{q}_2}\mathrm{mod}n;$

用于按照单向函数h变换数x来产生值h(x)的装置；以及

用于按照值h(x)的一个函数解码值W来恢复报文M的装置。

本发明涉及改进RAS密码中的解密速度的密码学系统与方法。该密码学系统采用基于Zn^*的子群中的取幂的陷门置换(trapdoorpermutation)的新族。

该系统包括编码器，将报文M变换成密文C并在通信信道上传输该密文C。密文C具有两个分量，值V及值W。值V为数x的函数，或V＝x^e，其中e为整数而x如下：x＝g^R mod n，其中：

(i)n是一个数n＝p₁p₂，其中p₁与p₂为素数，p₁＝r₁q₁+1且p₂=r₂q₂+1，其中r₁与r₂为随机数，而q₁与q₂为素数；

(ii)R为与随机数r₁与r₂无关地选取的随机数；以及

(iii)g为形式 $g=r_3^{(p_1-1)(p_2-1)/q_1{q}_2}\mathrm{mod}n$ 的数，其中r₃为与随机数r₁、r₂与R无关地选取的随机数。

值W是作为值h₁(x)与报文M的函数编码的(如h₁(x)M)，其中值h₁(x)为数x的单向函数(例如x的散列(hash)函数)。

编码器还用散列函数h计算数x与报文M的散列值h₂(x，M)。编码器在通信信道上发送密文C(包含值V与W，及散列值h₂(x，M)。

该系统还包括被耦合以从通信信道接收密文C及散列值h₂(x，M)及将密文C变换成报文M的解码器。

解码器首先按照 $x=V^{(1/e)\mathrm{mod}q1q2}\mathrm{mod}n$

从值V导出数x。然后利用值W和值h₁(x)函数(例如WH₁(x))解码报文M。复原报文M之后，解码器从数x与复原的报文M计算出测试散列值h₂’(x，M)，并将该测试散列值h₂’(x，M)与从编码器接收的散列值h₂(x，M)比较。如果两个散列值匹配，报文M便未曾改变。

附图简要描述

图1为密码系统的框图。

图2为实现该密码系统的计算机系统的框图。

图3为示出加密与解密报文的方法中的步骤的流程图。

优选实施例的详细描述

下面的讨论假定读者熟悉密码技术及模运算。对于密码学的基本介绍，引导读者阅读名为“应用密码学：协议、算法及C源码”的BruceSchneier编写的教科书，第二版，1996年版权所有者John Wiley & Sons出版，通过引用将其结合在此。

图1示出具有通过通信信道26耦合在解码器24上的编码器22的密码系统20。该密码系统20采用基于RSA算法的不对称密码学密码。更具体地，该较佳系统为采用RSA陷门置换族的Bellare-Rogaway密码系统。

通常，密码学密码采用包含四个素数p₁、p₂、q₁与q₂的秘密密钥。这些素数相关如下：

p₁＝r₁q₁+1

p₂＝r₂q₂+1

其中r₁与r₂为随机数，它们受到一个要求的制约：即在上式中它们的值得出素数p₁和p₂。

从该秘密密钥生成公开密钥。公开密钥包含三个数n、e与g。数e为整数，而数n与g的计算如下：

n＝p₁p₂

$g=r_3^{(p_1-1)(p_2-1)/q_1{q}_2}\mathrm{mod}n$

其中r₃是与随机数r₁与r₂无关地选取的随机数。虽然并非必要，随机数r₃与r₁和r₂不同。数g为阶q₁q₂的Zn^*的随机元素。

编码器22用由n、e及g构成的公开密钥将报文M编码成密文C。广义地说，密文C为报文M与数x的函数，其中x具有Zn^*中的阶q₁q₂。数x导出如下：

x＝g^R mod n

其中R为与随机数r₁与r₂无关地选取的随机数。虽然并非必要，随机数R非常可能与随机数r₁与r₂不同。密文C具有两个分量，值V与值W。值V为数x的函数，如下：

V＝x^e

值W为值h₁(x)与报文M的函数，其中值h₁(x)为数x的单向函数h₁的结果。作为一个实例，该单向函数实现为散列函数，诸如SHA(安全散列算法)。在一种实现中，值W用“异或”函数计算如下：

W＝h₁(x)M

然而只要该逻辑运算是可逆的，可采用值h₁(x)与M的其它逻辑组合来取代“异或”函数。

编码器22将值V与W组装在一起而构成密文C，并跨越通信信道26将其发送到解码器24。解码器24用秘密密钥从值V中重新计算出数x，数x中包含公开密钥加p₁、p₂、q₁、q₂如下：

$x=V^{(1/e)\mathrm{mod}{q}_1{q}_2}\mathrm{mod}n$

一旦复原了数x，解码器24从值W中恢复报文M如下：

M＝Wh(x)＝h(x)Mh(x)＝M

上述并在系统20中使用的密码学密码的优点在于与标准RSA密码中的解密相比，其解密速度更快。其原因在于用在复原x中的运算

比用在传统的RSA密码中的对应运算

明显地更快。

改进的解密速度是通过采用基于Zn^*的子群中的取幂的陷门置换的新族达到的。上述密码学码利用Zn^*的某一子群。更具体地，密码利用Zn^*的子群(它们是用g生成的)来计算x。这使得在解密方上的计算能具有Zn^*中的阶q₁q₂。

这一密码学密码的缺点在于与标准RSA算法中的加密相比加密过程较慢。这是因为新方案涉及在加密方上导出数x的增加的计算。通过只是有时而不是每一次都计算数x便能减少增加的计算的次数。下面更详细地讨论这一优化。

总体上，这一密码学密码在速度上与RSA密码大致相等。然而，在一些范围中，它对于改进解密过程的速度是有利的，即使这种改进是以较慢的加密为代价的。例如，在客户机一服务器角度上，在服务器上改进解密速度是有益的，即使它是以客户机上较慢的加密为代价得来的。客户机拥有充裕的时间来加密报文而较慢的速度是觉察不到的；然而，在服务器上的解密速度的任何改进都是受到珍视的。

图1的体系结构代表在其中使用加密能力的许多不同环境。例如，在客户机一服务器角度上，可在客户机与服务器两者上都实现编码器22及解码器24以便能使网络上的通信安全，诸如LAN(局域网)、WAN(广域网)、或因特网，作为另一实例，在智能卡的角度上，编码器22可实现在智能卡中而解码器24则可实现在连通的代理商中(诸如计算机，ATM，电话亭，售货机，顾客机等)。这里，信道26表示卡与代理商之间的电子接口。

为了继续讨论的目的，将密码系统20描述成实现在通用计算机中的，诸如个人计算机、服务器、工作站、膝上型计算机等等。

图2示出通用计算机30的示例性实现。计算机30包含处理单元32系统存储器34及将包含系统存储器34在内的各种系统部件耦合在处理单元32上的系统总线36。系统总线36可以是若干类型的总线结构中任何一种，其中包括存储器总线或存储器控制器、外围设备总线及使用多种总线结构中任何一种的局部总线。系统存储器34包含只读存储器(ROM)38及随机存取存储器(RAM)40。基本输入/输出系统42(BIOS)存储在ROM 38中。

通用计算机30还具有下述驱动器中一个或多个：用于读写硬盘的硬盘驱动器44，用于读写可拆卸的磁盘48的磁盘驱动器46，及用于读或写诸如CD ROM或其它光学介质等可拆卸的光盘52的光盘驱动器50。硬盘驱动器44、磁盘驱动器46及光盘驱动器50分别用硬盘驱动器接口54、磁盘驱动器接口56、及光学驱动器接口58连接在系统总线36上。这些驱动器与它们所关联的计算机可读的介质提供计算机可读的指令、数据结构、程序模块及用于通用计算机30的其它数据的非易失性存储。

虽然描述了可拆卸的磁盘48及可拆卸的光盘52，熟悉本技术的人员应理解也能用其它类型的计算机可读的介质来存储数据。其它介质包括盒式磁带、快速存储卡、数字视盘、Bernoulli盒式存储器、随机存取存储器(RAM)、只读存储器(ROM)等等。

可将若干程序模块存储在硬盘、磁盘48、光盘52、ROM38或RAM40上。这些程序包含操作系统60、一或多个应用程序62、其它程序模块64及程序数据66。

用户可通过诸如键盘68及鼠标器70等输入设备输入命令与信息到通用计算机30中。其它输入设备(未示出)可包含麦克风、操纵杆、游戏盘、卫星碟、扫描器等等。这些及其它输入设备通常通过耦合在系统总线36上的串行端口接口72连接在处理单元32上，但也可用诸如并行端口、游戏端口、或通用串行总线(USB)等其它接口连接。

监视器74或其它类型的显示设备也通过诸如视频适配器76等接口连接在系统总线36上。除了监视器之外，个人计算机通常还包括诸如扬声器与打印机等其它外围输出设备(未示出)。

通用计算机30具有网络接口或适配器78、调制解调器80或其它用于在网络82(如LAN、因特网等)上建立通信的装置。调制解调器80，可以是内置或外置的，通过串行端口接口72连接在系统总线36上。

密码系统20可作为软件、固件或硬件实现在计算机30中。例如，编码器22及解码器24可实现在操作系统60、应用程序62或程序模块64(诸如DLL-动态链接库)中。作为替代，编码器22及解码器24可实现在ROM38中。在又另一实施例中，编码器22与解码器24可实现在处理单元22内。

图3示出利用密码系统20加密与解密报文的方法的示范步骤。如图3中所图示的，步骤100、102、104和106是由编码器22执行的而步骤108、110、112和114是由解码器24执行的。编码器22知道从秘密密钥导出的公开密钥(即素数n、e与g)。可将这些密钥存储在存储器或寄存器中。解码器24知道秘密密钥(即数p₁、p₂、q₁与q₂)。

在步骤100上，编码器22计算作为g、阶q₁q₂的Zn*的随机元素的函数的数x。更具体地编码器22计算x如下：

x=g^R mod n

其中R为一随机数。

在步骤102上，编码器编码报文M产生密文C。这一编码包含生成值V与W，其中V＝x^e而W＝h₁(x)M。值h₁(x)为数x的第一散列函数h₁的结果。密文C包括值V与W。

在步骤104上，编码器22计算另一散列值h₂(x，M)，这是数x与报文M的第二散列函数h₂的结果。解码器24用这一值来检验报文M是否已被改变或在编码器与解码器之间的路途上受到损害。在步骤106上，编码器22在通信信道26上将密文C(即，V＝x^e及W=h₁(x)M)与第二散列值h₂(x，M)传输给解码器24。

在步骤108上，解码器24接收密文C与第二散列值h₂(x，M)。在步骤110上，解码器24随即从密文C的值V分量(即V＝x^e)中重新计算数x，如下：

$x=V^{(1/e)\mathrm{mod}{q}_1{q}_2}\mathrm{mod}n$

一旦复原了数x，解码器24用编码器22所采用的同一第一散列函数h₁计算散列值h₁(x)。在步骤112上，解码器24从密文C的值W分量中复原报文M，如下：

M＝Wh₁(x)

在步骤114上，解码器24取复原的数x与复原的报文M并用编码器所采用的同一第二散列函数h₂计算测试散列值h₂’(x，M)。如果测试散列值h₂’(x，M)等于从编码器22接收的散列值h₂(x，M)，解码器24确信报文M并未改变。

上述加密/解密过程可用下述伪代码表示。在加密/解密步骤之前可执行一次密钥计算来建立密钥值。密钥可根据需要更新。

密钥计算

int e，r₁，r₂，r₃

prime int p₁，p₂，q₁，q₂

p₁←r₁q₁+1

p₂←r₂q₂+1

n←p₁p₂

g←r₃ ^{(p1-1)(p2-1)/q1q2} mod n

加密

Function E(M，V，W，HV)\*M是一个输入参数*\

                       \*V，W和HV是输出参数*\

int R

x←g^R mod n

V←x^e mod n

W←h₁(x)M

HV←h₂(x，M)

return V，W，HV

解密

Function D(V，W，HV，M)\*V，W和HV是输入参数*\

                       \*M是输出参数*\

x←V^{(1/e)mod q1q2} mod n

M←Wh₁(x)

HV_test＝h₂(x，M)

Compare HV_test＝HV

return M

在一种实现中，将整数“e”设定为2，从而陷门置换的新族是基于Z_n*的子群的求平方的。

该密码方案的缺点之一在于加密过程比传统RSA加密慢，因为编码器要计算作为Zn*的随机元素的g的函数的数x。推导数x需要在传统的RSA加密中没有的附加计算。

改进加密阶段的速度的一种方法是计算数x一次而在下一次加密中利用该旧数x生成新数x。具体地，改进包含为每一次新的加密改变数x，其方式为比为每一次新加密重新计算g^R mod n有较低计算密集性。一种从旧数x生成新数x的方法如下：

x←x^k exp(i)，其中“k exp(i)”表示kⁱ。

编码器计算数x(即x＝g^R mod n)并将数x存储在存储器或寄存器中供以后使用。对于每一次以后的加密，编码器通过计算x^k exp(i)改变x，并选择值“i”使得当x改变时值V保持不变。然后编码器将值i连同值V一起发送给解码器供在复原值x中使用。

这一在若干次加密上分摊计算值x的过程减少了在各编码过程中的计算次数。密码系统保持了编码器的前面保密性，从而如果泄露了数x不会泄露过去的报文，但未来的报文可能泄露。编码器可在任何时间间隔上或它认为必要的任何时间上完全重新计算数x。

上述密码系统也能用来改进作为RSA的知名改进型的批量RSA的解密速度。密码系统类似于上述的，但不同之处在于用来推导素数P1与P2的随机数r₁与r₂进一步受到限制不被前b个素数除尽，其中b为解密批量大小。

对于批量RSA，数x仍导出如下：

x＝g^R mod n

然后计算值V如下：

V＝x^e mod n

其中e＝第(i+1)个奇素数而i来自Zb。

在解密方上，值x复原如下：

$x=V^{(1/e)\mathrm{mod}{q}_1{q}_2}\mathrm{mod}n$

上述对批量RSA的修改能使解密更快，因为在批量逆运算期间，能将幂缩减成模q₁q₂。

虽然己用结构特征与/或方法学步骤的特定语言描述了本发明，应理解所附权利要求书中所定义的发明没有必要限于这些描述的特定特征或步骤。反之，这些特定特征与步骤是作为实现所要求的发明的较佳方式公开的。

Claims (14)

1、一种在一个系统中通过网络在第一与第二计算单元之间发送报文的方法，包括下述步骤：

(a)在第一计算单元上将报文M加密成密文C，其中密文C包含如下的值V及值W：

(1)值V为数x的函数V＝x^e，其中e为整数且x如下：

x＝g^Rmod n，其中：

(i)n为数n＝p₁p₂，其中p₁与p₂为素数且p₁＝r₁q₁+1及p₂＝r₂q₂+1，其中r₁与r₂为随机数且q₁与q₂为素数；

(ii)R为与随机数r₁与r₂无关地选取的随机数；及

(iii)g为形式 $g={r_3}^{(p_1-1)(p_2-1)/q_1{q}_2}\mathrm{mod}n$ 的数，其中r₃为与随机数r₁，r₂及R无关地选取的随机数；

(2)值W为值h(x)与报文M的函数，值h(x)为数x的单向函数的结果；

(b)将密文C从第一计算单元发送到第二计算单元；以及

(c)在第二计算单元上解密密文C来再生报文M，其中M为值W与值h(x)的函数且x是作为 $x=V^{(1/e)\mathrm{mod}{q}_1{q}_2}\mathrm{mod}n$ 导出的。

2、如权利要求1所述的方法，其中该加密步骤(a)包括作为W＝h(x)M导出值W的步骤。

3、如权利要求2所述的方法，其中该解密步骤(c)包括作为M＝Wh(x)导出报文M的步骤。

4、如权利要求1所述的方法，其中，整数e等于2。

5、如权利要求1所述的方法，其中：

该加密步骤(a)包括从数x与报文M的散列函数h中计算散列值h(x，M)的步骤；

该发送步骤(b)包括将散列值h(x，M)连同密文C从第一计算单元发送到第二计算单元的步骤；以及

该解密步骤(c)包括从导出的数x与再生的报文M的散列函数h计算出测试散列值h’(x，M)及将从第一计算单元接收的散列值h(x，M)与测试散列值h’(x，M)进行比较来检验报文M是否曾被改变的步骤。

6、如权利要求1所述的方法，其中该加密步骤(a)包括下述步骤：

存储数x；

根据旧数x生成新数x’；以及

使用新数x’加密下一个报文。

7、如权利要求1所述的方法，其中，整数e选自前b个奇素数以及不被前b个奇素数除尽的随机数r1和r2。

8、一种能使包含处理模块的计算机将数字报文信号M加密成具有V和W两个分量的数字密文信号C的方法，其中：

n为形式n＝p₁p₂的数，其中p₁与p₂为素数；

p₁＝r₁q₁+1且p₂＝r₂q₂+1，其中r₁与r₂为随机数且q₁与q₂为素数；及

g为形式 $g={r_3}^{(p_1-1)(p_2-1)/\left(q_1{q}_2\right)}\mathrm{mod}n$ 的数，其中r₃为与随机数r₁与r₂无关地选取的随机数；

该方法包括下述步骤：

由该处理模块计算数x＝g^Rmod n，其中R为与随机数r₁、r₂与r₃无关地选取的随机数；

由该处理模块按照数x的函数计算数字分量V；

由该处理模块按照单向函数h变换数x产生值h(x)；以及

由该处理模块按照值h(x)的函数编码该数字报文信号M，以产生该数字分量W；以及

通过组合数字分量V和W而形成该数字密文信号C。

9、如权利要求8所述的方法，其中该编码步骤包括计算h(x)M的步骤。

10、如权利要求8所述的方法，还包括从数x与报文M的散列函数h计算散列值h(x，M)的步骤。

11、如权利要求8所述的方法，还包括下述步骤：

存储数x；

根据旧数x生成新数x’；以及

利用新数x’加密下一个报文。

12、一种能使包含处理模块的计算机解密具有V和W两分量的数字密文信号C以再生数字报文信号M的方法，其中：

n为形式n＝p₁p₂的数，其中p₁与p₂为素数；

p₁＝r₁q₁+1及p₂＝r₂q₂+1，其中r₁与r₂为随机数且q₁与q₂为素数；

该方法包括下述步骤：

由该处理模块从数字分量V中复原数x，其中x＝V^(1/e)modq1q2modn；

按照单向函数h，由该处理模块变换数x以产生值h(x)；以及

按照值h(x)的函数和该数字分量W，由该处理模块解码该数字密文信号C来恢复数字报文信号M。

13、如权利要求12所述的方法，其中该解码步骤包括计算Ch(x)的步骤。

14、如权利要求12所述的方法，还包括从数x与恢复的报文M的散列函数h计算散列值h(x，M)的步骤。

Images