暗号の進化と発展

2019年11月6日

クロアのロードバイク乗り

 

みなさん初めまして。CACクロアの”ロードバイク乗り”です。
天気の良い休日などは100㎞程度サイクリングを楽しんでいます。ロードバイクを乗らない方に話すと100㎞のサイクリングと聞いて驚かれますが、私も始めるまではそう思っていました。しかし、やってみるとどんどん走れる距離が伸びていき、今や100㎞は長距離とは思えないようになってしまいました。

さて本稿では、WEB技術において現在なくてはならない「暗号」の進化・発展についてご説明したいと思います。オンラインショッピングなどでクレジットカード番号を入力して送信する際、第三者に番号がわかってしまっては大変です。そこで、通信中に盗み見されないように大切な情報を暗号化しています。
「暗号」というと難しいイメージがありますが、その技術は意外と簡単な原理で実装されつつ、非常に強固にできています。しかし、近年では量子コンピューターの研究などが進み、この「暗号」も破られるのではないかと噂されています。
いつかは破られるかもしれない運命、現代社会において「暗号」も例外ではないようです。

暗号とは

「暗号」を広義でとらえれば、暗号を使う人以外(つまり第三者)が解読できないような手法で通信を行えれば、それは全て「暗号」だと言えます。そういう意味では、日本語も日本以外で使用すれば暗号(この場合は隠語といったほうがより近いかもしれません)として機能する可能性もあります。海外で現地の人に文句や皮肉を日本語で発音しても、相手は何を言っているのか理解できないわけです。
とはいえ言葉の意味は理解できなくても、なにかネガティブな発言であることは直観で見抜かれますので、発言には充分にお気を付けください。

初期の暗号

そうした広義の「暗号」ではなく、意図的に作成された「暗号」として古く有名なものに、紀元前のローマでカエサル(シーザー)が用いたとされる「シーザー暗号」があります。

ではここで問題です。

「dbd dspju dpsqpsbujpo」

 

 

上記はなにを表しているのか、皆さまはお判りでしょうか?・・・


答えは


「cac croit corporation」

 

です。当社の社名をシーザー暗号で暗号化してみました。
この暗号はシフト暗号とも呼ばれ、文字を辞書順に前、または後ろにある文字と置き換える「アルゴリズム」と、ずらす範囲の「鍵」が設定されています。今回は、文字順をひとつ後ろにずらして暗号化しています。

暗号通信文を受け取る相手には上記のアルゴリズムと鍵を前もって教えておけば解読できるようになっています。
暗号が生まれた初期の手法ですので、現代においては小学生でも解読可能かもしれません。
もっといえば、小学校の頃にこの暗号で、教師にわからないように通信していた方もいらっしゃることでしょう。

第二次世界大戦頃の暗号

この頃になると「シーザー暗号」のような単純な暗号は次々と解読されるようになり、より複雑化するために、機械で暗号を作成する方法が用いられました。
有名なものに、旧ドイツ軍が使用した「エニグマ」と呼ばれる、ローター式暗号機があります。
この機械は、多表式換字の暗号機で、タイプライターのように文章を打ち込むと暗号化された文章が印刷されるといったようなものでした。

エニグマ
エニグマ

 

「エニグマ暗号機」には3枚のローター(暗号円盤)が内蔵され、キーを押すと中のローターが回転し別の文字を印刷する、という仕組みになっています。
この暗号はローターがアルゴリズムになり、沢山あるローターの中でどの3枚を使用するか、また、そのセットする順番が鍵でした。
当時は解読不能だとおもわれていましたが、イギリスの数学者”アラン・チューリング”が見事解読に成功し、第二次世界大戦はドイツ帝国の敗北という結果に終わったのは皆さまもご承知の通り。このことは「イミテーション・ゲーム / エニグマと天才数学者の秘密」として映画化もされています。”アラン・チューリング”は他にも「チューリング完全」と呼ばれる、現在のコンピューター計算の礎を築いた人としても有名ですが、趣旨が異なりますので説明は省きます。

これまでのことから

  • アルゴリズム

 

この2点が明らかになれば、暗号は容易に解読できることがご理解いただけたかと思います。

その後、科学はさらに発展し、今では暗号の解読にコンピューターを利用できるようになり、ますます暗号作成者にとっては厳しい時代になっていきましたが、そこで、発想の転換がなされます。
「アルゴリズムや鍵はいずれ判明される。であれば、アルゴリズムや鍵を明かしても、解読されない暗号を作ればいいのではないか?」・・・その発想のもとに作成された暗号こそ、現在使われている「暗号」なのです。

現在の暗号

現在使われている暗号の中で、有名なものに「RSA暗号」「楕円曲線暗号」などが挙げられますが、いずれも暗号化の方法は一般に公開されており、誰でも入手することができます。
これらの「鍵」も「公開鍵」との名称で、その名の通り公開されています。このような暗号を「公開鍵暗号」と呼び、一方で暗号の作成も解読も同じ鍵を使う、前章のような古い暗号を「共通鍵暗号」と呼びます。
「公開鍵暗号」は、2つの鍵「秘密鍵」と「公開鍵」を使用し、暗号の作成には「公開鍵」を使い、解読には「秘密鍵」を使います。当然「秘密鍵」は誰にも知られてはいけません。
しかしながら「秘密鍵」がどのようなものであり、どのように作成されるかは公開されています。
近年最も利用されている「RSA暗号」を例にとると、「公開鍵」は素数同士が掛け合わされた数であり、「秘密鍵」も数であることだけは知られています。

現在主流のRSA暗号

「RSA暗号」について、詳しくお話ししましょう。現在のところ、解読不可能とされているこの暗号。安全性を誇る最大の根拠は巨大な数の素因数分解、つまり、素数に分けること(秘密鍵を知ること)が非常に困難であること。この場合の困難とは、素因素分解自体が難しいわけではなく、その結果が判明するまでの計算時間がとてつもなく長くかかることを意味しています。

原理(アルゴリズム)*1としては、至極単純なもので2つの素数と1つの数字を用意します。仮にその2つの素数をp=3とq=11とします。1つの数字をe=13と決めると(pxq)=33と(e)=13が公開鍵となります。そして秘密鍵*2はd=17とします。

A=2、C=4、とすると CAC という文字は 4、2、4となります。

暗号をかけて送る側は公開鍵33、13をつかって

C(4) -> 4の13乗を33で割ったあまり = 31
A(2) -> 2の13乗を33で割ったあまり = 8
C(4) -> 4の13乗を33で割ったあまり = 31

つまり暗号化した文字は 31、8、31となります。

暗号を受けとった側は秘密鍵17をつかって
31  -> 31の17乗を33で割ったあまり = 4 (C)
8    -> 8の17乗を33で割ったあまり   = 2 (A)
31  -> 31の17乗を33で割ったあまり = 4 (C)
となり元にもどります。

まさに レオナルド・ダ・ヴィンチの名言どおり
Simplicity is the ultimate sophistication. 「シンプルさは究極の洗練である」
中学校程度の数学の知識で理解できるシンプルな方法です。

この例の場合、pとqを掛け合わせた33という数字の素因数分解ができれば秘密鍵が判明してしまいます。しかし、もしpとqが500桁という巨大な数字であったらどうでしょうか?
最初に書いたように、巨大な数字を素因数分解するには現在の最新コンピューターをもってしても途方もない時間がかかるといわれています。

*1 実際のRSA暗号はもう少し複雑で同じ文字でも毎回違う暗号(数字)を発生するようになっています。
*2 秘密鍵dはed ≡ 1 mod (p – 1)(q – 1) となる正整数 d で求められる。

 

未来の暗号

未来の暗号?RSA暗号は、解読に時間がかかるので、実質的に解読不能なんでしょ?と今まで読まれた方は思われるかもしれませんね。しかし科学技術の進歩はいつも我々の想像を超えていきます。
もし、素因数分解がとてつもなく早く解けるコンピューターが開発されたらどうでしょうか?

2019年10月にはGoogleが、スーパーコンピューターで1万年かかる計算を200秒で処理したという、量子コンピューターの優位性を証明する実験結果を公開しました。
この結果には、さまざまな意見があるものの、このような量子コンピューターが開発されれば、今までよりはるかに短い時間で解読ができ、この暗号は役に立たなくなります。
それにそなえて暗号学者は、「格子暗号」などの耐量子コンピューター暗号の実用化に向けて世界中で競い合っています。

では、「格子暗号」ってどんなものなの?
これはまた別の機会にご説明しましょう。
(といいながら”ロードバイク乗り”もまだよくわかっておりません)

最後までお読みいただきありがとうございました。次号もお楽しみに!

 

 

※記載されている情報は2019年11月時点のものです。


TOP