Loading article…
暗号解読（ギリシャ語のkryptós「隠された」とanalýein「分析する」に由来）とは、情報システムを分析してシステムの隠された側面を理解するプロセスを指します。 [ 1 ]暗号解読は、暗号鍵が不明な場合でも、暗号化されたメッセージの内容にアクセスするために、暗号化されたセキュリティシステムを突破するために使用されます。
暗号解読には、暗号アルゴリズムの数学的解析に加えて、暗号アルゴリズム自体の脆弱性を標的とするのではなく、その実装上の脆弱性を悪用するサイドチャネル攻撃の研究も含まれる。
目標は同じでも、暗号解読の方法と技術は、暗号の歴史を通じて劇的に変化し、暗号の複雑さの増大に適応してきました。過去のペンと紙を使った方法から、第二次世界大戦中にブレッチリー・パークにあったイギリスのボンベやコロッサスといったコンピュータ、そして現代の数学的に高度なコンピュータ化された方式まで、その範囲は多岐にわたります。現代の暗号システムを破る方法は、多くの場合、純粋数学で綿密に構築された問題を解くことを含み、最もよく知られているのは整数因数分解です。
暗号化では、機密情報（「平文」と呼ばれる）は、送信者が暗号化アルゴリズムを使用してまず判読不能な形式（ 「暗号文」 ）に変換し、受信者に安全に送信されます。暗号文は安全でないチャネルを介して受信者に送信されます。受信者は逆復号アルゴリズムを適用して暗号文を復号し、平文を復元します。暗号文を復号するには、受信者は送信者からの秘密の知識、通常は暗号鍵と呼ばれる文字、数字、またはビット列を必要とします。この概念は、たとえ不正な人物が送信中に暗号文にアクセスできたとしても、秘密鍵がなければ平文に戻すことができないというものです。
暗号化は、歴史を通じて重要な軍事、外交、商業上のメッセージを送信するために用いられており、今日では電子メールやインターネット通信を保護するためにコンピュータネットワークで広く利用されている。
暗号解読の目的は、第三者である暗号解読者が、元の（ 「平文」 ）に関する情報をできるだけ多く入手し、暗号を「解読」して暗号文を読み取り、将来のメッセージを復号して読めるように秘密鍵を学ぶことです。[ 1 ]これを行うための数学的手法は、暗号攻撃と呼ばれます。暗号攻撃は、いくつかの方法で特徴づけることができます。
暗号解読攻撃は、攻撃者が利用できる情報の種類に基づいて分類できます。基本的な出発点として、分析の目的上、一般的なアルゴリズムが既知であると通常想定されます。これは、シャノンの格言「敵はシステムを知っている」[ 2 ]であり、これはケルクホフスの原理[ 3 ]に相当します。これは実際には妥当な想定です。歴史を通じて、秘密のアルゴリズムが、スパイ活動、裏切り、リバースエンジニアリングなどによって広く知られるようになった例は数え切れないほどあります。（また、純粋な演繹によって暗号が解読されたこともあります。たとえば、ドイツのローレンツ暗号や日本の紫暗号、さまざまな古典的な方式などです）[ 4 ]
攻撃は、必要とするリソースによっても特徴づけられる。それらのリソースには以下が含まれる。[ 5 ]
特に攻撃を実際に実装してテストすることが現実的でない場合、これらの量を正確に予測することは難しい場合があります。しかし、学術的な暗号解読者は、少なくとも攻撃の難易度の推定桁数を示す傾向があり、たとえば「SHA-1 衝突は現在 2 52です」と言います。[ 6 ]
ブルース・シュナイアーは、計算上非現実的な攻撃であっても、解読とみなされる可能性があると指摘している。「暗号を解読するということは、総当たり攻撃よりも少ない複雑さで悪用できる暗号の弱点を見つけることを意味する。総当たり攻撃には2¹²⁸回の暗号化が必要になるかもしれないが、 2¹¹⁰回の暗号化が必要な攻撃は解読とみなされるだろう…簡単に言えば、解読とは認証上の弱点、つまり暗号が宣伝どおりに機能しない証拠である可能性がある。」[ 7 ]
暗号解読の結果は、その有用性においてもばらつきがある。暗号学者のラース・クヌーセン（1998）は、発見された秘密情報の量と質に基づいて、ブロック暗号に対する様々な攻撃の種類を分類した。
学術的な攻撃は、ブロック暗号やハッシュ関数から一部のラウンドを削除したような、暗号システムの弱体化バージョンに対して行われることが多い。多くの攻撃は、暗号システムにラウンドが追加されるにつれて実行が指数関数的に難しくなるが、すべてではない[ 8 ]。そのため、ラウンド数を減らしたバージョンが弱くても、完全な暗号システムは強力である可能性がある。とはいえ、元の暗号システムを破る寸前までいく部分的な破りは、完全な破りにつながる可能性がある。DES 、MD5、SHA-1に対する攻撃の成功はすべて、弱体化バージョンに対する攻撃に先行していた。
学術的な暗号学では、暗号方式の弱点や破綻は通常、かなり保守的に定義されます。つまり、非現実的な量の時間、メモリ、または既知の平文が必要になる場合があります。また、攻撃者が現実世界の多くの攻撃者にはできないことを実行できる必要がある場合もあります。たとえば、攻撃者は暗号化する特定の平文を選択したり、秘密鍵に関連する複数の鍵を使用して平文を暗号化するように要求したりする必要があるかもしれません。さらに、暗号システムが不完全であることを証明するには十分ですが、現実世界の攻撃者にとって有用ではない、少量の情報しか明らかにしない場合もあります。最後に、攻撃は、完全なシステムを破るためのステップとして、ラウンド数を減らしたブロック暗号などの弱体化したバージョンの暗号ツールにのみ適用される場合があります。[ 7 ]
暗号解読は暗号技術と共に進化してきた。両者の競争は暗号技術の歴史を通して辿ることができる。古い欠陥のある暗号方式に代わる新しい暗号方式が設計され、改良された暗号方式を解読するための新しい暗号解読技術が発明されてきたのだ。実際には、これらは表裏一体の関係にある。つまり、安全な暗号方式を実現するには、暗号解読の可能性に対抗できる設計が必要となるのである。
「暗号解読」という言葉自体は比較的新しいものですが（1920年にウィリアム・フリードマンによって造語されました）、暗号や符号を解読する方法はそれよりもずっと古くから存在していました。デイビッド・カーンは著書『暗号解読者たち』の中で、アラブの学者たちが暗号解読の方法を体系的に記録した最初の人々であったと述べています。 [ 9 ]
暗号解読に関する最初の記録された説明は、9世紀のアラブの博学者アル・キンディ（801年頃～873年、ヨーロッパでは「アルキンドゥス」としても知られる） [ 10 ] [ 11 ]が『Risalah fi Istikhraj al-Mu'amma 』 （暗号メッセージの解読に関する手稿）の中で述べたものである。この論文には、頻度分析法の最初の記述が含まれている。[ 12 ]そのため、アル・キンディは歴史上最初の暗号解読者とみなされている。[ 13 ]彼の画期的な研究は、アル・ハリール（717年～786年）の影響を受けており、アル・ハリールは『暗号メッセージの書』を著した。この書には、母音の有無にかかわらず、可能なすべてのアラビア語の単語を列挙するために順列と組み合わせを初めて使用した記述が含まれている。[ 14 ]
頻度分析は、ほとんどの古典的な暗号を解読するための基本的なツールです。自然言語では、アルファベットの特定の文字が他の文字よりも頻繁に現れます。英語では、「E 」は平文のサンプルの中で最も頻繁に現れる文字である可能性が高いです。同様に、二重音字「TH」は英語で最も出現頻度の高い文字の組み合わせであり、以下同様です。頻度分析は、暗号がこれらの統計を隠蔽できないことに依存しています。たとえば、単純な置換暗号（各文字が単に別の文字に置き換えられる）では、暗号文で最も頻繁に現れる文字は「E」である可能性が高いです。したがって、暗号文が、含まれるアルファベットの文字を適切に代表する数を与えるのに十分な長さであれば、このような暗号の頻度分析は比較的容易です。[ 15 ]
アル・キンディーによる単表換字暗号を解読するための頻度分析技術の発明[ 16 ] [ 17 ]は、第二次世界大戦までで最も重要な暗号解読の進歩であった。アル・キンディーの『Risalah fi Istikhraj al-Mu'amma』は、多表換字暗号、暗号分類、アラビア語の音声学と構文など、最初の暗号解読技術について記述しており、最も重要なのは、頻度分析に関する最初の記述を与えたことである[ 18 ] 。彼はまた、暗号化の方法、特定の暗号化の暗号解読、アラビア語の文字と文字の組み合わせの統計分析についても取り上げた[ 19 ] [ 12 ] 。イブン・アドラン（1187-1268）の重要な貢献は、頻度分析を使用するためのサンプルサイズに関するものであった[ 14 ] 。
ヨーロッパでは、イタリアの学者ジャンバティスタ デッラ ポルタ(1535 ～ 1615 年) が、暗号解読に関する独創的な著作『 De Furtivis Literarum Notis』の著者でした。[ 20 ]
暗号解読の成功は、間違いなく歴史に影響を与えてきた。他人の秘密と思われた思考や計画を読み取る能力は、決定的な利点となり得る。例えば、1587年のイングランドでは、スコットランド女王メアリーが、イングランド女王エリザベス1世暗殺計画への関与を理由に反逆罪で裁判にかけられ、処刑された。これらの計画は、共謀者たちとの暗号化された書簡がトーマス・フェリペスによって解読されたことで明るみに出た。
15 世紀から 16 世紀にかけてのヨーロッパでは、フランスの外交官ブレーズ・ド・ヴィジュネル(1523–96)らによって多表式換字暗号の概念が開発されました。 [ 21 ]約 3 世紀にわたり、繰り返し鍵を使用して異なる暗号化アルファベットを順番に選択するヴィジュネル暗号は、完全に安全である ( le chiffre indéchiffrable —「解読不能な暗号」) と考えられていました。しかし、チャールズ・バベッジ(1791–1871) と、後に独立してフリードリヒ・カシスキ(1805–81) がこの暗号を解読することに成功しました。[ 22 ]第一次世界大戦中、いくつかの国の発明家は、ヴィジュネル暗号を解読するために利用された繰り返しを最小限に抑える試みとして、アーサー・シェルビウスのエニグマなどの回転式暗号機を開発しました。[ 23 ]
第一次世界大戦では、ツィンメルマン電報の解読がアメリカ合衆国の参戦に大きく貢献した。第二次世界大戦では、連合国はドイツの暗号（エニグマ暗号機やローレンツ暗号を含む）と日本の暗号（特に「パープル」とJN-25 ）の解読に共同で成功したことで大きな恩恵を受けた。「ウルトラ」諜報活動は、ヨーロッパでの戦争終結を最大2年早めたことから、最終的な結果を決定づけたことまで、あらゆることに寄与したとされている。太平洋戦争も同様に「マジック」諜報活動によって助けられた。[ 24 ]
敵のメッセージの暗号解読は、第二次世界大戦における連合国の勝利に重要な役割を果たした。FWウィンターボサムは、終戦時に西側連合国最高司令官ドワイト D. アイゼンハワーがウルトラ諜報活動が連合国の勝利に「決定的」であったと述べたことを引用している。[ 25 ]第二次世界大戦における英国諜報機関の公式歴史家であるハリー・ヒンズリー卿もウルトラについて同様の評価を下し、ウルトラによって戦争が「少なくとも2年、おそらく4年」短縮されたと述べ、さらにウルトラがなければ戦争がどのように終わったかは不明であるとも述べている。[ 26 ]
実際には、頻度分析は統計学と同様に言語学の知識に依存しているが、暗号が複雑になるにつれて、暗号解読において数学の重要性が増した。この変化は特に第二次世界大戦前と戦中に顕著であり、枢軸国の暗号を解読する努力には新たなレベルの数学的洗練が必要だった。さらに、自動化はポーランドのBomba装置、イギリスのBombe 、パンチカード装置の使用、そしてプログラムによって制御される最初の電子デジタルコンピュータであるColossusコンピュータによって、その時代に初めて暗号解読に適用された。[ 27 ] [ 28 ]
ローレンツ暗号や第二次世界大戦中にナチス・ドイツが使用したエニグマ暗号機のような相互暗号方式では、各メッセージに固有の鍵がありました。通常、送信側オペレーターは暗号化されたメッセージの前に平文や暗号文を送信することで、受信側オペレーターにこのメッセージ鍵を知らせました。これは、受信側オペレーターがメッセージを解読するために機械をどのように設定すればよいかを示すため、 「指示子」と呼ばれます。 [ 29 ]
設計と実装が不十分な指標システムにより、まずポーランドの暗号学者[ 30 ] 、次にブレッチリー・パークのイギリスの暗号学者[ 31 ]がエニグマ暗号システムを解読することができた。同様に不十分な指標システムにより、イギリスはローレンツSZ40/42暗号システムの診断につながる深さを特定し、暗号解読者が暗号機を見ることなくメッセージを完全に解読することができた[ 32 ] 。
同じ鍵で 2 つ以上のメッセージを送信することは安全でないプロセスです。暗号解読者にとって、そのようなメッセージは「深層」であると言われます。[ 33 ] [ 34 ]これは、送信オペレーターが受信オペレーターにメッセージの鍵生成器の初期設定を通知する同じインジケータをメッセージに持つことで検出できます。[ 35 ]
一般的に、暗号解読者は一連のメッセージ間で同一の暗号化操作を並べることで利益を得られる場合があります。たとえば、バーナム暗号は、平文と長い鍵を「排他的論理和」演算子（「モジュロ2加算」（⊕で表される）としても知られる）を使用してビット単位で組み合わせることで暗号化します。
復号化とは、同じ鍵ビットを暗号文と組み合わせて平文を復元することです。
（モジュロ2演算では、加算と減算は同じです。）このような2つの暗号文が深度的に整列している場合、それらを組み合わせることで共通の鍵が排除され、2つの平文の組み合わせだけが残ります。
個々の平文は、さまざまな箇所で可能性のある単語（またはフレーズ）、いわゆる「クリブ」を試すことによって言語的に解読できます。正しい推測が結合された平文ストリームと組み合わされると、もう一方の平文コンポーネントから理解可能なテキストが生成されます。
復元された2番目の平文の断片は、多くの場合、片方向または両方向に拡張でき、追加された文字を結合された平文の流れと組み合わせることで、最初の平文を拡張できます。解析者は、2つの平文の間を行き来しながら、推測を検証するために理解可能性基準を使用することで、元の平文の大部分またはすべてを復元できます。（深さ方向に2つの平文しかない場合、解析者はどちらがどちらの暗号文に対応しているか分からないかもしれませんが、実際にはこれは大きな問題ではありません。）復元された平文をその暗号文と組み合わせると、鍵が明らかになります。
鍵の知識があれば、アナリストは同じ鍵で暗号化された他のメッセージを読み取ることができ、関連する鍵のセットの知識があれば、暗号解読者はそれらの鍵を作成するために使用されたシステムを診断できる可能性がある。[ 32 ]
各国政府は、軍事および外交の両面における諜報活動において、暗号解読がもたらす潜在的な利点を長年認識しており、他国の暗号を解読することに特化した組織を設立してきた。例えば、GCHQやNSAなどが挙げられ、これらの組織は現在も活発に活動している。
第二次世界大戦中、ローレンツ暗号やその他のシステムの暗号解読において計算が大きな効果を発揮した一方で、これまで以上に桁違いに複雑な新しい暗号方式も可能になった。全体として見ると、現代の暗号は過去のペンと紙のシステムよりも暗号解読に対してはるかに耐性があり、今では純粋な暗号解読に対して優位に立っているように見える。歴史家のデイビッド・カーンは次のように述べている。 [ 36 ]
今日、何百もの商用ベンダーが提供する暗号システムの多くは、既知の暗号解読方法では解読できません。実際、そのようなシステムでは、選択された平文をその暗号文と照合する選択平文攻撃でさえ、他のメッセージを解読する鍵を得ることはできません。つまり、ある意味では、暗号解読は死んだと言えるでしょう。しかし、話はそこで終わりではありません。暗号解読は死んだかもしれませんが、比喩を混ぜて言えば、猫の皮を剥ぐ方法は一つではないのです。
カーン氏はさらに、傍受、盗聴、サイドチャネル攻撃、量子コンピュータが従来の暗号解読手段に取って代わる機会が増えていることに言及している。2010年、元NSA技術部長のブライアン・スノー氏は、学術界と政府の暗号学者はともに「成熟した分野で非常にゆっくりと前進している」と述べた。[ 37 ]
しかし、暗号解読の事後検証は時期尚早かもしれない。諜報機関が採用する暗号解読手法の有効性は不明のままだが、現代のコンピュータ暗号の時代には、学術的および実用的な暗号プリミティブに対する多くの深刻な攻撃が発表されている。[ 38 ]
したがって、最新の暗号はエニグマよりもはるかに暗号解読に強いかもしれないが、暗号解読と情報セキュリティのより広い分野は依然として非常に活発である。[ 39 ]
非対称暗号（または公開鍵暗号）は、2つの（数学的に関連する）鍵、すなわち秘密鍵と公開鍵を使用する暗号方式です。このような暗号は、その安全性の基盤として必ず「難しい」数学的問題に依存しているため、攻撃の明らかなポイントは、その問題を解決する方法を開発することです。2つの鍵を使用する暗号方式の安全性は、一般的に単一鍵を使用する暗号方式とは異なり、数学的な問題に依存しており、逆に暗号解読をより広範な数学研究と新しい形で結びつけています。[ 40 ]
非対称暗号方式は、さまざまな数学的問題を解くことの（想定される）難しさに基づいて設計されています。問題を解決するより優れたアルゴリズムが見つかれば、システムは弱体化します。たとえば、Diffie–Hellman 鍵交換方式の安全性は、離散対数を計算する難しさに依存しています。1983 年に、Don Coppersmith は（特定のグループで）離散対数を求めるより高速な方法を発見し、それによって暗号学者はより大きなグループ（または異なる種類のグループ）を使用する必要が生じました。RSAの安全性は（部分的に）整数因数分解の難しさに依存しており、因数分解のブレークスルーは RSA の安全性に影響を与えます。[ 41 ]
1980 年、難しい 50 桁の数を因数分解するには、10 12 回の基本的なコンピュータ操作が必要でした。1984 年までに、因数分解アルゴリズムの最先端技術は、75 桁の数を 10 12 回の操作で因数分解できるレベルにまで進歩しました。コンピュータ技術の進歩により、操作ははるかに高速に実行できるようになりました。ムーアの法則は、コンピュータの速度が今後も向上し続けると予測しています。因数分解技術も同様に向上し続ける可能性がありますが、おそらく数学的な洞察力と創造性に依存することになり、どちらもこれまで確実に予測できたことはありません。かつて RSA で使用されていたような 150 桁の数も因数分解されました。その労力は上記よりも大きかったものの、高速な現代のコンピュータでは不合理ではありませんでした。21 世紀初頭までに、150 桁の数はRSA の鍵のサイズとしては十分ではないとみなされるようになりました。 2005年時点では、数百桁の数字は素因数分解するにはまだ難しすぎると考えられていたが、今後、解読方法は改善され続け、それに追いつくためには鍵長を長くするか、楕円曲線暗号などの他の方法を用いる必要が出てくるだろう。
非対称暗号方式のもう1つの特徴は、対称暗号システムへの攻撃とは異なり、暗号解読において公開鍵から得られた知識を利用できる機会があることである。[ 42 ]
量子コンピュータはまだ研究の初期段階にあるが、暗号解読に利用できる可能性がある。例えば、ショアのアルゴリズムは多項式時間で大きな数を因数分解できるため、一般的に使用されている公開鍵暗号方式の一部を事実上破ることができる。[ 43 ]
量子コンピュータ上でグローバーのアルゴリズムを使用することで、総当たり鍵検索を2乗倍速くすることができる。しかし、鍵長を2倍にすることでこれに対抗できる可能性がある。[ 44 ]
アル・キンディは最初の暗号解読者と考えられている。