RSA算法原理及实现
- 格式：pdf
- 大小：109.95 KB
- 文档页数：3
RSA算法原理及实现
参考资料：
薄薄的密码学课本：《现代密码学》第⼆版陈鲁⽣ 等编著
写在前⾯：在DES之后，⼜迎来了蛋疼的年轻的巫婆布置的新⼀轮作业—RSA。拖了好久才开始写，写的过程也是艰难⽆⽐，对⼀个看到数
学⽅法就头疼的⼈来说- -应该⽊有⽐RSA更折腾⼈的事⼉了。课本上讲RSA的时候，⾸先唠唠叨叨了⼀⼤堆数论的知识，还不告诉你这个知
识点有什么⽤，各种看不下去。我觉得对于计算机系，⽽不是数学系的学⽣来讲，理解算法，不应该是那么复杂的事⼉。于是有了这篇，希
望能⽐上⼀篇DES理得清楚⼀点⼉。
⼀、 RSA是什么？
RSA是⽬前最有影响⼒的公钥加密算法，它能够抵抗到⽬前为⽌已知的绝⼤多数密码攻击，已被ISO推荐为公钥数据加密标准。
那公钥加密算法⼜是什么？
公钥加密，⾮对称加密。简单的说，就是明⽂通过公钥加密，但只能通过密钥来解密。假设机器A需要向机器B传送⼀段极隐私的数据，要
求只有机器B能解密，就需要机器B⽣成⼀对密钥，其中公钥向包括机器A在内的所有⼈公布，那机器A就可以⽤公钥加密传送的数据，机器
B接收到之后⽤私钥解密，其他⼈没有私钥，即使捕获到机器A发送的消息，也⽆法解密。
⼆、 RSA实现基本思路
RSA公钥密码体制描述如下：（m为明⽂，c为密⽂）
1. 选取两个⼤素数p,q。p和q保密
2. 计算n=pq，r=(p-1)(q-1)。n公开，r保密
3. 随机选取正整数1
4. 计算d，满⾜de=1(mod r).d是保密的解密密钥
5. 加密变换： c=m^e mod n
6. 解密变换： m=c^d mod n
三、 RSA为什么能⽤公钥加密，私钥解密？
RSA算法基于⼀个⼗分简单的数论事实：将两个⼤素数相乘⼗分容易，但是想要对其乘积进⾏因式分解却极其困难，因此可以将乘积公开作
为加密密钥。
四、 算法实现的关键点⼀ Miller-Rabin素性测试算法
待补充
五、 算法实现的关键点⼆ a^b%n的计算
这个是很简单的⼀个算法。
def fast_mul(a,b,n):
c=1
while b!=0:
if b%2==0:
b=b/2
a=(a*a)%n
elif b%2!=0:
b=b-1
c=(c*a)%n
return c
⽂字描述如下：
1. c=1
2. 如果b=0,输出c，结束
3. 如果b mod 2 ≠0，转到第五步4. b=b/2,a=(a*a)mod n，转到第三步
5. b=b-1，c=(c*a)mod n，转到第⼆步
六、 算法实现的关键点三 乘法逆元这个货
先说什么是乘法逆元：对于整数a、p，如果存在整数b，满⾜ab mod p =1，则说，b是a的模p乘法逆元。
算法实现（扩展的欧⼏⾥得算法）：
def ExtendedEuclid(n,u):
x1=y2=1
x2=y1=0
if n>u:
x3,y3=[n,u]
else:
x3,y3=[u,n]
while 1:
if y3==0:
return x3+u
elif y3==1:
return y2+u
q=x3/y3
t1,t2,t3=[x1-q*y1,x2-q*y2,x3-q*y3]
x1,x2,x3=[y1,y2,y3]
y1,y2,y3=[t1,t2,t3]
例：5模14的乘法逆元：
14=5*2+4
5=4+1
5与14互素，存在5关于14的乘法逆元。
1=5-4=5-(14-5*2)=5*3-14
因此，5关于模14的乘法逆元为3。
七、 萌萌哒源码（python实现）
1 # -*- coding:utf-8 -*-
2
3 import math
4 import random
5
6 #this function is for a^b%n
7 def fast_mul(a,b,n):
8 c=1
9 while b!=0:
10 if b%2==0:
11 b=b/2
12 a=(a*a)%n
13 elif b%2!=0:
14 b=b-1
15 c=(c*a)%n
16
17 return c
18
19 def ExtendedEuclid(n,u):
20 x1=y2=1
21 x2=y1=0
22 if n>u:
23 x3,y3=[n,u]
24 else:
25 x3,y3=[u,n]
26
27 while 1:
28 if y3==0:
29 return x3
30 elif y3==1:
31 return y2
32
33 q=x3/y3
34 t1,t2,t3=[x1-q*y1,x2-q*y2,x3-q*y3]
35 x1,x2,x3=[y1,y2,y3]
36 y1,y2,y3=[t1,t2,t3]
37
38 def MillerRabin(n):
39 m=n-1 40 k=a=b=0
41 while m/2*2 == m:
42 k+=1
43 m=m/2
44 a=random.random()%n
45 while a<1:
46 a+=1
47 b=fast_mul(a,m,n)
48 if 1==b:
49 return 1
50 for x in range(k):
51 if(b==n-1):
52 return 1
53 else:
54 b=b*b%n
55 return 0
56
57 def get_prime(max_num):
58 prime_num=[]
59 for i in xrange(2,max_num):
60 temp=0
61 sqrt_max_num=int(math.sqrt(i))+1
62 for j in xrange(2,sqrt_max_num):
63 if 0==i%j:
64 temp=j
65 break
66 if temp==0:
67 prime_num.append(i)
68
69 return prime_num
70
71 def get_key():
72 prime=get_prime(500)
73 print prime[-80:-1]
74 while 1:
75 prime_str=raw_input("please choose two prime number from above x1,x2: ").split(",")
76 p,q=[int(x) for x in prime_str]
77 if (p in prime) and (q in prime):
78 break
79 else:
80 print "the number you enter is not prime number."
81
82 N=p*q
83 r=(p-1)*(q-1)
84 r_prime=get_prime(r)
85 r_len=len(r_prime)
86 e=r_prime[int(random.uniform(0,r_len))]
87 d=(ExtendedEuclid(e,r)+r)%r;
88
89 return ((N,e),(N,d))
90
91 def encode(pub_key,origal):
92 N,e=pub_key
93 return fast_mul(origal,e,N)
94
95 def decode(pri_key,encry):
96 N,d=pri_key
97 return fast_mul(encry,d,N)
98
99 if __name__=='__main__':
100 pub_key,pri_key=get_key()
101 print "public key: ",pub_key
102 print "private key: ",pri_key
103
104 origal_text=raw_input("please input the origal text: ")
105 encode_text=[encode(pub_key,ord(x)) for x in origal_text]
106 decode_text=[chr(decode(pri_key,x)) for x in encode_text]
107
108 encode_show=",".join([str(x) for x in encode_text])
109 decode_show="".join(decode_text)
110 print "encode text: ",encode_show
111 print "decode text: ",decode_show
View Code
