今天講公鑰加密系統中有名的RSA加密演算法

回顧前幾天講的演算法問題分類，質因數分解問題被分類為NP(但不是NP完備)
今天講的RSA是利用找不到多項式時間做質因數分解的特性來設計

與離散對數類似，這邊指的複雜度是以該數的位元來表示

RSA加密步驟

假如Alice今天要用RSA加密一則重要訊息M(已先轉成數字)，步驟如下：

• 挑選足夠大的兩個質數p, q，乘起來得到N=pq
• 挑一個與L = (p-1)(q-1)互質的數e

這兩個數字(N,e)就會是ALice的公鑰，是所有人都可以獲得的資訊

想要加密M，我們將

得到密文C

想要解密C，要請Alice找一個數字d使得ed = 1 mod L

與背包加密手法很類似，都有需要找一個乘法反元素的步驟

由於邪惡的第三方無法輕易質因數分解N，因此無法透過公鑰(N,e)來算出d

此數字d即為Alice專屬的私鑰
有了數字d之後，原來的訊息M就可以利用

來還原

(上式為何成立其實不顯然！有興趣的人可以參考歐拉定理)

數字範例

這邊我用實際的數字演示一下RSA的操作，很建議各位也可以自己動手玩看看

假設今天要加密的數字M = 5201314

1. 首先選兩個質數 : p=7919, q=5419 相乘得到 N = 42913061
2. 找一個數字e與(p-1)(q-1)=L=42899724互質

有關e的尋找，當然直接令e=1也可以滿足與(p-1)(q-1)互質的關係，不過可以看出這跟沒有加密是一樣的
如果令e=L-1，也是可行，不過你會發現私鑰d會跟e一樣，相當不安全

因此，我採用隨機生成2到L-2之間的數字來找e，讓整個加密過程更加穩健

接著，我們利用這組公鑰來對訊息M進行加密

import numpy as np

M = 5201314

p = 7919
q = 5419

N = p * q

L = (p-1) * (q-1)


def find_rp(L):
    e = L
    while(np.gcd(e, L) != 1):
        e = np.random.randint(2, L-1)
    return e

#為了固定結果，實際執行可以把這行拿掉
np.random.seed(1)

e = find_rp(L)

得到e = 13419403

於是這組公鑰(N,e) = (42913061, 13419403)可以很安全地放在網路上公開給所有人知道

有了這組公鑰，訊息M便可進行加密

C = pow(M, e, N)

得到C = 34789139

私鑰d同樣可以用pow來得出

d = pow(e, -1, L)

得到d = 15849535

實際跑一段解碼的過程

pow(C, d, N)

會發現M神奇地被還原了！

小注意

以上範例中p, q很明顯都不夠大
實際執行以下程式，不到1秒的時間p, q就被找到了

def find_factor(N):
    i = 2
    while(N % i != 0):
        i += 1
    print(i, N // i)
    
find_factor(N)

實務上，n的大小可以是1024位元以上的長度(有1024個0和1的開關來儲存有關n的資訊)

1024位元的長度，可以表示相當於十進位的309位數
2048位元的長度，可以表示相當於十進位的617位數
達到安全層級的3072位元，可以表示相當於十進位的925位數

這數字大到我們無法用上面的方法來分解(宇宙中的原子個數為84位數)

我們可以看以下用16進位表示的一組一般的公鑰組

n = 0xa709e2f84ac0e21eb0caa018cf7f697f774e96f8115fc2359e9cf60b1dd8d4048d974cdf8422bef6be3c162b04b916f7ea2133f0e3e4e0eee164859bd9c1e0ef0357c142f4f633b4add4aab86c8f8895cd33fbf4e024d9a3ad6be6267570b4a72d2c34354e0139e74ada665a16a2611490debb8e131a6cffc7ef25e74240803dd71a4fcd953c988111b0aa9bbc4c57024fc5e8c4462ad9049c7f1abed859c63455fa6d58b5cc34a3d3206ff74b9e96c336dbacf0cdd18ed0c66796ce00ab07f36b24cbe3342523fd8215a8e77f89e86a08db911f237459388dee642dae7cb2644a03e71ed5c6fa5077cf4090fafa556048b536b879a88f628698f0c7b420c4b7
e = 0x010001

n是2048位元的一個數字，用十進位表示的話是

21086672194055230843612669443904574149811002047199307203395284381153222757946337921885021264571719641013039076957836127385367613397254088944127537594742835698599342510485047377962431798843899579770319434276737961042366904179340813692562855003898865028195278616282018741182344735960747779342416070036207295835459331516253126867178440116447801834476800207659890363928165409520291568362358485983049331749816176659779777775050704230265170530312109028338452264162399421025001847654072603050778790932784226771957796904573649393088878115602311774948562636636391090805302582907612057686556952164829704687199975950062033355959

一個617位數的數字

其私鑰如下

d = 0x10f22727e552e2c86ba06d7ed6de28326eef76d0128327cd64c5566368fdc1a9f740ad8dd221419a5550fc8c14b33fa9f058b9fa4044775aaf5c66a999a7da4d4fdb8141c25ee5294ea6a54331d045f25c9a5f7f47960acbae20fa27ab5669c80eaf235a1d0b1c22b8d750a191c0f0c9b3561aaa4934847101343920d84f24334d3af05fede0e355911c7db8b8de3bf435907c855c3d7eeede4f148df830b43dd360b43692239ac10e566f138fb4b30fb1af0603cfcf0cd8adf4349a0d0b93bf89804e7c2e24ca7615e51af66dccfdb71a1204e2107abbee4259f2cac917fafe3b029baf13c4dde7923c47ee3fec248390203a384b9eb773c154540c5196bce1

因此實際上，這些數字都是真正意義上的超級大，讓整個質因數分解的過程變得不可能實現