RSA是目前使用最廣泛的公鑰密碼體制之一，它是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的，當時他們三人都在麻省理工學院作業，RSA就是他們三人姓氏開頭字母拼在一起組成的，
RSA演算法的安全性基于RSA問題的困難性，也就是基于大整數因子分解的困難性上，但是RSA問題不會比因子分解問題更加困難，也就是說，在沒有解決因子分解問題的情況下可能解決RSA問題，因此RSA演算法并不是完全基于大整數因子分解的困難性上的，
**
1.歐拉函式
什么是歐拉函式
歐拉函式是小于x的整數中與x互素的數的個數，一般用φ(x)表示，特殊的，φ(1)=1.
如何計算歐拉函式
通式：φ(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn),其中p1, p2……pn為n的所有素因數，n是不為0的整數.
歐拉函式的一些性質
1. 對于素數p，φ§=p?1 2. 若p為素數，n=pk，則φ(n)=pk-p^(k-1) 3. 歐拉函式是積性函式，但不是完全積性函式；若m,n互素，則φ(m?n)=φ(m)?φ(n)，特殊的，當m=2，n為奇數時，φ(2n)=φ(n) 4. 當n>2時，φ(n)是偶數 5. 小于n的數中，與n互素的數的總和為：φ(n) * n / 2 (n>1) 6. n=∑d∣n?φ(d)，即n的因數（包括1和它自己）的歐拉函式之和等于n
歐拉定理
歐拉定理是指：如果兩個正整數a和n互素，則n的歐拉函式φ(n)可以讓下面的式子成立：
即a的φ(n)次方減去1，可以被n整除. 比如，3和4互質，φ(4)=2，(3^2-1)/4=2. 當a為正整數，n為素數且a不能被n整除時，則有 a^(n-1) ≡ 1 (mod n)這就是費馬小定理.
模反元素
如果兩個正整數a和n互素，那么一定可以找到整數b，使得 ab-1 被n整除，或者說ab被n除的余數是1. 這時，b就叫做a對模數n的模反元素.
歐拉定理可以用來證明模反元素必然存在，如下圖，可以看到：a的 φ(n)-1 次方，就是a對模數n的模反元素.
RSA演算法
5.1 密鑰的生成程序
- 隨意選擇兩個大的素數p和q，p不等于q，計算n = pq.
- 根據歐拉函式的性質3，求得r=φ(n)=φ§φ(q)=(p-1)(q-1).
- 選擇一個小于r的整數e,且e與r互素；并求得e關于r的模反元素，命名為d.(模反元素存在，當且僅當e與r互質; 求d令ed≡1(mod r)）
- 將p和q的記錄銷毀
其中(n，e)是公鑰，(n，d)是私鑰. 例如： - A隨機選兩個不相等的質數61和53，并計算兩數的積n=61*53=3233，n的長度就是密鑰長度，3233的二進制是110010100001，一共12位，
所以這個密鑰就是12位. 實際應用中，RSA密鑰一般是1024位，重要的場合是2048位. - 計算n的歐拉函式; φ(n)=(p-1)(q-1)=60*52=3120.
- A在1到3120上隨機選擇了一個亂數e=17，與3120互素.
- 計算e對φ(n)的模反元素d，即時，ed-1=kφ(n)，
即使求解：17x+3120y=1.用擴展歐幾里得演算法求解，可以算出一組解(x,y)=(2753,-15)，即d=2753. 公鑰(3233, 17)，私鑰(3233,2753)
至此完成計算.5.2 RSA的可靠性 在RSA私鑰和公鑰生成的程序中，共出現過p,q,n,φ(N),e,d，其中n,e組成公鑰，其他的都不是公開的，一旦d泄露，就等于私鑰泄露; 那么能不能根據n,e推匯出d呢？ 1. ed ≡ 1(mod φ(n)) 只有知道e和φ(n)，才能算出d 2. φ(n)=(p-1)(q-1) 只有知道p和q,才能算出φ(n） 3. n=pq,只有將n分解才能算出p和q 所以，只有將n素因數分解，才能算出d; 也就意味著私鑰破譯. 但是，大整數的質因數分解是非常困難的. 所以理論上來說，如果我們找到 了快速對大整數進行質因數分解的方法，那么RSA加密也就沒什么安全性可言了；遺憾的是，目前數學上并沒有找到這樣快速的質因數分解方法.5.3 RSA的加密程序 假設A要向B發送加密資訊m，他就要用B的公鑰(n,e)對m進行加密，但m必須是整數（字串可以取ascii值或unicode值），且m必須小 于n. 所謂加密就是計算下式的c: m^e ≡ c (mod n) 假設m=65,B的公鑰(3233,17),所以等式如下： 65^17≡2790（mod 3233） 所以c等于2790，A就把2790發給B.5.4 RSA的解密程序 B收到A發來的2790后，就用自己的私鑰(3233,2755)進行解密 c^d ≡ m (mod n) 也就是c的d次方除以n的余數就是m 2790^2753 ≡ 65 (mod 3233) 因此得到原文65.
C語言代碼
**
#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--;
}
return r;
}
main()
{
int p,q,e,d,m,n,t,c,r;
char s;
printf("請輸入大素數p和q ");
scanf("%d%d",&p,&q);
n=p*q;
printf("n=%3d\n",n);
t=(p-1)*(q-1);
printf("t=%3d\n",t);
printf("請輸入 e: ");
scanf("%d",&e);
if(e<1||e>t)
{
printf("輸入的e不合規，請重新輸入 ");
scanf("%d",&e);
}
d=1;
while(((e*d)%t)!=1) d++;
printf("計算d的結果為 %d\n",d);
printf("加密請輸入 1\n");
printf("解密請輸入 2\n");
scanf("%d",&r);
switch(r)
{
case 1: printf("輸入明文m: "); /*輸入要加密的明文數字*/
scanf("%d",&m);
c=candp(m,e,n);
printf("密文為 %d\n",c);break;
case 2: printf("輸入密文 c: "); /*輸入要解密的密文數字*/
scanf("%d",&c);
m=candp(c,d,n);
printf("明文為 %d\n",m);break;
}
getchar();
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/229929.html
標籤：區塊鏈