電子發燒友App
一、RSA算法?
首先， 找出三個數， p， q， r，
其中 p， q 是兩個相異的質數， r 是與 （p-1）（q-1） 互質的數
p， q， r 這三個數便是 private key
接著， 找出 m， 使得 rm == 1 mod （p-1）（q-1）
這個 m 一定存在， 因為 r 與 （p-1）（q-1） 互質， 用輾轉相除法就可以得到了
再來， 計算 n = pq
m， n 這兩個數便是 public key
編碼過程是， 若資料為 a， 將其看成是一個大整數， 假設 a 《 n
如果 a 》= n 的話， 就將 a 表成 s 進位 （s 《= n， 通常取 s = 2^t），
則每一位數均小於 n， 然後分段編碼
接下來， 計算 b == a^m mod n， （0 《= b 《 n），
b 就是編碼後的資料
解碼的過程是， 計算 c == b^r mod pq （0 《= c 《 pq），
於是乎， 解碼完畢 等會會證明 c 和 a 其實是相等的 ：）
如果第三者進行竊聽時， 他會得到幾個數： m， n（=pq）， b
他如果要解碼的話， 必須想辦法得到 r
所以， 他必須先對 n 作質因數分解
要防止他分解， 最有效的方法是找兩個非常的大質數 p， q，
使第三者作因數分解時發生困難
《定理》
若 p， q 是相異質數， rm == 1 mod （p-1）（q-1），
a 是任意一個正整數， b == a^m mod pq， c == b^r mod pq，
則 c == a mod pq
證明的過程， 會用到費馬小定理， 敘述如下：
m 是任一質數， n 是任一整數， 則 n^m == n mod m
（換另一句話說， 如果 n 和 m 互質， 則 n^（m-1） == 1 mod m）
運用一些基本的群論的知識， 就可以很容易地證出費馬小定理的
《證明》
因為 rm == 1 mod （p-1）（q-1）， 所以 rm = k（p-1）（q-1） + 1， 其中 k 是整數
因為在 modulo 中是 preserve 乘法的
（x == y mod z and u == v mod z =》 xu == yv mod z），
所以， c == b^r == （a^m）^r == a^（rm） == a^（k（p-1）（q-1）+1） mod pq
1. 如果 a 不是 p 的倍數， 也不是 q 的倍數時，
則 a^（p-1） == 1 mod p （費馬小定理） =》 a^（k（p-1）（q-1）） == 1 mod p
a^（q-1） == 1 mod q （費馬小定理） =》 a^（k（p-1）（q-1）） == 1 mod q
所以 p， q 均能整除 a^（k（p-1）（q-1）） - 1 =》 pq | a^（k（p-1）（q-1）） - 1
即 a^（k（p-1）（q-1）） == 1 mod pq
=》 c == a^（k（p-1）（q-1）+1） == a mod pq
2. 如果 a 是 p 的倍數， 但不是 q 的倍數時，
則 a^（q-1） == 1 mod q （費馬小定理）
=》 a^（k（p-1）（q-1）） == 1 mod q
=》 c == a^（k（p-1）（q-1）+1） == a mod q
=》 q | c - a
因 p | a
=》 c == a^（k（p-1）（q-1）+1） == 0 mod p
=》 p | c - a
所以， pq | c - a =》 c == a mod pq
3. 如果 a 是 q 的倍數， 但不是 p 的倍數時， 證明同上
4. 如果 a 同時是 p 和 q 的倍數時，
則 pq | a
=》 c == a^（k（p-1）（q-1）+1） == 0 mod pq
=》 pq | c - a
=》 c == a mod pq
首先是密鑰對的生成：
（1）選取兩個大素數p和q（目前兩個數的長度都接近512bit是安全的）
（2）計算乘積n=p*q，Φ（n）=（p-1）（q-1），其中Φ（n）為n的歐拉函數（因為兩素數乘積的歐拉函數等于兩數分別減一后的乘積）
（3）隨機選取整數e（1《e《Φ（n））作為公鑰d，要求滿足e與Φ（n）的最大公約數為1，即兩者互素
（4）用Euclid擴展算法計算私鑰d，已滿足d * e ≡ 1 （mod Φ（n）），即d ≡ e^（-1） （mod Φ（n））。則e與n是公鑰，d是私鑰
注意：e與n應公開，兩個素數p和q不再需要，可銷毀，但絕不可泄露。
加密過程：
將接收到的明文轉換成特定的編碼方式。如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;
}
運行結果：
C語言實現
/*
算法描述
1．選擇兩質數p、q 2. 計算n = p*q，【注意實際要加密的數據要小于n】。
3. 計算n的歐拉函數 （n）=（p-1）（q-1）。
4. 選擇整數e，使e與 （n）互質，且1《e《 （n）。
5. 計算d，使d*e=1 mod （n）。
6. 其中，公鑰 KU＝{e，n}，私鑰 KR＝{d，n}。
7. 加密：C=Me mod n
8. 解密：M＝Cd mod n=（Me）d mod n= Med mod n 。
*/
#include 《Windows.h》
#include 《stdio.h》
int candp（int a，int b，int c）
{
int r=1;
b=b+1;
while（b！=1）
{
r=r*a;
r=r%c;
b--;
}
printf（“%d ”，r）;
return r;
}
void main（）
{
int p，q，e，d，m，n，t，c，r;
char s;
printf（“please input the p，q： ”）;
scanf（“%d%d”，&p，&q）;
n=p*q;
printf（“the n is %3d ”，n）;
t=（p-1）*（q-1）;
printf（“the t is %3d ”，t）;
printf（“please input the e： ”）;
scanf（“%d”，&e）;
if（e《1||e》t）
{
printf（“e is error，please input again： ”）;
scanf（“%d”，&e）;
}
d=1;
while（（（e*d）%t）！=1）
d++;
printf（“then caculate out that the d is %d ”，d）;
bool flag = false;
while（1）
{
printf（“exit please input 0 ”）;
printf（“the cipher please input 1 ”）;
printf（“the plain please input 2 ”）;
scanf（“%d”，&r）;
switch（r）
{
case 0：
flag = true;
break;
case 1： printf（“input the m： ”）; /*輸入要加密的明文數字*/
scanf（“%d”，&m）;
c=candp（m，e，n）;
printf（“the cipher is %d ”，c）;
flag = false;
break;
case 2： printf（“input the c： ”）; /*輸入要解密的密文數字*/
scanf（“%d”，&c）;
m=candp（c，d，n）;
printf（“the cipher is %d ”，m）;
flag = false;
break;
}
if（flag）
break;
}
system（“pause”）;
}
工商網監
評論