分类: 网络与安全
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=(mi)e(mod n),密文c则由c1,c2,……ci组成。
3、解密
与加密一样,按如下公式进行计算:
mi=(ci)d(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},后面的加密和解密直接套相应公式即可。