1 RSA的歷史 2 RSA的原理 2.1 歐拉定理 2.2 費(fèi)馬小定理 ? ? 若p是質(zhì)數(shù)，則對(duì)于任意一個(gè)整數(shù)a，有a^?p???a?是p的整數(shù)倍，即若a不能被p整除，則a^?p???1???1同樣是p的整數(shù)倍。 2.3 歐幾里得引理 ? ? 若n是a*b的因子(a*b能被n整除)，且n與a互質(zhì)，則n是b的因子(b能被n整除)?？梢员硎緸椋喝鬾 | (a*b)， 且gcd(n,a) ?= 1, 則n ?| ?b。 3 RSA應(yīng)用過(guò)程 3.1 密鑰生成 ? ? ?RSA算法包括2個(gè)密鑰：公共密鑰(public key)和私有密鑰(private key)。一般來(lái)講，如果A和B要實(shí)現(xiàn)RSA加密通訊，那么A和B必須將自己的公共密鑰告訴對(duì)方，當(dāng)一方需要向另外一方發(fā)送加密信息時(shí)，則將明文用對(duì)方的公共密鑰加密為密文，對(duì)方在接收到密文后，用自己的私有密鑰對(duì)密文進(jìn)行解密得到明文。舉個(gè)例子：若A向B發(fā)送數(shù)據(jù)，A先用B的公共密鑰將明文進(jìn)行加密得到密文后再將數(shù)據(jù)發(fā)過(guò)去，B收到密文后用B的私有密鑰進(jìn)行解密得到了明文。就這么簡(jiǎn)單。

密鑰生成的具體過(guò)程如下：

1.隨機(jī)生成兩個(gè)不同的質(zhì)數(shù)p和q，由此可知p和q互質(zhì)。此外，p和q的二進(jìn)制數(shù)的bit位長(zhǎng)度要相近；判斷兩個(gè)數(shù)是否互質(zhì)一般使用米勒-拉賓素性檢測(cè)。


2.計(jì)算 n = p * q。


3.計(jì)算歐拉函數(shù)：φ(n) = φ(p)φ(q) = (p ? 1)(q ? 1) = n - (p + q -1),φ(n)表示與n為互質(zhì)的小于等于n的正整數(shù)的個(gè)數(shù)。


4.選取e，滿足1 < e < φ(n)且e與φ(n)互質(zhì)，即gcd(e, φ(n)) = 1。e和n構(gòu)成公共密鑰，e的二進(jìn)制數(shù)bit位長(zhǎng)度和漢明重量都不能取得太大（對(duì)于二進(jìn)制數(shù)來(lái)說(shuō)，漢明重量指的是1的個(gè)數(shù)，如11101 0B的漢明重量為4），一般取2^16 + 1 = 65,537，e的值越小安全性越差。

5.選取d滿足d ≡ (e^?1) (mod φ(n))，即ed ≡ 1(mod φ(n)), d和n構(gòu)成私有密鑰。

3.2 加密過(guò)程

? ??假設(shè)整數(shù)m為明文，則密文，此為 模冪運(yùn)算。

3.3 解密過(guò)程 ? ? 若c是密文，則明文，同樣是模冪運(yùn)算。
4 RSA的具體實(shí)現(xiàn)過(guò)程 ? ? 其實(shí)稍微懂一點(diǎn)數(shù)論，上述的應(yīng)用過(guò)程非常容易理解，但是要具體應(yīng)用在嵌入式編程中，尤其是系統(tǒng)資源不充足時(shí)，就是一個(gè)比較棘手的問(wèn)題。尤其在實(shí)際應(yīng)用中，N的二進(jìn)制位數(shù)要達(dá)到1024bit才能算是相對(duì)安全，那么對(duì)于上述的算法來(lái)說(shuō)，基于1024位數(shù)的運(yùn)算絕對(duì)是大數(shù)運(yùn)算了，因?yàn)槟壳扒度胧叫酒罡咭簿褪?2位的。因此，大數(shù)運(yùn)算是難點(diǎn)之一；其次，如何快速實(shí)現(xiàn)上述的一些復(fù)雜運(yùn)算，比如求參數(shù)d，模冪運(yùn)算，判斷兩個(gè)大數(shù)是否互質(zhì)等幾個(gè)問(wèn)題，因?yàn)橛鞋F(xiàn)成的一些公式和算法因此相對(duì)容易些。
4.1 如何生成隨機(jī)數(shù)？ ? ? 這個(gè)好解決，對(duì)于嵌入式系統(tǒng)來(lái)說(shuō)，生成隨機(jī)數(shù)需要一個(gè)自然隨機(jī)的模擬量，比如采集某個(gè)置空的AD腳，每次讀取時(shí)只取bit0的數(shù)據(jù)(0或1)作為隨機(jī)數(shù)的bit0，每次獲取一次隨機(jī)的0或1都要先將原來(lái)的值左移一位，然后將此次的隨機(jī)值作為bit0，之后，要滿足隨機(jī)數(shù)的位數(shù)，則可以把最高位置1。
4.2 如何判斷一個(gè)隨機(jī)數(shù)為質(zhì)數(shù)？ 4.2.1 概率性測(cè)試

? ? 對(duì)一個(gè)數(shù)進(jìn)行素性檢測(cè)可以通過(guò)多種辦法，如費(fèi)馬素性檢測(cè)、米勒-拉賓素性檢測(cè)、索爾維-施特拉森素性檢測(cè)等。這里將詳細(xì)介紹米勒-拉賓素性檢測(cè)。

? ? 首先，在有限域Z/pZ中，如果某個(gè)大于2的整數(shù)是素?cái)?shù)，則對(duì)于公式，x的解不是1(mod p)就是-1(mode p)。怎么理解？這里我們需要引用歐幾里得引理（見(jiàn)上文），公式可以轉(zhuǎn)換成因?yàn)閜是素?cái)?shù)

? ??