RSA 暗号がようやく分かった気がしたのでまとめてみる

「RSA 暗号」を知ったのは私が大学の３年生の頃だったかと思います。学科の必修として「危機管理工学」という名の講義があって、そこで暗号理論を学んだのです。当時は、たいして数学を勉強していなかったこともあって、単位は習得したものの「なんだかよくわからないなあ」と苦手意識があったのを覚えています。

最近、RSA 暗号について知人から質問をされる機会があり、せっかくなので久しぶりに調べ直してみたのです。

するとどうでしょう。すらすら理解できる。これは驚きました。おそらく、最近「素数と２次体の整数論」を学ぶ過程で、初等整数論の基礎が身についてきたからでしょうか。「RSA暗号」はまさに初等整数論に立脚していますからね。基礎は大事なのだと言うことを改めて痛感しました。

「分かった！」という感覚を忘れないようにと考えて、現状の私の理解をまとめてみようと思います。残念ながら、まだ噛み砕いて説明できるまでには至って居ませんので、少なくとも初等整数論を一通り勉強した方向けに書いてみたいと思っています。そのため、まったくの初学者にはわかりづらいかも。「そんな文章、どこにニーズがあるのか」と思うかもしれませんが・・・。再確認のために使っていただければと思います。

それではいきましょう。

RSA 暗号の目的

暗号化したい元の文章（これを平文といいます）があって、それに暗号化を施して別の文章（これを暗号文といいます）を作ります。RSA暗号の目的は「暗号文から平文を得るための復号方法を求めること」に他なりません。「何を当たり前のことを」と思うかもしれませんが、これを忘れるとよくわからなくなります。

今述べたことを、整数論の言葉で表現し直すとこうなります。

平文を P$P$ ，暗号文を C$C$ とします。暗号鍵を k$k$，公開鍵を m$m$ としたとき、平文 P$P$ から暗号文 C$C$ を得る操作（これを「暗号化 encryption」といいましょう）を、合同式によって次のように表します。

Pk≡C(modm)(1)$\begin{array}{}\text{(1)}& P^k\equiv C(\mathrm{mod}m)\end{array}$

逆に、復号鍵 u$u$ （ただし、u>0$u>0$） が存在して、暗号文 C$C$ から平文 P$P$ を得る操作（これを「復号化 decryption」と呼びます）が可能であると仮定すると、そのような復号化は次のように表せます。

Cu≡P(modm)(2)$\begin{array}{}\text{(2)}& C^u\equiv P(\mathrm{mod}m)\end{array}$

ここで、(1) を (2) に代入して、暗号文 C$C$ を消去すると、

(Pk)u≡P(modm)(3)$\begin{array}{}\text{(3)}& (P^k{)}^u\equiv P(\mathrm{mod}m)\end{array}$

が得られます。

このとき、任意の P$P$ に対して、(3) 式を満たすような、都合の良い u$u$ を見つけることができれば、鍵 u$u$ を知っている人が暗号文を復号化できます。これこそが RSA 暗号の目的なのです。

RSA 暗号においては、ここで使った公開鍵 m$m$ は、素数 p,q$p,q$ を用いて

m=pq$m=pq$

のように計算されるということを覚えておいてください。あとで登場します。

またRSA暗号は、「公開鍵暗号」と呼ばれる暗号方式ですが、k,m$k,m$ は誰にでも分かるように公開してしまいます。ただし、m$m$ を作るときに使った p,q$p,q$ は誰にも公開してはいけません。これもポイントです。

ここで３点疑問が現れます。

• そんな都合の良い「復号鍵 u$u$」が存在するのか？
• そのような「復号鍵 u$u$」は「秘密鍵 p,q$p,q$」から計算可能なのか？
• u$u$ が計算可能だとして、もし「復号鍵 u$u$」が「公開鍵 k$k$ と m$m$」から計算できてしまえば、暗号文が他人に復号化されてしまうけれども、その心配はないのか

１つめの疑問は、すべての暗号における共通の疑問です。復号鍵 u$u$ が存在しないと、復号化ができないので、そもそも暗号として成立していません。

２つめの疑問も同様。復号鍵 u$u$ が計算できなければ、暗号化された情報を誰も復号できないことになります。これでは暗号化しても仕方ありません。

３つめの疑問は、暗号の安全性についての疑問ですね。公開鍵暗号方式、固有の問題です。今回の場合、暗号化においても復号化においても、鍵 k$k$ と m$m$ を用います。つまり、暗号化する側に鍵を渡さないといけないわけです。もし、秘密鍵暗号方式であれば、特に問題にはならないでしょう。つまり、暗号文を送ってもらう相手だけに、こっそりと秘密の k$k$, m$m$ を渡してしまえば、それらが他人にばれない限り暗号は解読されませんから。しかしながら、今回の RSA 暗号は、公開鍵暗号方式です。この方式では k$k$ と m$m$ を、誰にも分かるような方法で公開してしまうので、誰でも暗号化できます。一方で、もしも k$k$ と m$m$ から復号鍵 u$u$ が簡単にばれてしまうようなことがあっては、暗号化の意味がありません。そんなことができないような工夫が必要です。

というわけで、以降では順番にこの問題を解決していきましょう。まずは、１つめの復号鍵 u$u$ が存在するか、という問題から。

1. 復号鍵 u>0$u>0$ は存在するか？

(3) 式を再掲しましょう。

(Pk)u≡P(modm)(3)$\begin{array}{}\text{(3)}& (P^k{)}^u\equiv P(\mathrm{mod}m)\end{array}$

この式の左辺をちょちょっと、計算しましょう。

Pk⋅u≡P(modm)$P^{k\cdot u}\equiv P(\mathrm{mod}m)$

ここで問題となるのは、べき乗して余りをとると「都合良く」元の形に戻るような、そんな k⋅u$k\cdot u$ が存在するのか、ということですね。

それがなんと存在するんですよ、奥さん！
オイラーの定理の出番です。

オイラーの定理は、いわゆる初等整数論の代表的な成果ですが、以下ような定理です。

定理：オイラーの定理

正整数 a,m$a,m$ に対して，a,m$a,m$ が互いに素であるとき，以下が成り立つ．

aφ(m)≡1(modm)(4)$\begin{array}{}\text{(4)}& a^{\phi (m)}\equiv 1(\mathrm{mod}m)\end{array}$

ただし，φ(m)$\phi (m)$ はオイラー関数を表す．

ここでオイラー関数 φ(m)$\phi (m)$ という関数が出てきました。知らない方のために説明すると、オイラー関数 φ(m)$\phi (m)$ は「m$m$ より小さい正の整数のうち，m$m$ と互いに素な数の個数」を表す関数です。

たとえば、m=10$m=10$ を考えると、10$10$ と互いに素な 10$10$ より小さい数は、{1,3,7,9}$\{1,3,7,9\}$ の 4$4$ 個なので、φ(10)=4$\phi (10)=4$ となります。

一方で、たとえば m$m$ が素数 p$p$ であれば、p$p$ と互いに素な p$p$ より小さい数は、{1,…,p−1}$\{1,\dots ,p-1\}$ の p−1$p-1$ 個なので、φ(p)=p−1$\phi (p)=p-1$ です。したがって、上に述べたオイラーの定理は、このブログでよく登場する「フェルマーの小定理」の拡張版になっています。もし、m$m$ が素数 p$p$ であれば、そのオイラー関数は φ(p)=p−1$\phi (p)=p-1$ より、ap−1≡1(modp)$a^{p-1}\equiv 1(\mathrm{mod}p)$ が成り立つわけです。

「オイラーの定理」については、tsujimotter の旧ブログのこちらの記事も参考になります：
オイラーの定理を導くまで

さてここで、オイラーの定理の式 (4) の a$a$ に P$P$ を代入した後、さらに両辺を v$v$ 乗します。ただし v$v$ は整数です。

Pφ(m)⋅v≡1(modm)$P^{\phi (m)\cdot v}\equiv 1(\mathrm{mod}m)$

この式の両辺に P$P$ をかけましょう。

Pφ(m)⋅v+1≡P(modm)(5)$\begin{array}{}\text{(5)}& P^{\phi (m)\cdot v+1}\equiv P(\mathrm{mod}m)\end{array}$

するとどうでしょう。式 (3') と全く同じ形になりましたね。同じ式の形になっていますので、左辺の指数を比較しましょう。すると、

k⋅u=φ(m)⋅v+1(6)$\begin{array}{}\text{(6)}& k\cdot u=\phi (m)\cdot v+1\end{array}$

となります。すなわち、式 (6) を満たすような、整数 u,v$u,v$ が存在して u>0$u>0$ であれば、暗号文 Pk$P^k$ は復号できる、というわけですね。

「そんな都合良く u,v$u,v$ はいつでも存在するのか」と思うわけです。ここでは、整数論を勉強していると必ず出てくる、以下のようなロジックを使うのですが、その前にちょっとだけ式 (6) を変形します。

k⋅u−φ(m)⋅v=1(6')$\begin{array}{}\text{(6')}& k\cdot u-\phi (m)\cdot v=1\end{array}$

移項しただけですね。しかしこうすることで、次のような定理に見えてきます。

定理：一次不定方程式の整数解

a,b$a,b$ を互いに素な整数としたとき，以下の方程式を満たすような整数解 u,v$u,v$ が存在する．

au+bv=1$au+bv=1$

a=k$a=k$, b=φ(m)$b=\phi (m)$ とおいて、−v→v$-v\to v$ とすれば、完全に同じ式ですね。同じ式に見せるために、わざわざ u,v$u,v$ を使っていたわけです。

ここで、もし a,b$a,b$ が互いに素、すなわち、k,φ(m)$k,\phi (m)$ が互いに素であるならば、定理より整数 u,v$u,v$ が存在します。もちろん、暗号鍵 k$k$ は適当に選んだ数なので、φ(m)$\phi (m)$ と互いに素になるようにうまく選べば良いわけですから、整数 u,v$u,v$ は必ず存在することが保証されました。

これで復号鍵 u$u$ が存在することが示せました！やったー！

・・・と言いたいところですが、まだ十分ではありません。

一次不定方程式の整数解 u,v$u,v$ は存在することは示せました。が、しかし、まだ整数であって、正の整数とは限らない。つまり、u≤0$u\le 0$ である可能性があるわけです。どうにかして、u>0$u>0$ となるような整数解 u,v$u,v$ の組を求める方法はないのだろうか。その方法はもちろんあります。

こう考えればよいです。たとえば、整数解 u0,v0$u_0,v_0$ が見つかったとします。ただし、u0≤0$u_0\le 0$ とします。これは、一次不定方程式 au+bv=1$au+bv=1$ を満たしますから、

au0+bv0=1$a{u}_0+b{v}_0=1$

この式が成り立っているとすると、整数 k$k$ を用いて、以下の式も成り立ちます。

a(u0+bk)+b(v0−ak)=1$a(u_0+bk)+b(v_0-ak)=1$

展開するとわかりますが、abk$abk$ がプラスマイナスで打ち消し合って消えると、上の式が成立します。

よく見ると、この (u0+bk),(v0−ak)$(u_0+bk),(v_0-ak)$ も、au+bv=1$au+bv=1$ の解になっていることがわかります。ここで k$k$ を適切に選べば、(u0+bk)>0$(u_0+bk)>0$ にすることが可能ですね。したがって、u>0$u>0$ となるような、au+bv=1$au+bv=1$ を満たす整数解 u,v$u,v$ が必ず存在することを示せました。

長かったですが、これにて復号鍵 u$u$ の存在が証明できました。

2. 復号鍵 u$u$ は計算可能か？

存在は示せましたが、じゃあ計算は可能なのか、という疑問に答えていきましょう。

結局、1. の議論から、式 (6') を満たすような整数解 u,v$u,v$ を求める方法はあるのか、という問題です。ここでは、u$u$ の符号にはこだわらないで、単に整数解を求める方法で十分です。

この問題は、ユークリッドの互除法で解決です。ユークリッドの互除法による一次不定方程式の解法は、わざわざここで解説せずとも、いろんなところで解説がありますので、そちらに投げましょう。（単に解説するのが面倒なだけですが・・・。）

とにかく、ここでは k$k$ と φ(m)$\phi (m)$ さえ分かれば、整数解 u,v$u,v$ を求める方法が存在することが言えました。整数解さえ求まれば、1. の方法を使って u$u$ を正にすることは容易です。

3. 他人に復号されてしまわないのか？

最後は RSA 暗号の安全性の話です。

RSA 暗号は冒頭で述べた通り「公開鍵暗号方式」なので、k$k$, m$m$ は公開されています。ここで、もし φ(m)$\phi (m)$ が計算できてしまえば、k$k$ が分かっているわけですから、2. の方法により即座に復号鍵 u$u$ が求まってしまいます。

もちろん、鍵を公開した本人であれば、復号化できるのはよいことですが、誰もが復号できてしまったらまずいです。そこで結局、鍵を公開した本人だけが φ(m)$\phi (m)$ を計算できるようなトリックが必要になります。果たしてそんなことは可能なのか。

鍵を公開した本人が、それ以外の人と違う点はどこでしょう。それは、p,q$p,q$ を知っていることです。

ポイントになるのは、オイラー関数は、p,q$p,q$ を知らないと計算できないという点です。冒頭で述べた通り m$m$ が素数 p,q$p,q$ を使って、m=pq$m=pq$ で表されます。このとき、オイラー関数 φ(m)$\phi (m)$ は、次のように計算できます。

φ(m)=(p−1)(q−1)(7)$\begin{array}{}\text{(7)}& \phi (m)=(p-1)(q-1)\end{array}$

右辺が p,q$p,q$ を使った積で得られることに注目してください。

結局、復号鍵 u$u$ を得るためには、オイラー関数 φ(m)$\phi (m)$ の計算が必要です。一方で、オイラー関数 φ(m)$\phi (m)$ を計算するためには、あらかじめ p,q$p,q$ を知っているか、m$m$ を素因数分解する必要があります。素因数分解を経ないで m$m$ から直接 φ(m)$\phi (m)$ を計算する方法はありません。

ここで、鍵を作った本人とそれ以外の人に、奇妙な非対称性が生まれます。すなわち、鍵を作った本人は p,q$p,q$ を知っているので復号鍵を作成可能、そうでない人は m$m$ を素因数分解できない限り復号鍵を作成できないのです。

これによって、RSA 暗号の安全性が素因数分解と結びつきました。

素因数 p,q$p,q$ があらかじめ分かっていて、そこから m$m$ を計算する処理は積１回で可能ですが、逆に m$m$ を素因数分解するような効率的な方法は存在しません。十分大きな桁数の p,q$p,q$ を用いて、公開鍵 m$m$ を生成すれば、現存するどんなコンピュータを用いたとしても m$m$ の素因数分解は困難となります。

したがって、公開鍵を生成した p,q$p,q$ を漏らさなければ、その鍵を元にした暗号は安全である、といえるわけです。

結局以上をまとめるとこの図のようになります。

まとめ

今回の記事では、初等整数論の言葉を使って RSA 暗号についてまとめてみました。
結局、以下の点がポイントでしたね。

• 法 m$m$ でべき乗したときに任意の P$P$ が元に戻ってくるような「都合のいい指数 k⋅u$k\cdot u$」が存在し、計算できる
• 「都合のいい指数」の計算には、オイラー関数 φ(m)$\phi (m)$ の計算が必要だが、これには m$m$ の素因数分解 p,q$p,q$ が不可欠

ここに至るまでに「合同式」「オイラーの定理」「一次不定方程式の整数解」「ユークリッドの互除法」「オイラー関数」と、初等整数論の基本的な内容が１通り登場しましたね。やはり基礎は大事だなと実感しました。

逆に、整数論の基礎的な部分を押さえないで、表面的な説明をしたところで、私の学部３年の頃のように「分かったような分かっていないような」な感じになってしまうのでは、と思いました。

RSA暗号に限らず、世の中にはこういった「分かった気にさせる」解説が多々存在しますが、そのような解説の功罪を考えずにはいられません。

2015/01/20 追記：
練習問題作りました！

RSA暗号からの脱出 - tsujimotterのノートブック

2015/01/20 さらに追記：
オイラー関数が合成数の場合についての参考記事を書きました！

オイラー関数についての補足 - tsujimotterのノートブック

2015/01/21 またまた追記：
一次不定方程式の理解のための補足記事を書きました！

一次不定方程式と油分け算 - tsujimotterのノートブック

参考サイト

上でいろいろ文句を言ったばかりですが、そのようなサイトの中でも、こちらは特に丁寧に説明してくれている「よい解説サイト」です。tsujimotter の話はよくわからん、という方はまずはこちらをご覧になることをおすすめします。

はじめに | サルにも分かるRSA暗号