RSA 暗号と中国剰余の定理による高速化についてのまとめ

Published: 2021/12/22


RSA 暗号についての個人的なまとめ。

1. 教科書的な RSA 暗号

RSA 暗号は公開鍵暗号であり、公開鍵を利用して電文 MM を元にして作成した暗号化電文 CC が、秘密鍵の保持者にしか元の電文 MM を復号できなければ良い。

1.1 定義

λ\lambdaカーマイケル関数とする。

ランダムに異なる2つの素数 pp, qq を用意し、N=pqN \coloncolonequals pq として NN を定義する。 適当な素数 ee も用意する。 このとき、eeλ(N)\lambda(N) が互いに素になるようにする。(計算方法は後述) ならない場合は pp, qq を生成しなおす。

こうして得られた NNee を公開鍵とし、 pp, qq を秘密鍵とする。

なお、メッセージは適当に符号化すれば良いので、 MMCC は自然数であるとする。 また、 RSA 暗号は NN を法として計算を行うので、 MMCCNN 未満であるとする。 (大きな MM を暗号化したい場合、それ以上に大きい NN を用いる)

1.2 暗号化

CMe(modN)\begin{equation*} C \equiv M^e \pmod N \end{equation*}

1.3 複合化(MMpp とも qq とも互いに素である場合の証明)

λ(N)\lambda(N) は、その素因数 pp, qq を知っている秘密鍵保持者のみが、以下の計算で求めることができる。

λ(N)=LCM(p1,q1)\begin{equation*} \lambda(N) = \mathrm{LCM}(p-1, q-1) \end{equation*}

この値を利用して、eeλ(N)\lambda(N) は互いに素になるように pp, qq を生成していたので、拡張ユークリッドの互除法によって、以下の条件を満たす自然数 dd を求める。

ed1(modλ(N))\begin{equation*} ed \equiv 1 \pmod{\lambda(N)} \end{equation*}

この時、適当な自然数 nn を用いて、 ed=nλ(N)+1ed = n\lambda(N) + 1 であり、カーマイケル関数の定義より Mλ(N)1(modN)M^{\lambda(N)} \equiv 1 \pmod{N} なので、

Cd=(Me)d=Med=Mnλ(N)+1=(Mλ(N))nM=M\begin{align*} C^d &=& (M^e)^d \\ &=& M^{ed} \\ &=& M^{n\lambda(N) + 1} \\ &=& (M^{\lambda(N)})^n M \\ &=& M \end{align*}

(算術はすべて modN\mod N で行う)

として CdC^d を計算することで、元の電文 MM を求めることができる。

1.4 MM11 から N1N-1 の任意の値であった場合でも通用する証明

MMpp ないし qq の倍数であった場合、上記の証明において利用した性質 Mλ(N)1(modN)M^{\lambda(N)} \equiv 1 \pmod{N} は必ずしも成立するとは限らない。 この場合、中国剰余の定理を用いることで、 MedM(modN)M^{ed} \equiv M \pmod{N} を示すことができる。 以下、その場合を証明すると、

pp, qq は互いに異なる素数であるとしたので、 MMppqq のうち少なくとも一つと互いに素。 よって、 MMpp と互いに素であったとして、証明の一般性を失わない。 このとき、 λ(N)=LCM(p1,q1)\lambda(N) = \mathrm{LCM}(p-1, q-1) であったので、 λ(N)\lambda(N)p1p-1 の倍数。 すると、 ed=nλ(N)+1ed = n\lambda(N) + 1 であったことより、 ed=m(p1)+1ed = m(p-1) + 1 を見たす mm が存在する。 フェルマーの小定理により、 Mp11(modp)M^{p-1} \equiv 1 \pmod{p}。 よって、

Med=Mm(p1)+1=(Mp1)mMM(modp)\begin{align*} M^{ed} &=& M^{m(p-1) + 1} \\ &=& (M^{p-1})^mM \\ &\equiv& M \pmod{p} \\ \end{align*}

ここで、もし MMqq に対しても互いに素であれば、同様に MedM(modq)M^{ed} \equiv M \pmod{q} を得る。

そうでない場合、 MMqq の倍数であるので、 M0(modq)M \equiv 0 \pmod{q} であり、 Med0(modq)M^{ed} \equiv 0 \pmod{q}。 よって、MedM(modq)M^{ed} \equiv M \pmod{q}

いずれにせよ、 MedM(modp)M^{ed} \equiv M \pmod{p} かつ MedM(modq)M^{ed} \equiv M \pmod{q} が示されたので、中国人剰余の定理により、 MedM(modN)M^{ed} \equiv M \pmod{N}

2. 中国剰余の定理による高速化

pp, qq, ee によって一意に計算される dd は、秘密鍵の生成時点で予め計算しておくことができる。 しかし、この値は modLCM(p1,q1)\mod{\mathrm{LCM}(p-1, q-1)} であるので、そこそこ大きな値であり、 CdC^d の計算に割と時間がかかってしまう。 中国剰余の定理を活用する以下の計算方法によって、複合化処理を高速化できる。

まず、以下の値を予め、秘密鍵生成時に計算しておく。

dp=d(modp1)dq=d(modq1)qinv=q1(modp)\begin{align*} d_p &\coloncolonequals& d &\pmod{p-1} \\ d_q &\coloncolonequals& d &\pmod{q-1} \\ q_{\mathrm{inv}} &\coloncolonequals& q^{-1} &\pmod{p} \end{align*}

暗号化電文 CC に対して、以下の計算を行うことで、 MM' が計算できるが、これがその実、 MM に一致する。

M1=Cdp(modp)M2=Cdq(modq)h=qinv(M1M2)(modp)M=M2+hq(modN)\begin{align*} M_1 &\coloncolonequals& C^{d_p} &\pmod{p} \\ M_2 &\coloncolonequals& C^{d_q} &\pmod{q} \\ h &\coloncolonequals& q_{\mathrm{inv}}(M_1 - M_2) &\pmod{p} \\ M' &\coloncolonequals& M_2 + hq &\pmod{N} \end{align*}

2.1 証明

2.1.1 MM1(modp)M \equiv M_1 \pmod{p} かつ MM2(modq)M \equiv M_2 \pmod{q}

同様の証明になるので、MM1(modp)M \equiv M_1 \pmod{p} について示す。

今、ppNN を割り切り、かつ MCd(modN)M \equiv C^d \pmod{N} であったので、 MCd(modp)M \equiv C^d \pmod{p}

CCpp の倍数の時、M1M_1(=Cdp\coloncolonequals C^{d_p}) も CdC^dmodp\mod p の基、00 なので等しい。

以降、CCpp の倍数でない場合を考える。 pp は素数だったので、 CCpp は互いに素。 フェルマーの小定理より、 Cp11(modp)C^{p-1} \equiv 1 \pmod{p}。 定義より、ある整数kk が存在して、 d=k(p1)+dpd = k(p-1) + d_p

よって、

Cd=Ck(p1)+dp=(Cp1)kCdp1kCdp(modp)=Cdp=M1\begin{align*} C^d &=& C^{k(p-1) + d_p} &\\ &=& (C^{p-1})^k C^{d_p} &\\ &\equiv& 1^k C^{d_p} &\pmod{p} \\ &=& C^{d_p} & \\ &=& M_1 & \end{align*}

以上より MCdM1(modp)M \equiv C^d \equiv M_1 \pmod{p}. 同様に MM2(modq)M \equiv M_2 \pmod{q}

2.1.2 MM1(modp)M' \equiv M_1 \pmod{p} かつ MM2(modq)M' \equiv M_2 \pmod{q}

一般に、整数 ppqq があって(素数でなくとも良い)、MM1(modp)M \equiv M_1 \pmod{p}, MM2(modq)M \equiv M_2 \pmod{q} であるとき、

M1MM2(modGCD(p,q))\begin{equation*} M_1 \equiv M \equiv M_2 \pmod{\mathrm{GCD}(p, q)} \end{equation*}

M1M2M_1 - M_2GCD(p,q)\mathrm{GCD}(p, q) は割り切るので、

k=(M1M2)/GCD(p,q)\begin{equation} k \coloncolonequals (M_1 - M_2) / \mathrm{GCD}(p, q) \end{equation}

として整数 kk と定義できる。 これを変形して、

kGCD(p,q)=(M1M2)\begin{equation} k \mathrm{GCD}(p, q) = (M_1 - M_2) \end{equation}

また、ここで拡張ユークリッドの互除法によって、整数 pinvp_{\mathrm{inv}}', qinvq_{\mathrm{inv}}' が存在して、

qinvq+pinvp=GCD(p,q)q_{\mathrm{inv}}'q + p_{\mathrm{inv}}'p = \mathrm{GCD}(p, q)

この2式より、

kqinvq+kpinvp=(M1M2)kqinvq+M2=M1kpinvp\begin{align*} kq_{\mathrm{inv}}'q + kp_{\mathrm{inv}}'p &=& (M_1 - M_2) \\ kq_{\mathrm{inv}}'q + M_2 &=& M_1 - kp_{\mathrm{inv}}'p \end{align*}

を得る。

今、 M=kqinvq+M2=M1kpinvpM'' \coloncolonequals kq_{\mathrm{inv}}'q + M_2 = M_1 - kp_{\mathrm{inv}}'p として MM'' を定義すると、MM1(modp)M'' \equiv M_1 \pmod{p} かつ MM2(modq)M'' \equiv M_2 \pmod{q} が成立する。 つまり、このように MM'' を構築することで、 MM が満たしていた合同条件を満たす MM'' が構築できる。

またこの時、qinvq_{\mathrm{inv}}' はその満たすべき制約である qinvq+pinvp=GCD(p,q)q_{\mathrm{inv}}'q + p_{\mathrm{inv}}'p = \mathrm{GCD}(p, q) において、 その値に pp の倍数を足し引きしても、 pinvp_{\mathrm{inv}}'を適宜調整すればこの制約を満たす。 qinvq_{\mathrm{inv}}' のみ注目するのならば、なので、 modp\mod p の中で好きな値を選択すれば良い。

次に、 h=kqinv(modp)h \coloncolonequals kq_{\mathrm{inv}}' \pmod{p} を満たす hh が得られたとする。 このとき、 M=hq+M2M' \coloncolonequals hq + M_2 とすると、まず MM2(modq)M' \equiv M_2 \pmod{q}。 次に、ある整数 nn が存在して h=kqinv+nph = kq_{\mathrm{inv}}' + np だから、

M=(kqinv+np)q+M2=kqinvq+M2+npq=M1kpinvp+npqM1(modp)\begin{align*} M' &=& (kq_{\mathrm{inv}}' + np)q + M_2 \\ &=& kq_{\mathrm{inv}}'q + M_2 + npq \\ &=& M_1 - kp_{\mathrm{inv}}'p + npq \\ &\equiv& M_1 \pmod{p} \end{align*}

ここまで一般整数 pp, qq を想定してきて議論してきたが、 pp, qq を異なる素数とするならば、 k=M1M2k = M_1 - M_2 となり、また、 qinvq_{\mathrm{inv}}' の選択において qinv=q1(modp)q_{\mathrm{inv}} \coloncolonequals q^{-1} \pmod{p} を採用することによって、以下を得る。

h=(M1M2)qinv(modp)M=hq+M2MM1(modp)MM2(modq)\begin{align*} h &\coloncolonequals& (M_1 - M_2)q_{\mathrm{inv}} &\pmod{p} \\ M' &\coloncolonequals& hq + M_2 &\\ M' &\equiv& M_1 &\pmod{p} \\ M' &\equiv& M_2 &\pmod{q} \end{align*}

これは、証明するべき MM' の定義と示したい合同式に他ならない。

2.1.3 まとめ

2.1.1 と 2.1.2 そして中国剰余の定理により、 MMM \equiv M' を得る。


Tags: rsachinese-remainder-theorem数学
Next: Internet Backend 時の Cloud Load Balancer からの接続アドレス
Prev: PostgreSQL の Incremental Sorting について