公開鍵暗号

公開鍵（非対称）暗号は、数学的に関連付けられた鍵ペアを使用します。この鍵ペアは、暗号化または署名検証のための公開鍵と、復号または署名のための秘密鍵で構成されており、これにより、これまで会ったことのない当事者間でも安全な通信が可能になります。

Definition

公開鍵暗号とは、各当事者が鍵のペア（自由に共有できる公開鍵と秘密に保持される秘密鍵）を保持し、一方の鍵で実行された操作がもう一方の鍵で反転または検証される暗号の分野です。

Scope

この分野は、整数因数分解や離散対数問題などの計算困難性仮定にセキュリティが依存する鍵ペアに基づく暗号を扱います。これには、公開鍵暗号（RSA、ElGamal）、鍵確立（Diffie-Hellman）、楕円曲線暗号、デジタル署名が含まれます。これらのスキームが依拠するトラップドアおよび一方向構造、ならびに標準的なセキュリティ目標（意味的セキュリティ、偽造不可能性）について論じます。対称プリミティブ、および公開鍵を配布する証明書と信頼のインフラストラクチャ（システムおよびネットワークセキュリティでカバー）は除外されます。

Sub-topics

• Diffie-Hellman Key Exchange
• Digital Signatures
• Elliptic-Curve Cryptography
• RSA and Integer Factorization

Core questions

• 事前に秘密を共有することなく、2つの当事者が安全に通信するにはどうすればよいですか？
• どのような計算問題（因数分解、離散対数）が公開鍵スキームを破ることを困難にしていますか？
• トラップドア一方向関数とは何ですか、そしてそれはどのように公開鍵暗号化を可能にしますか？
• デジタル署名はどのようにして真正性と否認防止を提供しますか？
• なぜ公開鍵暗号は実際には対称暗号と組み合わせて使用されるのですか？

Key concepts

• 公開鍵と秘密鍵のペア
• トラップドア一方向関数
• 整数因数分解問題
• 離散対数問題
• RSA
• Diffie-Hellman鍵交換
• 楕円曲線暗号
• デジタル署名
• ハイブリッド暗号化

Key theories

トラップドア一方向関数

公開鍵暗号は、計算は容易だが秘密の「トラップドア」情報なしでは反転が困難な関数に依存しています。RSAのモジュラーべき乗は、モジュラスの因数分解を知っている人にとっては反転が容易です。

公開鍵のアイデアと鍵交換

DiffieとHellmanは、2つの当事者が一方向関数を使用して公開チャネル上で共有秘密に合意できることを示し、暗号鍵を公開鍵と秘密鍵に分割することを提案しました。これが公開鍵暗号の分野を立ち上げました。

困難性仮定

非対称セキュリティは条件付きです。スキームは、整数因数分解、RSA問題、有限体または楕円曲線群における離散対数などの基礎となる問題の計算不能性という仮定に対して安全であることが証明されています。

Clinical relevance

公開鍵暗号は、実質的にすべての安全なインターネット通信の基盤となっています。TLSはサーバー認証とセッション鍵の確立にこれを使用し、コード署名とソフトウェア更新はデジタル署名に依存し、安全な電子メール（PGP、S/MIME）とSSHは鍵ペアを使用し、認証局はIDを公開鍵に紐付けます。暗号通貨は、トランザクションを承認するために公開鍵署名を使用します。実際には、ハイブリッドスキームで高速な対称暗号と組み合わせて使用されます。

Evidence & guidelines

RSA、Diffie-Hellman、および楕円曲線変種（ECDH、ECDSA、EdDSA）は標準化されています（PKCS、NIST SP 800-56、FIPS 186）。NISTは、古典的なセキュリティのために、少なくとも2048ビットのRSA/DHまたは224ビットの楕円曲線を推奨しています。Shorのアルゴリズムが量子コンピューター上でこれらすべてを脅かすため、NISTはポスト量子代替案（別途カバー）を標準化しています。

History

公開鍵暗号は、1976年にDiffieとHellmanによって公に発表されました（そして、機密扱いの研究では、GCHQのEllis、Cocks、Williamsonによって独立して発表されました）。RSA暗号システムは1977年から1978年に続き、最初の実用的な公開鍵暗号化および署名スキームを提供しました。ElGamal（1985年）は離散対数に基づいて暗号化と署名を構築し、KoblitzとMillerは1985年に独立して楕円曲線暗号を提案し、より小さな鍵を可能にしました。

Key figures

• Whitfield Diffie
• Martin Hellman
• Ralph Merkle
• Ronald Rivest
• Adi Shamir
• Leonard Adleman

Seminal works

• diffie1976
• rivest1978
• katz2020

Frequently asked questions

なぜ公開鍵暗号はすべての暗号化に使用されないのですか？

公開鍵操作は対称鍵操作よりもはるかに遅く、暗号文のオーバーヘッドが増加します。実際のシステムでは、公開鍵暗号は当事者の認証と対称セッション鍵の合意にのみ使用され、その後、大量のデータは対称的に暗号化されます。これはハイブリッドアプローチです。

量子コンピューターは公開鍵暗号を破るのでしょうか？

Shorのアルゴリズムを実行する大規模な量子コンピューターは、効率的に因数分解と離散対数を計算することで、RSA、Diffie-Hellman、および楕円曲線暗号を破るでしょう。このため、他の困難な問題に基づくポスト量子スキームが標準化され、展開されています。