RSA非對稱加密演算法 (四) 利用中國剩餘定理加速

使用RSA演算法在解密的計算時會需要較多時間，這時可以利用中國剩餘定理來加速
假設現在有一組金鑰，是由質數\(p,q\)生成，其中公鑰\((e,n)\),私鑰\((d,n)\),\(n=pq\)
在生成RSA金鑰的步驟中，最後一步是把\(p,q\)銷毀，但是在擁有私鑰的這一方若保留這兩個數則可以加快運算時間

假設收到一筆加密資料\(C\)

原本要計算的是
\(m= C^d \mod n =C^d \mod (pq)\)

把它轉換成中國剩餘定理的題型
\(\left\{ \begin{matrix} x \equiv m_1 \pmod{p} \\ x \equiv m_2 \pmod{q} \end{matrix} \right.\)
\(m_1=C^d \mod p \\ m_2=C^d \mod q\)
\(x\)的最小正整數解就是\(C^d\)


解這個方程式，令\(x=m_2+kq\)，帶入第一式
\(m_2+kq \equiv m_1 \pmod p\)
\(m_1-m_2 \equiv kq \pmod p\)
因為\(p,q\)為質數，\(\gcd (p,q) = 1\)
所以\(q\)存在模反原素 \(q^{-1}\)，\(qq^{-1} \equiv 1 \pmod p\)
\( q^{-1}(m_1-m_2) \equiv k \pmod p\)
\(k\)的最小正整數解為 \( q^{-1}(m_1-m_2) \mod p \)
\(\Rightarrow x=m_2+q\big(q^{-1}(m_1-m_2)\mod p\big)\)

再來說明為什麼比較快
\(m_1=C^d \mod p\)
\(p\)是質數\(\Rightarrow C^{p-1} \equiv 1 \pmod p\)
所以求 \(m_1\) 時只要計算\(C^{(d \mod (p-1))} \mod p\) 即可
同理 \(m_2=C^{(d \mod (q-1))} \mod q\)

重新整理一下式子並給予一些定義
\(d_p = d \mod (p-1)\)
\(d_q = d \mod (q-1)\)
\(q_{inv} = q^{-1} \mod p\)
這三個值是產生key時可以先算出來的
接下來要解密時只要以下步驟
\(m_1=C^{d_p} \mod p\)
\(m_2=C^{d_q} \mod q\)
\(h=q_{inv}(m_1-m_2)\mod p\)，這個餘數要找最小正整數
\(m=m_2+hq\)


接下來使用openssl產生一組key來玩玩看



預設public key為65537，據說加密計算比較快，還沒研究到這邊

接下來看一下key的內容


參數對應
modulus: \(n\)
publicExponent: \(e\)
privateExponent: \(d\)
prime1: \(p\)
prime2: \(q\)
exponent1: \(d_p\)
exponent2: \(d_q\)
coefficient: \(q_{inv}\)

在拿key來加解密前，先練習一下用p,q算出其他參數

load bigint

set p [bigint::convert 0x00fda39a0d5a044b0eb0eb9773afa747ed2f16cb609a049a50d0d6436f90f0df5f3f7f3fe9862ad71fd917d56451c219248812ddc943f413c27264e2806447a4cf]
set q [bigint::convert 0x00dfa9e58cb45e31f4013c8166b5b61eb94cde61b03f16e5a337300b6824c3531522239563cdf6af73b44e32f820b8edd3165de662c980e0b4025620e5bca09bb1]
set e 65537
set phy_n [bigint::mul [bigint::sub $p 1] [bigint::sub $q 1]]

set n    [bigint::mul $p $q]
set d    [bigint::invert 65537 $phy_n]
set dp   [bigint::mod $d [bigint::sub $p 1]]
set dq   [bigint::mod $d [bigint::sub $q 1]]
set qinv [bigint::invert $q $p]


foreach item {n d dp dq qinv} {
 puts $item=[bigint::hex [set $item]]
}

再來就加密後用不同方法解密比一下時間

# 先產生10000組數據
for {set i [bigint::convert 0]} {[bigint::cmp 10000 $i]} {set i [bigint::add $i 1]} {
 set C($i) [bigint::powm $i $e $n]
 # set m [bigint::powm $c $d $n]
 # puts "i=$i\tc=$c\tm=$m"
}

# 用同樣的數據做2次解密比較時間

puts [time {
 for {set i [bigint::convert 0]} {[bigint::cmp 10000 $i]} {set i [bigint::add $i 1]} {
  bigint::powm $C($i) $d $n
 }
}]

puts [time {
 for {set i [bigint::convert 0]} {[bigint::cmp 10000 $i]} {set i [bigint::add $i 1]} {
  set m1 [bigint::powm $C($i) $dp $p]
  set m2 [bigint::powm $C($i) $dq $q]
  set h  [bigint::mod [bigint::mul $qinv [bigint::sub $m2 $m1]] $p]
  set m  [bigint::add $m2 [bigint::mul $h $q]]
 }
}]

這是我用兩個平台跑出來的結果
win7 64bit i5-3230M
32950712 microseconds per iteration
10468731 microseconds per iteration

RaspberryPi
302722638 microseconds per iteration
98416506 microseconds per iteration

RSA的計算很花時間，所以通常應用時只用來初始化，先用RSA的方式溝通取得共用金鑰之後再用比較快的演算法加密