logo

RSA公開鍵暗号方式の証明 📂整数論

RSA公開鍵暗号方式の証明

ビルドアップ

20190703\_130027.png 左から順に アリス、ボブ、イブとしよう。アリスとボブはメッセージを交換する当事者で、イブはメッセージに興味がある受動的攻撃者だ。オレンジ色の箱はアリスだけが知っている情報を、空色の箱はボブだけが知っている情報を、黒色の箱は公開されている（イブも知っている）情報を表す。

アリスはボブから受信しなければならないメッセージ m∈Nm \in \mathbb{N} がある。

アルゴリズム 1

鍵設定: アリスが大きな素数 pp, qqの積 N=pqN=pq を選択し、gcd⁡(e,(p−1)(q−1))=1\gcd \left( e , (p-1)(q-1) \right) = 1、ee を満たす ee を選択して公開する。

20190703\_130618.png

暗号化: ボブが c≡me(modN)c \equiv m^{e} \pmod{N} を計算して公開する。

20190703\_131106.png

復号: アリスが de≡1(mod(p−1)(q−1))de \equiv 1 \pmod{(p-1)(q-1)} を満たす dd を見つけて x≡cd≡m(modN)x \equiv c^{d} \equiv m \pmod{N} を計算すれば x=mx=m を得る。イブは現実的に dd を知ることができないため、mm を知ることができない。

20190703\_131157.png

説明

RSA公開鍵暗号システムは、ロナルド・ライベストronald Rivest、アディ・シャミアadi Shamir、レナード・アドルマンleonard Adlemanによって開発され、彼らの名前の頭文字からRSAと呼ばれる。3人はこの功績で2002年にチューリング賞を受賞している。

離散対数問題の難しさにのみ基づいたエルガマル公開鍵暗号システムとは異なり、素因数分解問題の難しさにも基づいており、その堅牢さだけで大きな素数を探す価値があるようになる。さらに、理論的なものだけでなく、現実に今、世界中で使われている点から学ぶ楽しみがあるシステムだ。致命的な攻撃方法としては量子コンピューターを基盤としたショアアルゴリズムがあるが、量子コンピューターの商用化は遠いため、しばらくは現役でいると見られる。

証明

復号

アリスはNNの素因数分解N=pqN = pqを知っているため、gcd⁡(e,(p−1)(q−1))=1\gcd \left( e , (p-1)(q-1) \right) = 1を満たすeeを見つけることができる。

拡張ユークリッドの定理: 2つの整数a,ba,bに対し、必ずaX+bY=gcd⁡(a,b)aX + bY = \gcd (a,b)の整数解が存在する。

2つの整数ee、(p−1)(q−1)(p-1)(q-1)に対し eX+(p−1)(q−1)Y=1 e X + (p-1)(q-1) Y = 1 整数解{X=dY=−k\begin{cases} X=d \\ Y = - k \end{cases}が存在するため de=1+k(p−1)(q−1) de = 1 + k (p-1)(q-1) 言い換えるとdd、つまりeeのリングZ(p−1)(q−1)\mathbb{Z}_{(p-1)(q-1)}での逆元であり、アリスはpp、qqを知っているため、ddを簡単に見つけることができる。[ 注: リングでの乗法逆元の存在は決して自明でない点を考慮すると、gcd⁡(e,(p−1)(q−1))=1\gcd \left( e , (p-1)(q-1) \right) = 1という条件が必須であることがわかる。]

オイラーのφ関数定理: gcd⁡(a,m)=1  ⟹  aϕ(m)≡1(modm) \gcd(a,m) = 1 \implies a^{ \phi (m) } \equiv 1 \pmod{m}

gcd⁡(e,(p−1)(q−1))=1\gcd \left( e , (p-1)(q-1) \right) = 1であるため、eeの逆元ddは次のように求められる。 d=e−1=eϕ((p−1)(q−1))−1 d = e^{-1} = e^{\phi \left( (p-1)(q-1) \right) -1} これは単にeeを累乗するだけなので、連続累乗法で容易かつ迅速に計算することができる。gcd⁡(c,pq)=1\gcd ( c , pq ) = 1が成立する場合と成立しない場合に分けて考えよう。

ケース1. gcd⁡(c,pq)=1\gcd ( c , pq ) = 1

合同方程式の累乗根を求める問題に帰着される。

トーシェント関数の乗法的性質: gcd⁡(p,q)=1  ⟹  ϕ(pq)=ϕ(p)ϕ(q) \gcd (p , q) =1 \implies \phi ( p q ) = \phi (p) \phi (q)

ϕ(p)=p−1\phi (p) = p-1且つϕ(q)=q−1\phi (q) = q-1であるため ϕ(pq)=ϕ(p)ϕ(q)=(p−1)(q−1) \phi (pq) = \phi (p) \phi (q) = (p-1)(q-1)

オイラーのφ関数定理: gcd⁡(c,N)=1  ⟹  cϕ(N)≡1(modN) \gcd(c,N) = 1 \implies c^{ \phi (N) } \equiv 1 \pmod{N}

c(p−1)(q−1)=cϕ(pq)c^{(p-1)(q-1)} = c^{ \phi (pq ) }であるため (cd)e≡cde≡c1+k(p−1)(q−1)≡c⋅(c(p−1)(q−1))k≡c⋅1k≡c(modpq) \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)≠1\gcd ( c , pq ) \ne 1

C≡c(p−1)(q−1)(modpq) C \equiv c^{(p-1)(q-1)} \pmod{pq} ccがpqpqの倍数であればxe≡0x^{e} \equiv 0で、x=0x = 0である必要があるが、どうでも良い。したがって、ccはppまたはqqのどちらかの倍数であるとするが、どちらの倍数であっても構わないのでqqの倍数としよう。すると、あるn0∈Zn_{0} \in \mathbb{Z}とppの倍数ではないあるK∈ZK \in \mathbb{Z}に対し C=c(p−1)(q−1)+(pq)⋅n0=[qK](p−1)(q−1)+p⋅qn0 \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*} 上述の式を満たすqn0q n_{0}が存在するため c(p−1)(q−1)≡[(qK)q−1]p−1(modp) c^{(p-1)(q-1)} \equiv \left[ (qK)^{q-1} \right]^{p-1} \pmod{p}

パート1. (cd)e≡c(modp)\left( c^{d} \right)^{e} \equiv c \pmod{p}

フェルマーの小定理: 素数ppとppと互いに素な整数aaに対し、ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}

KKはppの倍数ではないので、[(qK)q−1]\left[ (qK)^{q-1} \right]はppと互いに素であり、 (cd)e≡cde≡c1+k(p−1)(q−1)≡c⋅[(qK)k(q−1)]p−1≡c⋅1(modp) \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. (cd)e≡c(modq)\left( c^{d} \right)^{e} \equiv c \pmod{q}

(cd)e≡cde≡[qK]de≡0≡qK≡c(modq) \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. (cd)e≡c(modpq)\left( c^{d} \right)^{e} \equiv c \pmod{pq}

モジュロの乗法: gcd⁡(m1,m2)=1\gcd ( m_{1} , m_{2} ) = 1であれば{a≡b(modm1)a=b(modm2)  ⟹  a≡b(modm1m2)\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で{(cd)e≡c(modp)(cd)e≡c(modq)\begin{cases} \left( c^{d} \right)^{e} \equiv c \pmod{p} \\ \left( c^{d} \right)^{e} \equiv c \pmod{q} \end{cases}だったから、次を得る。 (cd)e≡c(modpq) \left( c^{d} \right)^{e} \equiv c \pmod{pq}

したがって、x=cdx=c^{d}はどのような場合でもxe≡c(modpq)x^{e} \equiv c \pmod{pq}の解として存在する。また、別の解uuが存在するとしても、常にu≡cd(modpq)u \equiv c^{d} \pmod{pq}として現れることは容易に示される。

■

暗号化

イブはeeを知っているが、逆元ddを見つけるためには素因数分解問題N=pqN=pqを解かなければならない。これは非常に困難であるため、ボブはメッセージmmをアリスに安全に伝達することができる。

■

参照

素因数分解問題の難しさを利用したセキュリティアルゴリズム

素因数分解問題への攻撃アルゴリズム

  1. Hoffstein. (2008). An Introduction to Mathematical Cryptography: p115~122. ↩︎