こんにちは、ウチダです。
「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暗号の作り方や解き方・安全性まで
- 東北大学理学部数学科卒業
- 実用数学技能検定1級保持
- 高校教員→塾の教室長の経験あり
の僕がわかりやすく解説します。
RSA暗号の仕組みとは?【素因数分解を応用した公開鍵暗号です】
RSA暗号を一言で表すのであれば、「素因数分解を応用した公開鍵暗号」です。
ここで、よくわからない言葉「公開鍵暗号」が出てきましたので、そこから詳しく解説していきます。
公開鍵暗号(共通鍵暗号)とは?
- 公開鍵 … 誰でも知ることができる、暗号化するための鍵
- 秘密鍵 … 暗号を受信する人しか知り得ない、復号化するための鍵
公開鍵暗号(共通鍵暗号)では、上記の $2$ つの鍵を使います。
[ふきだし set=”考える男性”]暗号って聞くと、公開されていないイメージだけど、これでちゃんと暗号が作れるんだね![/ふきだし]
[ふきだし set=”ウチダ”]たしかにそのイメージはありますね。ただ、RSA暗号の最大の特徴は、「秘密鍵が特定されづらいこと」にあるのです![/ふきだし]
というより、秘密鍵が特定されたら暗号が破られてしまうため、アウトなんですが…(笑)
ここまででわかった情報を、一度図にまとめます。
では、特定されづらい秘密鍵 $Q$ を作るために、素因数分解を応用してみましょう!
素因数分解をどう応用する?
(1) $113×227$ を計算しなさい。
(2) $25651$ を素因数分解しなさい。
これ、実際に計算すると、
(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$ と復号して完了。
ではやっていきます。
前提知識に関する記事はこちらから
Step1.公開鍵と秘密鍵を用意しよう
今回 $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$ が見つかるので、ここまでは簡単に設定できますよ^^[/ふきだし]
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$ を復号しましょう。
[ふきだし set=”ウチダ”]このとき仮に通信が傍受されたとしても、秘密鍵 $Q$ を知っているものでなければ $X’=17$ を $X=8$ に復号化することができませんね。[/ふきだし]
$17$ を、最初に設定した秘密鍵 $Q=7$ 乗してみます。
$$17^7=410338673$$
最後に、法 $33$ として計算すると、
$$410338673≡8 \pmod{33}$$
となり、$X=8$ と解読できました~♪
【RSA暗号の原理】なんでそうなるの?
以上の操作は、$X$ がどんな情報であれ成り立ちます。
ではなぜ成り立つのか。
それは…
$p$,$q$ を相異なる素数とすると、$$X^{n(p-1)(q-1)+1} \pmod{pq}=X$$が成り立つ。
※厳密にはもう少し条件が付きますが、ここではスルー。
この原理の証明に「フェルマーの小定理」が使われるわけです。
だから、$PQ=n(p-1)(q-1)+1$ を満たすように公開鍵 $P$,秘密鍵 $Q$ を設定してやれば、
となり、法 $pq$ で $X$ に戻ってくるのです。
[ふきだし set=”ウチダ”]仕組みは何となく理解できましたか?ネット社会を支えているにもかかわらず、意外とシンプルな原理で成り立っていることさえ押さえればOKです^^[/ふきだし]
RSA暗号はネット社会を支えています【めちゃスゴイ】
さて、最後にRSA暗号の安全性について考察したいと思います。
RSA暗号の安全性
現時点で最も優秀だと言って良いRSA暗号。
これは「素因数分解の困難さ」から成り立っています。
ということは…
- 素数が現れる規則性が見つかったらヤバイ。
- めちゃくちゃ計算力が高いコンピュータができたらヤバイ。
そして前者が「リーマン予想」、後者が「量子コンピュータ」の話につながってきます。
[ふきだし set=”ウチダ”]しかし、リーマン予想が解決されたからと言って、RSA暗号の解読にはつながらないという主張が大多数です。[/ふきだし]
現実的にあり得そうなのは「量子コンピュータ」の方ですが、もしこれが実現したら「量子暗号」で太刀打ちできる、との噂もあります。
ここら辺は未だ研究段階ですので、何とも言えませんね、、汗
RSA暗号とサマーウォーズ
もう一つ。RSA暗号と聞くと思い出すのが「サマーウォーズ」という映画ではないでしょうか。
※以下、サマーウォーズのネタバレを一部含みますのでご了承下さい。
サマーウォーズの主人公である「小磯健二(以下ケンジで統一)」は、東京都在住の高校2年生。
物理部に所属しており、数学が大の得意で数学オリンピック代表候補でもある。
そんな中、世界中の人が集うインターネット上の仮想世界OZ(オズ)が謎のAIにハッキングされてしまい、社会的大混乱が起きる。
最後はケンジが見事暗号を打ち破り、探査機がケンジ宅に落ち半壊するというトラブルはあったものの、無事勝利を収め、社会とケンジの家族に平和が訪れるのであった。
大体こんなストーリーで、途中出てきた暗号というのが正しく「RSA暗号」なんですね。
[ふきだし set=”考える女性”]この世界線であっても、量子暗号は応用段階ではなかったということね。[/ふきだし]
…まあ、RSA暗号解読の困難さをわかっている状態でサマーウォーズを見ると、
え?これでケンジなんで数オリ出れないの??
と思ってしまうぐらいスゴイ。
というかもはや量子コンピュータをも軽く上回る計算力お化けなんですけどね。(笑)
ふつうにハラハラドキドキする面白い映画なので、気になる方はぜひご覧ください。
RSA暗号に関するまとめ
本記事のポイントをまとめます。
- RSA暗号は、素因数分解の困難さを応用して作られた、現在最も優秀な公開鍵暗号の $1$ つ。
- 「合同式の基本知識」と「フェルマーの小定理」を使えば、RSA暗号の原理が説明できる。
- サマーウォーズの主人公であるケンジは、人間離れしているというか、「量子コンピュータ」の計算力をもしのぐ。
これからの量子論の研究に注目するとともに、RSA暗号に感謝しながらネット時代を生き抜きましょう。
「整数の性質」全 25 記事をまとめました。こちらから次の記事をCHECK!!
おわりです。
コメントを残す
コメント一覧 (10件)
秘密鍵と公開鍵が同じになってしまっても成り立ちますか?
理論的には成り立つはずですが、まあセキュリティ上の観点から、良くはないでしょうね
n(p-1)(q-1)+1が素数の場合、PとQはどのようにすればいいでしょうか?
n(p-1)(q-1)+1が素数になることってあるんですかね??
これ考えてみても面白いかもしれないです
PとQをプログラムで機械的に作る場合、どのような判定にすればいいのでしょう?
PとQは素数であれば何でもいいので、大きな素数を2つ適当にピックアップすればいいのではないでしょうか?
nは何でもいい自然数と書いてありますが本当になんでもいいんですか?
はい、なんでも成り立ちます!
ただ、nを大きくするとpとqも必然的に大きくなって計算が大変なので、まあn=1で考えてもらえればOKです。
n(p-1)(q-1)+1ではどうしてpやqから1を引くのですか?
RSA暗号の原理の章で解説している通り、相異なるp,qに対して $X^{n(p-1)(q-1)+1} \pmod{pq}=X$ が成り立つからですね。
Xという暗号化したい数に、n(p-1)(q-1)+1乗という複雑な計算をかまして、その上でpqで割ったあまりを求めると、Xに戻ります。
この性質を使ってRSA暗号を作っているので、このn(p-1)(q-1)+1という数はRSA暗号を成り立たせている数だというふうにご認識ください。