Day 23. 非對稱式加密演算法 - RSA (觀念篇) - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

第 12 屆 iThome 鐵人賽

DAY 23

Security

看完眼眶濕濕的App開發者慘烈對抗險惡資安環境血與淚的控訴！系列第 23 篇

Day 23. 非對稱式加密演算法 - RSA (觀念篇)

12th鐵人賽

羊小咩

2020-10-08 19:10:11

45598 瀏覽

分享至

RSA 簡介

RSA加密演算法是一種非對稱加密演算法，在公開金鑰加密和電子商業中被廣泛使用。

RSA是由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）在1977年一起提出的。當時他們三人都在麻省理工學院工作。RSA 就是他們三人姓氏開頭字母拼在一起組成的。

rsa

圖片來源

RSA 基於數學難題所設計出來的演算法，對極大整數無法進行因數分解的難題，證實 RSA 演算法的可靠性。

觀念/名詞定義

有些幾個觀念和名詞大家小時候就念過了(?) 這邊複習一下

質數 Prime number（素數）

大於1的自然数中，除了1和該数自身外，無法被其他自然数整除的数（也可定義為只有1與該數本身两个正因数的数）。

p.s 大於1的自然數若不是質數，則稱之為合數

5是質數，其正因數只有1與5。

6是個合數，除了1與6外，2與3也是其正因數

互質數（互素數）

如果兩個或兩個以上的整數的最大公因數是 1，則稱它們為互質

8 與 10 的最大公因數是 2，不是 1，因此它們並不互質
又例如 7, 10, 13 的最大公因數是 1，因此它們互質

注意一點，並不需要兩個或兩個以上的數互質，但本身卻不一定是質數；上述例子 10 不是質數，但依然與 13 互質

模指數運算（modular exponentiation）

就是先做指數在做模除

指數（這個大家應該都知道）

又稱為指數運算、冪運算（Exponentiation）

表達式為 $bn$ 讀作「 $b$ 的 $n$ 次方」或「 $b$ 的 $n$ 次冪」。

其中， b稱為底數，而 $n$ 稱為指數，等同於 $b$ 自乘 $n$ 次。

$a$

模除（會寫程式工程師應該都用過）

又稱模數、取模操作、取模運算等（modulo / modulus），口語稱為除餘

讓m去被n整除，只取所得的餘數作為結果。

以表達式為『 5 mod 2 』得到 1 同理 26 mod 6 =2； 28 mod 2 = 0 等等

模指數 (從這後面幾項平常人根本用不到XD )

先做指數運算在做模除運算

$mod$

b底數 = 4 , n指數為3 m模除 = 3 求 c 運算如下

$5^3mod7$

歐拉函數 $\varphi (n)$

是小於或等於n的正整數中與n互質的數的數目

又稱為φ函數

例子： $\varphi (8)=4$ ，因為1,3,5,7 有四個質數和8互質。

歐拉/尤拉定理 Euler Theorem）

歐拉定理表明，若 n,a 為正整數，且 n,a 互質，則 $a^{{\varphi (n)}}\equiv 1{\pmod n}$

即 $mod$ 與1在模n下同餘， $\varphi (n)$ 為歐拉函數。

用簡單的例子。令 $a = 3$ ， $n=5$ ，此兩數為互質正整數。

小於等於5的正整數中與5互質的數有4個（1、2、3和4）

所以 $\varphi (5)=4$ （詳情見歐拉函數）

計算： $a^{\varphi(n)} = 3^4 = 81 \equiv 1 \pmod{5}$ (詳情請看同餘)

同餘 ≡

兩個整數 $a$ ， $b$ ，若它們除以正整數 $m$ 所得的餘數相等，則稱 $a$ ， $b$ 對於模 $m$ 同餘
記作 $a\equiv b{\pmod {m}}$
讀作 $a$ 同餘於 $b$ 模 $m$ ，或讀作 $a$ 與 $b$ 關於模 $m$ 同餘。

比如 $26\equiv 14{\pmod {12}}$

RSA 簡易運作原理及流程

複習一下前面的章節，公開金鑰密碼系統（Public-key cryptosystem）加密跟解密使用不同的金鑰，又稱『非對稱式加密系統』(asymmeric cryptosystem )

接收者先產生公鑰（Public-key）及私鑰 (Private-key 或 Secret-key)
非對稱式加密 特性就是公鑰加密上鎖後，無法在用公鑰解開，只能用**私鑰** 解鎖

金鑰計算方式

選出兩個較大的質數 p 和 q
計算兩個質數的乘積 n = p × q
計算出小於 n 且與 n 互質的整數個數

$\varphi (n)$ = (p - 1)(q - 1)
選出一個整數 e （拿來當做公鑰）
- 選擇條件
  - 1 < e < $\varphi (n)$
  - e 與 $\varphi (n)$ 互質
計算 d (私鑰)
- d 與 e 的關係
  - e x d / $\varphi (n)$ 餘數為 1
  - 因此 d = e - 1 mod $\varphi (n)$
可得
- 公鑰 KU = {e, n}。
- 私鑰 KR = {d, n}。

金鑰產生流程

用例子說明

隨機選擇兩個質數 p 和 q
- p = 61、q = 53 ，p q的乘積 n =3233 將n轉換為二進制:110010100001
- n 的二進制長度是12，也就是密鑰長度為12 (一般不會使用這麼短，實際上要使用1024bit 以上)
求初 n 的歐拉函數 (M)
- 這裡讓 $\varphi (n)$ = M
- p = 61、q = 53 則 n =3233 那麼n 的歐拉函數記為 M = (p-1)(n-1) = 60 x 52=3120
找出大於1 小於 n 的歐拉函數的整數 e
- 隨機選擇e為17
計算出 d 值
- 依照上面公式 e和d 的乘積除以歐拉函數(M)的餘數為 1
- 當 e=17，M =3120，K=1，2，3...時， 17 * d - k * M = 1
- 求解這個方程找到一組滿足關係的 d 和 k 即可，可證其中一組為(d,k)=(2753,15)。