RSA 是廣為使用的非對稱加密演算法,原本我以為已經很熟悉它了,想不到最近試圖用 Python 實作簽章驗證的時候,才發現有很多小細節是以前沒注意到的地方。
非對稱加密演算法
先複習一下大家熟到不能再熟的觀念。
在非對稱加密演算法中,會有兩把鑰匙。使用其中一把鑰匙加密過的資訊,必需用另一把鑰匙才能解開。一般的使用情況是:
- 發送者使用公鑰加密訊息,接收者使用私鑰解開密文。
- 發送者使用私鑰簽署訊息,接收者使用公鑰驗證簽章。
非對稱加密演算法有很多種,像什麼 ElGamal 或橢圓曲線加密法之類的,其中最常用的是 RSA。
RSA 數學原理
一組 RSA 鑰匙對 (key pair) 包含了三個數字:$(N, e, d)$,其中:
- $N$ 為兩個隨機產生質數 $(p, q)$ 的乘積。
- $(e, d)$ 是由 $(p, q)$ 所計算出來,且對任意自然數 $n$ 都滿足以下條件:$ n^{ed} \equiv n \mod N $
- 計算完 $(e, d)$ 後隨即丟棄 $(p, q)$。私鑰保留 $(N, e, d)$,公鑰則以 $(N, e)$ 的形式散布出去。
公鑰加密過程是把明文視為一個很大的數字 $n$,計算 $n^e$ 除以 $N$ 所得到的餘數:
$ c = n^e \mod N $
解密過程只是把上一步再作一次,但把 $e$ 代換成私鑰中的 $d$ 而已:
$ n = c^d \mod N $
實務上,因為加密和解密都是直接求餘數,因此必須限制 $n < N$,否則會導致解密出來的結果根本不是原來的 $n$。大於 $N$ 的訊息必需先切割成小區塊再個別加密。
簽章與驗證(錯誤示範)
簽章的原理很簡單:
- 發送者使用 MD5 或 SHA 之類的雜湊函數計算欲傳輸的訊息摘要 (digest)。
- 使用私鑰加密訊息摘要,並且和原本訊息一起傳送給接收者。
- 接收者使用公鑰解開摘要密文,並且用事先約定好的雜湊函數計算訊息摘要是否吻合。
若使用 openssl
來產生簽章,指令大概會像這樣:
|
|
第一行產生 SHA1 digest,第二行使用私鑰簽章,最後使用 base64 編碼輸出。然而這是錯誤的做法,產生的簽章會被其它軟體視為假簽章。
PKCS#1 v1.5 加密標準
關鍵點在於填充位元 (padding bytes)。為了安全考量,使用 RSA 對訊息加密或簽章時,必需先對訊息補上特定的填充位元 (padding bytes),才能進行加密。否則一些特殊的明文字串像是 0x00
或 0x01
加密後的結果和原來的明文一模一樣,就完全沒有加密效果了。
$ 0^e \mod N = 0 $
$ 1^e \mod N = 1 $
不管使用哪一支公鑰,0 和 1 都沒辦法加密
在大多數的應用場合中,都是遵循 PKCS#1 的規範來加入填充位元。在這套標準中,不同的雜湊函式要使用不同的填充位元,然而在前面的錯誤示範中,第二個 openssl
指令並不知道 pipe 進來的資料使用怎樣的雜湊函式,只好產生錯誤的填充位元。
正確的指令應該是這樣:
|
|
亦即在計算雜湊後馬上使用指定的私鑰簽章,讓 openssl 可以根據雜湊函數產生正確的填充位元。
使用 Python 實作
Python 有個 PyCrypto 函式庫,提供了各式加密演算法需要的功能,當然也包含了 PKCS#1。以下是簡單的實作:
|
|