本篇作為課程作業的筆記,著重在 RSA 加解密的實作流程與加速方法,不涉及其數學證明與推導。詳細的程式碼請參考 https://github.com/Petingo/RSA

公鑰、私鑰的產生:

  1. 隨機生成兩質數 ppqqpp 不等於 qq
  2. 計算 N=p×qN=p \times q
  3. 由歐拉函數可知,不大 NN 且與 NN 互質的整數個數為 (p1)×(q1)(p-1)\times(q-1);為方便表達,令 φ=(p1)×(q1)\varphi = (p-1)\times(q-1)
  4. 隨機挑選一個 eeφ\varphi 互質且小於 φ\varphi
  5. 計算 ee 對同餘 φ\varphi 的乘法反元素 dd;意即 d×e1(modφ)d \times e\equiv1\pmod{\varphi}
  6. 得出公鑰 (N,e)(N,e) 、私鑰 (N,d)(N,d)

加密

假設原始消息為 mm,加密後的訊息為 cc,則可以利用公鑰 (N,e)(N, e) 計算

c=memodNc = m ^ e \bmod{N}

解密

利用私鑰 (N,d)(N,d) 可以計算出

m=cdmodNm = c ^ d \bmod{N}

加速

Miller-Rabin Test

快速驗證一個數是否為質數,根據計算,當 key 的長度在 2048 bits 時,迭代的次數最好 ≥ 40。

快速冪

在 Miller-Rabin test 以及加解密的過程中會,需要不斷計算 xhmodNx ^ h \bmod N;可以採用 square and multiply(快速冪)進行加速。

中國剩餘定理

詳細推導可以參考這篇文章
當擁有 ppqq 時,可以下列式子加速運算(mm 為明文,cc 為密文):

dp=dmod(p1)d_p = d \bmod{(p-1)}
dq=dmod(q1)d_q = d \bmod{(q-1)}
qinv=q1modpq_{inv} = q^{-1} \bmod{p}

上面可以先算好並存起來,每次解密時需要執行:

m1=cdpmodpm_1 = c^{d_p} \bmod{p}
m2=cdqmodqm_2 = c^{d_q} \bmod{q}
h=qinv×(m1m2)modph = q_{inv} \times (m_1 - m_2) \bmod{p}
m=m2+h×qm = m_2 + h \times q

參考資料