CN1338166A - 公用与专用密钥加密方法 - Google Patents

Abstract

本发明涉及用于产生公用密钥(K)和专用密钥(K′)的加密方法,包括:选择邻近值的两个不同的大素数p和q,并计算积n=p·q;计算数(p－1)和(q－1)的最小公倍数:λ(n)=PPCM(p－1,q－1);确定下面两个条件的数g,0< g≤n²:(a)g是可逆模n²;和(b)ord(g,n²)=0modn。由参数n和g形成该公用密钥K,利用参数p,q和λ(n)或利用参数p和q形成它的专用密钥。对于表示信息的数m(0≤m< n)的加密方法包括计算密码C=g^mmodn²。

Description

公用与专用密钥加密方法

本发明涉及公用与专用密钥加密方法，这能用于其中需要保证通过任何信道发送的消息的机密性和/或需要确切识别与之交换消息的设备的所有应用中。

利用发送的信息的加密来获得通过任何通信信道在两个设备A与B之间发送的消息的机密性，以使此信息对于未预定发送此信息给之的任何人是不可懂的。消息的可靠识别部分基于消息的数字特征标记的计算。

实际上，能使用两种类型的加密方法，即一种类型是所谓的对称加密方法，具有保密密钥，其公知的示例是DES，另一种类型是所谓的非对称加密方法，使用公用与专用密钥对，描述在1976年11月IEEE Transactions on Information Theory上发表的Messrs Diffie与Hellman的文章“New Directions in Cryptography”中。非对称方法的公知示例是源于其发明者Ronald Rivest、Adi Shamir与Leonard Adleman名字的RSA，在US专利4405829中可找到此RSA方法的描述。

在本发明中，更具体地涉及非对称加密方法。

根据非对称加密方法的加密方法主要包括：对于希望机密地发送消息给目的地B的发射机A来说，考虑例如电话簿中目的地B的公用密钥K_B；利用此公用密钥对要进行发送的消息应用加密方法E；并发送给目的地B，得到密码C：

C＝E_KB(m)。

对于目的地B，此方法主要包括：接收密码C；并解码此密码C以获得原始消息m；利用只有它知道的专用密钥K′b对密码C应用解密方法D：m＝DK′b(C)。

根据此方法，任何人都能发送加密消息给目的地B，但只有后者能解密此消息。

通常将非对称加密方法用于特征标记的生成/验证。在此种情况下，希望证明其身份的用户利用只有他知道的专用密钥来生成消息m的数字特征标记s，即，他发送给目的设备的特征标记。目的设备利用此用户的公用密钥来进行此特征标记的验证。任何设备因而具有验证用户的特征标记、考虑此用户的公用密钥并将此公用密钥应用于验证算法中的能力。然而，只有相关的用户具有利用其专用密钥生成正确的特征标记的能力。此方法例如大多用于接入控制系统或银行交易中，这一般与加密方法的使用相结合，以便在发送特征标记之前加密此特征标记。

对于数字特征标记的生成/验证，有可能实际使用诸如对应于US国家标准与技术委员会建议的美国标准的DSA(数字特征标记算法)的此应用专用的非对称加密方法。也有可能使用具有能在加密与特征标记生成时使用的特性的RSA。

在本发明中，涉及能用于消息的加密和数字特征标记的生成的加密方法。在本技术领域的当前状态中，只有存在许多不同实施方案的RSA才提供此双重功能。

该RSA包括生成用于指定设备的公用密钥K与专用密钥K′的步骤，其中程序如下：

-选择两个不同的大素数p与q，

-计算其乘积n＝p·q，

-利用(p-1)(q-1)的最小公倍数选择一个素数。实际上，通常取e等于3。

随后利用参数对(n，e)形成该公用密钥K，并利用参数对(p，q)形成保密密钥K′。

通过选择大尺寸的p与q，其乘积n也具有大尺寸。N因此非常困难进行因子分解：保证在知道n的情况下不可能找到保密密钥K′＝(p，q)。

表示消息M的数字m(0≤m＜n)的加密方法则包括利用公用密钥K＝(n，e)执行下面的计算：

c＝E_B(m)＝m^e mod n。

该解密方法则部分包括利用保密的专用密钥K′＝(p，q)执行下面的逆计算：

m＝c^d mod(n)

其中 $d=\frac{1}{e}\mathrm{mod}(p-1)(q-1)$

已经知道：RSA具有能用于特征标记验证的特性。用户A的特征标记生成的相应方法包括使用借助该保密密钥的解密方法以便生成表示消息的数字m的特征标记s。因而：s＝m^d mod n。

将此特征标记s发送给目的地B，知道m的后者(例如，A发送s与m)，通过执行逆运算，也就是说使用借助发射机A的公用密钥的此加密方法，来验证此特征标记。即，他计算V＝s^e mod n，并验证v＝m。

一般地，为了提高这样的特征标记验证方法的安全性，在计算此特征标记之前首先对数字m应用散列函数，这能包括比特的置换和/或压缩。

在说到要加密或标记的消息M时，这当然是指能从先前的数字编码中得到的数字消息的情况。实际上，这些是其二进制大小(比特的数量)是可变的比特串。

然而，诸如RSA的加密方法使之有可能利用公用密钥(n，e)加密0与n-1之间的任何数字。为了将此方法应用于具有任何大小的消息M，因此实际需要将此消息划分为均满足条件0≤m＜n的一系列数字m。随后，将此加密方法应用于这些数字之中的每一个数字。下面，因此涉及对表示消息M的数字m应用此加密方法的情况。m能等于M或只是其一部分。下面，将m一般地用于表示该消息或代表此消息的数字。

本发明的一个目的是不同于基于RSA的方法的非对称加密方法。

本发明的一个目的是基于能应用于消息的加密或特征标记的生成的其他特性的方法。

本发明的一个目的是在某些结构中提供更迅速的处理时间的加密方法。

其特征在于，本发明涉及根据权利要求1的加密方法。

通过结合附图阅读作为示意给出的并且无论如何不限制本发明的下面描述将更好地理解本发明，其中：

图1是非对称类型的密码通信系统的功能图；

图2是用于根据本发明的密码通信系统中的通信设备的功能图；

图3是使用根据本发明的加密方法的消息加密/解密对话的流程图；和

图4是使用根据本发明的加密方法的特征标记生成/验证对话的流程图。

为了更好地理解本发明，需要完成一些数学准备。

在本说明书中，使用下面的数学表示法：

(1)如果a是相对整数，而b是真正的正整数，则a mod b(a模b)是a相对b的模余数并且表示正好小于b的唯一整数，以使b整除(a-a mod b)。

(2)(Z/bZ)表示模b的余数集合并形成模加法的组。

(3)(Z/bZ)*表示可逆模b的整数集合并形成模乘法的组。

(4)(Z/bZ)*的元素a的阶是使a^ord(a，b)＝1 mod b的最小自然整数ord(a，b)。

(5)LCM(a，b)表示a与b的最小公倍数。

(6)HCF(a，b)表示a与b的最大公因子。

(7)λ(a)表示a的Carmichael(卡迈克尔)函数。如果a＝p·q，则λ(a)＝LCM(p-1，q-1)。

(8)利用公知的Chinese Remainder Theorem(中国余数定理)得到下面的模等式的唯一解：

  x＝a₁ mod b₁

  x＝a₂ mod b₂

  …

  x＝a_k mod b_k

其中给定整数a_i与b_i，和其中i≠j时，i，j，HCF(b_i，b_j)＝1表示X＝CRT(a₁，…a_k，b₁，…b_k)。

(9)数字a的二进制大小是其中写入a的比特的数量。

现在，假定n为任意大小的整数。集合Un＝{x＜n²/x＝1 mod n}是(Z/n²Z)*的乘法子群。

随后，假定log_n是利用下式定义有关集合Un的函数： $\mathrm{Logn}\left(x\right)=\frac{X-1}{n}$

此函数具有以下特性：

x∈Un，y∈Un，log_n(xy mod n²)＝log_n(x)＋log_n(y)mod n。

结果，如果g是属于Un的任意整数，则对于任意数字m，0≤m＜n，这得到：

log_n(g^m mod n²)＝m.log_n(g)mod n

此数学特性以现在将描述的本发明中使用的加密方法为基础。

图1表示使用非对称加密方法的密码通信系统，它包括示例A与B中在通信信道1上通信的设备，此示例表示双向信道。每个设备包含一对公用密钥K与专用密钥K′。

公用密钥例如公开在诸如电话簿的公开文件2中，每个设备能查阅此公开文件。在此公开文件中，因而将找到设备A的共用密钥K_A和设备B的公用密钥K_B。

每个设备的专用密钥K′一般由此设备保密地存储在保护的非易失性存储区域中。设备A因而在保密存储器中包含它的专用密钥K′_A，而设备B在保密存储器中包含它的专用密钥K′_B，它们也存储其公用密钥，但存储在没有任何特殊存取保护的存储区域中。

在这样的系统中，设备A能利用设备B的公用密钥K_B在密码C_A中加密消息m；后者能利用其保密存储的专用密钥K′_B解密C_A。相反地，设备B能利用设备A的公用密钥K_A在密码C_B中加密消息m。后者能利用其保密存储的专用密钥K′_A解密C_B。

一般地，如图2所示，每个设备至少包括：处理装置10，即中央处理单元(CPU)，包括显然不同的用于计算的寄存器R；接口11，用于与通信信道通信；和存储装置。这些存储装置一般包括程序存储器12(ROM，EPROM，EEPROM)和工作存储器(RAM)13。实际上，每个设备都将其保密数据存储在程序存储器中提供的保护存取区域120中并将其公开数据存储在此存储器的正常存取区域中。工作存储器使之有可能对于计算要求的时间临时存储要加密的消息、要解密的密码或中间计算结果。

此处理与存储装置因而使之有可能执行与此应用相关的程序，并且特别使之有可能进行对应于根据本发明的消息的加密/解密和/或特征标记的生成/验证的加密方法的实施的计算，这些计算显然包括上升为幂、余数和模求逆，如在下面具体描述的。

此设备也能包括用于在某些不同的实施例中能参与上述计算的随机或伪随机数字r的生成器14。以图2中的虚线表示此生成器的框架，以表示此生成器对于根据本发明的所有不同的实施例不是必需的。

此设备的所有这些装置连接到地址与数据总线15。

本发明中使用的这样的设备是公知的，并且例如对应于使用RSA的现有技术状态的密码通信系统中使用的那些设备，因此将不再具体描述这样的设备。密码通信系统的一个实际示例是利用银行服务器和智能卡形成的用于管理金融交易的系统。然而，具有许多其他的应用，诸如与电子商务相关的应用。

现在将根据图3中所示的流程图具体描述本发明的第一实施例。

此流程图表示通信信道20上设备A与设备B之间的通信顺序。这些设备至少包括结合图2所述的处理、存储与通信装置。

根据本发明的加密方法包括生成公用密钥K与专用密钥K′的方法。

根据本发明，生成设备的公用与专用密钥的此方法包括以下步骤：

-选择不同的并且具有相邻大小的两个大素数p与q；

-计算等于p·q乘积的数字n；

-计算数字λ(n)＝LCM(p-1，q-1)，即数字n的Carmichael(卡迈克尔)函数；

-确定满足下面两个条件的数字g，0≤g＜n²：

 a)g是可逆模n²；和

 b)ord(g，n²)＝0 mod n。

根据上面定义的表示法，此条件b)表示从0到n²的整数的集合(Z/n²Z)*中的数字g的阶是数字n的非零倍数。

随后利用数字n与数字g形成公用密钥K，利用数字p、q与λ(n)或只利用数字p与q形成专用密钥，λ(n)能在每次使用保密密钥时重新进行计算。

根据此方法生成每个设备的公用与专用密钥。能根据考虑的设备与应用利用设备本身或利用外部组成部分来实现此生成。

每个设备(例如，设备A)因此在存储器中包含它的公用密钥K_A＝(n_A，g_A)和保密地包含它的专用密钥K′_A＝(p_A，q_A)。

另外，将公用密钥放置在公众可存取的文件中。

在下面将明白：在可能时，取g＝2是有益的，也就是说，g＝2满足根据本发明的特征标记生成方法的条件a)与b)。

根据设备A中实施的本发明的加密方法的第一实施例的加密方法为了发送消息给设备B而包括以下步骤的执行，其中0≤m＜n：

-给定有关设备A利用第二设备B的公用密钥K_B实施的加密方法的参数n与g的信息：n＝n_B，g＝g_B，

-计算密码C＝g^m mod n²；和

-通过通信信道发送密码C。

根据本发明的第一实施例的加密方法因此包括：取公用密钥的参数g；将此参数g升为m的幂；并计算相对n²的模余数。应注意，在RSA中，是消息m上升为幂，而在本发明中消息m用作指数。

接收加密消息(即，密码C)的设备B随后根据本发明利用其专用密钥的参数来实施解密方法。此解密方法包括以下计算：

-计算数字m，以使 $m=\frac{\log n\left(c^{\mathrm{\&lambda;}\left(n\right)}\mathrm{mod}{n}^2\right)}{\log n\left(g^{\mathrm{\&lambda;}\left(n\right)}\mathrm{mod}{n}^2\right)}\mathrm{mod}n$

其中 ${\log }_n\left(x\right)=\frac{x-1}{n}$ 。

如果g＝2，能明白：实施将g上升为幂的计算。因此，如果可能的话，最好取g＝2。换而言之，生成密钥的方法将通过查看g＝2是否满足条件a)与b)来开始。

能实施不同变型的解密方法的计算，这在此设备必须解密大量的密码时使之有可能预先计算某些数量并将这些数量保密存储在此设备中。一个必然结果是此设备的保密存储区域(图2中的区域120)必须更扩展，这是因为此区域必须包含除参数p与q之外的其他参数，这对实施一个变型或另一变型的选择没有影响，这是因为尤其在所谓的低成本设备(例如，某些类型的智能卡)中保护存储区域的实施昂贵，并因此具有一般有限的(存储)容量。

在解密设备的第一变型实施例中，假定此设备(在此种情况中为设备B)只预先计算一次此数量：

α_n，g＝log_n(g^λ(n)mod n²)^-1mod n

并将其保密存储在存储器中。

因而，相应地减少此设备接收的每条消息的解密所需的时间。这是因为在设备B执行此变型的解密方法的示例时，所要做的就是计算：

m＝log_n(C^λ(n)mod n²)α_n，g mod n。

在根据本发明的解密方法的第二变型实施例中，假定为了更好的效率(计算的速度)而使用中国余数定理。

在解密方法的此第二变型的一个示例中，此设备执行下面的(解密)计算：

1.m_p＝log_p(c^p-1 mod p²)log_p(g^p-1 mod p²)^-1mod p

2.m_q＝log_q(c^q-1 mod q²)log_q(g^q-1 mod q²)^-1 mod q

3.m＝CRT(m_p，m_q，p，q)，

其中 ${\log }_p\left(x\right)=\frac{x-1}{p}$ 与 ${\log }_q\left(x\right)=\frac{x-1}{q}$ 。

在这种情况中，在此设备必须解密非常大量的消息时，也能假定此设备只预先计算一次下面的数量：

α_p，g＝log_p(g^p-1 mod p²)^-1mod p；  和

α_q，g＝log_q(g^q-1 mod q²)^-1mod q

此设备随后必须将这些数量存储为保密数据。

在解密方法的一个示例期间进行的计算变成：

1.m_p＝log_p(c^p-1 mod p²)α_p，g mod p

2.m_q＝log_q(c^q-1 mod q²)α_q，g mod q

3.m＝CRT(m_p，m_q，p，q)，

如已经陈述的，在此设备得解密大量的消息时，并且在节约处理时间以补偿用于存储所有保密数据的保护区域的较大存储容量时，所有其不同的解密计算是有利的。一种或另一种变型的选择实际上取决于所述的应用和并存的费用与处理时间的约束。

本发明的第二实施例包括此加密方法中利用随机(或伪随机)数生成器提供的随机数的使用，以致于对于要发送的同一消息m，计算的密码C在每一种情况下都是不同的。通信系统的安全性因此更大，而解密方法不变。

本发明的此第二实施例包括两种变型。

在第一变型中，利用下面的计算获得密码c：c＝g^m+nr mod n²；

在第二变型中，利用下面的计算获得密码c：c＝g^mrⁿ mod n²。

此第二变型实际上要求比第一变型更长的处理时间，但提供更大的安全性。

在本发明的第三实施例中，要求(Z/nZ)*中g的阶是小整数，这通过实施不同的密钥生成方法来获得。

利用这样的有关参数g的阶的条件，减少此解密方法的计算的复杂性，这实际上变成相对数字n的大小的平方(即，x²的形式)。

在本发明的此第三实施例中，生成公用与专用密钥的方法则如下：

-保密地选择整数u和两个不同的并具有相邻大小的素数p与q，以使u整除(p-1)与(q-1)；

-计算等于p·q乘积的数字n；

-计算数字λ(n)＝LCM(p-1，q-1)，即，数字n的Carmichael(卡迈克尔)函数；

-确定满足下面两个条件的数字h，0≤h＜n²：

a)h可逆模n²，和

b)ord(h，n²)＝0 mod n

-计算数字g＝h^λ(n)/u mod n²。

随后利用数字n与数字q形成公用密钥K。专用密钥由保密存储在此设备中的整数(p，q，u)构成。

如果可能的话(即，如果h＝2满足条件a)与b)，以便于g的计算)，最好选择h＝2。

应注意：如果u＝HCF(p-1，q-1)，就无需存储此数字，这能利用此设备从p与q中找到此数字。

最好选择u为素数并具有一般为160比特的小尺寸，以提高此方法的安全性。通过选择小尺寸的u，将明白有助于此解密计算。

在此第三实施例中，应用加密方法来加密消息m与以前在本发明的第一实施例中所述的相同，密码等于C＝g^m mod n²。

也有可能利用随机变量r根据前述的本发明的第二实施例的第一变型计算密码c。r则是随机整数，具有与u相同的大小，并利用下面的计算来获得此密码：c＝g^m+nr mod n²。

将根据此加密方法的一个或另一前面的实施计算的密码c发送给设备B，此设备B必须解密此密码。由接收消息的设备B实施的解密方法稍有不同。

这是因为为了从密码c中找到数字m而在解密的一个示例中在此设备中进行的计算变成如下： $m=\frac{{\log }_n\left(c^u{\mathrm{mod}n}^2\right)}{{\log }_n\left(g^u{\mathrm{mod}n}^2\right)}\mathrm{mod}n$

如前面一样，有可能应用不同的计算，这使之有可能加快需要的处理时间。

在第一变型中，数量β_n，g＝log_n(g^u mod n²)^-1mod n将因而只预先计算一次并将保密存储在存储器中。

在接收的密码c的解密的一个示例期间，此设备随后只需要进行下面的计算：

m＝log_n(c^u mod n²)β_a，g mod n。

在第二变型中，利用函数log_p与log_q实施中国余数定理，如执行解密计算所明白的。

在解密接收的密码c的方法的此变型的一个示例中，此设备则执行下面的计算。

1.m_p＝log_p(c^u mod p²)log_p(g^u mod p²)^-1mod p

2.m_q＝log_q(c^u mod q²)log_q(g^u mod q²)^-1mod q

3.m＝CRT(m_p，m_q，p，q)。

在第三变型中，进一步加快根据第二变型的密码c的解密所需的处理时间，预先计算下面的数量：

β_p，g＝log_p(g^u mod p²)^-1mod p

β_q，g＝log_q(g^u mod q²)^-1mod q

并将这些数量保密地存储在此设备中。

在解密接收的密码c的方法的此第三变型的计算的示例中，此设备则只需执行下面的计算：

1.m_p＝log_p(c^u mod p²)β_p，g mod p

2.m_q＝log_q(c^u mod q²)β_q，g mod q

3.m＝CRT(m_p，m_q，p，q)。

在本发明的第四个实施例中，加密方法与解密方法具有是模n²的整数组的置换的特殊性。换而言之，如果消息m利用k个比特来表示，则通过对m应用此加密方法得到的密码c和通过对m应用此解密方法得到的特征标记s也在k个比特中。

此特殊性使此加密方法具有能用于加密/解密并用于特征标记生成/验证的附加特性。在这种情况中，此解密方法用作特征标记生成方法，而此加密方法用作特征标记验证方法。

在此第四实施例中，生成公用与专用密钥的方法和本发明的第一实施例相同：K＝(n，g)和K′＝(p，q，λ(n))或K′＝(p，q)。

如果设备A希望发送加密消息m给设备B，则设备A从设备B得到公用密钥(n，g)，并随后在此加密方法的一个示例中对数字m执行下面的计算，0≤m＜n²：

1.m₁＝m mod n

2.m₂＝(m-m₁)/n  (Euclidian欧几里德除法)

3.c＝g^m1m₂ ⁿ mod n².

正是将此密码c发送给设备B。

后者因此必须对此密码c应用相应的解密方法，以找到m₁、m₂并最后找到m。根据本发明的第四个实施的解密方法包括执行下面的计算：

1.m₁＝log_n(c^λ(n)mod n²)log_n(g^λ(n)mod n²)^-1mod n

2.w＝cg^-m1 mod n

3.m₂＝w^{1/n modλ(n)} mod n

4.m＝m₁＋nm₂。

与以前一样，根据本发明的此第四实施例的解密方法的变型是可应用的，这使之有可能减少解密给定消息所需的处理时间，这在此设备具有大量的密码要解密时是有益的。

第一变型包括预先计算下面的数量：

α_n，g＝log_n(g^λ(n)mod n²)^-1mod n；和

γ_n＝1/n modλ(n)。

这些数量设备B只计算一次而且保密保持在存储器中。

对于根据此第一变型接收的密码c的解密的每一个新示例，设备B只需执行下面的计算：

1.m₁＝log_n(c^λ(n) mod n²)α_n，g mod n

2.w＝cg^-m1 mod n

3.m₂＝w^γn mod n

4.m＝m₁＋nm₂。

在根据第四实施例的解密方法的实施的第二变型中，使用中国余数定理。

希望根据此第二变型解密密码c的设备则执行下面的连续计算：

1.m_1，p＝log_p(c^p-1 mod p²)log_p(g^p-1 mod p²)^-1mod p

2.w_p＝cg^-m1，p mod p

3.m_2，p＝w_p ^{1/q mod p-1} mod p

4.m_1，q＝log_q(c^q-1 mod q²)log_q(g^q-1 mod q²)^-1mod q

5.w_q＝cg^-m1，q mod q

6.m_2，q＝w_q ^{1/p mod q-1} mod q

7.m₁＝CRT(m_1，p，m_2，p，p，q)

8.m₂＝CRT(m_1，q，m_2，q，p，q)

9.m＝m₁＋pqm₂。

在第三变型中，为了进一步提高处理此第二变型的解密的时间，设备B能只预先计算一次下面的数量：

α_p，g＝log_p(g^p-1 mod p²)^-1mod p

α_q，g＝log_q(g^q-1 mod q²)^-1mod q

γ_p＝1/q mod p-1

γ_q＝1/p mod q-1

并且将这些数量保密保持在存储器中。

希望根据此第三变型解密密码c的设备只需执行下面的计算：

1.m_1，p＝log_p(c^p-1 mod p²)α_p，g mod p

2.w_p＝cg^-m1，p mod p

3.m_2，p＝w_p ^γp mod p

4.m_1，q＝log_q(c^q-1 mod q²)α_q，g mod q

5.w_q＝cg^-m1，q mod q

6.m_2，q＝w_q ^γq mod q

7.m₁＝CRT(m_1，p，m_2，p，p，q)

8.m₂＝CRT(m_1，q，m_2，q，p，q)

9.m＝m₁＋pqm₂

刚才描述的本发明的第四实施例使之有可能实现特征标记生成/验证。如图4的流程图所示，如果设备B必须生成对于设备A表示消息的数字m的特征标记s，则采用具有其专用密钥s＝D_K’B(m)的解密方法作为特征标记生成方法。

接收特征标记s并知道消息m的设备A通过计算利用公用密钥v＝E_KB(s)对特征标记s应用此加密方法获得的数量v来检验此特征标记是否正确。如果此特征标记是正确的，则v＝m。

使之有可能加快处理时间的此第四实施例的解密方法的所有变型实施例也能应用于特征标记生成/验证。

刚才描述的本发明可应用于其中希望能加密和/或标记消息的所有系统中，这根据是否寻求更加安全或增加处理速度来拓展适用于不同应用的可能性。有关这方面，应注意：其计算复杂性只是二次方程式(n的大小的平方的函数)的本发明的第三实施例在速度方面提供真实优势，而迄今为止所有的现有技术方法具有较高的复杂程度(n的大小的立方函数)。这样的优点更具体涉及使用便携式设备(诸如智能卡和更具体地低成本设备)的所有应用。

最后，本发明所涉及的技术领域的技术人员将明白：能对形式和/或细节进行修改而不背离本发明的精神。特别地，能加密特征标记，或能在计算其特征标记之前对消息m应用散列函数。

Claims (25)

1.一种加密方法，包括在能在至少一个通信信道上交换消息的设备中生成公用密钥(K)与专用密钥(K’)的方法，此专用密钥得保密存储在所述设备中，而此公用密钥得公开进行广播，此生成方法包括以下步骤：

-选择不同的并且具有相邻大小的两个素数p与q；

-计算等于p·q乘积的数字n；

其特征在于，所述方法也包括以下步骤：

-计算数字(p-1)与(q-1)的最小公倍数：λ(n)＝LCM(p-1，q-1)；

-确定满足下面两个条件的数字g，0≤g＜n²：

 a)g可逆模n²；和

 b)ord(g，n²)＝0 mod n，

利用参数n与g形成所述设备的公用密钥，并利用参数p、q与λ(n)或利用参数p与q形成其专用密钥。

2.根据权利要求1的生成方法，其特征在于，它包括在g满足所述条件a)与b)时取g＝2。

3.具有根据权利要求1或2生成的公用与专用密钥的一种密码通信系统，包括通信信道(20)和通信设备(A，B)，每个设备包括至少一个通信接口(11)、数据处理装置(10)和存储装置(12，13)，其特征在于，在第一设备(A)中实施加密方法，以发送表示消息的数字m给第二设备(B)，其中0≤m＜n，所述加密方法包括以下步骤：

-利用第二设备(B)的公用密钥(n_B，g_B)的参数来给出有关此加密设备的参数n与g的信息，

-计算密码c＝g^m mod n²，

随后通过此通信信道将所述密码c发送给第二设备。

4.根据权利要求3的系统，其特征在于，实施此加密方法的设备也包括用于随机整数r的生成器(15)，并且其特征在于，所述设备：

-执行随机整数r的绘制，和随后

-通过执行下面的加密计算来计算密码c：

 c＝g^m+nr mod(n²)。

5.根据权利要求3的系统，其特征在于，实施此加密方法的设备也包括用于随机整数r的生成器(15)，并且其特征在于，所述设备：

-执行随机整数r的绘制，和随后

-通过执行下面的加密计算来计算密码c：

 c＝g^mrⁿ mod(n²)。

6.根据权利要求3-5之中任何一个权利要求的系统，其特征在于，第二设备(B)实施解密方法，以解密所述密码c，并包括执行下面的计算：

m＝log_n(c^λ(n)mod n²)log_n(g^λ(n)mod n²)^-1mod n其中 ${\log }_n\left(x\right)=\frac{x-1}{n}$ 。

7.根据权利要求6的系统，其特征在于，实施所述解密方法的设备(B)预先计算数量α_n，g＝log_n(g^λ(n)mod n²)^-1mod n并将此数量保密存储。

8.根据权利要求6的系统，其特征在于，在所述解密方法的一个示例中，设备利用中国余数定理CRT执行以下计算步骤：

m_p＝log_p(c^p-1 mod p²)log_p(g^p-1 mod p²)^-1mod p

m_q＝log_q(c^q-1 mod q²)log_q(g^q-1 mod q²)^-1mod q

m＝CRT(m_p，m_q，p，q)，其中log_p与log_q使得 $\mathrm{lo}{g}_i\left(x\right)=\frac{x-1}{i}$ 。

9.根据权利要求8的系统，其特征在于，实施所述解密方法的设备预先计算以下数量：

α_p，g＝log_p(g^p-1 mod p²)^-1mod p

α_q，g＝log_q(g^q-1 mod q²)^-1mod q

并保密地存储这些数量。

10.具有根据权利要求1或2生成的公用密钥与专用密钥的一种密码通信系统，包括通信信道(20)和通信设备(A，B)，每个设备包括至少一个通信接口(11)、数据处理装置(10)和存储装置(12，13)，其特征在于，在第一设备(A)中实施加密方法，以发送表示消息的数字m给第二设备(B)，其中0≤m＜n²，所述加密方法包括以下步骤：

-利用第二设备(B)的公用密钥K_B＝(n_B，g_B)的参数来给出有关此加密设备的参数n与g的信息，

-并执行以下计算：

  1.m₁＝m mod n

  2.m₂＝(m-m₁)/n

  3.c＝g^m1m₂ ⁿ mod n²，

通过此通信信道发送所述密码c。

11.根据权利要求10的系统，其特征在于，第二设备(B)接收此密码c并实施解密方法，以解密所述密码，这包括执行以下计算步骤：

1.m₁＝log_n(c^λ(n)mod n²)log_n(g^λ(n)mod n²)^-1mod n

2.w＝cg^-m1 mod n

3.m₂＝w^{1/n modλ(n)}mod n

4.m＝m₁＋nm₂。

12.根据权利要求11的系统，其特征在于，实施所述解密方法的设备预先计算以下数量：

α_n，g＝log_n(g^λ(n)mod n²)^-1mod n；和

γ_n＝1/n modλ(n)

并且保密存储这些数量。

13.根据权利要求11的系统，其特征在于，在所述解密方法的一个示例中，设备使用中国余数定理执行以下计算步骤：

1.m_1，p＝log_p(c^p-1 mod p²)log_p(g^p-1 mod p²)^-1mod p

2.w_p＝cg^-m1，p mod p

3.m_2，p＝w_p ^{1/q mod p-1}mod p

4.m_1，q＝log_q(c^q-1 mod q²)log_q(g^q-1 mod q²)^-1mod q

5.w_q＝cg^-m1，q mod q

6.m_2，q＝w_q ^1/pmodq-1mod q

7.m₁＝CRT(m_1，p，m_2，p，p，q)

8.m₂＝CRT(m_1，q，m_2，q，p，q)

9.m＝m₁＋pqm₂

其中log_p与log_q使得 $\mathrm{lo}{g}_i\left(x\right)=\frac{x-1}{i}$ 。

14.根据权利要求13的系统，其特征在于，在所述解密方法的一个示例中，设备预先计算以下数量：

α_p，g＝log_p(g^p-1 mod p²)^-1mod p

α_q，g＝log_q(g^q-1 mod q²)^-1mod q

γ_p＝1/q mod p-1

γ_q＝1/p mod q-1

并保密地存储这些数量。

15.根据权利要求11-14之中任何一个权利要求的系统，其中此解密方法用于计算消息m的特征标记s，而此加密方法用于验证所述特征标记。

16.一种加密方法，包括在能在至少一个通信信道(20)上交换消息的设备中生成公用密钥(K)与专用密钥(K’)的方法，此专用密钥得保密存储在所述设备中，而此公用密钥得公开进行广播，一种生成方法包括以下步骤：

-选择数字u和具有相邻大小的两个不同的素数p与q，以使u整除(p-1)并整除(q-1)；

-计算等于p·q乘积的数字n；

-计算数字(p-1)与(q-1)的最小公倍数：λ(n)＝LCM(p-1，q-1)；

-确定满足下面两个条件的数字h，0≤h＜n²：

a)h可逆模n²；和

b)ord(h，n²)＝0 mod n，

-计算数字g＝h^λ(n)/u mod n²，

利用参数n与g形成所述设备的公用密钥，并利用参数p、q与u形成其专用密钥。

17.根据权利要求16的方法，其特征在于，它包括在满足条件a)与b)时选择h＝2。

18.根据权利要求16的方法，其特征在于，u是(p-1)、(q-1)的最大公因子。

19.根据权利要求16的方法，其特征在于，u是素数。

20.具有根据权利要求16-19之中任何一个权利要求生成的公用密钥与专用密钥的一种密码通信系统，包括通信信道(20)和通信设备(A，B)，每个设备包括通信接口(11)、数据处理装置(10)和存储装置(12，13)，其特征在于，在第一设备(A)中实施加密方法，以发送表示消息的数字m给第二设备(B)，其中0≤m＜n，所述加密方法包括以下步骤：

-利用第二设备(B)的公用密钥(n，g)_B的参数来给出有关此加密设备的参数n与g的信息，

-计算密码c＝g^m mod n²，

随后通过此通信信道将所述密码c发送给第二设备。

21.根据权利要求20的系统，其特征在于，实施此加密方法的设备也包括用于随机整数r的生成器(15)，并且其特征在于，所述设备：

执行随机整数r的绘制，和随后

计算密码c，执行下面的加密计算：

c＝g^m+nr mod(n²)。

22.根据权利要求20或21的系统，其特征在于，第二设备(B)实施接收密码c的解密方法，包括执行下面的计算：

m＝log_n(c^u mod n²)log_n(g^u mod n²)^-1mod n。

23.根据权利要求22的系统，其特征在于，实施所述解密方法的设备预先计算数量：

β_n，g＝log_n(g^u mod n²)^-1mod n

并将此数量保密存储。

24.根据权利要求22的系统，其特征在于，在所述解密方法的一个示例中，设备利用中国余数定理CRT执行以下计算步骤：

1.m_p＝log_p(c^u mod p²)log_p(g^u mod p²)^-1mod p

2.m_q＝log_q(c^u mod q²)log_q(g^u mod q²)^-1mod q

3.m＝CRT(m_p，m_q，p，q)，

其中log_p与log_q使得 ${\log }_i\left(x\right)=\frac{x-1}{i}$ 。

25.根据权利要求24的系统，其特征在于，实施所述解密方法的设备预先计算以下数量：

β_p，g＝log_p(g^u mod p²)^-1mod p

β_q，g＝log_q(g^u mod q²)^-1mod q

并保密地存储这些数量。

Images