首页 > 编程语言 > 详细

RSA加密算法

时间:2017-08-18 22:04:17      阅读:348      评论:0      收藏:0      [点我收藏+]

1.什么是RSA

  RSA是一种公钥加密算法,可用于公钥加密和数字签名

2.RSA加密

RSA加密过程可用下面的公式表达

密文=(明文^E) mod N

RSA的密文等于明文代表数字的E次方除以N 的余数

整个过程十分简单,只要知道E,N就能对明文进行加密。所以E,N的组合就是公钥。写成“公钥是{E,N}”

 

3.RSA解密过程

RSA解密也十分简单可用下面公式表达:

明文=(密文^D)mod N

所以D,N代表私钥(由于N是公钥的一部分,所以也可用说D是私钥)

 

下面就介绍如何生成E,D,N

4.密钥对生产

RSA密钥生成的步骤:

  (1)求N

  (2)求L (L是仅在生成密钥对的过程中使用的数)、

  (3)求E

  (4)求D

1.求N

  首先找到两个很大的素数p,q

N=p*q  (如果p,q太小密码会变得很容易破译)

2.求L

L是p-1,q-1的最小公倍数用lcm(p-1,q-1)表示

L=lcm(p-1,q-1)

3.求E

E是一个比1大,比L小的数。此外,E和L互质(最大公约数为1)

1<E<L
gcd(E,L)=1

找出gcd(E,L)=1的数,还要使用伪随机数生成器,生成大于1,小于L的E。再判断gcd(E,L)是否等于1.可用欧几里得辗转相除法求最大公约数

满足gcd(E,L)是为了保证一定存在解密所需要的D

求出E,N就生成了公钥

4.求D

数D由E计算得到。D、E、L之间必须存在下列关系:

1<D<L
E*D mod L=1

求出D 就是拥有了私钥

5.实践

准备两个质数p=17,q=19

N=17*19=323

L=lcm(17-1,19-1)=lcm(16,18)=144

有gcd(E,L)=1 可用得到E=5,7,11,13,17.……

E的选择有很多,这里选5,所以公钥是{E=5,N=323}

D*Emod L=1 E=5 可用找到D=29

所以私钥为{D=29,N=323}

1.加密

  要加密的明文必须是小于N的数

  假设明文为123

  密文=123^5 mod 323 =225

2.解密

  明文=225^29 mod 323=123

 

RSA加密算法

原文:http://www.cnblogs.com/hellow0rd/p/7392261.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!