場(chǎng)景
人物：臥底余罪绿聘、警長(zhǎng)老許、毒梟老傅
事件：老許安排余罪潛伏到老傅的身邊
RSA是什么徙缴？
RSA是一種非對(duì)稱加密算法，是目前最好的加密方法嘁信。非對(duì)稱加密又叫公鑰加密娜搂，也就是說(shuō)成對(duì)的密鑰，其中一個(gè)是對(duì)外公開的吱抚，所有人都可以獲得百宇，稱為公鑰，而與之相對(duì)應(yīng)的稱為私鑰秘豹，只有這對(duì)密鑰的生成者才能擁有携御。這是警局成立初期一直在延用的一個(gè)加密算法。
RSA能干啥
余罪發(fā)現(xiàn)老傅近期有一次毒品販賣活動(dòng)既绕，需要將信息匯報(bào)給老許啄刹，讓其安排抓捕行動(dòng)。為了防止信息被竊聽凄贩，需要使用RSA對(duì)信息進(jìn)行加密誓军。
RSA加密規(guī)則
在臥底行動(dòng)以前，警局需要制作本次行動(dòng)的RSA秘鑰疲扎，一個(gè)公鑰昵时，一個(gè)私鑰。根據(jù)RSA的規(guī)范椒丧，分以下幾步進(jìn)行生成
- 隨機(jī)選擇兩個(gè)不相等的質(zhì)數(shù)p和q壹甥。 老許選了 17 和 11，既p=17, q=11壶熏；
- 計(jì)算兩個(gè)數(shù)的乘積n句柠。既n = 17x11 = 187；
- 計(jì)算n的歐拉函數(shù)φ(n)棒假。φ(n) = (p-1)x(q-1) = (17-1)x(11-1) = 160溯职；
- 選擇一個(gè)整數(shù)e，條件是1< e < φ(n)帽哑，且e與φ(n) 互質(zhì)谜酒。老許就在1到160之間選擇了37；
- 到此公鑰已經(jīng)生成祝拯，既（n, e) = (187, 37)甚带。下面生成私鑰；
- 計(jì)算e對(duì)于φ(n)的模反元素d（模反元素存在佳头，當(dāng)且僅當(dāng)e與φ(n)互質(zhì)）鹰贵。根據(jù)模反元素的計(jì)算公式，既解下面的二元一次方程康嘉，ed+φ(n) n=1碉输，既。
37d+160n = 1;
我是通過(guò)下面的python腳步計(jì)算出的亭珍，方法比較局限敷钾。如果有更好的解二元一次方程的方法歡迎留言。
大概思路：
第一步：37d+160n = 1肄梨，既37d-1=-160n阻荒。
第二步：假設(shè)d為正整數(shù)，d落在[0, 100]區(qū)間內(nèi)众羡。
第三步：將區(qū)間內(nèi)的每一個(gè)整數(shù)依次賦予d侨赡，判斷37乘d 加1 或 減1 余160 是否為0。如果余0粱侣，根據(jù)當(dāng)前d就可以求出一組[d, n]的整數(shù)解羊壹。
第四步：如果[0, 100]區(qū)間內(nèi)沒(méi)有找到結(jié)果，可以擴(kuò)大區(qū)間齐婴，重復(fù)第三步油猫。
def jisuan(a, b):
d=0
while(d<100):
d+=1
if((a*i-1)%b==0 or (a*i+1)%b==0):
print d
- 二元一次方程可能會(huì)有很多個(gè)整數(shù)解，這里選擇了求出的第一組整數(shù)解(d, n) = (13, -3)
- 至此公鑰和私鑰都已生成柠偶。公鑰（n, e）= (187, 37)情妖。私鑰（n, d) = (187，13)
- 私鑰會(huì)留在老許的手里诱担，其他人誰(shuí)又不知道鲫售。公鑰會(huì)給到余罪用于發(fā)送情報(bào)
RSA怎么用
余罪要向老許發(fā)送情報(bào)k，首先要用公鑰對(duì)k進(jìn)行加密该肴。這里需要注意情竹，k必須是整數(shù)（字符串可以取ascii值、unicode值）匀哄，且k必須小于n秦效。
所謂"加密"，也就是根據(jù)以下公式計(jì)算出密文
密文= k 的 e次方 模 n
根據(jù)計(jì)算公式涎嚼，這是python的實(shí)現(xiàn)
miwen=pow(k, e, n)
最后將密文發(fā)送給老許阱州，老許收到后使用私鑰進(jìn)行解密，操作和加密類似
明文= miwen 的 e次方 模 n
根據(jù)計(jì)算公式法梯，這是python的實(shí)現(xiàn)
k=pow(miwen, d, n)
可以看出如果沒(méi)有私鑰d 苔货，即使得到了miwen犀概，也是無(wú)法解析的。
