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的方式溝通取得共用金鑰之後再用比較快的演算法加密