RSA暗号とは？作り方や解き方・安全性までわかりやすく解説します【サマーウォーズ】

こんにちは、ウチダです。

「RSA暗号」とは、現代のネット社会を支えている最重要の暗号です。

【解答】

$3×11=33$ を法とする。

また $n=1$ として $n(p-1)(q-1)+1$ を計算すると、$1・2・10+1=21=3×7$ 

よって、公開鍵 $P=3$ で暗号化すると、

$$8^3=512≡17 \pmod{33}$$

であり、秘密鍵 $Q=7$ で復号化すると、

$$17^7=410338673≡8 \pmod{33}$$

と、ちゃんと $X=8$ に戻ってきた。

(解答終了)

この計算式だけを見ても、あまりピンと来ないですよね。汗

よって本記事では、RSA暗号の仕組みから、RSA暗号の作り方や解き方・安全性まで

• 東北大学理学部数学科卒業
• 実用数学技能検定１級保持
• 高校教員→塾の教室長の経験あり

の僕がわかりやすく解説します。

RSA暗号の仕組みとは？【素因数分解を応用した公開鍵暗号です】

RSA暗号を一言で表すのであれば、「素因数分解を応用した公開鍵暗号」です。

ここで、よくわからない言葉「公開鍵暗号」が出てきましたので、そこから詳しく解説していきます。

公開鍵暗号（共通鍵暗号）とは？

• 公開鍵　…　誰でも知ることができる、暗号化するための鍵
• 秘密鍵　…　暗号を受信する人しか知り得ない、復号化するための鍵

公開鍵暗号（共通鍵暗号）では、上記の $2$ つの鍵を使います。

[ふきだし set=”考える男性”]暗号って聞くと、公開されていないイメージだけど、これでちゃんと暗号が作れるんだね！[/ふきだし]

[ふきだし set=”ウチダ”]たしかにそのイメージはありますね。ただ、RSA暗号の最大の特徴は、「秘密鍵が特定されづらいこと」にあるのです！[/ふきだし]

というより、秘密鍵が特定されたら暗号が破られてしまうため、アウトなんですが…(笑)

ここまででわかった情報を、一度図にまとめます。

では、特定されづらい秘密鍵 $Q$ を作るために、素因数分解を応用してみましょう！

素因数分解をどう応用する？

これ、実際に計算すると、

(1)　→　$25651$

(2)　→　$113×227$

となるんですが、ここで注目してほしいのは問題の解きやすさです。

…果たしてどちらが解きやすいですか？

[ふきだし set=”考える女性”](1)はただ計算するだけで簡単だけど、(2)は難しいです。(1)のヒントがなかったら、素因数分解するのに $10$ 分ぐらいかかりそう。[/ふきだし]

[ふきだし set=”ウチダ”]そうなんです。「掛け算は簡単だけど、素因数分解はめちゃムズイ。」これって、人間だけじゃなくコンピュータも同じなんですよ。[/ふきだし]

もちろんこのレベルであれば、コンピュータを使って一瞬で求めることができます。

ただ、今現在発見されている素数のうち最大の数は、なんと $24862048$ 桁にも及びます。

およそ $2500$ 万”桁”ですからね？とんでもない数ですよ？

実際そこまで大きな素数は必要じゃなくて、大体 $100$ 桁以上であればコンピュータでは計算不可能（できたとしても数億年かかる）と言われています。

さあ、仕組みはあらかたわかってきましたね！

それでは、実際にRSA暗号を作ることで、さらに理解を深めていきましょう。

RSA暗号の作り方・解き方を見てみよう【例題を通してわかりやすく解説】

それでは、冒頭に紹介した例題を通してわかりやすく解説していきます。

大まかな流れを先に書いておくと

• 素数を $2$ つ（今回は $p=3$，$q=11$ ）を用意する。
• 自然数 $n$ はなんでもいいので適当に決める。
• 受信側が $PQ=n(p-1)(q-1)+1$を満たす整数 $P$，$Q$ を見つけ、$P$ を公開鍵、$Q$ を秘密鍵と決める。
• 送信側が $X’≡X^{P} \pmod{pq}$ を送り、受信側が $(X’)^{Q} \pmod{pq}≡X$ と復号して完了。

ではやっていきます。

前提知識に関する記事はこちらから

あわせて読みたい

合同式の基本的な使い方３選とは【まずは練習問題でmodに慣れよう】 合同式（mod）の意味が分からない？本記事では、合同式（mod）の基本的な部分についてまとめました。具体的には、「modとは何か」「合同式に成り立つ性質５つ」「余りを求める問題」「一の位の数を求める問題」「倍数であることの証明問題」を解説します。

あわせて読みたい

フェルマーの小定理の２通りの証明とは？【京大入試を含む問題３選も解説】 「フェルマーの小定理とは何か」知りたいですか？本記事では、フェルマーの小定理の２通りの証明（数学的帰納法・互いに素）から、フェルマーの小定理の例題２問、さらには京大入試問題や暗号理論まで、わかりやすく解説します。本記事を読んで、「フェルマーの小定理マスター」になろう！

Step１．公開鍵と秘密鍵を用意しよう

今回 $n=1$ としてみましょう。

すると、$p=3$，$q=11$ であるので、

となりました。

つまり、$PQ=21$ を満たすように鍵のペアを決めます。

• 公開鍵 $P$　→　$3$
• 秘密鍵 $Q$　→　$7$

これにて Step $1$ は完了です♪

[ふきだし set=”考える男性”]実際は、もっと大きな素数を用意して公開鍵と秘密鍵を設定しないとダメなんですよね…？[/ふきだし]

[ふきだし set=”ウチダ”]ここの素因数分解の難しさが肝になってきますから、その通りですね。ただ、$n(p-1)(q-1)$ と互いに素な整数 $P$ を取ってきて、$PQ≡1 \pmod{(p-1)(q-1)}$ の合同方程式を解けば $Q$ が見つかるので、ここまでは簡単に設定できますよ＾＾[/ふきだし]

Step２．暗号化して情報を送ろう

では、送信者側になって、情報を実際に送ってみましょう。

今回、送りたい情報が $X=8$，公開鍵が $P=3$ なので、

$$X^{P}=8^3=512$$

と計算します。

次に、もう一つ公開されている情報である、法 $pq=33$ を用いて、

$$512≡17 \pmod{33}$$

を計算します。

つまり、$X=8$ が $X’=17$ に暗号化されました。

これにて Step $2$ 完了です。

Step３．復号化して情報を受け取ろう【完了】

最後に、受信側になったつもりで、$X’=17$ を復号しましょう。

[ふきだし set=”ウチダ”]このとき仮に通信が傍受されたとしても、秘密鍵 $Q$ を知っているものでなければ $X’=17$ を $X=8$ に復号化することができませんね。[/ふきだし]

$17$ を、最初に設定した秘密鍵 $Q=7$ 乗してみます。

$$17^7=410338673$$

最後に、法 $33$ として計算すると、

$$410338673≡8 \pmod{33}$$

となり、$X=8$ と解読できました～♪

【RSA暗号の原理】なんでそうなるの？

以上の操作は、$X$ がどんな情報であれ成り立ちます。

ではなぜ成り立つのか。

それは…

この原理の証明に「フェルマーの小定理」が使われるわけです。

RSA暗号の原理の大まかな証明

次の $2$ つの場合に分けて考える。

ⅰ）　$p$ と $X$ が互いに素である場合

フェルマーの小定理第 $1$ 形式より、$X^{p-1}≡1 \pmod{p}$ が言える。

あわせて読みたい

フェルマーの小定理の２通りの証明とは？【京大入試を含む問題３選も解説】 「フェルマーの小定理とは何か」知りたいですか？本記事では、フェルマーの小定理の２通りの証明（数学的帰納法・互いに素）から、フェルマーの小定理の例題２問、さらには京大入試問題や暗号理論まで、わかりやすく解説します。本記事を読んで、「フェルマーの小定理マスター」になろう！

よって、任意の自然数 $n$ に対して、

\begin{align}X^{n(p-1)(q-1)+1}&=(X^{(p-1)})^{n(q-1)}・X\\&≡X \pmod{p}\end{align}

が言えた。

ⅱ）　$p$ が $X$ の約数である場合

$X^{n(p-1)(q-1)+1}≡0≡X \pmod{p}$

ⅰ）ⅱ）より、いかなる場合も $X^{n(p-1)(q-1)+1}≡X \pmod{p}$ が成り立つ。

同様に、$X^{n(p-1)(q-1)+1}≡X \pmod{q}$ も言える。

したがって、$$X^{n(p-1)(q-1)+1}≡X \pmod{pq}$$

が成り立つ。

(証明終了)

だから、$PQ=n(p-1)(q-1)+1$ を満たすように公開鍵 $P$，秘密鍵 $Q$ を設定してやれば、

となり、法 $pq$ で $X$ に戻ってくるのです。

[ふきだし set=”ウチダ”]仕組みは何となく理解できましたか？ネット社会を支えているにもかかわらず、意外とシンプルな原理で成り立っていることさえ押さえればOKです＾＾[/ふきだし]

RSA暗号はネット社会を支えています【めちゃスゴイ】

さて、最後にRSA暗号の安全性について考察したいと思います。

RSA暗号の安全性

現時点で最も優秀だと言って良いRSA暗号。

これは「素因数分解の困難さ」から成り立っています。

ということは…

• 素数が現れる規則性が見つかったらヤバイ。
• めちゃくちゃ計算力が高いコンピュータができたらヤバイ。

そして前者が「リーマン予想」、後者が「量子コンピュータ」の話につながってきます。

[ふきだし set=”ウチダ”]しかし、リーマン予想が解決されたからと言って、RSA暗号の解読にはつながらないという主張が大多数です。[/ふきだし]

現実的にあり得そうなのは「量子コンピュータ」の方ですが、もしこれが実現したら「量子暗号」で太刀打ちできる、との噂もあります。

ここら辺は未だ研究段階ですので、何とも言えませんね、、汗

RSA暗号とサマーウォーズ

もう一つ。RSA暗号と聞くと思い出すのが「サマーウォーズ」という映画ではないでしょうか。

※以下、サマーウォーズのネタバレを一部含みますのでご了承下さい。

サマーウォーズの主人公である「小磯健二（以下ケンジで統一）」は、東京都在住の高校２年生。

物理部に所属しており、数学が大の得意で数学オリンピック代表候補でもある。

そんな中、世界中の人が集うインターネット上の仮想世界OZ（オズ）が謎のAIにハッキングされてしまい、社会的大混乱が起きる。

最後はケンジが見事暗号を打ち破り、探査機がケンジ宅に落ち半壊するというトラブルはあったものの、無事勝利を収め、社会とケンジの家族に平和が訪れるのであった。

大体こんなストーリーで、途中出てきた暗号というのが正しく「RSA暗号」なんですね。

[ふきだし set=”考える女性”]この世界線であっても、量子暗号は応用段階ではなかったということね。[/ふきだし]

…まあ、RSA暗号解読の困難さをわかっている状態でサマーウォーズを見ると、

え？これでケンジなんで数オリ出れないの？？

と思ってしまうぐらいスゴイ。

というかもはや量子コンピュータをも軽く上回る計算力お化けなんですけどね。(笑)

ふつうにハラハラドキドキする面白い映画なので、気になる方はぜひご覧ください。

RSA暗号に関するまとめ

本記事のポイントをまとめます。

1. RSA暗号は、素因数分解の困難さを応用して作られた、現在最も優秀な公開鍵暗号の $1$ つ。
2. 「合同式の基本知識」と「フェルマーの小定理」を使えば、RSA暗号の原理が説明できる。
3. サマーウォーズの主人公であるケンジは、人間離れしているというか、「量子コンピュータ」の計算力をもしのぐ。

これからの量子論の研究に注目するとともに、RSA暗号に感謝しながらネット時代を生き抜きましょう。

「整数の性質」全 25 記事をまとめました。こちらから次の記事をCHECK!!

あわせて読みたい

整数の性質とは？【高校数学Ａの解説記事総まとめ２５選】 「整数の性質」の総まとめ記事です。本記事では、整数の性質の解説記事全２５個をまとめています。「整数の性質をしっかりマスターしたい」「整数の性質を自分のものにしたい」という方は必見です。

おわりです。