「RSA暗号」を解説QuizKnockアプリで記事をもっと見やすくインストールする現在JavaScriptの設定が無効になっています。すべての機能を利用するにはJavaScriptの設定を有効にしてください。みな子2021.08.27城南信用金庫PR【前準備】テキストを数字に置き換えるまず、暗号化したい文章はそのまま暗号化されるわけではなく、テキストは数字に置き換えられる。「A」は「01」、「B」は「02」などに置き換え、それを数式で変換して暗号化される。▲テキストをそのまま暗号化できないため、数字に置き換えるRSA暗号で暗号化するには?数字に変換された文章を暗号化するには、先ほどの「南京錠つき箱」にあたる、2つの数字(e,n)を用いる。以下の式のように、数字に置き換えられた元の文「M」をe乗し、nで割った余りが等しくなるように暗号文Cを決定する。意外とシンプルな式だ。「mod」という表現が見慣れない人もいるかもしれないが、これは「モジュロ演算」という、割り算の余りを扱う計算のこと。上記の式では、「Cをnで割った余りと、Mのe乗をnで割った余りが同じ」ということを表している。作中で、健二が夏希先輩の生年月日を聞いてその日の曜日を答える、というシーンがあったが、これもモジュロ演算を利用したもの。RSA暗号で重要になるモジュロ演算について、彼が得意分野であることを示唆する、物語の伏線となっている。RSA暗号を解読するには?暗号文Cを受け取った人がこの暗号を読み解くには、自分しか持っていない(p,q,d)という3つの秘密の数字の組み合わせ(秘密鍵)が必要になる。ここで、dはp,q(それぞれ素数)と、公開鍵eに対して、以下の条件が成り立つようになっている。上記の条件を満たす「d」と、公開鍵の「n」を以下の式に沿って計算すると、暗号を解読することができる。このように、自分しか知らない鍵を用いることで、暗号が解読できるという仕組みだ。ちなみに、式に使用する(d,n)の組み合わせを秘密鍵と呼ぶ場合もある。他人が暗号を解読しようとしたら?では、この秘密鍵を知らない状態から、eとnのみを使って暗号を解こうとするとどうなるだろうか。dを導き出すには(p,q)が必要なのだが、そのヒントになるのが、公開鍵のひとつ「n」だ。nはpとqをかけ合わせた数字で、pとqはそれぞれ素数で設定されている。RSA暗号を解くには、このnを素因数分解してpとqを求められればほぼ突破できると言っても過言ではない。素因数分解といえば、中学数学で習う計算だ。問題の数字を小さな素数から順に割ることで、効率的に計算できることを学んだはず。あなどるなかれ、素因数分解はnの桁数が大きくなると非常に困難なのである。以下が彼が素因数分解したとされる「n」だ。そんなの信じられる?この素因数分解は、生身の人間だけでなく、コンピュータもそこまで得意ではない。いうのも、素因数分解を行うプログラム自体を人間が考えねばならない。数体篩法すうたいふるいほうをはじめとする、効率的に素因数分解を行える方法も研究されているが、まだ現在のRSA暗号の安全性を脅かすまでには至っていないということだ。過去には、コンピュータの技術の向上によって1993年(発表は1994年)に129桁の素因数分解に成功し、テストメッセージを解読された事例がある。これの解読には、1600台ほどの計算機が投入され、8カ月かかったとされている。それ以降もコンピュータが素因数分解ができる桁数は増えているが、現在RSA暗号の鍵に一般的に利用されている617桁以上(2048bit)の素因数分解は、未だ踏破された記録がない。ここでもう一度言おう、健二が素因数分解したとされているのは千桁以上のnだ。してnを素因数分解して、dを定めるのに非常に時間がかかるため、RSA暗号の堅牢さが守られているということだ。健二はなぜヤバいのか世界の最先端の技術をもってしても難しいとされる暗号解読を、彼は紙とペンだけでやってのけてしまった。これがどれくらいヤバいのか、おわかりいただけただろうか。あろうことに健二は重要な鍵のひとつ、eが明かされていない状態で解けてしまっているとの指摘もある。RSA暗号の解読には量子コンピュータの開発が大きな影響を与えるといわれているが、それどころではない。この情報化社会を支える地盤が揺らいでしまっている事態である。健二は早くどこかに隠れたほうがいい。そのヤバさが伝わる動画がQuizKnockのYouTubeチャンネルでも公開されている。ちなみに、動画内でメンバーが解いている問題を作成したY氏に尋ねてみたところ、「4桁の暗号を作るだけで丸一日かかった」とのことだった。関連エピソードを含めてもいろいろヤバいRSA暗号、興奮ついでに動画もぜひどうぞ。【合わせて読みたい】12Amazonのアソシエイトとして、当サイトは適格販売により収入を得ています。小学5年生で解ける時計の問題。長針と短針が重なる時刻は?「宝石」が時計に使われているって本当?身近に潜む科学のクイズ小学5年生で解ける「正方形と正六角形」の問題。みな子QuizKnock編集部で記事の編集をしながら、記事も書きます。記事を通して「知る楽しさ」の入り口を広げていきたいです。インターネットや動物、ポップカルチャーが大好き。大学時代は宇宙物理学を専攻していましたが、星座に詳しくないのが悩みです。