rsa算法由原理到实现

《rsa算法由原理到实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、希赛网技术频道，IT新技术

2、构架设计

3、嵌入式

4、Web工程

5、案例剖析

6、网络工程

7、数据库工程

8、分布式

9、IT运维本文版权归希赛网技术频道所有，未经许可，任何媒体均不得改变其形式进行转载或摘录，违者必究！张峰岭RSA是目前使用最广的公钥密码算法,本文比较全面地从原理到实现介绍了这个得到广泛接受和实现的算法，并简要介绍了一些攻击RSA的方法。1.一个公开环境下的信息加密，在加密算法是公开的情况下，唯一能保证信息加密的是密钥。在常规的对称加密算法中，如DES,加密和解密密钥是相同的，即信息的发送者和合法接收者使用相

10、同的密钥，意味前提条件为信息发送者和合法接收者互相认识或互相信任,而且意味着密钥将分布在通信的每个节点，由此而带来了密钥管理的问题。如果泄露了密钥意味着公开了所有秘密。如果使加密密钥和解密密钥不相同，我们可以把加密密钥公开作为公钥，信息合法接收者保管解密密钥作为私钥，则以上提到的问题则可以解决。RSA算法是目前应用最广的公钥密码，有Rivest,Shamir和Adleman在1977年提出。它基于一个非常简单的数论难题，很容易将两个素数乘起来，但分解该乘积却非常困难，从而，该乘积可以公开且可作为加密公钥

11、。不能从该乘积恢复这两个素数。解密需要用到这两个素数。从而用很简单的形式实现了非常可靠的密码系统。2.RSA1)选取两个大素数,p和q.计算乘积n=pq,n的欧拉函数?(n)=(p-1)(q-1)2)随机选取d(d>1),满足(d,?(n))=1,根据欧几里德算法,存在整数x,y,满足xd+y?(n)=1取e=x,显而易见,e满足(e,?(n))=1且ed≡1(mod?(n))d=e-1(mod?(n))3)e和n构成公开密钥作为E，即E=(n,e),d和n构成私人密钥作为D,即D=(n,d).E=(n

12、,e)可以公开。这时两个素数p和q可以不再需要，它们应该被舍弃，但绝不可泄露。1)获得信息接收者的公开密钥E=(n,e)2)将明文分组:m=m0,m1,m2,…,mk-1,使得每个mivkV.?玸玓希赛网技术频道，I

13、T新技术

14、构架设计

15、嵌入式

16、Web工程

17、案例剖析

18、网络工程

19、数据库工程

20、分布式

21、IT运维1)对每一组密文做解密变换mi=D(ci)=cd(modn)2)合并分组得到明文m=m0,m1,m2,…,mk-13.RSA设a,b∈Z,a≠0,如果存在q∈Z使得b=aq,那么就说b可被a整除，记作a

22、b，a是b的约数。设p≠0,±1,如果它除了显然约数±1,±p外没有其他的约数，那么，p就称为是素数，否则为合数。素数有无穷多个证明：用反证法，假设素数为有穷多个，设有n个，从2开始由小到大我们可以得到一个有限的素数

23、集合{qi

24、qi是素数且1<=i<=n}。我们考察a=q1q2….qn+1,因为我们知道qn是最大的素数，所以a是一个合数，且a大于所有素数，所以a至少可以被一个素数整除,设为qi,qi

25、a,因为又qi

26、q1q2…qn，所以qi

27、a-q1q2…qn，即qi

28、1,由于qi>2，所以假设是错误的，即素数必有无穷多个。：设a,b是两个给定的整数，a≠0,那么，一定存在唯一的一对整数q与r,满足b=qa+r,0≤r<

29、a

30、.此外，a

31、b的充要条件是r=0：设u0,u1是给定的两个整数，u1≠0,u1不整除u0,

32、则我们一定可以重复应用定理4得到下面k+1个等式:u0=q0u1+u2,0

33、u1

34、u1=q1u2+u3,0

35、u1

36、>u2>u3>…>uj+1>0对uj,uj+1不断用定理3.3.1，由于小于

37、u1

38、的正整数只有有限个以及1整除任一整数，所以这过程不能无限制地做下去，一定会出现某个k,要么1

39、uk,要么1=uk+1

40、uk：设a1,a2是两个整

41、数.如果d

42、a1且d

43、a2,那么，d就称为是a1和a2的公约数,a1,a2的公约数中最大的称为a1和a2的最大公约数，记作(a1,a2).设a1,…,ak是k个不全为零的整数,a1,…,ak的最大公约数,记作(a1,….,ak)最大公约数有以下几条性质:(i)若a1

44、aj,j=2,…,k,则(a1,a2)=(a1,a2,…,ak)=(a1)=

45、a1

46、;(ii)对任意整数x,(a1,a2)=(a1,a2,a1x)(a1,…,ak)=(a1,…