非对称密码学实验：Python实现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编码组成，如下所示：
>>> a = '你'
>>> a
'\xc4\xe3'
>>>
则在加密过程中会出现这么一个问题，即无法实现ord()内置函数将字符转换ASCII码值
这是因为，ord()内置函数只能逐一返回一个字符串参数的ASCII码或Unicode值。对此，在python中可采用元组的方法存放输入的明文，在加密过程中逐一加密，具体实现代码可以往下看
基本上要注意的就这两点，其他的或多或少都是有现成的算法或者资料
贴一下代码
# 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()
运行结果：
截图截不全
下面是完整的：
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