公钥密码系统和RSA公钥算法

简要介绍了公钥密码体制的思想和特点，具体介绍了RSA算法的理论基础、工作原理和具体实现过程，并通过一个简单的例子说明了算法是如何实现的。本文最后总结了RSA算法的一些不足和解决方法。

关键词:公钥密码系统，公钥，私钥，RSA

1简介

随着计算机网络化的逐步实现，互联网的前景越来越好，全球经济发展正在进入信息经济时代，知识经济初具规模。计算机信息的安全变得越来越重要。无论是个人信息交流，还是电子商务的发展，都迫切需要保证互联网上信息传输的安全。信息安全技术是一门综合学科，涉及信息论、计算机科学和密码学。其主要任务是研究计算机系统和通信网络中信息的保护方法，以实现系统中信息的安全、保密、真实和完整。其中，信息安全的核心是密码技术。密码学是一门集数学、计算机科学、电子学和通信于一体的交叉学科。它不仅能保证机密信息的加密，还能实现数字签名、身份验证、系统安全等功能。它是现代化的重要科学之一。本文将简要介绍公钥密码体制和目前该系统中最流行的RSA算法。

2公钥密码系统

要解释公钥密码体制，首先我们来了解一下加密算法的不同:目前的加密算法按照密钥方式可以分为单密钥密码体制和公钥密码体制。

2.1.一键密码

也称对称密码，是一种比较传统的加密方法，其加密操作和解密操作使用同一个密钥。在传输和处理信息时，信息的发送者和接收者都必须持有密码(称为对称密码)。因此，双方都必须获得该密钥，并对其保密。

单密钥密码系统的安全性取决于以下两个因素:一是加密算法必须足够强，实际中不可能基于密文本身来解密信息；第二，加密方法的安全性取决于密钥的保密性，而不是算法的保密性。因此，我们没有必要保证算法的保密性(实际上现实中使用的单密钥密码系统的很多算法都是公开的)，但必须保证密钥的保密性。

从单密钥密码的这些特点，我们很容易看出主要有两个问题:一是密钥的数量。在单密钥密码系统中，每对通信者都需要一对密钥。当用户数量增加时，钥匙的数量必然会成倍增加。因此，在网络通信中，大量密钥的生成、存储和分发将是一个难题。第二，密钥分发问题。在单密钥密码系统中，加密的安全性完全取决于密钥的保护。然而，由于双方使用相同的密钥，人们不得不相互交换密钥。因此，为了确保安全，人们必须使用一些其他的安全通道来分发密钥，例如使用特殊的信使来传输密钥。这是相当昂贵的，甚至是非常不现实的，尤其是在计算机网络环境下，人们利用网络传输加密文件，却需要另一个安全通道。

2.2公钥加密

正是由于单密钥密码体制的缺点，才使得它如此难以解决，因此开发一种新的、更有效、更先进的密码体制就显得更加迫切和必要。在这种情况下，一种新的公钥密码体制应运而生，它解决了困扰无数科学家的密钥分发问题。事实上，在这个系统中，人们甚至不必分发需要严格保密的密钥。这一突破也被认为是两千年来单码代替密码发明以来，密码学史上最伟大的成就。

这个全新的想法是由斯坦福大学的两位学者Diffie和Hellman在本世纪70年代提出的。该系统与单密钥加密的最大区别在于:

在公钥密码系统中，加密和解密使用不同的密钥(与对称密钥相比，人们称之为非对称密钥)，这两种密钥之间存在相互依赖关系:即用任一种密钥加密的信息只能用另一种密钥解密。这使得双方能够安全地通信，而无需事先交换密钥。其中，加密密钥和算法是公开的，每个人都可以用这个密钥加密文件并发送给收件人。这个加密密钥也称为公钥。接收方收到加密文件后，可以用他的解密密钥解密，解密密钥由他个人负责，不需要分发，所以也叫私钥，解决了密钥分发的问题。

为了说明这一观点，我们可以考虑以下类比:

在不安全的信道中进行通信的两个人，假设爱丽丝(接收者)和鲍勃(发送者)，想要安全地通信而不被对手奥斯卡破坏。爱丽丝想到了一个办法。她用的是锁(相当于公钥)。这种锁任何人轻轻一按就能锁上，但只有爱丽丝的钥匙(相当于私人钥匙)才能打开。然后爱丽丝发出无数这样的锁。当任何人，比如鲍勃，想给她寄信时，他只需要找到一个盒子，然后用爱丽丝的锁锁上，寄给爱丽丝。此时，除了拥有钥匙的爱丽丝之外，任何人(包括鲍勃本人)都无法打开箱子，所以即使奥斯卡能找到爱丽丝的锁，即使奥斯卡能在通信过程中截获箱子，但没有爱丽丝的钥匙，他也无法打开箱子，爱丽丝的钥匙也不需要分发，所以奥斯卡无法获得这个“私人钥匙”。

从上面的介绍可以看出，公钥密码体制的思想并不复杂，实现它的关键问题是如何确定公钥和私钥以及加/解密算法，也就是如何找到爱丽丝的锁和钥匙。我们假设在这个系统中，PK是公开信息，作为加密密钥使用，而SK需要用户自己保密，作为解密密钥使用。还公开了加密算法e和解密算法d。虽然SK和PK是成对出现的，但是SK是不能从PK计算出来的。他们必须满足以下条件:

①用加密密钥PK加密明文X后，用解密密钥SK解密恢复明文，或者写成:dsk (epk (x)) = X。

②加密密钥不能用于解密，即DPK (EPK (x)) ≠ X

③在计算机上可以很容易地生成PK和SK对。

④实际上不可能从已知的PK推导出SK。

⑤加密和解密的运算可以反过来，即EPK (DSK (x)) = X

从以上条件可以看出，在公钥密码体制下，加密密钥不等于解密密钥。加密密钥可以公开，这样任何用户都可以用公钥加密发送给这个用户的信息，而这个用户保存的唯一私钥是保密的，只有它才能恢复和解密密文。虽然理论上可以从加密密钥推导出解密密钥，但这种算法设计实际上是不可能的，或者说虽然可以推导出来，但耗时较长，变得不可行。因此，公开加密密钥不会危及密钥的安全。

这个系统的想法很简单，但是如何找到一个合适的算法来实现这个系统对于密码学家来说是一个真正的难题，因为由于Pk和SK是一对相互关联的密钥，因此很有可能从其中的一个推导出另一个。如果对手奥斯卡能从PK推导出SK，那么这个系统就不再安全了。因此，如何找到合适的算法生成合适的PK和SK，并使Pk无法推导出SK，是密码学家迫切需要解决的难题。这个问题甚至让公钥密码体制的发展停滞了很长一段时间。

为了解决这个问题，密码学家考虑了数学上的陷门单向函数。下面，我们可以给它非正式的定义:

Alice的公开加密函数应该很容易计算，而它的反函数(即解密函数)应该很难计算(针对Alice以外的人)。很多Y=f(x)形式的函数，对于给定的自变量x的值，很容易计算出函数Y的值；但是，从y的一个给定值，很多情况下很难根据函数关系f (x)计算出x的值。这样一个很容易计算但很难求逆的函数通常被称为单向函数。在加密过程中，我们希望加密函数e是一个单项式内射函数，这样它就可以被解密。虽然没有一个函数可以被证明是单向的，但是许多内射函数被认为是单向的。

例如，有一个函数被认为是单向的，假设n是两个大素数p和q的乘积，b是正整数，那么F被定义为:

f (x )= x b mod n

(如果gcd(b，φ(n))=1，那么实际上这就是我们下面要讲的RSA加密函数。)

如果要构造一个公钥密码系统，仅仅给出一个单向内射函数是不够的。从Alice的角度来看，e没有必要是单向的，因为它需要以有效的方式解密接收到的信息。所以爱丽丝应该有一个陷门，里面包含了你的函数容易找到的秘密信息e，换句话说，爱丽丝之所以能有效解密，是因为它有额外的秘密知识，即SK，可以为你提供解密函数d，所以我们称一个函数为陷门单向函数。如果它是一个单向函数，在知道了一个特定的陷门之后，很容易找到它的逆函数。

考虑上面的函数f (x) =？xb mod n .我们可以知道它的反函数f -1有一个类似的形式f (x) = xa？Mod n，用于a的适当值。陷印是使用n的因式分解来有效地计算正确的指数a(对于给定的b)。

为了方便起见，我们把某种陷门单向函数作为？。所以随机选一个函数f属于？作为公共加密函数；它的反函数f-1是一个秘密解密函数。然后就可以实现公钥密码系统了。

根据上述关于陷门单向函数的思想，学者们提出了许多公钥加密方法，其安全性基于复杂的数学问题。根据数学问题，至少有以下三种系统被认为是安全有效的:大整数因式分解系统(RSA)、椭圆曲线离散对数系统(ECC)和离散对数系统(DSA)。

3 RSA算法

3.1简介

目前最著名、应用最广泛的公钥体制RSA是由麻省理工学院(MIT)的Rivest、Shamir和Adleman在1978中发表的题为“获取数字签名和公钥密码体制的方法”的论文中提出的。它是一种基于数论和分组密码系统的非对称(公钥)密码系统。它的名字来自三个发明家的首字母。它的安全性是基于大整数素数分解的困难性，而大整数的分解是数学中著名的问题，没有有效的方法解决，所以RSA算法的安全性是可以保证的。RSA系统是公开密钥系统中最典型的方法。大多数使用公钥密码进行加密和数字签名的产品和标准都使用RSA算法。

RSA算法是第一个可以同时用于数据加密和数字签名的算法，因此它为公共网络上的信息加密和认证提供了一个基本的方法。通常是一对RSA密钥，其中一个是秘钥，由用户保管；另一种是公钥，可以公开，甚至可以在网络服务器中注册。人们使用公钥加密文件，并将其发送给个人，个人可以用私钥解密文件。为了提高安全强度，RSA密钥至少要有500位长，一般建议使用1024位。

该算法基于以下两个事实，这两个事实保证了RSA算法的安全性和有效性:

1)判断一个数是否为素数有一个快速算法；

2)确定一个合数的素因子的快速算法还没有找到。

3.2工作原理

1)任意选择两个不同的大素数p和q并计算乘积r = p * q；

2)任意选择一个大整数e，e与(p-1)*(q-1)互质，整数e作为加密密钥。注意:e的选取很容易，比如所有大于p和q的素数都有。

3)确定解密密钥D :D * E = 1 moduo(P-1)*(Q-1)根据E，P和Q，可以很容易地计算出D。

4)公开整数r和e，但不公开d；

5)将明文p(假设p是小于r的整数)加密成密文c，计算方法如下:

C = Pe模r

6)将密文c解密成明文p，计算方法如下:

P = Cd模r

但是，只从R和E(而不是P和Q)计算D是不可能的。因此，任何人都可以加密明文，但只有授权用户(知道D)才能解密密文。

3.3简单示例

为了说明算法的工作过程，下面我们举一个简单的例子。显然这里只能取很小的一个数，但是如上所述，为了保证安全，我们在实际应用中使用的数要大得多。

例:若p = 3，q = 5，则r=15，(p-1)*(q-1)=8。选择e=11(大于P和Q的素数)，由D * 11 = 1moduo8计算出d =3。

假设明文是13的整数。那么密文c就是

C = Pe模r

= 1311模15

= 1，792，160，394，037模15

= 7

恢复的明文p是:

P = Cd模r

= 73模15

= 343模15

= 13

因为E和D是互易的，所以公钥加密方法也允许加密的信息以这种方式被“签名”,从而接收方可以确信签名不是伪造的。

假设A和B想通过公钥加密传输数据，A和B分别公开了加密算法和对应的密钥，但没有公开解密算法和对应的密钥。A和B的加密算法是ECA和ECB，解密算法是DCA和DCB，ECA和DCA互逆，ECB和DCB互逆。如果A要发送明文P给B，不是简单的发送ECB(P)，而是先将其解密算法DCA应用于P，然后用加密算法ECB将结果加密后发送出去。

密文c是:

C =欧洲中央银行

B收到C后，依次应用其解密算法DCB和加密算法ECA，得到明文P:

非洲经委会

= ECA(DCB(ECB(DCA(P)))

= ECA(DCA(P))/*DCB和ECB相互抵消*/

=

p？/*DCB和ECB相互抵消*/

这样B就可以确认消息确实是从A发出的，因为只有加密过程使用DCA算法，P才能被ECA得到。只有A知道DCA算法，任何人，甚至B，都无法伪造A的签名。

3.4优点和缺点

3.4.1的优点

RSA算法是第一个既能用于加密又能用于数字签名的算法，也很容易理解和操作。RSA是研究最广泛的公钥算法。从提出到现在已经将近二十年了，经过各种攻击的考验，逐渐被人们所接受。它被普遍认为是目前最好的公钥方案之一。该算法的加密密钥与加密算法分离，使得密钥分发更加方便。特别适用于计算机网络环境。对于互联网上的大量用户来说，加密密钥可以在电话簿中打印出来。如果一个用户想与另一个用户进行秘密通信，他只需要从公钥本中找出对方的加密密钥，并用它来加密传输的信息。对方收到消息后，用只有自己知道的解密密钥对消息进行解密，从而知道消息的内容。可以看出，RSA算法解决了大量网络用户的密钥管理问题，这是公钥密码体制相比对称密码体制最突出的优势。

缺点

1)生成密钥很麻烦，受限于素数生成技术，很难做到一次一密。

2)安全性，RSA的安全性依赖于大数的因式分解，但并没有从理论上证明破译RSA的难度与大数因式分解的难度是等价的，密码学中的大多数人倾向于认为因式分解不是NPC问题。目前人们已经能够分解140以上的十进制素数，这需要使用更长的密钥，速度较慢；另外，目前人们也在积极寻找攻击RSA的方法，比如选择密文攻击。一般来说，攻击者会对某个信息进行盲复制，让有私钥的实体签名。然后，它可以通过计算得到它想要的信息。事实上，所有的攻击都利用了同一个弱点，即存在这样一个事实，即幂保持输入的乘法结构:

(XM )d = Xd *Md mod n

如前所述，这个固有的问题来自于公钥密码系统最有用的特性——每个人都可以使用公钥。但这个问题无法从算法上解决，主要有两种措施:一种是采用良好的公钥协议，保证实体不解密其他实体任意生成的信息，不签署自己一无所知的信息；另一个就是千万不要随便签署陌生人发来的文件。签名时，首先使用单向哈希函数对文档进行哈希，或者同时使用不同的签名算法。除了使用模数，人们还尝试了一些使用解密指数或φ(n)的攻击。

3)速度太慢。由于RSA的包长太大，为了保证安全性，n至少要600 bitx，使得运算成本非常高，特别是速度慢，比对称密码算法慢几个数量级；而且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前Set(安全电子交易)协议要求CA使用2048位密钥，其他实体使用1024位密钥。为了解决速度问题，目前人们广泛采用单密钥和公钥密码相结合的方法，两者优缺点互补:单密钥密码速度快，人们用它来加密长文件，再用RSA来加密文件密钥，很好地解决了单密钥密码的密钥分发问题。

4结论

目前，日益增长的电子商务和其他互联网应用的需求普及了公钥系统，公钥系统主要包括服务器资源的访问控制和电子商务交易的保护，以及权利、个人隐私、无线交易和内容完整性的保护(如确保新闻报道或股票报价的真实性)。公钥技术发展到今天，市场上明显的发展趋势是PKI与操作系统的融合。PKI是“公共的”

Key Infrastructure的缩写意为“公钥基础设施”。公钥系统广泛应用于CA认证、数字签名和密钥交换。

RSA是使用最广泛的公钥加密算法。RSA算法开发的最初思想和目标是让互联网安全可靠，旨在解决DES算法密钥通过开放信道传输和分发的难题。实际结果不仅很好地解决了这个问题；RSA还可以用来完成对消息的数字签名，以抵抗对消息的否认和否定；同时，利用数字签名可以很容易地发现攻击者对消息的非法篡改，从而保护数据信息的完整性。到目前为止，RSA算法已经被应用在很多加密技术中，在互联网的很多方面都得到了广泛的应用，包括安全接口层(SSL)标准的应用，这是web浏览器建立安全互联网连接所必需的。此外，RSA加密系统还可以应用于智能IC卡和网络安全产品。

但目前RSA算法的专利期即将结束，取而代之的是椭圆曲线密码体制(ECC算法)。与RSA算法相比，ECC有其相对优势，这使得ECC的特性更适合需要快速响应的电子商务的发展趋势。此外，一种全新的量子密码也正在研发中。

至于实际应用中应该采用哪种加密算法，要结合具体的应用环境和系统，不能简单的根据其加密强度来判断。因为除了加密算法本身，密钥的合理分配、加密效率与现有系统的结合、投入产出分析等都要在实际环境中考虑。随着网络的发展和更新，加密技术将产生更加安全和易于实现的算法，为信息安全提供更强有力的保障。未来，加密技术何去何从，我们拭目以待。

参考资料:

[1] Douglas R.Stinson,《密码学原理与实践》。北京:电子工业出版社，2003，2: 131-132。

[2]西蒙·辛格。密码的故事。海口:海南出版社，2001，1: 271-272。

[3]嬴政天下。加密算法的RSA算法。/yum dq/dzsw/a2.htm。

[5]黑客中级教程系列10。/jiaocheng/10.html