[go: up one dir, main page]

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

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

Info

Publication number
CN1281607A
CN1281607A CN98811894A CN98811894A CN1281607A CN 1281607 A CN1281607 A CN 1281607A CN 98811894 A CN98811894 A CN 98811894A CN 98811894 A CN98811894 A CN 98811894A CN 1281607 A CN1281607 A CN 1281607A
Authority
CN
China
Prior art keywords
value
computer
message
random number
function
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN98811894A
Other languages
English (en)
Other versions
CN1282325C (zh
Inventor
戴威
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Microsoft Corp
Original Assignee
Microsoft Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Microsoft Corp filed Critical Microsoft Corp
Publication of CN1281607A publication Critical patent/CN1281607A/zh
Application granted granted Critical
Publication of CN1282325C publication Critical patent/CN1282325C/zh
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
    • H04L9/302—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3236—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using cryptographic hash functions
    • H04L9/3239—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using cryptographic hash functions involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/08—Randomization, e.g. dummy operations or using noise

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computing Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Storage Device Security (AREA)
  • Mobile Radio Communication Systems (AREA)
  • Transmission Systems Not Characterized By The Medium Used For Transmission (AREA)

Abstract

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

Description

能快速解密的密码系统与方法
技术领域
本发明涉及密码系统、计算机及计算机实现的执行加密与解密运算的方法。更具体地，本发明涉及改进执行解密运算的速度的密码系统。
发明背景
公开密钥密码学是在否则不安全的通信信道上安全地传输报文的广为使用的方法。公开密钥密码学采用了不对称的密钥对。“不对称”密码密钥对包含两个独立的密钥，第一密钥以一种方式操作数据而第二密钥将操作后的数据转换回其原始形式。这两个密钥是基于其中的一个密钥不能从另一个密钥计算出(至少在任何合理的时间量中)的数学关系的。
密码密钥对可用于不同功能，诸如加密、解密、数字签名、签名检验及鉴定。作为实例，采用不对称密钥对的加密与解密可表示如下：
                    EKpub(M)=C
                    DKpri(C)=M
其中“EKpub”为使用公开密钥“Kpub”将明文报文“M”加密成密文“C”的加密函数，而“DKpri”则为使用秘密密钥“Kpri”的解密函数。其逆亦真，由于能用秘密密钥“签名”报文并用公开密钥检验签名。
在公开密钥系统中，公开密钥是分配给其它方的而秘密密钥是保密的。不对称公开与秘密密钥保证两种结果。第一，只有秘密密钥的持有者能解密用对应的公开密钥加密的报文。第二，如果另一方用公开密钥解密报文，该方能保证该报文是用秘密密钥加密的并从而推测源自该秘密密钥的持有者。
最知名与最广为使用的不对称密码为用其建立者Rivest、Shamir与Adleman命名的RSA密码学密码。原始RSA密码系统描述在以RivestShamir与Adleman的名义的1983年9月20日提交的名为“密码通信系统与方法”的美国专利4，405，829中。通过引用结合该专利作为背景信息。
加密与解密的RSA密码给出如下：
RAS加密：C=Memodn
RAS解密：M=C1/emod(p1-1)(p2-1) modn
其中p1与p2为素数，n为形式n=p1p2的合数，而e则为与(p1-1)(p2-1)互素的数。
运算“mod”为“模缩减”运算，或简单地说“模”运算，这是大整数算术的普通运算。模运算是算术运算，其结果为除法运算的余数。表示成“A mod B”，其中A为以某一基写出的数而B为“模”。A modB的结果为A除以模B的余数。作为简单的示例，模运算17mod3得出结果2，因为17除以3得出余数2。因为它产生余数，模运算通常也称作“除法余数”运算。
对于传统RAS密码学，解密比加密慢得多。这一差别是由于RAS密码需要比加密同一报文更多的计算来解密同一报文中这一事实。在一些环境中这一差别是不利的。例如，在客户服务器的范围之中，客户机与服务器通常互相交换加密的报文。单个客户机通常享有充分时间与资源来加密报文。不幸的是，服务器并不享受这种奢侈品并有时可能受到其快速解密进入的报文的限制，尤其是在高级客户机请求量的时段中。
从而，存在着改进RAS算法中的解密速度的要求。
发明概述
本发明涉及改进RAS密码中的解密速度的密码学系统与方法。该密码学系统采用基于Zn*的子群中的取幂的陷门置换(trapdoorpermutation)的新族。
该系统包括编码器，将报文M变换成密文C并在通信信道上传输该密文C。密文C具有两个分量，值V及值W。值V为数x的函数，或V=xe，其中e为整数而x如下：
              x=gRmodn，其中：
(ⅰ)n是一个数n=p1p2，其中p1与p2为素数，p1=r1q1+1且p2=r2q2+1，其中r1与r2为随机数，而q1与q2为素数；
(ⅱ)R为与随机数r1与r2无关地选取的随机数；以及
(ⅲ)g为形式g=r3(p1-1)(p2-1)/q1q2 modn的数，其中r3为与随机数r1、r2与R无关地选取的随机数。
值W是作为值h1(x)与报文M的函数编码的(如h1(x)_M)，其中值h1(x)为数x的单向函数(例如x的散列(hash)函数)。
编码器还用散列函数h计算数x与报文M的散列值h2(x，M)。编码器在通信信道上发送密文C(包含值V与W，及散列值h2(x，M)。
该系统还包括耦合成从通信信道接收密文C及散列值h2(x，M)及将密文C变换成报文M的解码器。解码器首先按照x=V(1/e)modq1q2 modn从值V导出数x。然后利用值W和值h1(x)函数(例如W_H1(x))解码报文M。复原报文M之后，解码器从数x与复原的报文M计算出测试散列值h2’(x，M)，并将该测试散列值h2’(x，M)与从编码器接收的散列值h2(x，M)比较。如果两个散列值匹配，报文M便未曾改变。
附图简要描述
图1为密码系统的框图。
图2为实现该密码系统的计算机系统的框图。
图3为示出加密与解密报文的方法中的步骤的流程图。
优选实施例的详细描述
下面的讨论假定读者熟悉密码技术及模运算。对于密码学的基本介绍，引导读者阅读名为“应用密码学：协议、算法及C源码”的BruceSchneier编写的教科书，第二版，1996年版权所有者John Wiley & Sons出版，通过引用将其结合在此。
图1示出具有通过通信信道26耦合在解码器24上的编码器22的密码系统20。该密码系统20采用基于RSA算法的不对称密码学密码。更具体地，该较佳系统为采用RSA陷门置换族的Bellare-Rogaway密码系统。
通常，密码学密码采用包含四个素数p1、p2、q1与q2的秘密密钥。这些素数相关如下：
 p1=r1q1+1
 p2=r2q2+1
其中r1与r2为随机数，它们受上式中它们的值得出素数p1与p2的要求的制约。
从该秘密密钥生成公开密钥。公开密钥包含三个数n、e与g。数e为整数，而数n与g的计算如下：
n=p1p2
g=r3(p1-1)(p2-1)/q1q2 modn
其中r3是与随机数r1与r2无关地选取的随机数。虽然并非必要，随机数r3与r1和r2不同。数g为阶q1q2的Zn*的随机元素。
编码器22用由n、e及g构成的公开密钥将报文M编码成密文C。广义地说，密文C为报文M与数x的函数，其中x具有Zn*中的阶q1q2。数x导出如下：
x=gRmodn
其中R为与随机数r1与r2无关地选取的随机数。虽然并非必要，随机数R非常可能与随机数r1与r2不同。密文C具有两个分量，值V与值W。值V为数x的函数，如下：
V=xe
值W为值h1(x)与报文M的函数，其中值h1(x)为数x的单向函数h1的结果。作为一个实例，该单向函数实现为散列函数，诸如SHA(安全散列算法)。在一种实现中，值W用“异或”函数计算如下：
W=h1(x)_M
然而只要该逻辑运算是可逆的，可采用值h1(x)与M的其它逻辑组合来取代“异或”函数。
编码器22将值V与W组装在一起而构成密文C，并跨越通信信道26将其发送到解码器24。解码器24用秘密密钥从值V中重新计算出数x，数x中包含公开密钥加p1、p2、q1、q2如下：
x=V(1/e)modq1q2 modn
一旦复原了数x，解码器24从值W中恢复报文M如下：
M=W_h(x)=h(x)_M_h(x)=M
上述并在系统20中使用的密码学密码的优点在于与标准RSA密码中的解密相比，其解密速度更快。其原因在于用在复原x中的运算“V(1/e)modq1q2 modn”比用在传统的RSA密码中的对应运算“C(1/e)mod(p1-1)(p2-1) modn”明显地更快。
改进的解密速度是通过采用基于Zn*的子群中的取幂的陷门置换的新族达到的。上述密码学码利用Zn*的某一子群。更具体地，密码利用Zn*的子群(它们是用g生成的)来计算x。这使得在解密方上的计算能具有Zn*中的阶q1q2。
这一密码学密码的缺点在于与标准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)存储在ROM38中。
计算机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或其它类型的显示设备也通过诸如视频适配器75等接口连接在系统总线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-106是由编码器22执行的而步骤108-114是由解码器24执行的。编码器22知道从秘密密钥导出的公开密钥(即素数n、e与g)。可将这些密钥存储在存储器或寄存器中。解码器24知道秘密密钥(即数p1、p2、q1与q2)。
在步骤100上，编码器22计算作为g、阶q1q2的Zn*的随机元素的函数的数x。更具体地编码器22计算x如下：
x=gRmodn
其中R为一随机数。
在步骤102上，编码器编码报文M产生密文C。这一编码包含生成值V与W，其中V=xe而W=h1(x)_M。值h1(x)为数x的第一散列函数h1的结果。密文C包括值V与W。
在步骤104上，编码器22计算另一散列值h2(x，M)，这是数x与报文M的第二散列函数h2的结果。解码器24用这一值来检验报文M是否已被改变或在编码器与解码器之间的路途上受到损害。在步骤106上，编码器22在通信信道26上将密文C(即，V=xe及W=h1(x)_M)与第二散列值h2(x，M)传输给解码器24。
在步骤108上，解码器24接收密文C与第二散列值h2(x，M)。在步骤110上，解码器24随即从密文C的值V分量(即V=xe)中重新计算数x，如下：
x=V(1/e)moaq1q2 modn
一旦复原了数x，解码器24用编码器22所采用的同一第一散列函数h1计算散列值h1(x)。在步骤112上，解码器24从密文C的值W分量中复原报文M，如下：
M=W_h1(x)
在步骤114上，解码器24取复原的数x与复原的报文M并用编码器所采用的同一第二散列函数h2计算测试散列值h2’(x，M)。如果测试散列值h2’(x，M)等于从编码器22接收的散列值h2(x，M)，解码器24确信报文M并未改变。
上述加密/解密过程可用下述伪代码表示。在加密/解密步骤之前可执行一次密钥计算来建立密钥值。密钥可根据需要更新。
密钥计算
        int e，r1，r2，r3
        prime int p1，p2，q1，q2
        p1←r1q1+1
        p2←r2q2+1
        n←p1p2
        g←r3(p1-1)(p2-1)/q1q2  mod n
加密Function E(M，V，W，HV)\*M是一个输入参数*\
                    \*V，W和HV是输出参数*\int Rx←gR mod nV←xe mod nW←h1(x)_MHV←h2(x，M)return V，W，HV解密
Function D(V，W，HV，M)\*V，W和HV是输入参数*\
x←V(1/e)mod q1q2  mod n.\*M是输出参数*\
M←W_h1(x)
HVtest=h2(x，M)
Compare HVtest=HVreturn M
在一种实现中，将整数“e”设定为2，从而陷门置换的新族是基于Zn*的子群的求平方的。
该密码方案的缺点之一在于加密过程比传统RSA加密慢，因为编码器要计算作为Zn*的随机元素的g的函数的数x。推导数x需要在传统的RSA加密中没有的附加计算。
改进加密阶段的速度的一种方法是计算数x一次而在下一次加密中利用该旧数x生成新数x。具体地，改进包含为每一次新的加密改变数x，其方式为比为每一次新加密重新计算gR mod n有较低计算密集性。一种从旧数x生成新数x的方法如下：
x←xK exp(i)，其中“k exp(i)”表示ki。
编码器计算数x(即x=gR mod n)并将数x存储在存储器或寄存器中供以后使用。对于每一次以后的加密，编码器通过计算xK exp(i)改变x，并选择值“i”使得当x改变时值V保持不变。然后编码器将值i连同值V一起发送给解码器供在复原值x中使用。
这一在若干次加密上分摊计算值x的过程减少了在各编码过程中的计算次数。密码系统保持了编码器的前面保密性，从而如果泄露了数x不会泄露过去的报文，但未来的报文可能泄露。编码器可在任何时间间隔上或它认为必要的任何时间上完全重新计算数x。
上述密码系统也能用来改进作为RSA的知名改进型的批量RSA的解密速度。密码系统类似于上述的，但不同之处在于用来推导素数P1与P2的随机数r1与r2进一步受到限制不被前b个素数除尽，其中b为解密批量大小。
对于批量RSA，数x仍导出如下：
x=gR mod n
然后计算值V如下：
V=xe mod n
其中e=第(i+1)个奇素数而i来自Zb。
在解密方上，值x复原如下：
            x=V(1/e)mod q1q2  mod n
上述对批量RSA的修改能使解密更快，因为在批量逆运算期间，能将幂缩减成模q1q2。
虽然已用结构特征与/或方法学步骤的特定语言描述了本发明，应理解所附权利要求书中所定义的发明没有必要限于这些描述的特定特征或步骤。反之，这些特定特征与步骤是作为实现所要求的发明的较佳方式公开的。

Claims (43)

1、在第一与第二计算单元之间的网络上发送报文的系统中的一种方法，包括下述步骤：
(a)在第一计算单元上将报文M加密成密文C，其中密文C包含值V及值W，如下：(1)值V为数x的函数V=xe，其中e为整数且x如下：
x=gRmod n，其中：
(ⅰ)n为数n=p1p2，其中p1与p2为素数且p1=r1q1+1及p2=r2q2+1，其中r1与r2为随机数且q1与q2为素数；
(ⅱ)R为与随机数r1与r2无关地选取的随机数；及
(ⅲ)g为形式g=r3(p1-1)(p2-1)/q1q2 modn的数，其中r3为与随机数r1，r2及R无关地选取的随机数；
(2)值W为值h(x)与报文M的函数，值h(x)为数x的单向函数的结果；
(b)将密文C从第一计算单元发送到第二计算单元；以及
(c)在第二计算单元上解密密文C来再生报文M，其中M为值W与值h(x)的函数且x是作为x=V(1/e)modq1q2 modn导出的。
2、权利要求1中所述的方法，其中该加密步骤包括作为W=h(x)_M导出值的步骤。
3、如权利要求2中所述的方法，其中该解密步骤包括作为M=W_h(x)导出报文M的步骤。
4、如权利要求1中所述的方法，其中，其中整数e等于2。
5、权利要求1中所述的方法，其中：
该加密步骤包括从数x与报文M的散列函数h中计算散列值h(x，M)的步骤；
该发送步骤包括将散列值h(x，M)连同密文C从第一计算单元发送到第二计算单元的步骤；以及
该解密步骤包括从导出的数x与再生的报文M的散列函数h计算出测试散列值h’(x，M)及将从第一计算单元接收的散列值h(x，M)与测试散列值h’(x，M)进行比较来检验报文M是否曾被改变的步骤。
6、如权利要求1中所述的方法，其中该加密步骤包括下述步骤：
存储数x；
根据旧数x生成新数x；以及
使用新数x加密下一个报文。
7、一种将报文M加密成密文C的方法，其中：
n为形式n=p1p2的数，其中p1与p2为素数：
p1=r1q1+1且p2=r2q2+1，其中r1与r2为随机数且q1与q2为素数；及
g为形式g=r3(p1-1)(p2-1)/q1q2  modn的数，其中r3为与随机数r1与r2无关地选取的随机数；
该方法包括下述步骤：
计算数x=gRmod n，其中R为与随机数r1、r2与r3无关地选取的随机数；
按照单向函数h变换数x产生值h(x)；以及
按照值h(x)的函数编码报文M。
8、如权利要求7中所述的方法，其中该编码步骤包括计算h(x)_M的步骤。
9、权利要求7中所述的方法，还包括从数x与报文M的散列函数h计算散列值h(x，M)的步骤。
10、权利要求7中所述的方法，还包括下述步骤：
存储数x；
根据旧数x生成新数x；以及
利用新数x加密下一个报文。
11、一种计算机可读的介质，包括用于执行权利要求7中所述的方法中的步骤的计算机可执行的指令。
12、一种以用于执行权利要求7中所述的步骤的计算机可执行的指令编程的计算机。
13、一种用于解密密文C来再生报文M的方法，其中：
n为形式n=p1p2的数，其中p1与p2为素数；
p1=r1q1+1及p2=r2q2+1，其中r1与r2为随机数且q1与q2为素数；
g为形式g=r3(p1-1)(p2-1)/q1q2 modn的数，其中r3为与随机数r1与r2无关地选取的随机数；
x为形式x=gRmodn的数，其中R为与随机数r1、r2及r3无关地选取的随机数；
e为一整数；及
V为形式V=xe的值；
该方法包括下述步骤：
从值V中复原数x，其中x=V(1／e)modq1q2 modn；
按照单向函数h变换数x以产生值h(x)；以及
按照值h(x)的函数解码密文C来恢复报文M。
14、按照权利要求13中所述的方法，其中该解码步骤包括计算C_h(x)的步骤。
15、如权利要求13中所述的方法，还包括从数x与恢复的报文M的散列函数h计算散列值h(x，M)的步骤。
16、一种包括用于执行权利要求13中所述的方法中的步骤的计算机可执行的指令的计算机可读的介质。
17、一种以用于执行权利要求13中所述的方法中的步骤的计算机可执行的指令编程的计算机。
18、在第一与第二计算单元之间的网络上发送报文的系统中的一种方法，包括下述步骤：
(a)在第一计算单元上将报文M加密成密文C，其中该密文C包含值V与值W，如下：
(1)值V为数x的函数V=xe，其中e为选自前b个奇素数的整数，而x如下：
x=gRmodn，其中：
(ⅰ)n为数n=p1p2，其中p1与p2为素数且p1=r1q1+1及p2=r2q2+1，其中q1与q2为素数且r1与r2为不被前b个奇数素数除尽的随机数；
(ⅱ)R为与随机数r1与r2无关地选取的随机数；及
(ⅲ)g为形式g=r3(p1-1)(p2-1)／q1q2 modn的数，其中r3为与随机数r1、r2及R无关地选取的随机数；
(2)值W为值h(x)与报文M的函数，值h(x)为数x的单向函数的结果；
(b)将密文C从第一计算单元发送到第二计算单元；以及
(C)在第二计算单元上解密密文C来再生报文M，其中M为值W与值h(x)的函数且x是作为x=V(1/e)modq1q2 modn导出的。
19、在采用RSA陷门置换族的Bellare-Rogaway密码系统中，通过用基于在Zn*的子群中取幂的陷门置换族取代RSA陷门置换族来改进解密的方法。
20、一种包括用于执行权利要求19中所述的方法中的步骤的计算机可执行的指令的计算机可读的介质。
21、一种从用于执行权利要求19中所述的方法中的步骤的计算机可执行的指令编程的计算机。
22、一种在通信信道上发送报文的系统，包括：
将报文M变换成密文C并在通信信道上传输该密文C的编码器，其中该密文C包含值V与值W，如下：
(1)值V为数x的函数V=Xe，其中e为整数而x如下：
x=gRmodn，其中：
(ⅰ)n为数=p1p2，其中p1与p2为素数且p1=r1q1+1及p2=r2q2+1，其中r1与r2为随机数，而q1与q2为素数；
(ⅱ)R为与随机数r1与r2无关地选取的随机数；及
(ⅲ)g为形式g=r3(p1-1)(p2-1)/q1q2 modn的数，其中r3为与随机数r1、r2及R无关地选取的随机数；
(2)值W为值h(x)与报文M的函数，值h(x)为数x的单向函数的结果：
以及耦合成从通信信道接收密文C及值V并将密文C变换回报文M的解码器，其中M为值W与值h(x)的函数且x是作为x=V(1/e)modq1q2 modn导出的。
23、权利要求22中所述的系统，其中该编码器作为W=h(x)_M导出值W。
24、权利要求23中所述的系统，其中该解码器作为M=W_h(x)导出报文M。
25、权利要求22中所述的系统，其中整数e等于2。
26、权利要求22中所述的系统，其中：
编码器从数x与报文M的散列函数h计算出散列值h(x，M)并连同密文C一起传输散列值h(x，M)；以及
解码器从导出的数x与再生的报文M的散列函数h计算出测试散列值h’(x，M)，并将从第一计算单元接收的散列值h(x，M)与测试散列值h’(x，M)比较来检验报文M是否已被改变。
27、权利要求22中的所述的系统，其中该编码器存储数x，根据旧数x生成新数x，及用该新数x计算值V与W。
28、一种用于密码系统的编码器，其中：
n为形式n=p1p2的数，其中p1与p2为素数；
p1=r1q1+1及p2=r2q2+1，其中r1与r2为随机数且q1与q2为素数；及
g为形式g=r3(p1-1)(p2-1)/q1q2 modn的数，其中r3为与随机数r1与r2无关地选取的随机数；
该编码器包括：
用于计算数x=gRmodn的装置，其中R为与随机数r1、r2及r3无关地选取的随机数；
用于按照单向函数h变换数x来产生值h(x)的装置；以及用按照值h(x)的函数编码报文M的装置。
29、如权利要求28中所述的编码器，其中该编码装置按照h(x)_M编码报文M。
30、如权利要求28中所述的编码器，还包括：
用于存储数x的装置
用于根据旧数x生成新数x的装置；以及
用于利用新数x导出值h(x)的装置。
31、一种用于密码系统的解码器，其中：
n为形式n=p1p2的数，其中p1与p2为素数；
p1=r1q1+1及p2=r2q2+1，其中r1与r2为随机数且q1与q2为素数：
g为形式g=r3(p1-1)(p2-1)/q1q2 modn的数，其中r3为与随机数r1与r2无关地选取的随机数；
x为形式x=gRmodn的数，其中R为与随机数r1、r2与r3无关地选取的随机数；
e为整数；
V为形式V=xe的值；及
W为从报文M与值h(x)的函数导出的值，其中h(x)为单向函数h的结果；
该解码器包括：
用于接收值V与W的装置；
用于从值V复原数x的装置，其中x=V(1/e)modq1q2 modn；
用于按照单向函数h变换数x来产生值h(x)的装置；以及
用于按照值h(x)的一个函数解码值W来恢复报文M的装置。
32、权利要求31中所述的解码器，其中该解码装置计算函数W_h(x)来恢复报文M。
33、权利要求31中所述的解码器，还包括用于从数x与恢复的报文M的散列函数h计算散列值h(x，M)的装置。
34、一种用于在通信信道上发送报文的系统，包括：
将报文M变换成密文C及在通信信道上传输密文C的编码器，其中密文C包含如下的值V与值W：
(1)值V为数x的函数V=xe，其中e为选自前b个奇素数的整数，而x如下：
x=gRmodn，其中：
(ⅰ)n为数n=p1p2，其中p1与p2为素数且p1=r1q1+1及p2=r2q2+1，其中q1与q2为素数及r1与r2为不能被前b个奇素数除尽的随机数；
(ⅱ)R为与随机数r1与r2无关地选取的随机数；及
(ⅲ)g为形式g=r3(p1-1)(p2-1)/q1q2 modn的数，其中r3为与随机数r1、r2及R无关地选取的随机数；
(2)值W为数值h(x)与报文M的函数，值h(x)为数x的单向函数的结果；
(3)耦合成从通信信道接收报文C与值V并将密文C变换回报文M的解码器，其中M为值W及值h(x)的函数而是x作为x=V(1/e)modq1q2 modn导出的。
35、一种采用RSA陷门置换族的Bellare-Rogaway密码系统，其特征在于用基于Zn *的子群中的取幂的陷门置换的族取代RSA陷门置换族。
36、一种具有指导计算机将报文M加密成密文C的计算机可执行的指令的计算机可读的介质，其中：
n为形式n=p1p2的数，其中p1与p2为素数；
p1=r1q1+1及p2=r2q2+1，其中r1与r2为随机数且q1与q2为素数；及
g为形式g=r3(p1-1)(p2-1)/q1q2 modn的数，其中r3为与随机数r1、r2及
R无关地选取的随机数；
该计算机可读的介质包括：
指导计算机计算数x=gRmodn的计算机可执行的指令，其中R为与随机数r1、r2及r3无关地选取的随机数；
指导计算机按照单向函数h变换数x来产生值h(x)的计算机可执行的指令；以及
指导计算机按照值h(x)的函数编码报文M的计算机可执行的指信。
37、权利要求36中所述的计算机可读的介质，还包括指导计算机按照函数h(x)_M编码报文M的计算机可执行的指令。
38、权利要求36中所述的计算机可读的介质，还包括指导计算机存储数x，根据旧数x生成新新x及利用该新数x导出值h(x)的计算机可执行的指令。
39、一种编程成执行在权利要求36中所述的计算机可读的介质上所体现的计算机可执行的指令的处理器。
40、一种具有指导计算机解密密文C以复原报文M的计算机可执行的指令的计算机可读的介质，其中：n为形式n=p1p2的数，其中p1与p2为素数；
p1=r1q1+1及p2=r2q2+1，其中r1与r2为随机数且q1与q2为素数：
g为形式g=r3(p1-1)(p2-1)/q1q2 modn的数，其中r3为与随机数r1、r2及R无关地选取的随机数；
x为形式x=gRmodn的数，其中R为与随机数r1、r2与r3无关地选取的随机数；
e为整数；及
V为V=xe形式的值；
该计算机可读的介质包括：
指导计算机从值V复原数x的计算机可执行的指令，其中x=V(1/e)modq1q2 modn；
指导计算机按照单向函数n变换数x以产生h(x)的计算机可执行的指令；以及
指导计算机按照函数h(x)解码密文C以恢复报文M的计算机可执行的指令。
41、权利要求40中所述的计算机可读的介质，还包括指导计算机按照函数C_h(x)解码密文C的计算机可执行的指令。
42、权利要求40中所述的计算机可读的介质，还包括指导计算机从数x与恢复的报文M的散列函数h计算散列值h(x，M)的计算机可执行的指令。
43、一种编程成执行在权利要求40中所述的计算机可读的介质上体现的计算机可执行的指令的处理器。
CNB988118947A 1997-10-20 1998-09-16 能快速解密的密码系统与方法 Expired - Fee Related CN1282325C (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US08/953,911 US6081598A (en) 1997-10-20 1997-10-20 Cryptographic system and method with fast decryption
US08/953,911 1997-10-20

Publications (2)

Publication Number Publication Date
CN1281607A true CN1281607A (zh) 2001-01-24
CN1282325C CN1282325C (zh) 2006-10-25

Family

ID=25494714

Family Applications (1)

Application Number Title Priority Date Filing Date
CNB988118947A Expired - Fee Related CN1282325C (zh) 1997-10-20 1998-09-16 能快速解密的密码系统与方法

Country Status (7)

Country Link
US (1) US6081598A (zh)
EP (1) EP1031204B1 (zh)
JP (1) JP4369618B2 (zh)
CN (1) CN1282325C (zh)
CA (1) CA2307619C (zh)
DE (1) DE69833334T2 (zh)
WO (1) WO1999034552A2 (zh)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101061661B (zh) * 2004-10-20 2010-10-27 思科技术公司 加密方法

Families Citing this family (30)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10361802B1 (en) 1999-02-01 2019-07-23 Blanding Hovenweep, Llc Adaptive pattern recognition based control system and method
GB9410337D0 (en) * 1994-05-24 1994-07-13 Cryptech Systems Inc Key transmission system
KR100332763B1 (ko) * 1999-02-10 2002-04-17 구자홍 디지탈데이터 플레이어의 복제방지 장치 및 방법
JP2001016196A (ja) * 1999-04-28 2001-01-19 Fuji Soft Abc Inc 多重アファイン鍵を用いる暗号化・復号化方法、認証方法、及びこれを用いる各装置
US20020039420A1 (en) * 2000-06-12 2002-04-04 Hovav Shacham Method and apparatus for batched network security protection server performance
US20020087884A1 (en) * 2000-06-12 2002-07-04 Hovav Shacham Method and apparatus for enhancing network security protection server performance
US6959091B1 (en) * 2000-07-28 2005-10-25 Atmel Corporation Cryptography private key storage and recovery method and apparatus
US7137143B2 (en) 2000-08-07 2006-11-14 Ingrian Systems Inc. Method and system for caching secure web content
US7155610B2 (en) * 2000-12-19 2006-12-26 Matsushita Electric Industrial Co., Ltd. Cryptocommunication system, transmission apparatus, and reception apparatus
US7757278B2 (en) * 2001-01-04 2010-07-13 Safenet, Inc. Method and apparatus for transparent encryption
JP4284867B2 (ja) * 2001-01-18 2009-06-24 株式会社日立製作所 標準モデル上で適応的選択暗号文攻撃に対して安全な公開鍵暗号方法
US7181017B1 (en) 2001-03-23 2007-02-20 David Felsher System and method for secure three-party communications
US7164765B2 (en) * 2001-04-11 2007-01-16 Hitachi, Ltd. Method of a public key encryption and a cypher communication both secure against a chosen-ciphertext attack
US6718536B2 (en) * 2002-06-21 2004-04-06 Atmel Corporation Computer-implemented method for fast generation and testing of probable prime numbers for cryptographic applications
AU2003262857A1 (en) * 2002-08-24 2004-03-11 Ingrian Networks, Inc. Selective feature activation
JP4563037B2 (ja) * 2003-01-24 2010-10-13 シャープ株式会社 暗号化装置および復号化装置、並びにこれらを備えた暗号システム、暗号化方法および復号化方法
US9818136B1 (en) 2003-02-05 2017-11-14 Steven M. Hoffberg System and method for determining contingent relevance
US20060149962A1 (en) * 2003-07-11 2006-07-06 Ingrian Networks, Inc. Network attached encryption
US8442219B2 (en) * 2004-03-31 2013-05-14 Jesse Lipson Public key cryptographic methods and systems
US7519835B2 (en) * 2004-05-20 2009-04-14 Safenet, Inc. Encrypted table indexes and searching encrypted tables
US20060251248A1 (en) * 2005-05-03 2006-11-09 Jesse Lipson Public key cryptographic methods and systems with preprocessing
US20070079140A1 (en) * 2005-09-26 2007-04-05 Brian Metzger Data migration
US20070079386A1 (en) * 2005-09-26 2007-04-05 Brian Metzger Transparent encryption using secure encryption device
US20070074038A1 (en) * 2005-09-29 2007-03-29 International Business Machines Corporation Method, apparatus and program storage device for providing a secure password manager
US8874477B2 (en) 2005-10-04 2014-10-28 Steven Mark Hoffberg Multifactorial optimization system and method
US8386768B2 (en) * 2006-02-08 2013-02-26 Safenet, Inc. High performance data encryption server and method for transparently encrypting/decrypting data
US7958091B2 (en) 2006-02-16 2011-06-07 Ingrian Networks, Inc. Method for fast bulk loading data into a database while bypassing exit routines
US8379865B2 (en) * 2006-10-27 2013-02-19 Safenet, Inc. Multikey support for multiple office system
US20090132804A1 (en) * 2007-11-21 2009-05-21 Prabir Paul Secured live software migration
US10574451B2 (en) * 2017-10-19 2020-02-25 Bank Of America Corporation Method and apparatus for perfect forward secrecy using deterministic hierarchy

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4405829A (en) * 1977-12-14 1983-09-20 Massachusetts Institute Of Technology Cryptographic communications system and method
US5323464A (en) * 1992-10-16 1994-06-21 International Business Machines Corporation Commercial data masking
US5483598A (en) * 1993-07-01 1996-01-09 Digital Equipment Corp., Patent Law Group Message encryption using a hash function
EP0639907B1 (en) * 1993-08-17 1999-12-08 R3 Security Engineering AG Digital signature method and key agreement method
FR2737369A1 (fr) * 1995-07-26 1997-01-31 Trt Telecom Radio Electr Systeme de communication de messages cryptes selon un procede de type r.s.a.

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101061661B (zh) * 2004-10-20 2010-10-27 思科技术公司 加密方法

Also Published As

Publication number Publication date
CA2307619C (en) 2008-09-09
JP2004524548A (ja) 2004-08-12
WO1999034552A3 (en) 1999-09-16
EP1031204B1 (en) 2006-01-25
JP4369618B2 (ja) 2009-11-25
DE69833334T2 (de) 2006-10-26
WO1999034552A9 (en) 1999-10-28
WO1999034552A2 (en) 1999-07-08
CA2307619A1 (en) 1999-07-08
EP1031204A2 (en) 2000-08-30
CN1282325C (zh) 2006-10-25
DE69833334D1 (de) 2006-04-13
US6081598A (en) 2000-06-27

Similar Documents

Publication Publication Date Title
CN1281607A (zh) 能快速解密的密码系统与方法
CN1257648C (zh) 多级多维内容保护方法
CN1659821A (zh) 在两个装置之间交换安全数据的方法
CN1297881C (zh) 一种保证数据安全传输的打印控制方法
CN1122213C (zh) 给对象签名和签章的方法和设备
WO2018182818A1 (en) Homomorphic white box system and method for using same
US20100046755A1 (en) Cryptography related to keys with signature
CN1809984A (zh) 改进的保密验证信道
CN1702999A (zh) 一种对加密密钥进行备份与恢复的方法
NZ535698A (en) An cryptosystem involving generating an isogeny that maps points from one elliptic curve onto another elliptic curve and publishing a public key corresponding to the isogeny
CN1186580A (zh) 在用户计算机设备u和网络计算机设备n之间计算机辅助交换密钥的方法
CN110889123B (zh) 一种认证方法及密钥对的处理方法、装置与可读存储介质
CN1423451A (zh) 基于时间的加密密钥
WO2006095891A1 (ja) データ処理装置
CN1292185A (zh) 用于向所选成员传达私人消息的方法和设备
CN1820448A (zh) 用于使用三阶段加密来加密和验证消息的系统和方法
CN1759562A (zh) 用于加密和解密的装置、方法、程序及记录介质
JP2001202010A (ja) メッセージの公開型且つ非可換性の符号化方法及び暗号化方法
CN101040474A (zh) 为提高安全性的置换数据变换
CN1592190A (zh) 硬件加密引擎和加密方法
CN1771691A (zh) 用于网络设备的安全管理的方法、系统和计算机程序
CN1483260A (zh) 用于检测一个键对和用于产生rsa键的方法和装置
CN102598575A (zh) 用于对密码保护的有效数据单元加速解密的方法和系统
US20220060314A1 (en) Privacy preserving fully homomorphic encryption with circuit verification
CN118233577A (zh) 一种结合ecc非对称加密算法的混沌图像加密方法

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
C14 Grant of patent or utility model
GR01 Patent grant
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20061025

Termination date: 20140916

EXPY Termination of patent right or utility model