RSA 密碼系統

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

原理

睇埋：因數

RSA 密碼系統建基於一點：

「

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

」

想像家陣噉樣做：

• 攞兩個數值有返咁上下大嘅質數 $x$ 同 $y$。
• 計出 $n$，$n=x\times y$。喺實際應用上，$x$ 同 $y$ 嘅數值極之大－喺廿一世紀初，$x$ 同 $y$ 用十進制表示嘅話兩個都會有超過 150 個位；所以「要用演算法搵出 $n$ 嘅因數」要嘥極大量嘅時間。
• 計出 $\phi$，$\phi =(x-1)\times (y-1)$。
• 搵一個整數 $e$，當中 $e$ 係 $\phi$ 嘅相對質數（coprime）－即係話 $e$ 同 $\phi$ 嘅最大公因數 $=1$；而且 $1<e<n$。
• 計出 $d$，當中 $d\times e=1{\pmod {\phi }}$（可以睇商餘計算）。
• $n$ 同 $e$ 係公開匙，$x$、$y$、$\phi$ 同 $d$ 要保密。

用虛擬碼表達嘅話：

 int x = 61, int y = 53; // 為咗簡單起見，當住 x 同 y 係 61 同 53 先。
 int n = x * y; // 計出 n
 // n = 3233.
 
 // 計出 $\phi$
 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;

因為 $x$、$y$ 同 $\phi$ 數值極大，要用電腦喺夠短嘅時間之內搵出 $d$ 嘅數值喺運算上行唔通（可以睇吓運算理論，尤其係運算複雜度理論）。而且做密碼嗰一方仲有得定時改變呢啲數值嚟加強保安。