1 RSA的歷史 2 RSA的原理 2.1 歐拉定理 2.2 費馬小定理 ? ? 若p是質(zhì)數(shù)，則對于任意一個整數(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)用過程 3.1 密鑰生成 ? ? ?RSA算法包括2個密鑰：公共密鑰(public key)和私有密鑰(private key)。一般來講，如果A和B要實現(xiàn)RSA加密通訊，那么A和B必須將自己的公共密鑰告訴對方，當(dāng)一方需要向另外一方發(fā)送加密信息時，則將明文用對方的公共密鑰加密為密文，對方在接收到密文后，用自己的私有密鑰對密文進行解密得到明文。舉個例子：若A向B發(fā)送數(shù)據(jù)，A先用B的公共密鑰將明文進行加密得到密文后再將數(shù)據(jù)發(fā)過去，B收到密文后用B的私有密鑰進行解密得到了明文。就這么簡單。

密鑰生成的具體過程如下：

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


2.計算 n = p * q。


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


4.選取e，滿足1 < e < φ(n)且e與φ(n)互質(zhì)，即gcd(e, φ(n)) = 1。e和n構(gòu)成公共密鑰，e的二進制數(shù)bit位長度和漢明重量都不能取得太大（對于二進制數(shù)來說，漢明重量指的是1的個數(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 加密過程

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

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

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

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

? ??