關(guān)于RSA耕捞，你了解它嗎？
說(shuō)起RSA烫幕，可能很多人都或多或少了解過(guò)俺抽，看到了它，腦子里就打印出幾個(gè)字“一種加密算法”较曼，但真正讓你講出其原理呢凌埂？額...好像它變陌生了。哈哈诗芜，此時(shí)你就不得不靜下心來(lái)問(wèn)自己瞳抓，真的了解它嗎？
只要有戰(zhàn)爭(zhēng)伏恐，就會(huì)有密碼孩哑，加密方式也就隨之出現(xiàn)。提及RSA翠桦，就不得不說(shuō)一下密碼學(xué)横蜒。密碼學(xué)的歷史大致可以追溯到兩千年前胳蛮，相傳古羅馬名將凱撒大帝為了防止敵方截獲情報(bào)，用密碼傳送情報(bào)丛晌。凱撒的做法很簡(jiǎn)單仅炊，就是對(duì)二十幾個(gè)羅馬字母建立一張對(duì)應(yīng)表。這樣澎蛛，如果不知道密碼本抚垄，即使截獲一段信息也看不懂。
?在1976年以前谋逻，所有的加密方法都是同一種模式：加密呆馁、解密使用同一種算法。在交互數(shù)據(jù)的時(shí)候毁兆，彼此通信的雙方就必須將規(guī)則告訴對(duì)方浙滤，否則沒(méi)法解密。那么加密和解密的規(guī)則（簡(jiǎn)稱密鑰）气堕，它保護(hù)就顯得尤其重要纺腊。傳遞密鑰就成為了最大的隱患。這種加密方式被成為對(duì)稱加密算法（symmetric encryption algorithm）
?1976年茎芭，兩位美國(guó)計(jì)算機(jī)學(xué)家迪菲（W.Diffie）摹菠、赫爾曼（M.Hellman）提出了一種嶄新構(gòu)思，可以在不直接傳遞密鑰的情況下骗爆，完成密鑰交換次氨。這被稱為“迪菲赫爾曼密鑰交換”算法。開(kāi)創(chuàng)了密碼學(xué)研究的新方向
?1977年三位麻省理工學(xué)院的數(shù)學(xué)家羅納德·李維斯特（RonRivest）摘投、阿迪·薩莫爾（AdiShamir）和倫納德·阿德曼（LeonardAdleman）一起設(shè)計(jì)了一種算法煮寡，可以實(shí)現(xiàn)非對(duì)稱加密。這個(gè)算法用他們?nèi)齻€(gè)人的名字命名犀呼，叫做RSA算法幸撕，RSA也就由此而來(lái)。
RSA的數(shù)學(xué)原理
說(shuō)到了數(shù)學(xué)原理外臂，大家可曾還記得以前學(xué)過(guò)的歐拉函數(shù)坐儿？不記得了？沒(méi)關(guān)系宋光，繼續(xù)往下看貌矿。
首先在這里，我們一起回憶以下幾個(gè)概念：
如果兩個(gè)正整數(shù)罪佳，除了1以外逛漫，沒(méi)有其他公因數(shù)，我們就稱這兩個(gè)數(shù)是互質(zhì)關(guān)系（coprime）赘艳。
那么
任意給定正整數(shù)n酌毡，請(qǐng)問(wèn)在小于等于n的正整數(shù)之中克握，有多少個(gè)與n構(gòu)成互質(zhì)關(guān)系呢？
其實(shí)呀枷踏，計(jì)算這個(gè)值的方式就叫做歐拉函數(shù)菩暗，使用：Φ(n)表示（此函數(shù)以其首名研究者歐拉命名）
如:
計(jì)算8的歐拉函數(shù)，和8互質(zhì)的1旭蠕、2停团、3、4下梢、5客蹋、6塞蹭、7孽江、8 ????????φ(8) = 4
計(jì)算7的歐拉函數(shù)，和7互質(zhì)的1番电、2岗屏、3、4漱办、5这刷、6、7????????????????φ(7) = 6
可是當(dāng)這個(gè)正整數(shù)n過(guò)大的時(shí)候娩井，怎么去計(jì)算呢暇屋？顯然口算是很難的，這個(gè)時(shí)候我們也發(fā)現(xiàn)了一些特殊對(duì)應(yīng)關(guān)系：
如計(jì)算56的歐拉函數(shù)
φ(56) =? φ(8) *? φ(7) = 4 * 6 = 24（ps：不信的同學(xué)可以自己列出來(lái)去數(shù)一數(shù)哦洞辣，但要認(rèn)真別數(shù)錯(cuò)了）
可以看出咐刨，歐拉函數(shù)是由一些特點(diǎn)的
歐拉函數(shù)特點(diǎn)
1、當(dāng)n是質(zhì)數(shù)的時(shí)候扬霜，φ(n)=n-1定鸟。
2、如果n可以分解成兩個(gè)互質(zhì)的整數(shù)之積著瓶，如n=A*B則： φ(A*B)=φ(A)*φ(B)
根據(jù)以上兩點(diǎn)得到：
如果N是兩個(gè)質(zhì)數(shù)P1和?P2的乘積則
φ(N)=φ(P1)*φ(P2)=(P1-1)*(P2-1)
歐拉定理
如果兩個(gè)正整數(shù)m和n互質(zhì)联予，那么m的φ(n)次方減去1，可以被n整除材原。
還有一個(gè)歐拉定理的特殊情況：
費(fèi)馬小定理（這個(gè)你自己可以隨便舉些例子驗(yàn)證）
如果兩個(gè)正整數(shù)m和n互質(zhì)沸久，而且n為質(zhì)數(shù)！那么φ(n)結(jié)果就是n-1余蟹。
現(xiàn)在我們來(lái)進(jìn)行一些列公式轉(zhuǎn)換
此時(shí)麦向，我們先記錄下此轉(zhuǎn)換結(jié)果；
模反元素
如果兩個(gè)正整數(shù)e和x互質(zhì)客叉，那么一定可以找到整數(shù)d诵竭，使得 ed-1 被x整除话告。那么d就是e對(duì)于x的模反元素
因?yàn)閑*d 一定是x的倍數(shù)加1，所以在此轉(zhuǎn)換一次：
此時(shí)卵慰，想起之前我們轉(zhuǎn)換的結(jié)果
此時(shí)我們發(fā)現(xiàn)了兩個(gè)公式有一定的關(guān)系沙郭，因此最終轉(zhuǎn)換
此公式成立的前提是：1.d是e相對(duì)于(n)的模反元素（?
(n)就相當(dāng)于x?）;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?2.m < n
我們也可以用python3（做運(yùn)算很方便哦）來(lái)驗(yàn)證一下下：
m經(jīng)過(guò)一些列運(yùn)算后仍得m，那么是不是嗅出了一絲加密的味道呢裳朋？
?mod ?n?
?m ?????: ? ? ? ? ?
? ?（加密）
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? C mod n = m ? ? （解密）
這樣會(huì)出現(xiàn)一個(gè)問(wèn)題：加密的結(jié)果C會(huì)非常大
那么如何有效的拆分這個(gè)公式呢
迪菲赫爾曼密鑰交換
此圖中客戶端和服務(wù)器約定了一個(gè)數(shù)17得到它的源根3病线，
客戶端取隨機(jī)數(shù)13、服務(wù)器取隨機(jī)數(shù)15鲤嫡；
客戶端將通過(guò)運(yùn)算將加密的結(jié)果12傳遞給服務(wù)器送挑；而服務(wù)器通過(guò)運(yùn)算將6傳遞給客戶端；
我們可以知道通過(guò)傳遞的只有12和6兩個(gè)數(shù)字暖眼，黑客就算截獲后由于不知道私密數(shù)據(jù)13和15惕耕，所以他是沒(méi)有辦法得到10的
交換原理
說(shuō)明：
公鑰：n和e
私鑰：?n和d
明文:???m
密文:???c
關(guān)于RSA的安全：
除了公鑰用到了n和e其余的4個(gè)數(shù)字是不公開(kāi)的。
目前破解RSA得到d的方式如下：
1诫肠、要想求出私鑰?d?司澎。由于e*d=φ(n)*k+1。要知道e和φ(n);
2栋豫、e是知道的挤安，但是要得到?φ(n)，必須知道p1和?p2丧鸯。
3蛤铜、由于?n=p1*p2。只有將n因數(shù)分解才能算出丛肢。
因此
n會(huì)非常大围肥，長(zhǎng)度一般為1024個(gè)二進(jìn)制位。（目前人類已經(jīng)分解的最大整數(shù)摔踱，232個(gè)十進(jìn)制位虐先，768個(gè)二進(jìn)制位），這樣就保證了RSA的可靠性派敷。
最后由于RSA計(jì)算量比較大蛹批，進(jìn)而效率低，適合加密小數(shù)據(jù)類型的文件篮愉。（ps：RSA通常用來(lái)加密密鑰腐芍、數(shù)字簽名等）。
以上就是本人對(duì)RSA的理解歸納试躏，如果有誤煩請(qǐng)指出喲猪勇。
