素数の積（１１×１９）を公開鍵２０９にしたＲＳＡ暗号、作り方と解読方法の具体例の解説～ＮＨＫ『笑わない数学』第９回

この計算は大変だった。特に、最後の宿題みたいな問題は、終盤に出て来る数が大き過ぎるから、少し工夫しないと専門サイトでも計算できない。桁数が数十～百ケタ以上になるから、普通の電卓でも無理なはず。

なるほど、ＲＳＡ暗号というシステムは良く出来てる。たかが１１×１９＝２０９を公開鍵にしただけで、これほど大変な計算になるのなら、巨大な素数（３００ケタとか）の積を公開鍵にすればほとんど解読不可能だろう。開発中の量子コンピューターはさておき。

放送（２２年９月７日、２３時～２３時３０分）から１９時間ほど経った現在、「笑わない数学　暗号　計算」でＧｏｏｇｌｅ検索をかけると、最後の問題を解いた方の計算式のツイート画像が１つ見つかる。

ただ、それは番組とは少し計算の仕方が違うし、番組内容の解説まではしてない。特に、私がテレビを見て引っかかったのは、計算に利用する１７と５という数字だった。以下では、番組内容に即して、暗号理論の実際を具体的に解説してみよう。２１と３９の暗号化と解読方法だ。

参考にしたサイトは２つ。英語版ウィキペディアの「RSA (cryptosystem)」と、高校数学の美しい物語（学研グループ）。説明の仕方や記号の使い方が多少、違ってるが、本質的には同じ説明だった。たぶん、世界標準の方法だろう。

　　　　　☆　　　　　☆　　　　　☆

まず、素数の掛け算（ｐ×ｑ）で、公開鍵Ｎを作成する。ここでは簡単な素数を使って、１１×１９＝２０９。これが、Ｎ。公開鍵は英語だと public key（パブリック・キー） 。

掛け合わせた数２０９を公開鍵として一般公開する。尾形に情報を送りたい人は、Ｎ＝２０９で送ってね。１１×１９であることは秘密で、誰にも伝えない。

それに加えて、番組では「ある決めた回数だけ、掛け合わせ」とだけ説明してたが、１７という数字も公開する。この１７とは、（ｐ－１）（ｑ－１）＝１０×１８＝１８０と、互いに素な自然数の１つ。別に１７である必要はない。

「互いに素」とは、お互いの公約数が１だけという意味であって、１８０自体は素数ではないので念のため。もちろん、２０９も素数ではない。

　　　　　　☆　　　　　☆　　　　　☆

スタッフが、「２１」という元の情報を尾形にメールなどで送りたいとする。建物の階数の指定。２０９と１７を使って、次のように暗号化する。

「（２１の１７乗）÷２０９の余り」を計算。私はいつものように、カシオの計算サイトを利用。確かに、余りは１０になった。最初の掛け算は、桁数の設定を多めにしないと失敗する。

30041942495081691894741÷209の余りは、１０。この数字１０が、尾形に伝える暗号になる。パソコンのＷｉｎｄｏｗｓ付属の関数電卓でも計算可能。

ただ、番組で使ってた（ように見せてた）電卓は、個人か中小企業が税金の計算に使うもので、１０桁しか扱えないから論外。電卓の右上に、１０と書いてあった。

左上の企業名を消してたが、ＣＡＳＩＯのＭＷ－１００ＴＣだろう。ａｍａｚｏｎで９０２円。演出で身近なコンピューターのイメージとして使っただけで、実際には別の計算機か計算サイト、アプリを使ってる。人力の筆算でも出来なくはない。

　　　　　　　☆　　　　　☆　　　　　☆

尾形が暗号を解読する時には、１７に加えて、尾形だけが知ってる素数１１と１９を使って、まず次のようにｄを計算する。ｄは秘密鍵、個人鍵と訳されるもので、元の英語は private key（プライベート・キー）。

　ｄ＝｛（ｐ－１）（ｑ－１）×５＋１｝／１７

この「もどす方法」の分子に、「５」と「1」という数字がある。１はもう決まった数だが、５は別の数でもよい。ｄの値が自然数になるような小さい自然数の１つが５ということ。

例えば、１０×１８×１＋１では、１７で割り切れない。１０×１８×２＋１も１７で割り切れない。１０×１８×３＋１も、１０×１８×４＋１も失敗。その次の５で、ようやく成功する。

ｄ＝（１０×１８×５＋１）／１７＝５３。

　　　　　☆　　　　　☆　　　　　☆

少し突っ込んで考えると、上の式は、分母を払って左右を入れ替えると、５３×１７＝１０×１８×５＋１

ということは、５３×１７を１０×１８で割った余りは１となる。要するに、「１７と掛け合わせると、１０×１８で割った余りが１になるような自然数の１つ」が、５３ということ。その時、１０×１８で割った「商」が、５。

ただし、ｄを１８０以下に制限するなら、ただ１つに定まる（ここでは５３）。これが、英語版ウィキや学研系サイトの説明になってた。番組では分かりやすく、説明抜きで割り算。

とにかく、秘密鍵ｄの値は、相手が送って来る暗号とは無関係。最初から尾形（＝解読する人、受信者）が用意しておけばよい。

本質的には、ｄだけが解読のポイント。しかしｄは、ｐとｑと１７から計算されるので、ｐとｑも秘密にする必要がある。ｐ×ｑの値を公開しても、それが非常に巨大な数なら、そこからｐとｑを求めるのは難しい。

番組の２０９なら、人間でもすぐに１１×１９と分かってしまうが、一般向けのバラエティ番組の例え話だから構わない。

　　　　　☆　　　　　☆　　　　　☆

最後に、このｄ＝５３と暗号を用いて、次のように計算する。

「（１０の５３乗）÷２０９」のあまり。これを、カシオのサイトの「余り計算」で行うと、割られる数が大き過ぎてエラーになってしまった。

そこで、５３乗を、３０乗と２３乗に分けて計算する。（１０の３０乗）÷２０９の余りは、４５。また、（１０の２３乗）÷２０９の余りは、９８。この余り同士を掛け合わせると、４５×９８＝４４１０。

さらに、４４１０÷２０９の余りは、２１。これが、（１０の５３乗）÷２０９の余りになる。数年前まで、高校（数学Ａ）の合同式（ｍｏｄ）の箇所で教えてた基本公式（性質）で、ここでは説明省略。今現在は、高校数学の課程から外されてるらしい。

とにかく、暗号化する前の情報が「２１」だと分かった。解読成功！

　　　　　　☆　　　　　☆　　　　　☆

一方、番組最後のナゾナゾ問題は計算が大変過ぎて、本当に計算した視聴者は僅かだろう。元の情報を暗号化した数字が、９６。

ここでも、あえて途中の数字は書かないが、９６を５３乗すると非常に大きな数になってしまう。そこで私は、１０乗と３乗を利用して計算した。１０乗を２０９で割ると、余り１。また、３乗を２０９で割ると、余り３９。

∴　｛（９６の５３乗）を２０９で割った余り）｝

　=〔｛（１の５乗）×３９｝を２０９で割った余り〕

　＝３９

したがって、元の情報は、３９。つまり、「サンキュー」。ケタ数の設定に注意して、皆さん、お試しあれ。今回は素直に面白い番組で、情報理論の勉強にもなった。３９♪　それでは今日はこの辺で。。☆彡

ｃｆ．　デカルトが「虚数（nombre imaginaire）」と名付けたという説明は誤り（ｏｒ不正確）～『笑わない数学』第６回

　初期値敏感性とカオス（混沌）理論でピザ作り、「パイこね変換」具体例の計算と解説～第８回

　　　　　　　（計　２８５６字）