A simple implement of RSA, speed up with Chinese Remainder Theorem and square-and-multiply algorithms
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
code
tex
.gitignore
README.md
README.tex.md

README.md

RSA 加密

本篇作為課程作業的筆記,著重在 RSA 加解密的實作流程與加速方法,不涉及其數學證明與推導。

程式執行

git clone https://github.com/Petingo/RSA
cd RSA/code
python3 test.py

公鑰、私鑰的產生:

  1. 隨機生成兩質數 不等於
  2. 計算
  3. 由歐拉函數可知,不大 且與 互質的整數個數為 ;為方便表達,令
  4. 隨機挑選一個 互質且小於
  5. 計算 對同餘 的乘法反元素 ;意即
  6. 得出公鑰 、私鑰

加密

假設原始消息為 ,加密後的訊息為 ,則可以利用公鑰 計算

解密

利用私鑰 可以計算出

加速

Miller-Rabin Test

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

快速冪

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

中國剩餘定理

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

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

參考資料