第0.5回 RSAへのAttack ～RSA-CRT～

どうも。duckです。
二回目にして唐突な0.5刻み。マイナーバージョンアップかな？
.5では、Attackじゃないけど知っておかないとCTFで困る（困った）知識について書いていきます。
今回のRSA-CRTだったり、RSA-OAEPだったりですね。

RSA-CRT
一言でいうと、復号の際の高速化処理のために中国剰余定理を使う手法のこと。
ChineseReductionTheoremゆえにCRT。

CRT:
CTFで使う数学後編 - CTFと共に生きる

まずは、ふつーの復号を見よう。
$m = C ^d \pmod N$
一ミリも面白くない。まあこの計算が重いので軽くしようぜってこと。

まずは中国剰余定理でばらして復号してみる。
$x \equiv C^d \pmod p$
$x \equiv C^d \pmod q$
の連立合同方程式の解は $0 \leq x < pq$ の中にあり中国剰余定理で計算できる。
これが実は $m$ になる。

なぜか。
$C ^ d \equiv m ^ {ed -1} \equiv m * {(m^{p-1})}^{k(q-1)} \equiv m \pmod p$ となる。
（フェルマーの小定理：CTFで使う数学前編 - CTFと共に生きる）
対称性を考慮し、上の連立合同方程式は
$x\equiv m \pmod p$
$x\equiv m \pmod q$
とかける。これを(*)とおく。

よって
$x=pk+m,x=ql+m$ ( $k,l$ :整数)と書け、両辺引くことにより
$pk=ql$ 。 $p,q$ は互いに素だから $k=q,l=p$
つまり $x=pq+m \equiv m \pmod N$ 。

実際に $x=m$ を求めるために、
$m_p=m\pmod p,m_q=m\pmod q$ とおく。
中国剰余定理の解の求め方としてGarner法を思い出すと
$x=m=m_p + p * t$
ただし、 $t=(p ^{-1} \bmod q )((m_q - m_p) \bmod q)$

この式がよく復号のところで出てくる。

ここからさらに高速化する。
$x \equiv C^d \pmod p$
$x \equiv C^d \pmod q$
を使っていたが、これは
$x \equiv C_p ^ {d_p} \pmod p$
$x \equiv C_q ^ {d_q} \pmod q$ を用いても同じでありこっちのほうが計算が早い。
ただし、
$C_p \equiv C \pmod p,e d_p \equiv 1 \pmod p-1,C_q \equiv C \pmod q,e d_q \equiv 1 \pmod q-1$ を満たす。

$C_p ^ {d_p} \equiv C ^ {d_p} \equiv m ^ {e d_p} \equiv m ^ {a(p-1)} \equiv m \pmod p$ 、 $a$ は整数。
最後の $\equiv$ はフェルマーの小定理による。

(*)と同じになったことからこの解は $m$ となることがわかる。

まとめると $C_p,C_q,d_p,d_q$ を
$C_p \equiv C \pmod p,ed_p \equiv 1 \pmod {p-1},C_q \equiv C \pmod q,ed_q \equiv 1 \pmod {q-1}$ を満たすものとし、
$x \equiv C_p ^ {d_p} \pmod p$
$x \equiv C_q ^ {d_q} \pmod q$ を考える。
この連立合同方程式の解は $m\pmod N$ となり

実際に
$m_p= C_p ^ {d_p}\pmod p,m_q=C_q ^ {d_q}\pmod q$ 、
$t=(p ^{-1} \bmod q )((m_q - m_p) \bmod q)$ とすると
$x=m=m_p + p * t$ 、と求められる。