《RSA算法由原理到实现.doc》由会员分享，可在线阅读，更多相关《RSA算法由原理到实现.doc（33页珍藏版）》请在金锄头文库上搜索。
1、希赛网技术频道，IT新技术|构架设计|嵌入式|Web工程|案例剖析|网络工程|数据库工程|分布式|IT运维 本文版权归希赛网技术频道所有，未经许可，任何媒体均不得改变其形式进行转载或摘录，违者必究！ 张峰岭 RSA是目前使用最广的公钥密码算法,本文比较全面地从原理到实现介绍了这个得到广泛接受和实现的算法，并简要介绍了一些攻击RSA的方法。 1. 一个公开环境下的信息加密，在加密算法是公开的情况下，唯一能保证信息加密的是密钥。在常规的对称加密算法中，如DES,加密和解密密钥是相同的，即信息的发送者和合法接收者使用相同的密钥，意味前提条件为信息发送者和合法接收者互相认识或互相信任,而且意味着密钥将
2、分布在通信的每个节点，由此而带来了密钥管理的问题。如果泄露了密钥意味着公开了所有秘密。 如果使加密密钥和解密密钥不相同，我们可以把加密密钥公开作为公钥，信息合法接收者保管解密密钥作为私钥，则以上提到的问题则可以解决。 RSA算法是目前应用最广的公钥密码，有Rivest,Shamir和Adleman在1977年提出。它基于一个非常简单的数论难题，很容易将两个素数乘起来，但分解该乘积却非常困难，从而，该乘积可以公开且可作为加密公钥。不能从该乘积恢复这两个素数。解密需要用到这两个素数。从而用很简单的形式实现了非常可靠的密码系统。 2.RSA 1)选取两个大素数,p和q.计算乘积n=pq ,n的欧拉函
3、数?(n)=(p-1)(q-1) 2)随机选取d(d1),满足(d, ?(n)=1,根据欧几里德算法,存在整数x,y,满足 xd+y?(n)=1 取e=x ,显而易见,e满足(e, ?(n)=1且 ed1(mod ?(n) d=e-1(mod ?(n) 3)e和n构成公开密钥作为E，即E=(n,e), d和n构成私人密钥作为D,即D=(n,d).E=(n,e)可以公开。这时两个素数p和q可以不再需要，它们应该被舍弃，但绝不可泄露。 1) 获得信息接收者的公开密钥E=(n,e) 2)将明文分组:m=m0,m1,m2,mk-1 ,使得每个mivkV.?玸玓 希赛网技术频道，IT新技术|构架设计|嵌
4、入式|Web工程|案例剖析|网络工程|数据库工程|分布式|IT运维 1)对每一组密文做解密变换mi=D(ci)=cd (mod n) 2)合并分组得到明文m=m0,m1,m2,mk-1 3.RSA 设a,bZ,a0,如果存在qZ使得b=aq,那么就说b可被a整除，记作a|b，a是b的约数。 设p0,1,如果它除了显然约数1, p外没有其他的约数，那么，p就称为是素数，否则为合数。 素数有无穷多个 证明：用反证法，假设素数为有穷多个，设有n个，从2开始由小到大我们可以得到一个有限的素数集合qi|qi是素数且1=i 2，所以假设是错误的，即素数必有无穷多个。 ：设a,b是两个给定的整数，a0,那么
5、，一定存在唯一的一对整数q与r,满足 b=qa+r,0r|a|.此外，a|b的充要条件是r=0 ：设u0,u1是给定的两个整数，u10,u1不整除u0,则我们一定可以重复应用定理4得到下面k+1个等式: u0=q0u1+u2, 0u2|u1| u1=q1u2+u3, 0u3u2 u2=q2u3+u4, 0u4u3 uk-1=qk-1uk+uk+1, 0uk+1u2u3uj+10 对uj,uj+1不断用定理3.3.1，由于小于|u1|的正整数只有有限个以及1整除任一整数，所以这过程不能无限制地做下去，一定会出现某个k,要么1uk+1|uk,要么1=uk+1|uk ：设a1,a2是两个整数.如果d
6、|a1且d|a2,那么，d就称为是a1和a2的公约数,a1,a2的公约数中最大的称为a1和a2的最大公约数，记作(a1,a2).设a1,ak是k个不全为零的整数,a1,ak的最大公约数,记作(a1,.,ak) 最大公约数有以下几条性质: (i)若a1|aj,j=2,k,则(a1,a2)=(a1,a2,ak)=(a1)=|a1|; (ii)对任意整数x,(a1,a2)=(a1,a2,a1x) (a1,ak)=(a1,ak,a1x) 希赛网技术频道（http:/） 0731-8873047-8000， 第 2 页 00， 第 1 ?希赛网技术频道，IT新技术|构架设计|嵌入式|Web工程|案例剖析
7、|网络工程|数据库工程|分布式|IT运维 (iii)对任意整数x,(a1,a2)=(a1,a2+a1x), (a1,ak)=(a1,a2+a1x,a3,ak) ：若(a1,a2)=1,则称a1和a2是既约的，也称a1和a2是互素的. ：设正整数m|(a1,ak).我们有m(a1/m,ak/m)=(a1,ak) 特别地有1),.,(,.,),.,(111=kkkaaaaaa (公式9) 证:设D=(a1,ak).由m|D,D|aj(1 = j =k)知m|aj(1=j=k),因而有 (D/m)|(aj/m), j=1,k。所以D/m =(a1/m,ak/m)，另一方面，若d|(aj/m),1=j
8、=k,则有md|aj ,1=j=k ，所以md=D ，即d0,我们有(mb1,mbk)=m(b1,bk) 证:设aj=mbj,根据定理3.4.3可以得证 :设(m,a)=1,我们有(m,ab)=(m,b) 证: (m,b)=(m,b(m,a)=(m,(bm,ba)=(m,mb,ab)=(m,ab) :设(m,a)=1,若m|ab,则m|b 证:(m,a)=1,所以根据定理3.4.5,(m,b)=(m,ab)，若m|ab,则有(m,ab)=|m|，即(m,b)=|m|,所以m|b. 设a1,a2是两个不全为零的整数，那么，一定存在整数x1,x2，使得 (a1,a2)=x1*a1+x2*a2 证:
9、见217-18页 设a1,ak是k个均不等于零的整数.如果a1|L,ak|L，则称L是a1,ak的公倍数，我们把正的公倍数中最小的称为a1,ak的最小公倍数.记为a1,ak :设m0,有ma1,.,mak=ma1,.,ak 证:maj|ma1,.,mak,所以aj|ma1,.,mak/m,所以a1,.,ak=ma1,.,mak/m另一 方面aj|a1,.,ak，所以maj|ma1,.,ak,所以ma1,.,mak=ma1,.,ak，所以ma1,.,mak=ma1,.,ak。 aj|c(1=j ac(mod m) ab(mod m), cd(mod m) 则a+cb+d(mod m) 证:由m|
10、a-b,m|c-d = m|(a-b)+(c-d) =m|(a+c)-(b+d)= a+cb+d(mod m) ab(mod m), cd(mod m) 则acbd(mod m) 证：ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d) ab(mod m) =m|a-b cd(mod m)=m|c-d 所以m|c(a-b)+b(c-d)即m|ac-bd 所以 acbd(mod m) 证:d|m,m|a-b =d|a-b = ab(mod d) 证: m|a-b ,dm|da-db 又m|dm 所以dadb(mod m) 等价于 ab(mod m/(c,m)，特别当 (c,m)=1时，
11、上式等价于 ab(mod m)。 证: cacb(mod m) 即m|c(a-b) 等价于)(),(|),(bacmccmm? 根据定理2.4.3结论有1),(,),(=cmccmm ,根据定理2.4.5和上式有 )(|),(bacmm?。得证 证:根据定理3.4.7,存在ax0+my0=1,取c=x0 即满足要求。 希赛网技术频道（http:/） 0731-8873047-8000， 第 4 页 .,mak,所以aj|ma1,.,mak/m,所以a1,.,ak=ma1,.,mak/m另一 方面a希赛网技术频道，IT新技术|构架设计|嵌入式|Web工程|案例剖析|网络工程|数据库工程|分布式|IT运维 ab(m
