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

webp

上图三个帅哥是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()

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

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