RSA，一种用于保密通信的公钥密码体制外文翻译资料

英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

RSA，一种用于保密通信的公钥密码体制

摘要:一种新的密码体制提出运用取模算术运算，它是基于RSA公钥密码体制。这种体制有一个特点，即加密和解密过程在计算上不密集，所以这种体制适合高数据率通信。

关键字：密码分析学；高数据率通信；加密；解密

1.引言

本论文中，Shannon【6】指出如果想要提高当前密码体制的安全等级，就需要开发新的密码体制。在本文中，我们提出了一种密码体制【8】，这种密码体制通过在RSA基础上引入一种新的加密体制。

我们都知道，如果RSA的加密和解密过程在计算上相互关联，那么备受关注的RSA公钥密码体制【4】是无法在高数据率通信系统中使用的。甚至那鲜为人知的ElGamal公钥密码体制【1】对于高数据率的情况在计算上也是不允许的。此外，这种体制的密文的大小是明文的2倍。

这里设计的加密体制计算不密集，因此可以用于高数据率通信系统。

上面提出的体制在第2节和第3节讨论了一些体制设计方面的问题。该体制的实例说明在第4节，攻击分析在第5节。最后，计算一个整数的乘法逆的算法在附录里有介绍。

2.提出的体制

在这个体制中，发送者选择满足条件（1）的整数集合使用在公共目录或者从接收者获取的RSA公钥加密程序去加密选择的整数集，从而得到相应的密文。这个密文然后发送给原定的接收者。接收者利用只有他才知道的RSA解密私钥对密文进行解密，得到整数集。转换选定的整数集后，发送者使用（3）即涉及特定的模算术运算，在整数集和消息块，从而获得相应的密文,然后传送给接收者。通过在（4）中执行指定的逆模算术运算，接收者恢复了消息块。一般的，体制如下所示。

公钥

N：整数，具有很大的素数因子P和Q。

e:d模的乘法逆元，是N的欧拉函数。

私钥

d:小于并且和互质。

P和Q：N的素数因子。

：欧拉函数，等于。

加密

选取整数集（不一定是素数）和，它们满足如下关系：

用RSA公钥e和N加密程序，对选定的整数集加密，获得相应的密文,计算如下：

其中假设和小于N，否则每个整数应该被分割为一个小于N的小整数集。

传送密文给指定接收者。

将消息划分成块，使每个块的数值小于。现在对每个消息块加密，使用如下关系：

获得密文，然后发送密文。

解密

收到，然后计算，利用RSA解密程序的私钥d,获取整数集，具体过程如下。

使用如下关系,从密文块恢复消息块。是相对于的乘法逆元。

(4)

3.体制设计方面的问题

对于RSA中素数P和Q以及密钥d的选择，参考Salomaa【5】编写的书。d应该很大并且和互质。d如果小的话，通过一定合理数量计算的直接搜索会暴露密钥。为了检查选择的整数d是否和互质，通过附录中产生的来解释。如果，则d和互质，否则不是。

一旦d和互质，那么d模的乘法逆元e存在。e可以通过欧几里得算法计算得到，附录中有介绍。

发送者可以随机选择整数，这些整数必须来自大的整数集。否则，明文字符的频率可能会在密文中保留。而且，直接搜索可能会泄露消息加密体制的密钥（整数）。

关于加密和解密程序的计算方面，在加密时，密文的产生需要3个乘法，3个加法和3个除法。为了计算，可以通过指数运算，即不断地乘方和乘法【4】。这个过程需要最多个乘法，个除法。欲知更多有效过程，看【3】。

不断地做平方和乘法运算的指数运算方法同样可以运用在解密中去获取。值得注意的是，由于只有接收者知道d,所以密码分析者是无法使用此过程的。为了从得到消息，接收者应该能首先计算出，通过欧几里得算法在的黄金比例处终止的迭代【7】。每一个迭代需要一个带余除法运算。在开始通信之前，发送者可计算，然后用代替发送。接收者可以仅仅只用用3个乘法，3个减法和3个除法运算恢复消息。

特殊情况下，该体制可以通过修改来缓冲算术运算的次数，比如删掉，而不以牺牲该体制的安全等级为代价。

该体制的实例解释如下。

4.实例

令作为传送消息的三部分。

公钥

私钥

加密

选择。值得注意的是，。用RSA的公钥e=3,N=391加密,得到密文

类似的，加密,然后得到密文。

传送密文给原定接收者。这是一次性传输，同时整数成为了消息加密体制的密钥。

加密第一个消息块，得到密文

对余下的消息块重复此步骤,得到密文。

解密

用RSA的私钥d=235对进行解密，得到

类似的，解密,然后得到。

接收到密文，然后通过计算恢复消息。

其中。

5.该体制的安全性分析

上述提出的体制对可能密码分析方法进行分析，发现该体制是安全的。

很容易发现，从计算得到等同于破坏RSA，所以假设无法从得到。 因此，上述提出的体制的安全性等同于上述提出的加密体制的安全性。

唯密文攻击

根据得到的密文，入侵者也许能够将密文分割成块，破译的大小，从而得到。

此外，入侵者，几乎是不可能的，可能会发现对应于密文块的明文字符的最大数量，知道的大小，得到。为了防止消息由于的大小而泄露，分割消息以便于每个块小于。

然而和，只有通过穷举搜索才能得到，但是这种计算是不可行的。

已知和选择明文攻击

为了分析该体制在已知明文攻击和选择明文攻击的情况，写下,已知部分消息和密钥，则

其中是模运算的商。方便起见，这个可以写为：

其中，

J是正整数的子集。在已知明文攻击中，假定密码分析员知道，

但是不知尽管假定已知。然后他需要解决，。由于，是J的基数，变量方程，该体制是确定的并且有大量的解决方案，所以该体制对已知明文攻击是足够安全的。

类似的，该体制也可以被证明在选择明文攻击下是安全的。同时，他在面对解决等价密钥的威胁也是安全的。

6.致谢

作者要感谢中心研究实验室的Mr M Sethuraman以及Bharat电子有限公司在密码分析方面的建议。

7.附录（乘法逆元运算）

agt;bgt;0，a和b是整数。以下过程（欧几里得算法）计算a和b的最大公约数，记作gcd(a,b)。如果gcd(a,b)=1，a和b互质，则该过程同样计算b模a的乘法逆。步骤如下：

其中，。a和b的最大公约数是。现在为了计算a模b的乘法逆，定义：

如果,b模a的乘法逆市模a的正残基。如果,则gcd(a,b)=表示a和b不互质，因此b模a的乘法逆不存在。{},{}可以计算为如下表【2】：

作为实例，令a=352,b=235，则b模a的乘法逆元的计算如下：

由于。作为检查，考虑。

参考文献

[1] ElGamal T, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE

Trans. Inform. Theory, IT-31 (1985) 469-472

[2] Gregory R T and Krishnamurthy E V, Methods and applications of error-free computation, (New York:

Springer-Verlag), (1984)

[3] Knuth D E, The art of computer programming, 2: Seminumerical algorithms (Reading Mass:

Addison-Wesley) (1969)

[-4] Rivest R L, Shamir A and Adleman L, A method for obtaining digital signatures and public-key

cryptosystems, Comm. ACM, 21 (1978) 120-126

1-5] Salomaa A, Public- Key Cryptography, EATCS monographs on Theoretical Computer Science,

Vol. 23 (Berlin, Heidelberg: Springer-Verlag) (1990)

I-6] Shannon C E, Communication theory of secrecy systems, Bell Syst. Tech. J. 28 (1949) 656-715

I-7] Van Tilberg H C A, An introduction to cryptology (Hingham Mass: Kluwer Academic) (1988)

[-8] Venkaiah V Ch, Is this a secure cryptosystem?, Labtalk 1 (1991) (Labtalk is an house journal of Central

Research Laboratory, Bharat Electronics, Bangalore, India)

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[29400]，资料为PDF文档或Word文档，PDF文档可免费转换为Word