這幾天在重點(diǎn)研究ZIOS的加密部分，之所以這次重點(diǎn)要做加密，主要原因是之前的mini-HID甚至jubeat的P4IO都被抄過(guò)了。不過(guò)先前的就算了，當(dāng)初也沒(méi)想著要防。

花了一些時(shí)間研究了RSA加密的數(shù)學(xué)邏輯和程序算法，發(fā)現(xiàn)挺有趣又不難理解，做一些總結(jié)和分享。

RSA加密有兩把"鑰匙"，一個(gè)是“公鑰”，一個(gè)是“私鑰”。

有趣的點(diǎn)是，用公鑰鎖上之后，是用私鑰打開(kāi)。所以打開(kāi)的那把鑰匙是不會(huì)暴露給別人的，自然就更難被他人破解和復(fù)制。

從某種意義上來(lái)講，就是一種亂序密碼表。例如這個(gè)密碼的范圍是1、2、3、4、5，用1來(lái)表示3，用2來(lái)表示5等等……總共5種不重復(fù)的組合。由于不知道密鑰，就等同于不知道密碼表，那么假設(shè)看到的密文是1，也沒(méi)辦法確定實(shí)際要表達(dá)的意思是12345種的哪一個(gè)了。

如果這個(gè)時(shí)候做一個(gè)超~超~超~超~超~大型密碼表，數(shù)據(jù)長(zhǎng)度可能繞地球5圈都繞不完的那種，那么從密文破解到明文的難度就非常大了。

可是那么大的密碼表要怎么實(shí)現(xiàn)……畢竟電腦可能都存不下來(lái)那么龐大的數(shù)據(jù)量。這里就是RSA加密最精髓的地方了。

RSA加密用的是余數(shù)的方式，因?yàn)橛鄶?shù)的范圍是確定的，就像7的余數(shù)一定是0-6，這樣就確定了整個(gè)表的大小，也確定了明文的范圍一定要在余數(shù)的范圍內(nèi)。

然后用了兩個(gè)算法，確定余數(shù)之間的唯一對(duì)應(yīng)關(guān)系，就實(shí)現(xiàn)了超大型密碼表。

具體的數(shù)學(xué)算法：

先隨便選2個(gè)質(zhì)數(shù)，假設(shè)是7和11。

先得出兩個(gè)數(shù)相乘的數(shù)N = 7 x 11 = 77

然后將兩個(gè)質(zhì)數(shù)各-1，得出最小公倍數(shù)M。6和10的最小公倍數(shù)是30。

然后再取一個(gè)和M互質(zhì)的數(shù)E，并且不能為1，也不能大于M，這里E有多個(gè)解，我們假設(shè)取13好了。

下一步就要確定一個(gè)數(shù)D，這里要求D不能為1也不能大于M，而且E x D 的結(jié)果除以M的余數(shù)為1.

這里如果用窮舉，可以試一下M有余1的數(shù)有哪些：

31，61，91........咦！91÷13=7，是個(gè)整數(shù)。所以這里D=7。

所以這里可以獲得最終結(jié)果：

公鑰E,N：E=13,N=77

私鑰D,N：D=7,N=77

接下來(lái)進(jìn)行加密：

密文 =?( 明文的E次方?)?求N的余

根據(jù)之前的分析，明文是不能大于N的，這里隨便假設(shè)我們想要傳遞的明文是 20

那么密文就是? (20^13)mod77 = 69

然后獲取到加密的數(shù)據(jù)是69，這時(shí)候要解密成正確的明文：

明文 = ( 密文的D次方 ) 求N的余

試算一下：(69^7)mod77 = 20

這樣就完成了密碼表上的對(duì)應(yīng)。

但這里存在一個(gè)問(wèn)題，如果密碼表超級(jí)大，求次方的時(shí)候電腦算的過(guò)來(lái)么？

確實(shí)是算不過(guò)來(lái)，但這里因?yàn)槟康氖乔笥?，所以有個(gè)很有趣的特性：

假設(shè)14÷13余1，那么(2x14)÷13就余2，(3x14)÷13就余3....

所以14的平方÷13的余，就是1x14再求余，所以答案是1。

就可以總結(jié)出 n的平方求m的余 =??（（n先求m的余）乘?n）再求m的余

利用這點(diǎn)，就可以讓電腦不用存那么大的次方數(shù)再求余了。

所以RSA算法實(shí)現(xiàn)起來(lái)并不復(fù)雜誒