RSA 密碼系統
(由RSA跳轉過嚟)
RSA 密碼系統(英文:RSA cryptosystem)係一種好出名嘅公開密匙密碼系統,專門攞嚟幫一啲以數字形式存在嘅重要資料(信用咭號碼、電話號碼同埋生日日期呀噉)做加密。
原理
編輯睇埋:因數
RSA 密碼系統建基於一點[1]:
「 | 」 |
想像家陣噉樣做:
- 攞兩個數值有返咁上下大嘅質數 同 。
- 計出 , 。喺實際應用上, 同 嘅數值極之大-喺廿一世紀初, 同 用十進制表示嘅話兩個都會有超過 150 個位;所以「要用演算法搵出 嘅因數」要嘥極大量嘅時間[2]。
- 計出 , 。
- 搵一個整數 ,當中 係 嘅相對質數(coprime)-即係話 同 嘅最大公因數 ;而且 。
- 計出 ,當中 (可以睇商餘計算)[1]。
- 同 係公開匙, 、 、 同 要保密。
int x = 61, int y = 53; // 為咗簡單起見,當住 x 同 y 係 61 同 53 先。
int n = x * y; // 計出 n
// n = 3233.
// 計出
int phi = (x-1)*(y-1);
// phi = 3120.
int e = findCoprime(phi); // 計出 e
// 喺呢個例子當中,e = 17 滿足到上述嘅條件。
// 搵出滿足到以下條式嘅 d:
d = (1 mod (phi))/e;
// 喺呢個例子當中,d = 2753
public_key = (e=17, n=3233);
private_key = (d=2753, n=3233);
// 想像明文 P = 123, 密文 C 會係:
C = (123^17) % 3233 = 855;
// 幫密文 C 做解密嘅話:
P = (855^2753) % 3233 = 123;
因為 、 同 數值極大,要用電腦喺夠短嘅時間之內搵出 嘅數值喺運算上行唔通(可以睇吓運算理論,尤其係運算複雜度理論)。而且做密碼嗰一方仲有得定時改變呢啲數值嚟加強保安[4][5]。
攷
編輯- ↑ 1.0 1.1 Rivest, Ronald L.; Shamir, A.; Adleman, L. (1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems". Communications of the ACM. 21 (2): 120–126.
- ↑ Why Are Prime Numbers Important in Cryptography? 互聯網檔案館嘅歸檔,歸檔日期2021年7月26號,.. Medium.
- ↑ Boneh, Dan (1999). "Twenty Years of attacks on the RSA Cryptosystem". Notices of the American Mathematical Society. 46 (2): 203–213.
- ↑ Håstad, Johan (1986). "On using RSA with Low Exponent in a Public Key Network". Advances in Cryptology - CRYPTO '85 Proceedings. Lecture Notes in Computer Science. 218. pp. 403–408.
- ↑ Coppersmith, Don (1997). "Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities". Journal of Cryptology. 10 (4): 233-260.