« 藤井聡太・五冠王、4勝1敗で王位三連覇!、豊島将之九段の善戦及ばず(2022年・第63期) | トップページ | 季節の変わり目、エアコン冷房睡眠と雨天ジョグで(?)久々にプチ風邪モード »

素数の積(11×19)を公開鍵209にしたRSA暗号、作り方と解読方法の具体例の解説~NHK『笑わない数学』第9回

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

     

なるほど、RSA暗号というシステムは良く出来てる。たかが11×19=209を公開鍵にしただけで、これほど大変な計算になるのなら、巨大な素数(300ケタとか)の積を公開鍵にすればほとんど解読不可能だろう。開発中の量子コンピューターはさておき。

   

放送(22年9月7日、23時~23時30分)から19時間ほど経った現在、「笑わない数学 暗号 計算」でGoogle検索をかけると、最後の問題を解いた方の計算式のツイート画像が1つ見つかる。

   

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

      

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

  

  

     ☆     ☆     ☆

220908a

  

まず、素数の掛け算(p×q)で、公開鍵Nを作成する。ここでは簡単な素数を使って、11×19=209。これが、N。公開鍵は英語だと public key(パブリック・キー) 。

   

220908b

    

掛け合わせた数209を公開鍵として一般公開する。尾形に情報を送りたい人は、N=209で送ってね。11×19であることは秘密で、誰にも伝えない。

  

それに加えて、番組では「ある決めた回数だけ、掛け合わせ」とだけ説明してたが、17という数字も公開する。この17とは、(p-1)(q-1)=10×18=180と、互いに素な自然数の1つ。別に17である必要はない。

  

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

      

   

      ☆     ☆     ☆

220908c

  

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

     

220908d

  

(21の17乗)÷209の余り」を計算。私はいつものように、カシオの計算サイトを利用。確かに、余りは10になった。最初の掛け算は、桁数の設定を多めにしないと失敗する。

 

220908l

   

30041942495081691894741÷209の余りは、10。この数字10が、尾形に伝える暗号になる。パソコンのWindows付属の関数電卓でも計算可能。

    

220908m

  

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

     

左上の企業名を消してたが、CASIOのMW-100TCだろう。amazonで902円。演出で身近なコンピューターのイメージとして使っただけで、実際には別の計算機か計算サイト、アプリを使ってる。人力の筆算でも出来なくはない。

  

   

       ☆     ☆     ☆

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

  

220908f

  

 d={(p-1)(q-1)×5+1}/17

   

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

    

例えば、10×18×1+1では、17で割り切れない。10×18×2+1も17で割り切れない。10×18×3+1も、10×18×4+1も失敗。その次の5で、ようやく成功する。

    

d=(10×18×5+1)/17=53

   

  

     ☆     ☆     ☆

少し突っ込んで考えると、上の式は、分母を払って左右を入れ替えると、53×17=10×18×5+1

     

ということは、53×17を10×18で割った余りは1となる。要するに、「17と掛け合わせると、10×18で割った余りが1になるような自然数の1つ」が、53ということ。その時、10×18で割った「商」が、5。

   

ただし、dを180以下に制限するなら、ただ1つに定まる(ここでは53)。これが、英語版ウィキや学研系サイトの説明になってた。番組では分かりやすく、説明抜きで割り算。

    

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

  

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

  

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

   

   

     ☆     ☆     ☆

最後に、このd=53と暗号を用いて、次のように計算する。

  

220908h

  

「(10の53乗)÷209」のあまり。これを、カシオのサイトの「余り計算」で行うと、割られる数が大き過ぎてエラーになってしまった。

  

そこで、53乗を、30乗と23乗に分けて計算する。(10の30乗)÷209の余りは、45。また、(10の23乗)÷209の余りは、98。この余り同士を掛け合わせると、45×98=4410。

   

さらに、4410÷209の余りは、21。これが、(10の53乗)÷209の余りになる。数年前まで、高校(数学A)の合同式(mod)の箇所で教えてた基本公式(性質)で、ここでは説明省略。今現在は、高校数学の課程から外されてるらしい。

     

220908p

    

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

   

   

      ☆     ☆     ☆

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

    

220908j

   

ここでも、あえて途中の数字は書かないが、96を53乗すると非常に大きな数になってしまう。そこで私は、10乗と3乗を利用して計算した。10乗を209で割ると、余り1。また、3乗を209で割ると、余り39。

     

∴ {(96の53乗)を209で割った余り)}

 =〔{(1の5乗)×39}を209で割った余り〕

 =39

     

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

   

  

cf. デカルトが「虚数(nombre imaginaire)」と名付けたという説明は誤り(or不正確)~『笑わない数学』第6回

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

    

       (計 2856字)

| |

« 藤井聡太・五冠王、4勝1敗で王位三連覇!、豊島将之九段の善戦及ばず(2022年・第63期) | トップページ | 季節の変わり目、エアコン冷房睡眠と雨天ジョグで(?)久々にプチ風邪モード »

映画・テレビ」カテゴリの記事

数学」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



« 藤井聡太・五冠王、4勝1敗で王位三連覇!、豊島将之九段の善戦及ばず(2022年・第63期) | トップページ | 季節の変わり目、エアコン冷房睡眠と雨天ジョグで(?)久々にプチ風邪モード »