公開鍵暗号

すべての公開鍵暗号方式は、理論上「総当たり鍵探索攻撃」に対して脆弱である。^{[ 18 ]}しかし、クロード・シャノンが「ワークファクター」と呼んだ、成功するために必要な計算量がすべての潜在的な攻撃者の手の届かないものであれば、そのような攻撃は非現実的である。多くの場合、ワークファクターは単に長い鍵を選択することで増加させることができる。しかし、他のアルゴリズムは本質的にワークファクターがはるかに低い場合があり、総当たり攻撃（たとえば、長い鍵による）に対する耐性は無関係になる。いくつかの特別な特定のアルゴリズムは、一部の公開鍵暗号アルゴリズムを攻撃するのに役立つように開発されている。RSAとElGamal暗号の両方には、総当たりアプローチよりもはるかに高速な既知の攻撃が存在する。しかし、これらのどれも、実際に実用的であるほど十分に改善されていない。

かつて有望視されていたいくつかの非対称鍵アルゴリズムに重大な脆弱性が発見されました。「ナップサックパッキング」アルゴリズムは、新しい攻撃手法の開発後に安全でないことが判明しました。^{[ 19 ]}すべての暗号機能と同様に、公開鍵実装は、情報漏洩を利用して秘密鍵の検索を簡素化するサイドチャネル攻撃に対して脆弱である可能性があります。これらは、使用されているアルゴリズムとは無関係であることが多いです。新しい攻撃を発見し、それらから保護するための研究が進行中です。

非対称鍵を使用する際のもう1つの潜在的なセキュリティ脆弱性は、「中間者攻撃」の可能性です。これは、公開鍵の通信が第三者（「中間者」）によって傍受され、別の公開鍵を提供するように変更される攻撃です。疑念を避けるためには、暗号化されたメッセージと応答は、すべての場合において、異なる通信セグメントの正しい公開鍵を使用して攻撃者によって傍受、復号、再暗号化されなければなりません。^{[ 20 ]}

通信は、データが傍受（「スニッフィング」とも呼ばれる）を許容する形で送信される場合、安全ではないと言われます。これらの用語は、送信者のプライベートデータ全体を読み取ることを指します。傍受を送信者が防止または監視できない場合、通信は特に安全ではありません。^{[ 21 ]}

中間者攻撃は、現代のセキュリティプロトコルの複雑さゆえに実行が難しい場合があります。しかし、送信者が公共ネットワーク、インターネット、無線通信などの安全性の低い媒体を使用している場合は、攻撃は容易になります。このような場合、攻撃者はデータ自体ではなく、通信インフラを侵害することができます。インターネットサービスプロバイダ（ISP）の悪意のある従業員であれば、中間者攻撃は比較的容易に実行できるかもしれません。公開鍵を傍受するには、ISPの通信機器を介して送信される鍵を探すだけで済みます。適切に実装された非対称鍵暗号方式では、これは大きなリスクにはなりません。

高度な中間者攻撃では、通信の一方の側では元のデータが見えるのに、もう一方の側では悪意のある変異体が受信されます。非対称中間者攻撃では、ユーザーが接続が侵害されていることに気づけない場合があります。これは、一方のユーザーのデータが侵害されていることがわかっている場合でも、もう一方のユーザーにはデータが正常に見えるため、変わりません。これにより、どちらのユーザーにも非がない場合でも、「あなたの側の問題に違いない！」など、ユーザー間で混乱を招く意見の相違が生じる可能性があります。したがって、中間者攻撃は、通信インフラストラクチャが一方または両方の当事者によって物理的に制御されている場合（送信者の建物内の有線ルートなど）にのみ完全に防止できます。要約すると、送信者が使用する通信ハードウェアが攻撃者によって制御されている場合、公開鍵は変更されやすくなります。^{[ 22 ] [ 23 ] [ 24 ]}

こうした攻撃を防ぐための一つの方法として、公開鍵基盤（PKI）の利用が挙げられます。PKIとは、デジタル証明書の作成、管理、配布、使用、保存、失効、および公開鍵暗号の管理に必要な役割、ポリシー、手順の集合体です。しかし、これには潜在的な弱点があります。

例えば、証明書を発行する認証局は、鍵所有者の身元を適切に確認し、証明書発行時に公開鍵の正当性を保証し、コンピュータの不正コピーから保護され、保護された通信を開始する前にすべての参加者と各自の証明書を確認する取り決めを交わしているなど、すべての参加者から信頼されている必要があります。例えば、 Webブラウザには、PKIプロバイダーから提供される「自己署名ID証明書」の長いリストが用意されています。これらは、認証局の正当性を確認し、次に、通信を行う可能性のある相手の証明書を確認するために使用されます。これらの認証局のいずれかを悪用して偽の公開鍵の証明書を発行させることができた攻撃者は、証明書スキームが全く使用されていない場合と同様に、容易に「中間者攻撃」を仕掛けることができます。認証局のサーバーに侵入し、証明書と鍵（公開鍵と秘密鍵）の保管場所を入手した攻撃者は、通信の流れに割り込むことができれば、無制限に偽装、なりすまし、復号、トランザクションの偽造を行うことができるようになる。

理論的および潜在的な問題点があるにもかかわらず、公開鍵基盤は広く利用されている。例としては、TLSとその前身であるSSLがあり、これらはウェブブラウザのトランザクションのセキュリティを確保するために一般的に使用されている（例えば、ほとんどのウェブサイトはHTTPSにTLSを使用している）。

公開鍵システムを導入する際には、特定の鍵ペアの攻撃に対する耐性だけでなく、認証階層のセキュリティも考慮する必要があります。通常、サーバーコンピュータ上で動作する専用プログラムである認証局が、デジタル証明書を発行することで、特定の秘密鍵に割り当てられたIDを保証しています。公開鍵デジタル証明書は通常、数年間有効であるため、関連する秘密鍵はその期間中、安全に保管する必要があります。PKIサーバー階層の上位で証明書作成に使用された秘密鍵が侵害されたり、誤って漏洩したりすると、「中間者攻撃」が発生する可能性があり、下位の証明書はすべて完全に安全ではなくなります。

利用可能な公開鍵暗号ソフトウェアのほとんどは、送信者と受信者の身元、送信日時、件名、使用ソフトウェアなどを含むメタデータをメッセージヘッダーに隠蔽しません。むしろ、メッセージ本文のみが隠蔽され、意図した受信者の秘密鍵でのみ復号化できます。つまり、メッセージ本文自体が隠蔽されていても、第三者は通信ネットワークの参加者や議論されている内容について、かなり詳細なモデルを構築できてしまう可能性があるのです。

しかし、最近、送信者と受信者の身元を隠蔽し、第三者が利用できるメタデータを大幅に削減する暗号化ヘッダーを使用したメッセージングの実証が行われた。^{[ 25 ]} この概念は、個別に暗号化されたメタデータブロックと暗号化されたメッセージを含むオープンリポジトリに基づいている。意図された受信者のみがメタデータブロックを復号化でき、復号化することで、メッセージを識別してダウンロードし、復号化することができる。このようなメッセージングシステムは現在実験段階であり、まだ展開されていない。この方法を拡張すると、第三者には受信者が使用している受信トレイサーバーと送信および受信のタイムスタンプのみが明らかになる。サーバーは数千人のユーザーで共有される可能性があり、ソーシャルネットワークモデリングははるかに困難になる。

ウィリアム・スタンレー・ジェボンズは、 1874年の著書『科学の原理』の中で次のように書いています。^{[ 26 ]}

読者は、2つの数を掛け合わせると8,616,460,799 になる数を答えられるだろうか？^{[ 27 ]}私以外には誰も知ることはないと思う。^{[ 26 ]}

ここで彼は、一方向関数と暗号の関係について説明し、トラップドア関数を作成するために使用される因数分解問題について具体的に議論しました。1996 年 7 月、数学者のSolomon W. Golombは、「Jevons は公開鍵暗号の RSA アルゴリズムの重要な特徴を予見していたが、公開鍵暗号の概念を発明したわけではない」と述べました。^{[ 28 ]}

1970年、英国政府通信本部（GCHQ）の英国人暗号学者ジェームズ・H・エリスは、「非秘密暗号化」（現在では公開鍵暗号と呼ばれている）の可能性を思いついたが、それを実装する方法が見つからなかった。^{[ 29 ] [ 30 ] [ 31 ]}

1973年、同僚のクリフォード・コックスは、後にRSA暗号アルゴリズムとして知られるようになるものを実装し、「非秘密暗号化」の実用的な方法を提供しました。そして1974年、GCHQの別の数学者で暗号学者のマルコム・J・ウィリアムソンは、現在ディフィー・ヘルマン鍵交換として知られるものを開発しました。このスキームは、米国の国家安全保障局にも引き継がれました。^{[ 32 ]}どちらの組織も軍事に重点を置いており、いずれにしても利用できる計算能力は限られていました。公開鍵暗号の可能性は、どちらの組織にも実現されませんでした。ラルフ・ベンジャミンによれば、

私は軍事用途において最も重要だと判断しました...鍵を迅速かつ電子的に共有できれば、相手に対して大きな優位性を得られます。バーナーズ＝リーがCERN向けにオープンインターネットアーキテクチャを設計し、それがARPANETに適応・採用されてからの進化の終盤になって初めて、公開鍵暗号方式はその真の可能性を実現しました。^{[ 32 ]}

これらの発見は、1997年に英国政府によって研究が機密解除されるまで公には認められなかった。^{[ 33 ]}

1976年、ホイットフィールド・ディフィーとマーティン・ヘルマンは、ラルフ・マークルの公開鍵配布に関する研究に影響を受け、非対称鍵暗号システムを発表し、公開鍵合意の方法を開示した。有限体でのべき乗を用いるこの鍵交換方法は、ディフィー・ヘルマン鍵交換として知られるようになった。^{[ 34 ]}これは、事前の共有秘密鍵を使用せずに、認証された（ただし機密ではない）通信チャネル上で共有秘密鍵を確立するための、初めて公表された実用的な方法であった。マークルの「公開鍵合意技術」はマークルのパズルとして知られるようになり、1974年に考案され、1978年に発表された。このため、非対称暗号化は、暗号学自体は2000年以上前に遡るにもかかわらず、暗号学の中では比較的新しい分野となっている。^{[ 35 ]}

1977年、コックスの方式の一般化が、当時MITに在籍していたロン・リヴェスト、アディ・シャミア、レナード・アドレマンによってそれぞれ独立に考案された。後者の著者らは1978年にマーティン・ガードナーのサイエンティフィック・アメリカン誌のコラムでその研究を発表し、そのアルゴリズムは彼らの頭文字をとってRSAとして知られるようになった。^{[ 36 ]} RSAは、 2つの非常に大きな素数の積を法とするべき乗を用いて暗号化と復号を行い、公開鍵暗号と公開鍵デジタル署名の両方を実行する。その安全性は、大きな整数の因数分解の極めて困難な問題に関連しており、この問題に対する効率的な一般的な手法は知られていない。アルゴリズムの説明は、サイエンティフィック・アメリカン誌1977年8月号の「Mathematical Games」コラムに掲載された。^{[ 37 ]}

1970年代以降、ラビン署名、エルガマル暗号、DSA、ECCなど、数多くの多様な暗号化、デジタル署名、鍵合意、その他の技術が開発されてきた。

オープンな学術コミュニティや標準化コミュニティ内で開発されたアルゴリズムに加え、いくつかの国では、自国の管轄区域内で使用するための国家公開鍵暗号規格が開発されている。これらには、SM2およびSM9（中国）、GOST R 34.10-2012（ロシア）、EC-KCDSA（韓国）、DSTU 4145（ウクライナ）などがある。