簡介
RSA公開密鑰密碼體制於1978年提出,名字來源於提出者名字縮寫。這種密碼體制由數論構造,是迄今為止理論上最為成熟完善的密碼體制,安全性能目前看來依然良好,並且應用十分廣泛。密碼體制一般基於數學難題,RSA也不例外。
RSA是基於大整數分解的難題。給定整數e和c,尋找滿足條件的m,使得c = m^e mod N。
基礎知識
RSA基於以下數論內容
- 歐拉函數
- 同餘
- 擴展歐幾裡德算法
- 一次同餘式及其求解
- 費馬小定理(或歐拉定理)
算法
求最大公約數(Greatest Common Divisor)
通過類輾轉相除法
long int gcd(long int a, long int b){
if(b == 0)
return a;
return gcd(b, a % b);
}
快速指數算法
由模運算性質
[(a mod n) + (b mod n)] mod n = (a + b) mod n
[(a mod n) × (b mod n)] mod n = (a × b) mod n
可以簡化運算。
例如求 3^19 mod 7
= 3×3^18 mod 7
= 3×(3^2)^9 mod 7
= 3×(9 mod 7)^9 mod 7
= 3×2^9 mod 7
= 6×2^8 mod 7
= 6×4^4 mod 7
= 6×(16 mod 7)^2 mod 7
...
= 3
long int fastModel(long int base, long int power, long int model){
long int temp = 1;
long int result = 0;
while(power != 1){
if(power % 2 == 0){
power /= 2;
base = base * base % model;
}
else if(power % 2 != 0){
power -= 1;
temp = temp * base % model;
}
}
result = temp * base % model;
if (result <= 0){
result += model;
}
return (long int)result;
}
計算乘法逆元(解一次同餘式)
已知a,n,ax ≡ 1 (mod n),求x。
①定義X1,X2,X3,Y1,Y2,Y3。令(X1,X2,X3)=(1,0,n);(Y1,Y2,Y3)=(0,1,a)。
②令Q = X3/Y3(不留小數點)
③令(T1,T2,T3)=(X1-Q×Y1,X2-Q×Y2,X3-Q×Y3);(X1,X2,X3)=(Y1,Y2,Y3);(Y1,Y2,Y3)=(T1,T2,T3)
④迴圈這一步,直到Y3 = 1或0。如果為0,則無解;如果為1,則解為Y2。
阅读全文»