加密過程：

　　將接收到的明文轉換成特定的編碼方式。如p=43，q=59，e=13，明文為cybergreatwall，按照英文字母表的順序a=00，b=01，。。。 ，z=25進行編碼后為022401041706001922001111。

　　然后將轉碼后的字符串分塊，分組要求：每個分組對應的十進制數小于0。這個要求是什么意思呢？我個人的理解通過舉例向大家說明：上文字符串分組如下0224 0104 1706 0019 2200 1111。每一分組的數都小于n（2537），而2537能接受的最大的數為2525（也就是‘zz’的情況），所以是4位1組，即兩字符一組。這樣一來，m1=0224，m2=0104，。。。 ，m6=1111

　　現在可以加密了~~加密算法就是這個式子----ci ≡ mi^e （mod n），如第一分組 0224^13 ≡ mod 2537 ≡ 1692=c1 。這里有個隱藏的算法是需要了解的：

　　在RSA算法過程中容易出現天文數字（像上文的0224^13），而這些天文數字會為我們編程的過程造成一定的麻煩，更可惡的是會影響速度！！為了避免這種情況，快速取模指數算法可以很有效地算出c≡m^e mod n的準確結果且避免過程中出現天文數字~~

　　這個定理說明 a 經過編碼為 b 再經過解碼為 c 時， a == c mod n （n = pq）

　　但我們在做編碼解碼時， 限制 0 《= a 《 n， 0 《= c 《 n，

　　所以這就是說 a 等於 c， 所以這個過程確實能做到編碼解碼的功能

　　二、RSA 的安全性

　　RSA的安全性依賴于大數分解，但是否等同于大數分解一直未能得到理論上的證明，因為沒有證明破解 RSA就一定需要作大數分解。假設存在一種無須分解大數的算法，那它肯定可以修改成為大數分解算法。目前， RSA 的一些變種算法已被證明等價于大數分解。不管怎樣，分解n是最顯然的攻擊方法。現在，人們已能分解多個十進制位的大素數。因此，模數n 必須選大一些，因具體適用情況而定。

　　三、RSA的速度

　　由于進行的都是大數計算，使得RSA最快的情況也比DES慢上倍，無論是軟件還是硬件實現。速度一直是RSA的缺陷。一般來說只用于少量數據加密。

　　四、RSA的選擇密文攻擊

　　RSA在選擇密文攻擊面前很脆弱。一般攻擊者是將某一信息作一下偽裝（ Blind），讓擁有私鑰的實體簽署。然后，經過計算就可得到它所想要的信息。實際上，攻擊利用的都是同一個弱點，即存在這樣一個事實：乘冪保留了輸入的乘法結構：

　　（ XM ）^d = X^d *M^d mod n

　　前面已經提到，這個固有的問題來自于公鑰密碼系統的最有用的特征--每個人都能使用公鑰。但從算法上無法解決這一問題，主要措施有兩條：一條是采用好的公 鑰協議，保證工作過程中實體不對其他實體任意產生的信息解密，不對自己一無所知的信息簽名；另一條是決不對陌生人送來的隨機文檔簽名，簽名時首先使用 One-Way HashFunction 對文檔作HASH處理，或同時使用不同的簽名算法。在中提到了幾種不同類型的攻擊方法。

　　五、RSA的公共模數攻擊

　　若系統中共有一個模數，只是不同的人擁有不同的e和d，系統將是危險的。最普遍的情況是同一信息用不同的公鑰加密，這些公鑰共模而且互質，那末該信息無需私鑰就可得到恢復。設P為信息明文，兩個加密密鑰為e1和e2，公共模數是n，則：

　　C1 = P^e1 mod n

　　C2 = P^e2 mod n

　　密碼分析者知道n、e1、e2、C1和C2，就能得到P。

　　因為e1和e2互質，故用Euclidean算法能找到r和s，滿足：

　　r * e1 + s * e2 = 1

　　假設r為負數，需再用Euclidean算法計算C1^（-1），則

　　（ C1^（-1） ）^（-r） * C2^s = P mod n

　　另外，還有其它幾種利用公共模數攻擊的方法。總之，如果知道給定模數的一對e和d，一是有利于攻擊者分解模數，一是有利于攻擊者計算出其它成對的e’和d’，而無需分解模數。解決辦法只有一個，那就是不要共享模數n。

　　RSA的小指數攻擊。 有一種提高 RSA速度的建議是使公鑰e取較小的值，這樣會使加密變得易于實現，速度有

　　所提高。但這樣作是不安全的，對付辦法就是e和d都取較大的值。

　　RSA算法是第一個能同時用于加密和數字簽名的算法，也易于理解和操作。RSA是被研究得最廣泛的公鑰算法，從提出到現在已近二十年，經歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優秀的公鑰方案之一。RSA的安全性依賴于大數的因子分解，但并沒有從理論上證明破譯RSA的難度與大數分解難度等價。即RSA的重大缺陷是無法從理論上把握它的保密性能 如何，而且密碼學界多數人士傾向于因子分解不是NPC問題。 RSA的缺點主要有：A）產生密鑰很麻煩，受到素數產生技術的限制，因而難以做到一次一密。B）分組長度太大，為保證安全性，n 至少也要 600 bits 以上，使運算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數量級；且隨著大數分解技術的發展，這個長度還在增加，不利于數據格式的標準化。目前，SET（ Secure Electronic Transaction ）協議中要求CA采用比特長的密鑰，其他實體使用比特的密鑰。

　　下面用偽代碼為大家介紹下這種神奇的算法（個人感覺偽代碼里的 ‘《-’ 就是平時用的 ‘=’ ）：

　　t《-0;c《-1

　　for i《-k downto 0

　　do t《-2*t

　　c《-（c*c）mod n

　　if bi=1 then t《-t+1

　　c《-（c*m）mod n

　　return c

　　（p.s：e的二進制表示為bk bk-1 。。。 b0，如e=13=（1101），所以k為3）

　　所以，用快速取模指數算法計算上文例子里的c1過程就該是這樣子噠：

　　i 3 2 1 0

　　bi 1 1 0 1

　　t 1 3 6 13

　　ci （1*224）mod2537 （224*224*224）mod2537 （514*514）mod2537 （348*348*224）mod2537

　　=224 =514 =348 =1692

　　到這里RSA加密的算法就講完了，下面附上代碼

　　［cpp］ view plain copy#include《stdio.h》

　　#include《stdlib.h》

　　/* 函數申明 */

　　int long_n（int n）;

　　int shuru（char *arr， int k， char *wei， int is_first）;

　　void jiami（char *arr， int k， int e， int n）;

　　/* 輸入函數，記錄從鍵盤輸入的明文*/

　　int shuru（char *arr， int k， char *wei， int is_first）

　　{

　　int i;

　　char ch;

　　/*判斷是否為第一分組的輸入，如果是則獲取輸入的字符，否則就將上一分組最后獲取的字符作為這一分組的第一個字符*/

　　if （is_first == 1）

　　ch = getchar（）;

　　else

　　ch = *wei;

　　for （i = 0; （i 《 k） && （ch ！= ‘ ’）;i++） //獲取字符直到獲取到回車符為止

　　{

　　arr［i］ = ch;

　　ch = getchar（）;

　　}

　　*wei = ch; //最后獲取到的字符準備作為下一分組的第一個字符

　　for （i = i; i 《 k; i++）

　　arr［i］ = ‘a’; //輸入不夠一組個數的整數倍則補‘a’（即為補零）

　　if （ch == ‘ ’） //接收到回車符返回0，否則為1

　　return 0;

　　else

　　return 1;

　　}

　　/*加密函數*/

　　void jiami（char *arr， int k， int e， int n）

　　{

　　int m = 0，c=1， i， j，t=0， shu，temp，num=0;

　　int *array;

　　/*Mi賦值過程*/

　　for （i = 0; i 《 k; i++）

　　{

　　temp = 1;

　　for （j = 0; j 《 （k-i-1）*2; j++）

　　temp = temp * 10;

　　shu = （int）arr［i］ - 97;

　　m = m + temp * shu;

　　}

　　temp = e;

　　/*獲取e的二進制表達形式的位數*/

　　do{

　　temp = temp / 2;

　　num++;

　　} while （temp ！= 0）;

　　array = （int *）malloc（sizeof（int）*k）; //申請動態數組

　　temp = e;

　　/*動態數組存儲e的二進制表達形式*/

　　for （i = 0; i 《 num; i++）

　　{

　　array［i］ = temp % 2;

　　temp = temp / 2;

　　}

　　/*避免出現天文數字的算法，詳情見上文文字說明*/

　　for （i = num - 1; i 》= 0; i--）

　　{

　　t = t * 2;

　　temp = c*c;

　　if （temp 》 n）

　　{

　　for （j = 0; temp - n*j 》= 0; j++）;

　　j--;

　　c = temp - n*j;

　　}

　　else

　　c = temp;

　　if （array［i］ == 1）

　　{

　　t = t + 1;

　　temp = c*m;

　　if （temp 》 n）

　　{

　　for （j = 0; temp - n*j 》= 0; j++）;

　　j--;

　　c = temp - n*j;

　　}

　　else

　　c = temp;

　　}

　　e = e / 2;

　　}

　　temp = c;

　　i = 0;

　　/*c的位數小于分組長度則在前補零*/

　　do{

　　temp = temp / 10;

　　i++;

　　} while （temp ！= 0）;

　　for （i; i 《 num; i++）

　　printf（“0”）;

　　printf（“%d”， c）;

　　}

　　/*獲取分組的長度*/

　　int long_n（int n）

　　{

　　int temp，i，j，k，shi，comp=0;

　　temp = n;

　　/*獲取n的位數*/

　　for （i = 1; temp / 10 ！= 0; i++）

　　{

　　temp = temp / 10;

　　}

　　temp = i;

　　/*若n的位數為基數*/

　　if （i % 2 ！= 0）

　　{

　　i = i - 1;

　　return i;

　　}

　　/*若位數為偶數*/

　　else

　　{

　　for （j = 0; j 《 i/2; j++）

　　{

　　shi = 1;

　　for （k = 0; k 《 temp - 2; k++）

　　shi = shi * 10;

　　comp = comp + shi * 25;

　　temp = temp - 2;

　　}

　　if （comp 《= n）

　　return i;

　　else

　　{

　　i = i - 2;

　　return i;

　　}

　　}

　　}

　　/*主函數*/

　　int main（）

　　{

　　int p， q， e， d， n， fai_n， k， i，is_first=1;

　　char ch，*arr，wei=‘a’;

　　printf（“請輸入p、q、e值，用空格間隔開 ”）;

　　scanf_s（“%d%d%d”， &p， &q， &e）; //從鍵盤獲取p、q、e值

　　n = p*q;

　　fai_n = （p-1）*（q-1）; //Φ（n）

　　for （k = 0; （k*n + 1） % e ！= 0; k++）;

　　if （（k*n + 1） % e == 0）

　　d = （k*n + 1） / e; //d * e ≡ 1 （mod Φ（n））

　　k = long_n（n）;

　　k = k / 2; //分組的長度

　　ch = getchar（）; //緩沖回車符

　　arr = （char *）malloc（sizeof（char）*k）; //申請動態數組

　　printf（“請輸入明文 ”）;

　　while （1）

　　{

　　i=shuru（arr，k，&wei，is_first）; //調用輸入字符的函數，接收到回車符返回0，否則為1

　　is_first = 0; //第一分組錄入結束設為0

　　jiami（arr，k，e，n）; //調用加密函數

　　if （i == 0） //接收到返回值為0跳出循環

　　break;

　　}

　　printf（“ ”）;

　　return 0;

　　}