公开密钥密码体制的RSA算法简介

1. 公开密钥密码体制的RSA算法简介

正是基于这种理论，1978年出现了著名的RSA算法。这种算法为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。

2. 密钥密码体系的公开密钥算法RSA

公开密钥算法是在1976年由当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)两人首先发明的（论文New Direction in Cryptography）。但目前最流行的RSA是1977年由MIT教授Ronald L.Rivest,Adi Shamir和Leonard M.Adleman共同开发的,分别取自三名数学家的名字的第一个字母来构成的。1976年提出的公开密钥密码体制思想不同于传统的对称密钥密码体制，它要求密钥成对出现，一个为加密密钥(e)，另一个为解密密钥(d)，且不可能从其中一个推导出另一个。自1976年以来，已经提出了多种公开密钥密码算法，其中许多是不安全的， 一些认为是安全的算法又有许多是不实用的，它们要么是密钥太大，要么密文扩展十分严重。多数密码算法的安全基础是基于一些数学难题， 这些难题专家们认为在短期内不可能得到解决。因为一些问题(如因子分解问题)至今已有数千年的历史了。公钥加密算法也称非对称密钥算法，用两对密钥：一个公共密钥和一个专用密钥。用户要保障专用密钥的安全；公共密钥则可以发布出去。公共密钥与专用密钥是有紧密关系的，用公共密钥加密的信息只能用专用密钥解密，反之亦然。由于公钥算法不需要联机密钥服务器，密钥分配协议简单，所以极大简化了密钥管理。除加密功能外，公钥系统还可以提供数字签名。公钥加密算法中使用最广的是RSA。RSA使用两个密钥，一个公共密钥，一个专用密钥。如用其中一个加密，则可用另一个解密，密钥长度从40到2048bit可变，加密时也把明文分成块，块的大小可变，但不能超过密钥的长度，RSA算法把每一块明文转化为与密钥长度相同的密文块。密钥越长，加密效果越好，但加密解密的开销也大，所以要在安全与性能之间折衷考虑，一般64位是较合适的。RSA的一个比较知名的应用是SSL，在美国和加拿大SSL用128位RSA算法，由于出口限制，在其它地区（包括中国）通用的则是40位版本。RSA算法研制的最初理念与目标是努力使互联网安全可靠，旨在解决DES算法秘密密钥的利用公开信道传输分发的难题。而实际结果不但很好地解决了这个难题；还可利用RSA来完成对电文的数字签名以抗对电文的否认与抵赖；同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完性。 公用密钥的优点就在于，也许你并不认识某一实体，但只要你的服务器认为该实体的CA是可靠的，就可以进行安全通信，而这正是Web商务这样的业务所要求的。例如信用卡购物。服务方对自己的资源可根据客户CA的发行机构的可靠程度来授权。目前国内外尚没有可以被广泛信赖的CA。美国Natescape公司的产品支持公用密钥，但把Natescape公司作为CA。由外国公司充当CA在我国是一件不可想象的事情。公共密钥方案较保密密钥方案处理速度慢，因此，通常把公共密钥与专用密钥技术结合起来实现最佳性能。即用公共密钥技术在通信双方之间传送专用密钥，而用专用密钥来对实际传输的数据加密解密。另外，公钥加密也用来对专用密钥进行加密。在这些安全实用的算法中，有些适用于密钥分配，有些可作为加密算法，还有些仅用于数字签名。多数算法需要大数运算，所以实现速度很慢，不能用于快的数据加密。以下将介绍典型的公开密钥密码算法-RSA。RSA算法很好的完成对电文的数字签名以抗对数据的否认与抵赖；利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完整性。目前为止，很多种加密技术采用了RSA算法，比如PGP（PrettyGoodPrivacy）加密系统，它是一个工具软件，向认证中心注册后就可以用它对文件进行加解密或数字签名，PGP所采用的就是RSA算法。由此可以看出RSA有很好的应用。

3. 什么是公钥密码算法？

20世纪70年代，美国学者Diffie和Hellman，以及以色列学者Merkle分别独立地提出了一种全新的密码体制的概念。Diffie和Hellman首先将这个概念公布在1976年美国国家计算机会议上，几个月后，他们这篇开创性的论文《密码学的新方向》发表在IEEE杂志信息论卷上，由于印刷原因，Merkle对这一领域的贡献直到1978年才出版。他们所创造的新的密码学理论，突破了传统的密码体制对称密钥的概念，竖起了近代密码学的又一里程碑。
不同于以前采用相同的加密和解密密钥的对称密码体制，Diffie和Hellman提出了采用双钥体制，即每个用户都有一对选定的密钥：一个是可以公开的，另一个则是秘密的。公开的密钥可以像电话号码一样公布，因此称为公钥密码体制或双钥体制。公钥密码体制的主要特点是将加密和解密的能力分开，因而可以实现多个用户的信息只能由一个用户解读；或只能由一个用户加密消息而由多个用户解读，前者可以用于公共网络中实现保密通信，而后者可以用于认证系统中对消息进行数字签名。公开密钥密码的基本思想是将传统密码的密钥一分为二，分为加密密钥Ke和解密密钥Kd，用加密密钥Ke控制加密，用解密密钥Kd控制解密。而且由计算复杂性确保加密密钥Ke在计算上不能推导出解密密钥Kd。这样，即使将Ke公开也不会暴露Kd，也不会损害密码的安全。于是便可以将Ke公开，而只对Kd保密。由于Ke是公开的，只有Kd是保密的，因此从根本上克服了传统密码在密钥分配上的困难。
公开密钥密码满足的条件根据公开密钥密码的基本思想，可知一个公开密钥密码应当满足下面三个条件：
解密算法D和加密算法E互逆，即对所有明文M都有，D(E(M,Ke),Kd)=M。在计算上不能由Ke推导出Kd。算法E和D都是高效的。条件1是构成密码的基本条件，是传统密码和公开密钥密码都必须具备的起码条件。条件2是公开密钥密码的安全条件，是公开密钥密码的安全基础，而且这一条件是最难满足的。目前尚不能从数学上证明一个公开密钥密码完全满足这一条件，而只能证明它不满足这一条件。条件3是公开密钥密码的工程实用条件。因为只有算法E和D都是高效的，密码才能实用。否则，密码只有理论意义，而不能实际应用。满足了以上三个条件，便可构成一个公开密钥密码，这个密码可以确保数据的秘密性。然而还需要确保数据的真实性，则还需满足第四个条件。4.对于所有明文M都有E(D(M,Kd),Ke)=M。条件4是公开密钥密码能够确保数据真实性的基本条件。如果满足了条件1、2、4，同样可以构成一个公开密钥密码，这个密码可以确保数据的真实性。如果同时满足以上四个条件，则公开密钥密码可以同时确保数据的秘密性和真实性。此时，对于所有的明文M都有D(E(M,Ke),Kd)= E(D(M,Kd),Ke)=M。公开密钥密码从根本上克服了传统密码在密钥分配上的困难，利用公开密钥密码进行保密通信需要成立一个密钥管理机构（KMC），每个用户将自己的姓名、地址和公开的加密密钥等信息在KMC登记注册，将公钥记入共享的公开密钥数据库。KMC负责密钥的管理，并对用户是可信赖的。这样，用户利用公开密钥密码进行保密通信就像查电话号码簿打电话一样方便，再也不需要通信双方预约密钥，因此特别适合计算机网络应用，而且公开密钥密码实现数字签名容易，所以特别受欢迎。下图是公钥密码体制的框图，主要分为以下几步：
网络中要求接收消息的端系统，产生一对用来加密和解密的密钥，如图中的接收者B，产生一对密钥PKB，SKB，其中PKB是公开钥，SKB是秘密钥。端系统B将加密密钥（图中的PKB）存储在一个公开的寄存器或文件中，另一密钥则被保密（图中个SKB）。A要想向B发送消息m，则使用B的公开钥加密m，表示为 c=EPKB[m] 其中，c是密文，E是加密算法。B收到密文c后，用自己的秘密钥SKB解密，表示为 m=DSKB[c] 其中，D是解密算法。因为只有B知道SKB，所以其他人无法对c解密。这就是公开密钥的原理~
（转载需向本人获取权限）

4. 公钥的RSA

RSA公钥系统发明于新思想提出后一年在麻省理工学院，里维斯特(Ronald Rivest)、沙米尔(Adi Shamir)和阿德勒曼(Len Adleman)提出第一个较完善的公钥密码体制——RSA体制，由三位发明人的姓氏首字母命名。这是一种建立在大数因子分解基础上的算法。它是第一个成熟的、迄今为止理论上最成功的公钥密码体制。它的安全性是基于数论中的大整数因子分解。该问题是数论中的一个困难问题，至今没有有效的算法，（即大整数因子分解不能在多项式时间内完成）这使得该体制具有较高的保密性。并且得到了广泛应用。不为人知的是，早在1970年的秘密研究中，英国情报机构GCHQ的数学家James H. Ellis便已发明非对称钥匙密码学，而且Diffie-Hellman与RSA都曾被Malcolm J. Williamson与Clifford Cocks分别发明于前。这两个最早的公钥系统提供优良的加密法基础，因而被大量使用。其他公钥系统还有Cramer-Shoup、Elgamal、以及椭圆曲线密码学等等。这些事件直到1997年历史文件解密的时候才为大众所知。

5. 关于RSA算法 求密钥和加密

n=pq=1457,所以公钥对（n,e）=（1457,77）
(p-1)*(q-1)=1380,要e2*e mod 1380 =1,所以e2=233，所以私钥对（1457，233）

N=M^e mod n=921


综上所述，密钥（应该是私钥）是（1457，233），加密得到921

6. 如何描述RSA密钥交换算法

　　密钥交换算法中讲到的密钥都是一般指对称加密算法的密钥（注意区别：非对称算法自己本身的密钥），因为对于对称算法的特性来说，采取”一次一密”的话才比较安全。
　　RSA，可以用做密钥传输算法，即使用对端的RSA公钥对密钥进行加密，对端使用自己的私钥对其进行解密，就可以获取密钥。
　　RSA密钥生成步骤:

　　RSA加密和解密步骤:

7. 什么是RSA公钥密码

RSA公钥密码
RSA公钥密码是1977年由Ron Rivest、Adi Shamirh和LenAdleman在MIT(美国麻省理工学院〉开发的,1978年首次公布[RIVE78]。它是目前最有影响的公钥加密算法,它能够抵抗到目前为止已知的所有密码攻击。目前它已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但是想分解它们的乘积却极端困难,因此可以将乘积公开作为加密密钥。

RSA的算法结构相当简单,整个算法可以描述如下:

(1)选取两个大素数p和q(保密)；

(2)计算n=pq(公开),γ=(p一1〉(q-1)(保密)；

(3)随机选取整数e(公开,加密密钥),使得ed(ear)=1

(4)计算d(保密,私人密钥),使得ed≡1(mod r),即d=e-1(mod r);

（5)加密:c=me mod n

(6)解密:m=cd mod n。

利用RSA对被加密的信息m (长度小于log2n的整数)进行加密得到相应的密文c=me mod n;解密算法则是计算m=cd modn RSA的优点是不需要密钥分配,但缺点是速度慢。RSA公钥密码 RSA 公钥 密码

8. 密码学笔记5——公钥密钥及RSA密码

   发送方     a.A首先查PKDB，查到B的公开的加密钥keB   b.A用KeB加密M得到密文C:C=E(M,KeB)   c.A发C给B     接受方     a.B接受C   b.B用自己的KdB解密，得到明文M=D(C,KdB)=D(E(M.KeB),KdB)     安全性分析     1.只有B才有KdB，因此只有B才能解密，确保了数据的秘密性   2.任何人都可以查PKDB得到B的KeB，所以任何人都可以冒充A给B发送数据，不能保证数据的真实性。
     发送方     a.A首先用自己的KdA对M进行解密，得到C=D(M,kdA)   b.A发C给B     接受方     a.B接受C   b.B查PKDB查到A公开的加密钥KeA   c.B用KeA加密C，得到明文M=E（C,KeA)=E(D(M,KdA),KeA)     安全性分析     1.只有A才有KdA，因此只有A才能解密，确保了数据的真实性   2.任何人都可以查PKDB得到A的KeA，所以任何人都可以加密得到明文，不能保证数据的秘密性
     发送方     a.A首先用自己的KdA对明文M进行解密得到S=D(M,KdA)   b.A查PKDB，查到B公开的密钥KeB   c.A用KeB加密S得到C=E（S，KeB）   d.A发C给B     接受方     a.B接受C   b.B用自己的KdB解密C，得到S=D(C,KdB)   c.B查PKDB，查到Ade公开密钥KeA   d.B用A的公开的加密钥KeA加密S，得到M=E(S,KeA)     安全性分析     1.只有A才有KdA，因此只有A才能解密，确保了数据的真实性   2.只有B才有KdB，只有B才能进行解密，保证了数据的秘密性
   a.随机选择两个大素数p和q，而且保密   b.计算n=pq，公开n   c.计算O(n)=(p-1)(q-1) 对O(n)保密（这里O(n)代表计算n的欧拉函数）   d.随机选择一个正整数e，1<e<O(n)且gcd（e,O(n))=1,将e公开   e.根据ed=1modO(n),求出d，并对d保密     加密：C=M^e mod n       解密：M=C^d mod n=(M e) d mod n=M^ed mod n       这里，私钥为{d，n},公钥为{e,n}  
                                             这里明文对应的每一个字母分别与一个两位的十进制数对应（a=00,A=26)