Link

リンク

サルにも分かるRSA暗号

共通鍵暗号

現代の暗号のエッセンスは、伝えたい文を数値に直した後の 数値を別の数値に変換する という点にあることが分かりました。このような現代暗号は、これまでに DESAESFEALE2CameliaRC6IDEA… など、実に様々な方法が研究・設計がされています。 これら暗号には、数々の面白いエピソードが知られていますが、詳しくは筆者の本で紹介するとして、ここでは最近の大きな話題をいくつか紹介します。

DES(デス)は、1976年にアメリカ商務省標準局(NBS:現在のNIST)が行った標準暗号の公募に対してIBMが応募し、採用された暗号方式です。 アメリカ政府機関のお墨付や実用における長い間の実績があり、前世紀中は最も安全性の高い暗号の一つとして幅広く標準的に利用されていました。 しかし、RSA Security 社 という前世紀までRSA暗号の権利を持っていた企業が、「長年使用され古くなってきた DES の安全性は既に破綻しており危険だ」ということをアメリカ政府に認知させるために開催した暗号解読コンテストで、見事に DES の暗号文が解読されてしまいました(※1)。 このような背景から、NIST はDESに代わってAES(エー・イー・エス)と呼ぶことにする新たな標準暗号の公募を行い、数年間の策定作業を経て 2000 年に Rijindael(ラインドール・リンデールなどと発音しますが、設計者はどう発音しても構わないようです)という暗号がこれに選ばれました(※2)

FEAL(フィール)は、我が国のNTTの宮口氏らが、現代暗号の草創期にDESを参考にして設計した暗号方式で、DESよりも高速に暗号化・復号の計算ができるのが利点の一つでした。 しかし、早い段階で現実的な解読方法が発見されてしまい、その後の FEAL-NX と呼ばれる方式等で改良されました。 同社は新たにE2(イー・ツー)という暗号方式を設計し、これをAESの公募に応募しましたものの最終候補の選定で落選しました。 これは、公募した NIST が「本来のE2ではなく、E2の設計が少し違ったものだったらどれくらい弱い暗号になるか」を考察した論文を本物のE2に対する評価だと勘違いしてしまったためだという興味深いエピソードが知られています。 その後、同社は三菱電機と協力して Camellia(キャメリア)という暗号を設計しています。

RC6(アール・シー・シックス)はRSA暗号でも有名な RSA Security 社(※5)の創業者で、RSA暗号のRとしても知られている Ron Rivest 博士が設計した暗号です。 それ以前にも同氏はRC5(※3)などの「RCシリーズ」と呼ばれる一連の RC○ という暗号を設計していますが、これらの中には既に 暗号学的に 解読されているものもあります(※4)。 RC6もAESの公募に応募され、下馬評では最有力候補の一つと言われて最終候補まで残ったものの、数年間の選定途中で Knudsen と Meier という研究者によって、「コリレーションアタック」と呼ぶ統計的手法による攻撃法が有効であることが発見されました。 最終候補までは残った暗号であり、重大な問題こそ見つかっていなかったものの、結局RC6がAESに選ばれることはなく、同社は2002年10月にRC6の普及活動自体を止めました。

IDEA(アイデア,イデア)は Massey と Lai というスイス人が設計した暗号で、独特の設計により解読の難しい暗号の一つとして知られています。 有効な攻撃法としては、Meier という人が発見した特定の鍵を使用した時に非常に簡単に解読が行なえるという "弱鍵(Weak Key)" による攻撃法くらいしか見付かっておらず、AESに応募されるのではとも噂されていましたが、結局されませんでした。 IDEAの権利を持つスイスの ASCOM Systec 社は既にこの暗号を業としており、AESの応募要件である権利放棄に抵抗があったのでしょうか。 かつては PGP という電子メールの暗号化システムに標準採用されていたため、インターネット社会でも比較的有名な暗号です。

この他、最近開発された国産の方式だけでも CIPHERUNICORN シリーズ(日本電気)、Hierocrypt シリーズ(東芝)、MISTY シリーズ(三菱電機)、SC2000(富士通)など数多くの暗号方式が存在しますが、これら従来の暗号方式は全て、鍵は 暗号化にも復号にも同一のもの を使用してきました。 つまり、送信者と受信者が同一の鍵 を周囲には秘密に共有しなければならないのです。 もちろんシーザー暗号でも同じで、送信者が「5文字 ずらす」と決めれば、受信者も「5文字 逆にずらす」必要があり、やはり鍵は同じ 5文字 を使用することになります。

このことは、相手へメッセージを秘密裏に伝えたいのなら、その前にまず暗号化に使うための 鍵を 周囲に秘密裏に相手に伝えなければならないことを表しています。 つまり、ある文を秘密に伝えたいなら、まず先に鍵を秘密に伝えなければならない のです。 これは本末転倒、「それでは、その鍵はどうやって伝えればいいんだ」という話になります。 しかしこの問題は2000年もの長い暗号の歴史上仕方ないこととされ、誰にも解決できませんでした。

※1 DESの暗号解読コンテスト

このコンテスト、実際に広く使われていたDESの暗号文が解読対象だったにも関わらず、初めて開かれた時には 7 万台のコンピュータを使う団体が 140日、二回目は世界中のコンピュータを使う distributed.net という団体が 約1ヶ月 で解読。 さらに次に開かれた時には、一千万円程度の機械を 一台 使った EFF という団体によってたった 2日半 で解読されてしまいました。

2 日半という時間に対する驚異以上に、世界中のコンピュータを使う形式ではなく、たった一台の専用マシン、しかも安価に作った団体だったことから世界も主催者も驚きました。 しかし、これこそ主催者の望んでいた結果だったのです。

その後、1999年1月18日に最後の DES Challenge III が行われ、ついに24時間を切る22時間15分で解読されてしまいました。 優勝者は、過去のコンテスト解読者(チーム)の distributed.net と EFF の合同チームでした。

※2 AES

コンピュータの高速化に伴って、設計当初は現実的な時間では解読不可能であったDESの技術がDES暗号解読コンテスト (※1) の結果などから噂通り破綻していることが明らかになりました。 このためアメリカ標準技術協会(NIST)は、AESと呼ぶことにする、DESに代わる新しい標準暗号アルゴリズムを一般に公募しました。 三度の候補絞り込みの結果、2000年に Rijindael という暗号に 決まりました。 DESは、国家とのつながりも深いIBMが設計を担当しており、S-Box(エスボックス)と呼ばれる「しくみ自体は公開されているが、なぜそんなしくみにしたか設計思想が明らかになっていない部分」に、国家が解読するためのフックが用意されているのでは?といった疑念を持たれたことを踏まえたのか、今回はアメリカ国外で設計されたものが選ばれたことが特徴です。 最終候補に残った暗号の多くは基本的には既存の攻撃に対して十分な安全性を持っていたようですが、その中でも Rijindael は無難な選択だったようです。 例えば、パソコン等の「ソフトウェア」として暗号化プログラムを作った時に、特定のコンピュータのみで高速に処理できたり、低速だったりすることなく、平均的にそこそこ速く処理できたことが評価されたとも言われています。

本節で紹介したすべての暗号は、RSA暗号とは暗号のしくみが根本的に異なる方式であるため、「サルにもわかるRSA暗号」ではこれ以上詳しくは触れませんが、これらの暗号もRSA暗号に負けず劣らず面白いエピソードがたくさんある面白い分野です。 筆者の本 ではこれらにも触れております。

※3 RC6

RSA Security 社は、自社の暗号を世界標準にしようとDES暗号解読コンテスト (※1) でDESの破綻を広く知らせ、アメリカ政府をDESに代わるAESの公募へと動かしました。 同社はRC5を改良したRC6をAESに応募しました。

かつて、アメリカ政府は暗号技術の輸出を厳しく制限していました。 簡単に言えば実用になる強い暗号(解読が難しい暗号)は輸出を禁じられ、 解読される恐れのある暗号だけが輸出を認められてきたのです。 当然 RSA Security 社を始めとするセキュリティベンダ各社は、この政策に反対の立場でした。 そこで同社はDESの解読コンテストに続き、今度は「強い暗号であっても、政府の許可する制限内では簡単に解読されてしまう」ことを広く知らせるため、輸出可能な弱い暗号にも、輸出不可能な強力な暗号にも調整できる柔軟なRC5を用いて、様々な強さ別の暗号文を出題し、解読させる「RC5解読コンテスト」も開催しました。

なお、このコンテストに使われている RC5がRSA暗号のことだと勘違い してる方が時々いらっしゃるようですが、これらは種類の全く異なる暗号方式です。

※4 「解読」に対する誤解

新聞などで「○○暗号が解読された」などという記事をみかけることがあります。 この「解読された」という表現、まるでその暗号がもう使い物にもならないかのような印象を与えるのですが、実際には「解読」と言っても様々な意味があり、実際にはすぐに危険というわけではない場合も多々あります。

簡単に紹介すると、まずは本当に危険な「解読」があります。 DESが解読されたというのは、これに該当します。 暗号文だけを元に、一千万円程度の機械で一日で解読できるのでは、解読したいと思った暗号文を自由に現実的な時間で解読できてしまいます。 すぐに不安だと言えるのは、こんな解読だけでしょう。

次に、一文を解読されただけの意味の解読です。 強さを調整したRC5という暗号は、解読コンテストで世界中のコンピュータを使い5〜6年で解読できる予定でした。しかし、たった一文に世界中のコンピュータを協調して5〜6年もかかるという事実は、逆にそこまでしないと解読できない証拠なのですから、このような場合は逆に本来は安心すべきくらいかもしれせん (追記:2002年夏、この出題が東京在住の匿名の日本人によって解読されました)。

最後に暗号学的な意味での解読です。 RC5はコンテストとは別に、暗号学的な解読もされています。 しかしその意味は、「解読者にとって都合の良い、非常に多くの暗号文とその平文を知っていれば、存在し得る全ての鍵を試すより(わずかにでも)早い時間で鍵を知ることができる」というものなのです。 現実にはそのような都合の良い情報をたくさん得ることは難しい場合が殆んどですし、「存在し得る全ての鍵を試すよりも早い時間」が現実的に意味のある時間でない事も多いのです。 したがって、これもすぐに不安になるべきものとは言えません。

※5 RSA Security 社

RSA Security 社は、情報セキュリティの標準規格の策定にも力を持つ企業の一つで、歴史的に国際標準化団体による標準化より先に同社の独自規格が業界標準になってしまう状況が多々ありました。 そんな RSA Security 社も、現在は EMC という IT 企業の傘下に入りました。

戻る
進む
ページ上部へ