RSA 暗号についての個人的なまとめ。
1. 教科書的な RSA 暗号
RSA 暗号は公開鍵暗号であり、公開鍵を利用して電文 M を元にして作成した暗号化電文 C が、秘密鍵の保持者にしか元の電文 M を復号できなければ良い。
1.1 定義
λ をカーマイケル関数とする。
ランダムに異なる2つの素数 p, q を用意し、N::=pq として N を定義する。
適当な素数 e も用意する。
このとき、e と λ(N) が互いに素になるようにする。(計算方法は後述)
ならない場合は p, q を生成しなおす。
こうして得られた N と e を公開鍵とし、 p, q を秘密鍵とする。
なお、メッセージは適当に符号化すれば良いので、 M と C は自然数であるとする。
また、 RSA 暗号は N を法として計算を行うので、 M と C は N 未満であるとする。
(大きな M を暗号化したい場合、それ以上に大きい N を用いる)
1.2 暗号化
C≡Me(modN)
1.3 復号化(M が p とも q とも互いに素である場合の証明)
λ(N) は、その素因数 p, q を知っている秘密鍵保持者のみが、以下の計算で求めることができる。
λ(N)=LCM(p−1,q−1)
この値を利用して、e と λ(N) は互いに素になるように p, q を生成していたので、拡張ユークリッドの互除法によって、以下の条件を満たす自然数 d を求める。
ed≡1(modλ(N))
この時、適当な自然数 n を用いて、 ed=nλ(N)+1 であり、カーマイケル関数の定義より Mλ(N)≡1(modN) なので、
Cd=====(Me)dMedMnλ(N)+1(Mλ(N))nMM
(算術はすべて modN で行う)
として Cd を計算することで、元の電文 M を求めることができる。
1.4 M が 1 から N−1 の任意の値であった場合でも通用する証明
M が p ないし q の倍数であった場合、上記の証明において利用した性質 Mλ(N)≡1(modN) は必ずしも成立するとは限らない。
この場合、中国剰余の定理を用いることで、 Med≡M(modN) を示すことができる。
以下、その場合を証明すると、
p, q は互いに異なる素数であるとしたので、 M は p か q のうち少なくとも一つと互いに素。
よって、 M が p と互いに素であったとして、証明の一般性を失わない。
このとき、 λ(N)=LCM(p−1,q−1) であったので、 λ(N) は p−1 の倍数。
すると、 ed=nλ(N)+1 であったことより、 ed=m(p−1)+1 を見たす m が存在する。
フェルマーの小定理により、 Mp−1≡1(modp)。
よって、
Med==≡Mm(p−1)+1(Mp−1)mMM(modp)
ここで、もし M が q に対しても互いに素であれば、同様に Med≡M(modq) を得る。
そうでない場合、 M は q の倍数であるので、 M≡0(modq) であり、 Med≡0(modq)。
よって、Med≡M(modq)。
いずれにせよ、 Med≡M(modp) かつ Med≡M(modq) が示されたので、中国人剰余の定理により、 Med≡M(modN)。
2. 中国剰余の定理による高速化
p, q, e によって一意に計算される d は、秘密鍵の生成時点で予め計算しておくことができる。
しかし、この値は modLCM(p−1,q−1) であるので、そこそこ大きな値であり、 Cd の計算に割と時間がかかってしまう。
中国剰余の定理を活用する以下の計算方法によって、複合化処理を高速化できる。
まず、以下の値を予め、秘密鍵生成時に計算しておく。
dpdqqinv::=::=::=ddq−1(modp−1)(modq−1)(modp)
暗号化電文 C に対して、以下の計算を行うことで、 M′ が計算できるが、これがその実、 M に一致する。
M1M2hM′::=::=::=::=CdpCdqqinv(M1−M2)M2+hq(modp)(modq)(modp)(modN)
2.1 証明
2.1.1 M≡M1(modp) かつ M≡M2(modq)
同様の証明になるので、M≡M1(modp) について示す。
今、p は N を割り切り、かつ M≡Cd(modN) であったので、 M≡Cd(modp)
C が p の倍数の時、M1(::=Cdp) も Cd も modp の基、0 なので等しい。
以降、C が p の倍数でない場合を考える。
p は素数だったので、 C と p は互いに素。
フェルマーの小定理より、 Cp−1≡1(modp)。
定義より、ある整数k が存在して、 d=k(p−1)+dp。
よって、
Cd==≡==Ck(p−1)+dp(Cp−1)kCdp1kCdpCdpM1(modp)
以上より M≡Cd≡M1(modp).
同様に M≡M2(modq)
2.1.2 M′≡M1(modp) かつ M′≡M2(modq)
一般に、整数 p と q があって(素数でなくとも良い)、M≡M1(modp), M≡M2(modq) であるとき、
M1≡M≡M2(modGCD(p,q))
M1−M2 を GCD(p,q) は割り切るので、
k::=(M1−M2)/GCD(p,q)
として整数 k と定義できる。
これを変形して、
kGCD(p,q)=(M1−M2)
また、ここで拡張ユークリッドの互除法によって、整数 pinv′, qinv′ が存在して、
qinv′q+pinv′p=GCD(p,q)
この2式より、
kqinv′q+kpinv′pkqinv′q+M2==(M1−M2)M1−kpinv′p
を得る。
今、 M′′::=kqinv′q+M2=M1−kpinv′p として M′′ を定義すると、M′′≡M1(modp) かつ M′′≡M2(modq) が成立する。
つまり、このように M′′ を構築することで、 M が満たしていた合同条件を満たす M′′ が構築できる。
またこの時、qinv′ はその満たすべき制約である
qinv′q+pinv′p=GCD(p,q) において、
その値に p の倍数を足し引きしても、 pinv′を適宜調整すればこの制約を満たす。
qinv′ のみ注目するのならば、なので、 modp の中で好きな値を選択すれば良い。
次に、 h::=kqinv′(modp) を満たす h が得られたとする。
このとき、 M′::=hq+M2 とすると、まず M′≡M2(modq)。
次に、ある整数 n が存在して h=kqinv′+np だから、
M′===≡(kqinv′+np)q+M2kqinv′q+M2+npqM1−kpinv′p+npqM1(modp)
ここまで一般整数 p, q を想定してきて議論してきたが、 p, q を異なる素数とするならば、 k=M1−M2 となり、また、
qinv′ の選択において qinv::=q−1(modp) を採用することによって、以下を得る。
hM′M′M′::=::=≡≡(M1−M2)qinvhq+M2M1M2(modp)(modp)(modq)
これは、証明するべき M′ の定義と示したい合同式に他ならない。
2.1.3 まとめ
2.1.1 と 2.1.2 そして中国剰余の定理により、 M≡M′ を得る。