RSA 密碼系統

(由RSA跳轉過嚟)

RSA 密碼系統英文RSA cryptosystem)係一種好出名嘅公開密匙密碼系統,專門攞嚟幫一啲以數字形式存在嘅重要資料信用咭號碼電話號碼同埋生日日期呀噉)做加密

原理

編輯
睇埋:因數

RSA 密碼系統建基於一點[1]

將兩個埋一齊係好容易嘅,要搵出『一個數係由邊幾個因數乘埋產生嘅』相比之下就麻煩好多。

想像家陣噉樣做:

  • 攞兩個數值有返咁上下大嘅質數   
  • 計出   。喺實際應用上,   嘅數值極之大-喺廿一世紀初,  十進制表示嘅話兩個都會有超過 150 個位;所以「要用演算法搵出   嘅因數」要嘥極大量嘅時間[2]
  • 計出   
  • 搵一個整數  ,當中   相對質數(coprime)-即係話   最大公因數  ;而且  
  • 計出  ,當中  (可以睇商餘計算[1]
  •    係公開匙,     要保密。

虛擬碼表達嘅話[3]

 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. 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.
  2. Why Are Prime Numbers Important in Cryptography? 互聯網檔案館歸檔,歸檔日期2021年7月26號,.. Medium.
  3. Boneh, Dan (1999). "Twenty Years of attacks on the RSA Cryptosystem". Notices of the American Mathematical Society. 46 (2): 203–213.
  4. 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.
  5. Coppersmith, Don (1997). "Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities". Journal of Cryptology. 10 (4): 233-260.