Chinaunix首页 | 论坛 | 博客
  • 博客访问: 180826
  • 博文数量: 24
  • 博客积分: 205
  • 博客等级: 入伍新兵
  • 技术积分: 365
  • 用 户 组: 普通用户
  • 注册时间: 2012-08-29 12:43
文章分类

全部博文(24)

文章存档

2015年(20)

2013年(1)

2012年(3)

我的朋友

分类: 网络与安全

2015-06-03 16:11:03

RSA算法中利用欧几里得算法求d详细过程

RSA是第一个也是使用的最广泛的公钥加密算法,在1978年由R.Rivest、AdiShamir和Adleman三人发明,并以他们的名字命名。RSA算法的安全性基于大数因子分解的困难性,下面介绍一下它的基本原理:


1、生成公钥和私钥

(1)选取两个大素数:p和q;
(2)计算n=p*q;
(3)计算小于n并且与n互质的整数的个数,即欧拉函数?(n)=(p-1)*(q-1);
(4)随机选择加密密钥e,使1
(5)最后,利用Euclid(欧几里得)算法计算解密密钥d,使其满足ed=1(mod ?(n))。

然后将(e,n)公开,即为公钥PK,私人保存好d,即为私钥SK;

2、加密

将明文m分解成等长数据块m1,m2,……,mi。加密时,按如下公式进行计算即可:

ci=(mie(mod n),密文c则由c1,c2,……ci组成。

 

3、解密

与加密一样,按如下公式进行计算:

mi=(cid(mod n),明文m则由m1,m2,……,mi组成。


以上就是RSA算法的公私钥产生、加密和解密的过程。整个过程中,最难理解的部分应是1.5中的求私钥d,很多课本提到的都是用欧几里得算法,但并未给出具体的计算过程,下面本人就通过一个实例向大家介绍欧几里得算法在RSA中的应用。

例:令p=47,q=71,求用RSA算法加密的公钥和私钥。

计算如下:

(1)n=pq=47*71=3337;
(2)?(n)=(p-1)*(q-1)=46*70=3220;
(3)随机选取e=79(满足与3220互质的条件);
(4)则私钥d应该满足:79*d mod 3220 = 1;

那么这个式子(4)如何解呢?这里就要用到欧几里得算法(又称辗转相除法),解法如下:

(a)式子(4)可以表示成79*d-3220*k=1(其中k为正整数);
(b)将3220对79取模得到的余数60代替3220,则变为79*d-60*k=1;
(c)同理,将79对60取模得到的余数19代替79,则变为19*d-60*k=1;
(d)同理,将60对19取模得到的余数3代替60,则变为19*d-3*k=1;
(e)同理,将19对3取模得到的余数1代替19,则变为d-3*k=1;

当d的系数最后化为1时,

令k=0,代入(e)式中,得d=1;
将d=1代入(d)式,得k=6;
将k=6代入(c)式,得d=19;
将d=19代入(b)式,得k=25;
将k=25代入(a)式,得d=1019,这个值即我们要求的私钥d的最终值。

此时,我们即可得到公钥PK=(e,n)={79,3337},私钥SK={1019,3337},后面的加密和解密直接套相应公式即可。

阅读(2650) | 评论(0) | 转发(1) |
0

上一篇:RSA 加解密算法

下一篇:RSA加密算法(转)

给主人留下些什么吧!~~