筆記:RSA 簽章驗證

RSA 是廣為使用的非對稱加密演算法,原本我以為已經很熟悉它了,想不到最近試圖用 Python 實作簽章驗證的時候,才發現有很多小細節是以前沒注意到的地方。

非對稱加密演算法

先複習一下大家熟到不能再熟的觀念。

在非對稱加密演算法中,會有兩把鑰匙。使用其中一把鑰匙加密過的資訊,必需用另一把鑰匙才能解開。一般的使用情況是:

  1. 發送者使用公鑰加密訊息,接收者使用私鑰解開密文。
  2. 發送者使用私鑰簽署訊息,接收者使用公鑰驗證簽章。

非對稱加密演算法有很多種,像什麼 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$ 的訊息必需先切割成小區塊再個別加密。

簽章與驗證(錯誤示範)

簽章的原理很簡單:

  1. 發送者使用 MD5 或 SHA 之類的雜湊函數計算欲傳輸的訊息摘要 (digest)。
  2. 使用私鑰加密訊息摘要,並且和原本訊息一起傳送給接收者。
  3. 接收者使用公鑰解開摘要密文,並且用事先約定好的雜湊函數計算訊息摘要是否吻合。

若使用 openssl 來產生簽章,指令大概會像這樣:

1
2
3
$ openssl sha -binary data.txt \
| openssl rsautl -sign -inkey private_key.pem \
| base64

第一行產生 SHA1 digest,第二行使用私鑰簽章,最後使用 base64 編碼輸出。然而這是錯誤的做法,產生的簽章會被其它軟體視為假簽章。

PKCS#1 v1.5 加密標準

關鍵點在於填充位元 (padding bytes)。為了安全考量,使用 RSA 對訊息加密或簽章時,必需先對訊息補上特定的填充位元 (padding bytes),才能進行加密。否則一些特殊的明文字串像是 0x000x01 加密後的結果和原來的明文一模一樣,就完全沒有加密效果了。

$ 0^e \mod N = 0 $
$ 1^e \mod N = 1 $
不管使用哪一支公鑰,0 和 1 都沒辦法加密

在大多數的應用場合中,都是遵循 PKCS#1 的規範來加入填充位元。在這套標準中,不同的雜湊函式要使用不同的填充位元,然而在前面的錯誤示範中,第二個 openssl 指令並不知道 pipe 進來的資料使用怎樣的雜湊函式,只好產生錯誤的填充位元。

正確的指令應該是這樣:

1
$ openssl sha -sign private_key.pem data.txt | base64

亦即在計算雜湊後馬上使用指定的私鑰簽章,讓 openssl 可以根據雜湊函數產生正確的填充位元。

使用 Python 實作

Python 有個 PyCrypto 函式庫,提供了各式加密演算法需要的功能,當然也包含了 PKCS#1。以下是簡單的實作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from base64 import b64encode, b64decode
from Crypto.PublicKey import RSA
from Crypto.Hash import SHA
from Crypto.Signature import PKCS1_v1_5
def generate_rsa_sha1_signature(data, private_key):
hash_obj = SHA.new(data)
key = RSA.importKey(private_key)
signer = PKCS1_v1_5.new(key)
signature = signer.sign(hash_obj)
return b64encode(signature)
def verify_rsa_sha1_signature(data, public_key, signature):
hash_obj = SHA.new(data)
key = RSA.importKey(public_key)
signature = b64decode(signature)
verifier = PKCS1_v1_5.new(key)
return verifier.verify(hash_obj, signature)
分享到 評論