非对称密码学实验:Python实现RSA的加解密

RSA

###上图三个帅哥是RSA的作者们
RSA算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但是想要对其乘积进行因式分解却极其困难。那么也就是说要使用RSA算法,前提是必须有两个大素数才行,那么你有没有想过大素数是怎么生成的呢?更进一步,考虑到RSA算法的高效性和安全性,怎样快速生成一个大素数呢?

###这里我用的是AKS素性测试

AKS素数测试(又被称为Agrawal–Kayal–Saxena素数测试和Cyclotomic AKS test)是一个决定型素数测试算法,由三个来自Indian Institute of Technology Kanpur的计算机科学家,Manindra Agrawal、Neeraj Kayal和Nitin Saxena,在2002年8月6日发表于一篇题为PRIMES is in P(素数属于P)的论文。作者们因此获得了许多奖项,包含了2006年的哥德尔奖和2006年的Fulkerson Prize。这个算法可以在多项式时间之内,决定一个给定整数是素数或者合数。

简单的说就是一个比较牛逼的算法
然后是中文的加解密问题
在计算机中汉字是由两个16进制的unicode编码组成,如下所示:

1
2
3
4
>>> a = '你'
>>> a
'\xc4\xe3'
>>>

则在加密过程中会出现这么一个问题,即无法实现ord()内置函数将字符转换ASCII码值
这是因为,ord()内置函数只能逐一返回一个字符串参数的ASCII码或Unicode值。对此,在python中可采用元组的方法存放输入的明文,在加密过程中逐一加密,具体实现代码可以往下看

基本上要注意的就这两点,其他的或多或少都是有现成的算法或者资料
贴一下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
# coding=utf-8
from Tkinter import *
import random

class RsaGUI(object):
def __init__(self):
self.top=Tk()
self.top.title('Hey~ I am RSA')
self.frame=[]
self.frame.append(Frame())
self.frame.append(Frame())
self.slbar=Scrollbar(self.frame[0],orient = HORIZONTAL)
self.slbar.pack(side=BOTTOM,fill=X)
self.MessageOut=Listbox(self.frame[0],height=25,fg='black')
self.MessageOut['xscrollcommand']=self.slbar.set
self.MessageOut.pack(expand=1,fill=BOTH)
self.slbar['command']=self.MessageOut.xview
self.frame[0].pack(expand=1,fill=BOTH)

self.MessageIn=Entry(self.frame[1],width=60,fg='red')
self.MessageIn.pack(expand=1,fill=X,pady=10,padx=15)

self.decryptButton=Button(self.frame[1],
text='Decrypt',
width=10,
command=self.DecryptText)
self.decryptButton.pack(side=BOTTOM and RIGHT,padx=20,pady=10)
self.encryptButton=Button(self.frame[1],
text='Encrypt',
width=10,
command=self.EncryptText)
self.encryptButton.pack(side=BOTTOM and RIGHT,padx=20,pady=10)

self.getKeyButton=Button(self.frame[1],text='Get Key',width=10,command=self.OnGetKey)
self.getKeyButton.pack(side=RIGHT,padx=20,pady=10)
self.frame[1].pack()

def EncryptText(self):
self.send_data=''
self.send_data=self.MessageIn.get()
# chinese trans
self.send_data=self.send_data.encode('utf-8')
self.send_data=str(self.send_data)
if self.send_data:
self.MessageOut.insert(END,'EncryptText: '+str(RSA_encrypt(rsa_e,rsa_n,self.send_data)))

def DecryptText(self):
if self.send_data:
self.MessageOut.insert(END,'DecryptText: '+str(RSA_decrypt(rsa_d,rsa_n,rsa_tep)))

def OnGetKey(self):
getKey()
self.MessageOut.insert(END,'p = '+str(rsa_p))
self.MessageOut.insert(END,'q = '+str(rsa_q))
# autoNewLine(str(rsa_p))
self.MessageOut.insert(END,'Public [e, n] = [')
self.MessageOut.insert(END, str(rsa_e)+',')
self.MessageOut.insert(END, str(rsa_n)+']')
self.MessageOut.insert(END,'Private [d, p, q] = [')
self.MessageOut.insert(END, str(rsa_d)+',')
self.MessageOut.insert(END, str(rsa_p)+',')
self.MessageOut.insert(END, str(rsa_q)+']')

# RSA解密模块
def RSA_decrypt(d, n, tep):
M=[]
for i in tep:
M.append(pow(i, d, n))
a=''
for i in M:
# 强制转换成字符,组合
a=a+chr(i)
print 'Dncrypt: ', a
return a

# RSA加密模块
def RSA_encrypt(e, n, plain):
global rsa_tep
print plain
M=plain
M=M.lower()
rsa_tep=[]
for i in M:
rsa_tep.append(pow(ord(i), e, n))
print 'Encrypt: ', rsa_tep
return rsa_tep

# 拓展的欧几里得算法__求e的逆元
def extended_euclid(a, b):
X1=1
X2=0
X3=b
Y1=0
Y2=1
Y3=a
while Y3!=1:
if Y3==0:
return 0 # if无逆元
Q=X3/Y3
T1=X1-Q*Y1;T2=X2-Q*Y2;T3=X3-Q*Y3
X1=Y1;X2=Y2;X3=Y3
Y1=T1;Y2=T2;Y3=T3
return Y2%b

# 判断是否互质
def gcd(a, b):
if a<b:
a, b=b, a
while b!=0:
temp=a%b
a=b
b=temp
return (a, b)

# 获取与欧拉数n互质的数e
def product_e(euler_n):
tepflag=1;counter=0
while tepflag:
e=random.randrange(euler_n)
counter=counter+1
if gcd(e,euler_n)==(1,0):
print "Get e, loop times: ",counter
tepflag=0
return e

#AKS素性检验
def _aks_(a,n):
flag=0;
a1=pow(17-a, n, n)
a2=pow(17, n, n)-(a%n)
if a1==a2:
return 1
else:
return 0

#获得一个大随机数
def get_big_number():
flag=0
while not flag:
n=random.randrange(2**50, 2**500) #在50位-500位之间选取
if(n%2==0 or n%3==0 or n%5==0 or n%7==0 or n%11==0 or n%13==0):
continue
flag=_aks_(2, n)
return n

def getKey():
global rsa_p
global rsa_q
global rsa_n
global rsa_euler_n
global rsa_e
global rsa_d
rsa_p=get_big_number()
rsa_q=get_big_number()
rsa_n=rsa_p*rsa_q
rsa_euler_n=(rsa_p-1)*(rsa_q-1) #产生欧拉数
rsa_e=product_e(rsa_euler_n) #扩展的欧几里得函数求逆元
rsa_d=extended_euclid(rsa_e,rsa_euler_n)

def main():
tkl=RsaGUI()
mainloop()

if __name__=='__main__':
main()

运行结果:
RSA2
截图截不全
下面是完整的:

1
2
3
4
5
6
7
8
9
10
11
p = 7326855850690054036992102055197163961428966481645933717527499041541336408261185728078214386943753172307077587749919638485366374214193839998566651401
q = 1369387723038847347871270089456692953723279926078304138187058103938898288915699017194034868979420868781578584365788217093586833345915264674173586972871
Public [e, n] = [
5825723550723421247430798564341540294589283053174102848266347288999064604869064113342622616689368012425571287262873139806910315105458666844506907698015289370382954676494616367022731178959743799351788721056973136730404804105173200259715756961277047962752920278187109982409067666696723816701346643487,
10033306450410309994497979473440865230177783292255674890725683807927850650738450510651529984555131154777101573597652185529358445560277171469572258249126140374743270242268544553019854776662463035971657942690816980800785641327552692911772441029318867075382523587699812010408933053774412269630701142271]
Private [d, p, q] = [
1493990191558338382406400665566680126478271410761120335959485984587717917636414607834536517016163946540461034407030157127655280935954385748815378651959325423969221964566101437424860156183269529058422048943922024634008785723758678038041292991663404678858753564154408286359396025281468378478185987423,
7326855850690054036992102055197163961428966481645933717527499041541336408261185728078214386943753172307077587749919638485366374214193839998566651401,
1369387723038847347871270089456692953723279926078304138187058103938898288915699017194034868979420868781578584365788217093586833345915264674173586972871]
EncryptText: [8887592300058450492822086878182759900356145482202031723702866978267949732256294407476798805114057348602643237096280418602743562534957273041862237552820838310881233230281780560443457554267282871317462789580667258564397953319559620108068932587523808859446554339458811513345743523857816826447686232865L, 6834498416759241213974999616174549488641544390621668870502972560431533010229312161564738881772923578428879704232365617318494494972685883582888019608385043252329053006663607685088557833337991929353772011535516307460752862797975171171502704547617894841650109870948975098587267744474667913930423940965L, 3869279189579724428195454235132073857975878252532336966466243867049743005598354893246969899221831247155876681684987372476064785257104820734635492772419565903063720683661106932377635125265637381385248193359963426517190923468001635943518894109637016487224791152179729083319043084983156869988125782687L, 6746074359876419363207279289318677351104588951575098673276065006465827095665218536893012494702469365384214518714725440506024547336515817354137843467756092743124574493528283827120866355428728220237201628496067256659094668674960834229711852316561554758880747426604097120765055394655084169102369066637L, 8221382923250271426555905690618561825002590141639342284052000568089013161242546960347065761116781886421836630112484171979060283942843104490503700919837371864159018252471538623621238524243183605661588427382797535316414576256574189955542949996840155250478634043194671059353123219977066637395054936840L, 6834498416759241213974999616174549488641544390621668870502972560431533010229312161564738881772923578428879704232365617318494494972685883582888019608385043252329053006663607685088557833337991929353772011535516307460752862797975171171502704547617894841650109870948975098587267744474667913930423940965L, 1448366456650053669558279092419953646980488946213085564573326996309662634071270258944934605686174072000555450709233437765021151111233552595765021519506876496762702136992950334926452359732404850510564076177748820888409491236239035735864936555855609688846447440224002426131617778613469058419821643903L, 510791589717577261010192033094346315725381798683627659773151205669805706358023289139819778089594838979745476196303932210257230214890964840334640723145528689189037964401780964641820345501845866492618235162509202063493552732973372926735804161227374919087207801949389273066044757619840542853496972139L, 7124119123461302685652319539247027333770318003527533830509059886323036179931142183434384778053096676005768151442341165215310175967958731468151850583371975329010522231201796884161642231064873301598301606512922785120289481320794580924468745901547520178429589168452280904061500131885115997465548141323L, 6526886137096206521927803575429984938690017507472540097729000771052454008652184754486255915360828239435222751778954305137956326273093255842705914556247370095745128007178908844962001234972381502526493550562483420055489105649077516960320729935712589671697968575844112678597916413495243865348253789709L, 5073245868817081730805935598162762711929351510267502524015550748490684465858059730173103487322049428021030181646773234921242815389013656861133631861056463445092141812192160688051618277318678042300560360996870515379389540127366336214677927278919698263367904504807919073658032005813950581092532803049L, 8067980453906149151571263692602878056159789665645787489183921357126574402349779209485676201574458193591420500036280750367356257443424859901852567047297027467699464738284473677898294086329162242988598815234595782419696501302510028446912212311541562482446212870764162565244446811088668954303168714891L]
DecryptText: 你好,rsa

参考资料:http://ju.outofmemory.cn/entry/93761