RSA公開鍵暗号方式の証明
ビルドアップ
左から順に アリス、ボブ、イブとしよう。アリスとボブはメッセージを交換する当事者で、イブはメッセージに興味がある受動的攻撃者だ。オレンジ色の箱はアリスだけが知っている情報を、空色の箱はボブだけが知っている情報を、黒色の箱は公開されている（イブも知っている）情報を表す。
アリスはボブから受信しなければならないメッセージ $m \in \mathbb{N}$ がある。
アルゴリズム 1
鍵設定: アリスが大きな素数 $p$, $q$の積 $N=pq$ を選択し、$\gcd \left( e , (p-1)(q-1) \right) = 1$、$e$ を満たす $e$ を選択して公開する。
暗号化: ボブが $c \equiv m^{e} \pmod{N}$ を計算して公開する。
復号: アリスが $de \equiv 1 \pmod{(p-1)(q-1)}$ を満たす $d$ を見つけて $x \equiv c^{d} \equiv m \pmod{N}$ を計算すれば $x=m$ を得る。イブは現実的に $d$ を知ることができないため、$m$ を知ることができない。
説明
RSA公開鍵暗号システムは、ロナルド・ライベストronald Rivest、アディ・シャミアadi Shamir、レナード・アドルマンleonard Adlemanによって開発され、彼らの名前の頭文字からRSAと呼ばれる。3人はこの功績で2002年にチューリング賞を受賞している。
離散対数問題の難しさにのみ基づいたエルガマル公開鍵暗号システムとは異なり、素因数分解問題の難しさにも基づいており、その堅牢さだけで大きな素数を探す価値があるようになる。さらに、理論的なものだけでなく、現実に今、世界中で使われている点から学ぶ楽しみがあるシステムだ。致命的な攻撃方法としては量子コンピューターを基盤としたショアアルゴリズムがあるが、量子コンピューターの商用化は遠いため、しばらくは現役でいると見られる。
証明
復号
アリスは$N$の素因数分解$N = pq$を知っているため、$\gcd \left( e , (p-1)(q-1) \right) = 1$を満たす$e$を見つけることができる。
拡張ユークリッドの定理: 2つの整数$a,b$に対し、必ず$aX + bY = \gcd (a,b)$の整数解が存在する。
2つの整数$e$、$(p-1)(q-1)$に対し $$ e X + (p-1)(q-1) Y = 1 $$ 整数解$\begin{cases} X=d \\ Y = - k \end{cases}$が存在するため $$ de = 1 + k (p-1)(q-1) $$ 言い換えると$d$、つまり$e$のリング$\mathbb{Z}_{(p-1)(q-1)}$での逆元であり、アリスは$p$、$q$を知っているため、$d$を簡単に見つけることができる。[ 注: リングでの乗法逆元の存在は決して自明でない点を考慮すると、$\gcd \left( e , (p-1)(q-1) \right) = 1$という条件が必須であることがわかる。]
オイラーのφ関数定理: $$ \gcd(a,m) = 1 \implies a^{ \phi (m) } \equiv 1 \pmod{m} $$
$\gcd \left( e , (p-1)(q-1) \right) = 1$であるため、$e$の逆元$d$は次のように求められる。 $$ d = e^{-1} = e^{\phi \left( (p-1)(q-1) \right) -1} $$ これは単に$e$を累乗するだけなので、連続累乗法で容易かつ迅速に計算することができる。$\gcd ( c , pq ) = 1$が成立する場合と成立しない場合に分けて考えよう。
ケース1. $\gcd ( c , pq ) = 1$
合同方程式の累乗根を求める問題に帰着される。
トーシェント関数の乗法的性質: $$ \gcd (p , q) =1 \implies \phi ( p q ) = \phi (p) \phi (q) $$
$\phi (p) = p-1$且つ$\phi (q) = q-1$であるため $$ \phi (pq) = \phi (p) \phi (q) = (p-1)(q-1) $$
オイラーのφ関数定理: $$ \gcd(c,N) = 1 \implies c^{ \phi (N) } \equiv 1 \pmod{N} $$
$c^{(p-1)(q-1)} = c^{ \phi (pq ) }$であるため $$ \begin{align*} \left( c^{d} \right)^{e} & \equiv c^{de} \\ & \equiv c^{1 + k (p-1)(q-1)} \\ & \equiv c \cdot \left( c^{(p-1)(q-1)} \right)^{k} \\ & \equiv c \cdot 1^{k} \\ & \equiv c \pmod{pq} \end{align*} $$
ケース2. $\gcd ( c , pq ) \ne 1$
$$ C \equiv c^{(p-1)(q-1)} \pmod{pq} $$ $c$が$pq$の倍数であれば$x^{e} \equiv 0$で、$x = 0$である必要があるが、どうでも良い。したがって、$c$は$p$または$q$のどちらかの倍数であるとするが、どちらの倍数であっても構わないので$q$の倍数としよう。すると、ある$n_{0} \in \mathbb{Z}$と$p$の倍数ではないある$K \in \mathbb{Z}$に対し $$ \begin{align*} C =& c^{(p-1)(q-1)} + (pq) \cdot n_{0} \\ =& \left[ qK \right]^{(p-1)(q-1)} + p \cdot q n_{0} \end{align*} $$ 上述の式を満たす$q n_{0}$が存在するため $$ c^{(p-1)(q-1)} \equiv \left[ (qK)^{q-1} \right]^{p-1} \pmod{p} $$
パート1. $\left( c^{d} \right)^{e} \equiv c \pmod{p}$
フェルマーの小定理: 素数$p$と$p$と互いに素な整数$a$に対し、$a^{p-1} \equiv 1 \pmod{p}$
$K$は$p$の倍数ではないので、$\left[ (qK)^{q-1} \right]$は$p$と互いに素であり、 $$ \begin{align*} \left( c^{d} \right)^{e} & \equiv c^{de} \\ & \equiv c^{1 + k (p-1)(q-1)} \\ & \equiv c \cdot \left[ (qK)^{k(q-1)} \right]^{p-1} \\ & \equiv c \cdot 1 \pmod{p} \end{align*} $$
パート2. $\left( c^{d} \right)^{e} \equiv c \pmod{q}$
$$ \begin{align*} \left( c^{d} \right)^{e} & \equiv c^{de} \\ & \equiv \left[ qK \right]^{de} \\ & \equiv 0 \\ & \equiv qK \\ & \equiv c \pmod{q} \end{align*} $$
パート3. $\left( c^{d} \right)^{e} \equiv c \pmod{pq}$
モジュロの乗法: $\gcd ( m_{1} , m_{2} ) = 1$であれば$\begin{cases} a \equiv b \pmod{ m_{1} } \\ a = b \pmod{ m_{2} } \end{cases} \implies a \equiv b \pmod{ m_{1} m_{2} }$
パート1、2で$\begin{cases} \left( c^{d} \right)^{e} \equiv c \pmod{p} \\ \left( c^{d} \right)^{e} \equiv c \pmod{q} \end{cases}$だったから、次を得る。 $$ \left( c^{d} \right)^{e} \equiv c \pmod{pq} $$
したがって、$x=c^{d}$はどのような場合でも$x^{e} \equiv c \pmod{pq}$の解として存在する。また、別の解$u$が存在するとしても、常に$u \equiv c^{d} \pmod{pq}$として現れることは容易に示される。
■
暗号化
イブは$e$を知っているが、逆元$d$を見つけるためには素因数分解問題$N=pq$を解かなければならない。これは非常に困難であるため、ボブはメッセージ$m$をアリスに安全に伝達することができる。
■
参照
素因数分解問題の難しさを利用したセキュリティアルゴリズム
素因数分解問題への攻撃アルゴリズム
Hoffstein. (2008). An Introduction to Mathematical Cryptography: p115~122. ↩︎