圖解|什么是RSA算法
1. 數(shù)學(xué)之美和密碼學(xué)
前陣子閑來無事看了會兒《數(shù)學(xué)之美》,其中第17章講述了由電視劇《暗算》展開的密碼學(xué)背后的一些數(shù)學(xué)原理。
書中從凱撒密碼到二戰(zhàn)盟軍和日軍,講到密碼學(xué)中均勻分布&統(tǒng)計獨立的基礎(chǔ)理論,看得我津津有味,但是其中一些細(xì)節(jié)沒有整明白,于是決定搞篇文章。
2. 加密算法的一點歷史
我們知道常見的加密算法有:對稱加密和非對稱加密,非對稱加密是我們今天的主角。
非對稱加密不是一蹴而就的,它是1976年之后才出現(xiàn)的,可以說非對稱加密是對稱加密的優(yōu)化。
2.1 對稱加密的缺點
所謂對稱加密是指:發(fā)送方使用一種規(guī)則對信息進(jìn)行處理,接收方需要使用相同的規(guī)則對信息進(jìn)行逆向處理。
對稱加密要求通信雙方使用相同的規(guī)則和密鑰進(jìn)行加解密,這樣如何妥善保管密鑰和規(guī)則就非常重要了。
如果密鑰泄露那么再強(qiáng)大的對稱加密算法也是徒勞的,所以如何安全地交換對稱加密的規(guī)則和密鑰是短板。
如何安全地交換密鑰呢?讓人頭疼。
2.2 密鑰交換算法
1976年兩位美國計算機(jī)學(xué)家 Whitfield Diffie 和 Martin Hellman,提出了一種嶄新構(gòu)思,可以在不傳遞密鑰的情況下,完成解密,聽著很厲害的樣子,這難道就是江湖上傳說的隔空打牛?
其實這是被稱為 Diffie-Hellman 迪菲-赫爾曼密鑰交換算法,來看看維基百科上兩位大神的簡介:
這兩位大神是密碼學(xué)的先驅(qū),為非對稱加密算法指出了明路:雙方不一定要直接交換密鑰。
迪菲-赫爾曼密鑰交換算法中通信雙方并沒有真正交換密鑰,而是通過計算生成出一個相同的共享密鑰,具體的過程還是比較復(fù)雜,在此不展開了。
非對稱加密算法RSA借鑒了這種思想,使用公鑰和私鑰來完成加解密,但是又避免了密鑰傳輸,RSA算法的公鑰是公開的,使用公鑰加密的信息,必須使用對應(yīng)的私鑰才能解密。
3. RSA算法
RSA算法可以說是地球上最重要的算法之一,是數(shù)據(jù)通信和網(wǎng)絡(luò)安全的基石。
3.1 算法作者
RSA是1977年由羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)一起提出的。
當(dāng)時他們?nèi)硕荚诼槭±砉W(xué)院工作,RSA就是他們?nèi)诵帐祥_頭字母拼在一起組成的。
RSA算法密鑰越長越難破解,根據(jù)相關(guān)文獻(xiàn),目前被破解的最長RSA密鑰是768個二進(jìn)制位。一般認(rèn)為,1024位的RSA密鑰基本安全,2048位的密鑰極其安全,RSA算法目前支持4096位長度。
密鑰長度和加解密的時間是成正比的,因此我們需要根據(jù)自己的場景來選擇密鑰長度,不必追求一味長密鑰。
3.2 算法過程
RSA算法的本質(zhì)就是數(shù)學(xué),公鑰和私鑰是數(shù)學(xué)上關(guān)聯(lián)的,無須直接傳遞。
算法過程包括:密鑰生成、密鑰加解密。
3.2.1 密鑰生成
RSA算法的密鑰是成對的,公鑰加密私鑰解密,來看下這對密鑰是如何被計算出來的。
-
1.隨機(jī)選擇兩個質(zhì)數(shù)P和Q
我們選擇P=61,Q=53,計算PQ的乘積N=PQ=61*53=3233,將N轉(zhuǎn)換為二進(jìn)制:110010100001,N的二進(jìn)制長度是12,也就是密鑰長度為12。
本文只是闡述算法原理,在實際中密鑰長度在1024位以上才安全,12位基本上就是個演示。
-
2.求N的歐拉函數(shù)值M
歐拉函數(shù)的定義:任意給定正整數(shù)n,請問在小于等于n的正整數(shù)之中,有多少個與n構(gòu)成互質(zhì)關(guān)系?
歐拉函數(shù)有個通用的計算公式:
要證明歐拉函數(shù)需要分為很多種情況,特別地,當(dāng)n是質(zhì)數(shù)時會出現(xiàn)一些特殊的情況。
直接來個結(jié)論:
a. 如果k是質(zhì)數(shù),則φ(k) = k-1;
b.如果 n = P * Q,P 與 Q 均為質(zhì)數(shù),則 φ(n) = φ(P * Q)= φ(P)φ(Q) = (P - 1)(Q - 1) 。
P=61、Q=53 則N=3233,那么N的歐拉函數(shù)記為M=(P-1)*(N-1) = 60*52=3120
-
3.找一個與M互素的整數(shù)E
M和E之間除了1以外沒有公約數(shù)(互質(zhì))且E<M,我們隨機(jī)選擇E為17。 -
4.找一個整數(shù)D,滿足如下關(guān)系:
(E*D) mod M = 1,換句話說E和D的乘積除以M的余數(shù)為1,這里有一個術(shù)語-模逆元,也就是指有一個整數(shù)d,可以使得ed被φ(n)除的余數(shù)為1。
等價于 如下計算過程:
當(dāng)E=17,M=3120,K=1,2,3...時,
17*D - K*M = 1,求解這個方程找到一組滿足關(guān)系的D和K即可,可證其中一組為(D,K)=(2753,15)。
綜上所述,我們找到了通過隨機(jī)選擇的互質(zhì)的P和Q計算得到N、M、E、D,我們把這些數(shù)字分為兩組:(E,N)和(D,N)分別為公鑰組和私鑰組,E是公鑰、D是私鑰。
在本例中公鑰組為(E,N)=(17,3233),私鑰組(D,N)=(2753,3233),接下來我們將使用這對密鑰進(jìn)行加解密。
3.2.1 加密過程
由于RSA算法本質(zhì)是數(shù)字的運算,因此我們在對字符串進(jìn)行加密時需要先將字符串?dāng)?shù)值化,可以借助ascii碼、unicode編碼、utf-8編碼等將字符串轉(zhuǎn)換為數(shù)字。
需要特別注意轉(zhuǎn)換后的數(shù)字X需要小于密鑰組中的N,如果字符串轉(zhuǎn)換后的數(shù)字大于N則需要進(jìn)行拆分,這可能也是在數(shù)據(jù)量大時我們使用對稱加密算法來加密內(nèi)容,用非對稱加密算法來加密密鑰的原因吧。
加密過程滿足:
X^E mod N = Y
其中X為明文,E為公鑰,N為大整數(shù),Y為密文,mod取余運算。
3.2.3 解密過程
我們獲得密文Y后,開始解密,過程滿足:
Y^D mod N = X
其中Y為密文,D為私鑰,N為大整數(shù),X為明文,mod取余運算。
上述的加密和解密過程涉及到了費爾馬小定理。
3.2.4 歐拉定理和費爾馬小定理
這塊有點晦澀,但是確實RSA算法的核心部分,簡單看下吧:
費爾馬小定理給出了素數(shù)檢測性質(zhì),歐拉對其進(jìn)行了證明,也就是費馬-歐拉定理。
3.3 RSA算法可靠性分析
經(jīng)過上面的密鑰生成、加解密過程,我們難免要問:RSA算法可靠嗎?通過公鑰組(E,N)能否推導(dǎo)出私鑰D呢?
來梳理一下:
-
由于ed≡1 (mod φ(N)),只有知道e和φ(N),才能算出d,e是公鑰匙,所以需要知道φ(N)就可以。
-
根據(jù)歐拉函數(shù) φ(N)=(P-1)(Q-1),只有知道P和Q,才能算出φ(N)。
-
N=pq,只有將N進(jìn)行因數(shù)分解,才能算出P和Q。
所以,如果大數(shù)N可以被因數(shù)分解,私鑰D就可以算出,從而破解密文。
3.5 大整數(shù)因數(shù)分解
大整數(shù)的因數(shù)分解是極其困難的,屬于NPC問題,除了暴力破解沒有很好的解決方案,目前人類分解的最大長度的二進(jìn)制數(shù)為768位,1024位的長度目前尚未破解,因此1024長度的二進(jìn)制密鑰是安全的。
所以RSA算法的安全性取決于大整數(shù)分解的難度,目前RSA算法可以支持4096位密鑰長度,分解難度超乎想象,即使借助于量子計算機(jī)難度和時間都是非常非常大的。
4. 總結(jié)
本文從對稱加密算法傳遞密鑰安全性為起點,說到迪菲-赫爾曼算法進(jìn)行密鑰交換協(xié)商,該算法為RSA算法的公鑰和私鑰提供了靈感。
麻省理工的三位數(shù)學(xué)家在歐拉定理&費爾馬定理等等一些數(shù)學(xué)定理的基礎(chǔ)上創(chuàng)造了偉大的RSA非對稱加密算法。
RSA算法的安全性取決于大數(shù)質(zhì)因數(shù)分解的難度,目前而言1024位二進(jìn)制長度的密鑰人類都沒有破解,為了安全性考慮可使用2048位長度的RSA密鑰進(jìn)行加密。
確實是燒腦的硬核內(nèi)容啊,不由得感嘆素數(shù)真是個神奇的東西,段位有限只能拋磚引玉,到此為止啦!
感謝各位的傾情閱讀,如果有問題請?zhí)砑哟蟀孜⑿牛?span style="color: rgb(255, 76, 65);">baymax9901
免責(zé)聲明:本文內(nèi)容由21ic獲得授權(quán)后發(fā)布,版權(quán)歸原作者所有,本平臺僅提供信息存儲服務(wù)。文章僅代表作者個人觀點,不代表本平臺立場,如有問題,請聯(lián)系我們,謝謝!