RSA加密算法是最常用的非对称加密算法,CFCA在证书服务中离不了它。但是有不少新来的同事对它不太了解,恰好看到一本书中作者用实例对它进行了简化而生动的描述,使得高深的数学理论能够被容易地理解。我们经过整理和改写特别推荐给大家阅读,希望能够对时间紧张但是又想了解它的同事有所帮助。

RSA是第一个比较完善的公开密钥算法,它既能用于加密,也能用于数字签名。RSA以它的三个发明者Ron Rivest, Adi Shamir, Leonard Adleman的名字首字母命名,这个算法经受住了多年深入的密码分析,虽然密码分析者既不能证明也不能否定RSA的安全性,但这恰恰说明该算法有一定的可信性,目前它已经成为最流行的公开密钥算法。

RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数(100到200位十进制数或更大)的函数。从一个公钥和密文恢复出明文的难度,等价于分解两个大素数之积(这是公认的数学难题)。

RSA的公钥、私钥的组成,以及加密、解密的公式可见于下表:

可能各位同事好久没有接触数学了,看了这些公式不免一头雾水。别急,在没有正式讲解RSA加密算法以前,让我们先复习一下数学上的几个基本概念,它们在后面的介绍中要用到:

一、 什么是“素数”?

素数是这样的整数,它除了能表示为它自己和1的乘积以外,不能表示为任何其它两个整数的乘积。例如,15=3*5,所以15不是素数;又如,12=6*2=4*3,所以12也不是素数。另一方面,13除了等于13*1以外,不能表示为其它任何两个整数的乘积,所以13是一个素数。素数也称为“质数”。

二、什么是“互质数”(或“互素数”)?

小学数学教材对互质数是这样定义的:“公约数只有1的两个数,叫做互质数。”这里所说的“两个数”是指自然数。

判别方法主要有以下几种(不限于此):

(1)两个质数一定是互质数。例如,2与7、13与19。

(2)一个质数如果不能整除另一个合数,这两个数为互质数。例如,3与10、5与 26。

(3)1不是质数也不是合数,它和任何一个自然数在一起都是互质数。如1和9908。

(4)相邻的两个自然数是互质数。如 15与 16。

(5)相邻的两个奇数是互质数。如 49与 51。

(6)大数是质数的两个数是互质数。如97与88。

(7)小数是质数,大数不是小数的倍数的两个数是互质数。如 7和 16。

(8)两个数都是合数(二数差又较大),小数所有的质因数,都不是大数的约数,这两个数是互质数。如357与715,357=3×7×17,而3、7和17都不是715的约数,这两个数为互质数。等等。

三、什么是模指数运算?

指数运算谁都懂,不必说了,先说说模运算。模运算是整数运算,有一个整数m,以n为模做模运算,即m mod n。怎样做呢?让m去被n整除,只取所得的余数作为结果,就叫做模运算。例如,10 mod 3=1;26 mod 6=2;28 mod 2 =0等等。

模指数运算就是先做指数运算,取其结果再做模运算。如

好,现在开始正式讲解RSA加密算法。

算法描述:

(1)选择一对不同的、足够大的素数p,q。

(2)计算n=pq。

(3)计算f(n)=(p-1)(q-1),同时对p, q严加保密,不让任何人知道。

(4)找一个与f(n)互质的数e,且1

(5)计算d,使得de≡1 mod f(n)。这个公式也可以表达为d ≡e-1 mod f(n)

这里要解释一下,≡是数论中表示同余的符号。公式中,≡符号的左边必须和符号右边同余,也就是两边模运算结果相同。显而易见,不管f(n)取什么值,符号右边1 mod f(n)的结果都等于1;符号的左边d与e的乘积做模运算后的结果也必须等于1。这就需要计算出d的值,让这个同余等式能够成立。

(6)公钥KU=(e,n),私钥KR=(d,n)。

(7)加密时,先将明文变换成0至n-1的一个整数M。若明文较长,可先分割成适当的组,然后再进行交换。设密文为C,则加密过程为:

(8)解密过程为:

实例描述:

在这篇科普小文章里,不可能对RSA算法的正确性作严格的数学证明,但我们可以通过一个简单的例子来理解RSA的工作原理。为了便于计算。在以下实例中只选取小数值的素数p,q,以及e,假设用户A需要将明文“key”通过RSA加密后传递给用户B,过程如下:

(1)设计公私密钥(e,n)和(d,n)。

令p=3,q=11,得出n=p×q=3×11=33;f(n)=(p-1)(q-1)=2×10=20;取e=3,(3与20互质)则e×d≡1 mod f(n),即3×d≡1 mod 20。

d怎样取值呢?可以用试算的办法来寻找。试算结果见下表:

通过试算我们找到,当d=7时,e×d≡1 mod f(n)同余等式成立。因此,可令d=7。从而我们可以设计出一对公私密钥,加密密钥(公钥)为:KU =(e,n)=(3,33),解密密钥(私钥)为:KR =(d,n)=(7,33)。

(2)英文数字化。

将明文信息数字化,并将每块两个数字分组。假定明文英文字母编码表为按字母顺序排列数值,即:

则得到分组后的key的明文信息为:11,05,25。

(3)明文加密

用户加密密钥(3,33) 将数字化明文分组信息加密成密文。由C≡Me(mod n)得:

因此,得到相应的密文信息为:11,31,16。

(4)密文解密。

用户B收到密文,若将其解密,只需要计算

,即:

用户B得到明文信息为:11,05,25。根据上面的编码表将其转换为英文,我们又得到了恢复后的原文“key”。

你看,它的原理就可以这么简单地解释!

当然,实际运用要比这复杂得多,由于RSA算法的公钥私钥的长度(模长度)要到1024位甚至2048位才能保证安全,因此,p、q、e的选取、公钥私钥的生成,加密解密模指数运算都有一定的计算程序,需要仰仗计算机高速完成。

(多选)RSA属于哪些密码体制?A非对称密码体制B序列密码体制C对称密码体制D传统密码体制E分组密码体制

A非对称密码体制,E分组密码体制。

n的欧拉函数=(5-1)*(7-1)=24

e和d的关系关于n的欧拉函数为逆元

也就是说 e*d=1(mod n的欧拉函数)

可以算出来5*5=1(mod 24) 也就是说d凑巧也为5

M=10的五次方(mod 35)

n的欧拉函数,永远算公钥和私钥也就是e和d

n用于加密解密

扩展资料:

RSA密码体制是根据PKC算法,该体制的理论基础是数论中的下述论断:要求得到两个大素数(如大到100位)的乘积在计算机上很容易实现,但要分解两个大素数的乘积在计算机上几乎不可能实现,即为单向函数。

由于进行的都是大数计算,使得RSA最快的情况也比DES慢上好几倍,无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA的速度比对应同样安全级别的对称密码算法要慢1000倍左右。

参考资料来源:百度百科-RSA算法

RSA、Diffie-Hellman和中间人攻击

网络上常常有对RSA、DH算法,以及中间人攻击的讨论。

一种说法是“RSA密钥协商(交换)不会受到中间人攻击”,听起来似乎RSA比DH做密钥协商更优。

这种说法有些不负责任。下面把这个问题中涉及到的概念都解释一下,再来看这个问题。

中间人攻击,可以这样解释:攻击者一定程度上控制了网络,成为网络双方通信的中间者,从而获取到双方的通信信息;而通信双方都感知不到中间人的存在。

这个话题往往和加密通信一起讨论:如果加密信道中存在中间人,那明文就会被中间人获取,而通信双方还不会知晓。

中间人攻击的根本,在于通信双方没有进行身份认证。即:不知道和自己直接通信的人是谁。如果双方能确认直接通信的人就是对方,也就不存在中间人攻击了。

RSA加密算法 是一种非对称加密技术。由一对密钥(公钥+私钥)组成。

可以利用私钥来生成公钥。

一般来说,私钥会被秘密保存起来,而公钥则分发出去。

公钥加密,私钥解密,称为RSA加密算法。 是为了保证公钥加密的内容,只有私钥持有者可以解密。常常用在客户端账密登录过程:客户端对密码进行公钥加密,发送到服务端后用私钥解密,这样即使请求被截获也不会泄露密码(实际上要更复杂一些)。

私钥加密,公钥解密,称为RSA签名算法。 是为了保证公钥持有者获取的内容,确实是来自私钥持有者的正确内容。比如服务器持有私钥,将一个重要信息计算hash再私钥签名后,和信息本身一起发送到客户端;客户端用公钥解密签名得到hash值,再计算信息的hash值,进行比对,就知道内容是否被篡改。由于私钥的保密性,攻击者无法伪造有效的签名。

DH密钥交换算法 并不是 加密算法,而是双方在不安全的网络中交换信息而生成双方仅有的密钥的一种方法。其结果是,交换的双方得到了一样的会话密钥,而其他任何人不能得到这个密钥。

由于算法的结果是通信双方拥有了一样的密钥,双方往往会利用这个密钥进行 对称 加密通信。

DH算法的过程可以简单解释如下:通信双方AB,各自生成一对DH密钥(Pa,Sa)和(Pb,Sb)(P代表公钥,S代表私钥)。双方交换各自的公钥P,于是A持有Sa、Pb,B持有Sb、Pa。通过某种计算,Sa、Pb可以生成会话密钥K,Sb、Pa也可以生成相同的K。

DH算法本身不包含身份认证机制,所以中间人攻击是其明显的问题。

设想:

在AB间,有一C。AB交换DH公钥P时,C在中间截获;C自己生成一对DH密钥(Pc,Sc),用Pc和A、B完成密钥交换。于是C与A间有了会话密钥Kac=f(Pa,Sc)=f(Pc, Sa),C与B间有了会话密钥Kcb=f(Pb,Sc)=f(Pc, Sb)。只要C从一方获得的信息,重新加密后传递给另一方,AB就都不会发现他们的通信被劫持了。

密钥协商(key establishment)包括“密钥传输”(key transmission)和“密钥交换”(key exchange)。

所谓RSA密钥协商实际是密钥传输,即一方生成密钥,传递给另一方,而不必双方交换。

具体来说,就是A自己生成一个密钥K,用自己的RSA公钥加密,再传递给B;B用RSA私钥解密得到K。仅就这个过程而言,不会存在中间人攻击。

但是这不是说RSA就比DH就更安全了。设想上面的情况,必须先要令A持有RSA公钥,B持有RSA私钥。这首先先进行一次RSA公钥传递,而这个传递过程是存在中间人攻击的。

设想:

B生成一对RSA密钥Pb、Sb,将公钥Pb发送给A。而AB中有C。C截获了Pb,而自己生成了一对RSA密钥Pc、Sc,将Pc发送给A。

A用Pc加密了会话密钥K,发送给B,被C截获。C用Sc解密得到K,再用Pb加密后给B。这时C完成了中间人攻击。

所以说: RSA的公钥在端与端间传递时,存在中间人攻击问题。

RSA最好的使用场景在服务端/客户端之间,服务端持有私钥,客户端直接内置好公钥,就不用担心中间人攻击了。

平时我们使用的,号称安全的https协议,也存在中间人攻击问题。比如Fiddler这种抓包软件,就能充当https通信中的中间人。

一般上网时使用的https是 单向认证 ,即客户端通过CA认证服务器持有有效证书,来确认其身份。服务器不会验证客户端的身份。

如果使用 双向认证 ,通过CA确认两端的身份都是正确的,就可以防止中间人攻击了。这种双向认证一般出现在企业应用对接中。

网络上有这样一种说法:

通信两端交换RSA公钥,通过对方公钥加密数据,自己私钥解密。这样就实现了端到端加密。

实际上这 不是端到端加密 。因为不能保证服务器无法修改数据:服务器可以用公钥来加密任何的数据发给两端。

而且,按之前所说的,这种交换, 存在中间人攻击问题

des和rsa属于什么加密技术

RAS:不对称加密算法

不对称加密算法使用两把完全不同但又是完全匹配的一对钥匙—公钥和私钥。在使用不对称加密算法加密文件时,只有使用匹配的一对公钥和私钥,才能完成对明文的加密和解密过程。加密明文时采用公钥加密,解密密文时使用私钥才能完成,而且发信方(加密者)知道收信方的公钥,只有收信方(解密者)才是唯一知道自己私钥的人。不对称加密算法的基本原理是,如果发信方想发送只有收信方才能解读的加密信息,发信方必须首先知道收信方的公钥,然后利用收信方的公钥来加密原文;收信方收到加密密文后,使用自己的私钥才能解密密文。显然,采用不对称加密算法,收发信双方在通信之前,收信方必须将自己早已随机生成的公钥送给发信方,而自己保留私钥。由于不对称算法拥有两个密钥,因而特别适用于分布式系统中的数据加密。广泛应用的不对称加密算法有RSA算法和美国国家标准局提出的DSA。以不对称加密算法为基础的加