QuizKnock

アプリで記事をもっと見やすく

インストールする

カテゴリ

ログイン
花王
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暗号、興奮ついでに動画もぜひどうぞ。

【合わせて読みたい】

2
Amazonのアソシエイトとして、当サイトは適格販売により収入を得ています。

関連記事

この記事を書いた人

野口 みな子

QuizKnock編集部で記事の編集をしながら、記事も書きます。記事を通して「知る楽しさ」の入り口を広げていきたいです。インターネットや動物、ポップカルチャーが大好き。大学時代は宇宙物理学を専攻していましたが、星座に詳しくないのが悩みです。名古屋大学の大学院理学研究科卒。

野口 みな子の記事一覧へ