RSA暗号の仕組みとは?【作り方や解き方・安全性までわかりやすく解説します】

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

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

例題. $p=3$,$q=11$ という $2$ つの素数を使って、$X=8$ という情報をRSA暗号化しなさい。また、復号してしっかり $8$ に戻るか確認しなさい。

【解答】

$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暗号の作り方や解き方・安全性まで

  • 東北大学理学部数学科卒業
  • 教員採用試験に1発合格 → 高校教諭経験アリ

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

スポンサーリンク
スポンサーリンク
目次

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

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

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

公開鍵暗号(共通鍵暗号)とは?

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

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

数学太郎のアイコン画像数学太郎
暗号って聞くと、公開されていないイメージだけど、これでちゃんと暗号が作れるんだね!
ウチダのアイコン画像ウチダ
たしかにそのイメージはありますね。ただ、RSA暗号の最大の特徴は、「秘密鍵が特定されづらいこと」にあるのです!

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

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

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

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

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

例題. 次の問いに答えよ。
(1) $113×227$ を計算しなさい。
(2) $25651$ を素因数分解しなさい。

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

(1) → $25651$

(2) → $113×227$

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

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

数学花子のアイコン画像数学花子
(1)はただ計算するだけで簡単だけど、(2)は難しいです。(1)のヒントがなかったら、素因数分解するのに $10$ 分ぐらいかかりそう。
ウチダのアイコン画像ウチダ
そうなんです。「掛け算は簡単だけど、素因数分解はめちゃムズイ。」これって、人間だけじゃなくコンピュータも同じなんですよ。

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

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

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

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

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

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

スポンサーリンク

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

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

例題. $p=3$,$q=11$ という $2$ つの素数を使って、$X=8$ という情報をRSA暗号化しなさい。また、復号してしっかり $8$ に戻るか確認しなさい。

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

  • 素数を $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$ と復号して完了。

ではやっていきます。

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

  1. 合同式の基本的な使い方3選とは【まずは練習問題でmodに慣れよう】
  2. フェルマーの小定理の2通りの証明とは?【京大入試を含む問題3選も解説】

Step1.公開鍵と秘密鍵を用意しよう

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

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

\begin{align}n・(p-1)・(q-1)+1&=1・2・10+1\\&=21\end{align}

となりました。

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

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

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

数学太郎のアイコン画像数学太郎
実際は、もっと大きな素数を用意して公開鍵と秘密鍵を設定しないとダメなんですよね…?
ウチダのアイコン画像ウチダ
ここの素因数分解の難しさが肝になってきますから、その通りですね。ただ、$n(p-1)(q-1)$ と互いに素な整数 $P$ を取ってきて、$PQ≡1 \pmod{(p-1)(q-1)}$ の合同方程式を解けば $Q$ が見つかるので、ここまでは簡単に設定できますよ^^

Step2.暗号化して情報を送ろう

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

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

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

と計算します。

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

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

を計算します。

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

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

Step3.復号化して情報を受け取ろう【完了】

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

ウチダのアイコン画像ウチダ
このとき仮に通信が傍受されたとしても、秘密鍵 $Q$ を知っているものでなければ $X’=17$ を $X=8$ に復号化することができませんね。

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

$$17^7=410338673$$

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

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

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

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

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

ではなぜ成り立つのか。

それは…

【RSA暗号の原理】
$p$,$q$ を相異なる素数とすると、$$X^{n(p-1)(q-1)+1} \pmod{pq}=X$$が成り立つ。
※厳密にはもう少し条件が付きますが、ここではスルー。

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

【原理の大まかな証明】

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

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

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

≫参考記事:フェルマーの小定理の2通りの証明とは?【京大入試を含む問題3選も解説】

よって、任意の自然数 $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$ を設定してやれば、

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

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

ウチダのアイコン画像ウチダ
仕組みは何となく理解できましたか?ネット社会を支えているにもかかわらず、意外とシンプルな原理で成り立っていることさえ押さえればOKです^^
スポンサーリンク

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

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

RSA暗号の安全性

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

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

ということは…

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

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

ウチダのアイコン画像ウチダ
しかし、リーマン予想が解決されたからと言って、RSA暗号の解読にはつながらないという主張が大多数です。

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

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

それぞれの詳しい解説はこちらから

  • リーマン予想とは(準備中)
  • 量子コンピュータとは(準備中)
  • 量子暗号とは(準備中)

RSA暗号とサマーウォーズ

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

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

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

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

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

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

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

数学花子のアイコン画像数学花子
この世界線であっても、量子暗号は応用段階ではなかったということね。

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

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

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

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

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

RSA暗号に関するまとめ

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

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

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

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

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

終わりです。

遊ぶ数学公式LINEやってます!

遊ぶ数学管理人「ウチダショウマ」に数学を直接教わることができるオンライン家庭教師サービス”Play MATH”を開始しました。

その他にも

・ウチダショウマとお話がしたい
・勉強に関する悩みを相談したい

などでもOKですので、ぜひ気軽にご連絡ください。

↓友達追加はこちらから↓

友だち追加

スポンサーリンク

コメント

コメントする

目次
閉じる