RSA 密碼系統

密碼系統係一種好出名嘅公開密匙密碼系統，專門攞嚟幫一啲以數字形式存在嘅重要資料做加密。

原理

RSA 密碼系統建基於一點：

想像家陣噉樣做：
攞兩個數值有返咁上下大嘅質數  同 。
計出 ，。喺實際應用上， 同  嘅數值極之大－喺廿一世紀初， 同  用十進制表示嘅話兩個都會有超過 150 個位；所以「要用演算法搵出  嘅因數」要嘥極大量嘅時間。
計出 ，。
搵一個整數 ，當中  係  嘅相對質數－即係話  同  嘅最大公因數 ；而且 。
計出 ，當中 。
 同  係公開匙，、、 同  要保密。
用虛擬碼表達嘅話：
  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;
因為 、 同  數值極大，要用電腦喺夠短嘅時間之內搵出  嘅數值喺運算上行唔通。而且做密碼嗰一方仲有得定時改變呢啲數值嚟加強保安。

攷

密碼學