2022年RSA加密算法加密與解密過(guò)程解析

1、RSA 加密算法加密與解密過(guò)程解析1. 加密算法概述加密算法依據(jù)內(nèi)容是否可以仍原分為 可逆加密和非可逆加密；可逆加密依據(jù)其加密解密是否使用的同一個(gè)密鑰而可以分為 對(duì)稱加密和非對(duì)稱加密；所謂對(duì)稱加密即是指在加密和解密時(shí)使用的是同一個(gè)密鑰：舉個(gè)簡(jiǎn)潔的例子,對(duì)一個(gè)字符串 C 做簡(jiǎn)潔的加密處理, 對(duì)于每個(gè)字符都和A 做異或,形成密文 S；解密的時(shí)候再用密文 S 和密鑰 A 做異或,仍原為原先的字符串 C；這種加密方式有一個(gè)很大的缺點(diǎn)就是擔(dān)憂全,由于一旦加密用的密鑰泄露了之后,就可以用這個(gè)密鑰破解其他全部的密文；非對(duì)稱加密在加密和解密過(guò)程中使用不同的密鑰,即公鑰和私鑰； 公鑰用于加密,全部人都可見,私鑰

2、用于解密,只有解密者持有；就算在一次加密過(guò)程中原文和密文發(fā)生泄漏,破解者在知道原文、密文和公鑰的情形下無(wú)法推理出私鑰,很大程度上保證了數(shù)據(jù)的安全性；此處,我們介紹一種特殊具有代表性的非對(duì)稱加密算法,RSA 加密算法；RSA算法是 1977 年制造的,全稱是 RSA Public Key System,這個(gè) Public Key就是指的公共密鑰；2. 密鑰的運(yùn)算獵取過(guò)程密鑰的運(yùn)算過(guò)程為：第一選擇兩個(gè)質(zhì)數(shù)p 和 q,令 n=p*q ；令 k= .n =p-1q-1, 原理見 4 的分析選擇任意整數(shù) d ,保證其與 k 互質(zhì)取整數(shù) e,使得 dek=1k；也就是說(shuō) de=kt+1,t 為某一整數(shù)；3

3、.RSA 加密算法的使用過(guò)程同樣以一個(gè)字符串來(lái)進(jìn)行舉例,例如要對(duì)字符串the art of programming進(jìn)行加密, RSA 算法會(huì)供應(yīng)兩個(gè)公鑰 e 和 n ,其值為兩個(gè)正整數(shù),解密方持有一個(gè)私鑰 d ,然后開頭加密解密過(guò)程過(guò)程；1. 第一依據(jù)確定的規(guī)整將字符串轉(zhuǎn)換為正整數(shù)z,例如對(duì)應(yīng)為 0 到 36 ,轉(zhuǎn)化后形成了一個(gè)整數(shù)序列；2. 對(duì)于每個(gè)字符對(duì)應(yīng)的正整數(shù)映射值z(mì),運(yùn)算其加密值 M=Ne%n. 其中 Ne 表示 N 的 e 次方；3. 解密方收到密文后開頭解密,運(yùn)算解密后的值為Md%n ,可在此得到正整數(shù) z；4. 依據(jù)開頭設(shè)定的公共轉(zhuǎn)化規(guī)章,即可將z 轉(zhuǎn)化為對(duì)應(yīng)的字符,獲得明文；

4、4.RSA 加密算法原懂得析下面分析其內(nèi)在的數(shù)學(xué)原理,說(shuō)到RSA 加密算法就不得不說(shuō)到歐拉定理；歐拉定理 Euler s theorem 是歐拉在證明費(fèi)馬小定理的過(guò)程中,發(fā)覺的一個(gè)適用性更廣的定理；第確定義一個(gè)函數(shù),叫做歐拉Phi 函數(shù),即 .n ,其中, n 是一個(gè)正整數(shù)；.n= 總數(shù)從 1 到 n-1 ,與 n 互質(zhì)整數(shù) 比如 5 ,那么 1 ,2 ,3 ,4 ,都與 5 互質(zhì)；與 5 互質(zhì)的數(shù)有 4 個(gè)； .5=4再比如 6 ,與 1 ,5 互質(zhì),與 2 ,3 ,4 并不互質(zhì)；因此, .6=2對(duì)于一個(gè)質(zhì)數(shù) p 來(lái)說(shuō),它和 1, 2, 3, , p 1 都互質(zhì),所以 .p=p-1；比如 .

5、7=6, .11=10歐拉定理表達(dá)如下：歐拉定理：假如 n 是一個(gè)正整數(shù), a 是任意一個(gè)非 0 整數(shù),且 n 和 a 互質(zhì)；那么, a .n-1 可以被 n 整除；推論 1 ：假如 m 和 n 是互質(zhì)的正整數(shù)；那么,推論 2 ：abn=anbnn.mn= .m .n 證明：假設(shè) a 和 b 除以 n 的余數(shù)為 c1,c2 ；a 和 b 可以寫成a=nt1+c1,b=nt2+c2；那么, ab=n2t1t2+nt1c2+nt2c1+c1c2；因此 ab除以 n 的余數(shù)為 c1c2 ；即 abn=anbn；有以上定理后,由此可以推導(dǎo)出 RSA 算法的內(nèi)在原理；依據(jù)歐拉定理,對(duì)于任意z .nn=z

6、kn=1n 因此,z,假如 z 與 n 互質(zhì),那么：zden=zkt+1n=zkt*zn=zktn*zn= zn 由于 zkn = 1n 上面主要使用了de=kt+1以及推論 2 ；也就是說(shuō)：zden=zn 依據(jù) 2 的推論,有zend=zn 即 d 個(gè)余數(shù)相乘,由于其乘積可能大于n ,所以由 abn=anbnn,例如令 a 和 b 都為 5 ,n 為 3 ,可知該結(jié)論故上式可描述為 zendn=zn=z,就是原數(shù)字乘方求余數(shù),然后再乘方求余數(shù)后得到原先數(shù)字的過(guò)程,得證；公開的加密方式,私有的解密方式；數(shù)進(jìn)行因子分解；5.RSA 加密的缺點(diǎn)RSA 安全的關(guān)鍵在于很難對(duì)一個(gè)大的整1 ）產(chǎn)生密鑰很麻煩, 受到素?cái)?shù)產(chǎn)生技術(shù)的限制, 因而難以做到一次一密；2 ）安全性,RSA 的安全性依靠于大數(shù)的因子分解, 但并沒(méi)有從理論上證明破譯 RSA的難度與大數(shù)分解難度等價(jià), 而且密碼學(xué)界多數(shù)人士?jī)A向于因子分解不是 NP 問(wèn)題；3 ）速度太慢,由于 RSA