非対称鍵暗号

このレッスンでは、今日の多くの安全なネットワーク通信の基盤を成す非対称鍵暗号について学びます。

レッスンを終えると、次の内容を理解できるようになります：

• 非対称鍵暗号とは何か
• 鍵交換やデジタル署名を含む、非対称鍵暗号の利用方法
• 非対称鍵暗号全般のセキュリティ
• RSA、DSA、楕円曲線アルゴリズムとそのセキュリティの詳細
• アルゴリズムの実際の動作を示すPythonコード例
• 古典コンピューターおよび量子コンピューターからこれらのアルゴリズムへの脅威

非対称鍵暗号入門

前回のレッスンで学んだように、対称鍵暗号は情報保護において非常に高速かつ効率的ですが、いくつかの限界があります：

1. 安全な情報交換を希望する当事者の数が増えるにつれて、必要な鍵の数は組み合わせ爆発的に増大します。送信者と受信者の間でこれらの鍵を安全に配布するメカニズムは提供されていません。
2. 否認防止の仕組みがありません。いかなる当事者もメッセージを復号または暗号化でき、メッセージが受信されたこと、あるいはその発信元を保証する方法がありません。

これら両方の問題の解決策が、非対称鍵暗号（AKC）、別名公開鍵暗号（PKC）によって提供されており、それゆえに現代のデジタルセキュリティの礎となっています。

非対称鍵暗号（AKC）では、公開鍵と秘密鍵の一対の鍵を使用します。公開鍵と秘密鍵は暗号学的に連携しており、通常は特殊な数学的アルゴリズムを使って同時に鍵ペアとして生成されます。公開鍵はその名が示す通り自由に配布されることを意図している一方、秘密鍵は鍵ペアを生成した当事者によって秘密に保たれます。非対称鍵ペアを使った通信のセキュリティは、秘密鍵が機密に保たれている限り保証されます。

図1. 非対称鍵暗号化

AKCは以下のような有用な機能を提供します：

1. 暗号化と復号 による通信の機密性の確保。
2. デジタル署名 による真正性、完全性、否認防止の保証。
3. 安全な鍵交換 による対称暗号システムの後続利用の促進。

現代のアプリケーションでは、AKCは主にデジタル署名と安全な鍵交換に使用されます。このレッスンでは、これら二つの主要な機能を紹介し、それらの機能に対するいくつかの暗号プロトコルのバリエーションについて説明します。

非対称鍵暗号による鍵交換

暗号学における基本的な問題の一つが、鍵を安全に交換することです。たとえば、二者が対称暗号を使いたい場合、両者がメッセージを暗号化・復号するために同じ鍵を必要とします。しかし、その鍵をどうやって安全に交換するのでしょうか？非対称鍵暗号は、インタラクティブおよび非インタラクティブな鍵交換メカニズムによってこの問題に対処します。

インタラクティブな鍵交換

インタラクティブな鍵交換プロトコルとは、安全でない通信チャネルを通じて二者が協力して共有秘密鍵を作成する方法を指します。この共有秘密鍵はその後、対称暗号化と復号の作業に使用できます。

このようなプロトコルの中で最もよく知られているのが、鍵交換を促進するために特別に考案されたDiffie-Hellmanアルゴリズム（DH）です。このプロトコルでは、各当事者が鍵ペア（公開鍵と秘密鍵）を生成し、公開鍵を公開します。次に各当事者は、自分の秘密鍵と相手の公開鍵を使って共有秘密鍵を生成します。DHは剰余算の原理を用いることで、互いに相手の公開鍵にしかアクセスできない状況でも両者が同じ共有秘密にたどり着けるようにしています。

楕円曲線暗号（ECC）に基づく現代の暗号システムは、楕円曲線Diffie-Hellman（ECDH）鍵交換によってこの概念を拡張しています。ECDHはDHと同様に機能しますが、楕円曲線の性質を利用することで、より安全かつ効率的なシステムを実現しています。

図2. 鍵交換プロトコル

非インタラクティブな鍵交換

DHやECDHのような鍵交換プロトコルは対話的であり、対称鍵を決めるために双方向の通信を必要とします。それとは異なり、AKCは共有秘密鍵を確立するための非インタラクティブな方法も提供しています。このような方式では、一方の当事者が鍵ペア（公開鍵と秘密鍵）を生成し、もう一方の当事者と公開鍵を共有します。この第二の当事者はランダムな対称鍵を生成し、受け取った公開鍵で暗号化して第一の当事者に送り返します。第一の当事者は秘密鍵を使って受け取ったメッセージを復号し、共有対称鍵を取得します。この方式は、対称鍵が一方の当事者によって決定され、暗号化された形で安全にもう一方に通知されるという意味で非インタラクティブです。

非インタラクティブな鍵交換における重要な考慮事項として、交換したい対称鍵のビット長とAKCで推奨されるメッセージサイズの差異があります。通常、現代の対称鍵は128〜256ビット程度ですが、RSAなどの非対称鍵暗号システムは1024〜4096ビット程度のメッセージサイズで動作します。そのため、AKCを使って対称鍵を送信する場合でも、セキュリティ上の理由から1024〜4096ビットの長いメッセージにエンコードする必要があります。これには二つのアプローチで対応できます：

• パディングベースの鍵交換： このアプローチでは、まず短い（128〜256ビットの）対称鍵を生成し、次にOAEPなどの合意済みの可逆パディング方式を使って長い（1024〜4096ビットの）メッセージに埋め込みます。この長いメッセージはAKCで暗号化され、暗号文として送信されます。受信者はまず暗号文を復号し、次にパディングを除去して短い対称鍵を取り出します。

• 鍵カプセル化メカニズム（KEM）： KEM ベースの鍵交換では、まずランダムな長い（1024〜4096ビットの）平文メッセージを生成し、そこから合意済みの鍵導出関数（KDF）を使って短い（128〜256ビットの）対称鍵を導出します。長い平文はAKCで暗号化され、暗号文として受信者に送信されます。受信者は秘密鍵を使って暗号文をデコードし、KDFを使って短い（128〜256ビットの）対称鍵を導出します。RSAのような一般的な暗号システムは、データを直接暗号化できる能力を持つことからKEMの実装に使用できます。

図3. 鍵カプセル化メカニズム

非対称鍵暗号によるデジタル署名

デジタル署名は非対称鍵暗号のもう一つの強力な応用です。AKCにおいて各エンティティが固有の秘密鍵を持つという事実を活かし、認証、完全性、否認防止を実現します。署名プロトコルの基本的な考え方は、安全なメッセージの送信者が固有の秘密鍵を使ってメッセージにデジタル署名を付加するというものです。受信者は送信者の公開鍵を使ってデジタル署名を検証します。AKCにおけるデジタル署名は、専用に設計されたアルゴリズムを使用するか、汎用暗号システムを使って実装できます。

図4. 非対称鍵暗号によるデジタル署名

専用デジタル署名アルゴリズム

現在、デジタル署名に関する米国連邦情報処理標準（FIPS）は、単にデジタル署名アルゴリズム（DSA）と呼ばれる専用方式です。Diffie-Hellmanプロトコルとある程度類似した形で、DSAは署名の生成と検証に剰余指数演算と乗法逆元の代数的性質を活用します。

楕円曲線デジタル署名アルゴリズム（ECDSA）はDSAのECCバリアントであり、同じ機能を提供しながら鍵長が大幅に短くなっています。これにより効率が向上し、リソース制約のあるシステムでの人気の選択肢となっています。

DSAとECDSAの両方については、後でより詳しく説明します。

汎用暗号システムを使ったデジタル署名方式

専用アルゴリズムに加えて、デジタル署名はRSAのような汎用非対称暗号システムを使っても生成できます。

RSAについては後のセクションで詳しく説明しますが、これも剰余乗法逆元と剰余指数演算を基本演算として活用しますが、DSAとは異なる順序でそれらを組み合わせています。RSAでは、署名者が通常メッセージのハッシュを作成し、そのハッシュを秘密鍵で暗号化してデジタル署名を生成します。どの当事者も署名者の公開鍵でその署名を復号し、ハッシュ化されたメッセージと比較することで署名を検証できます。

非対称鍵暗号の応用

非対称鍵暗号は現代のデジタル技術アプリケーションに遍在しています。上述のAKCの基本機能は、以下を含む多くの上位アプリケーションプロトコルの構成要素となっています：

1. インターネット通信： HTTPSなどのインターネット上の安全な通信は、非対称鍵暗号に大きく依存しています。トランスポート層セキュリティ（TLS）およびその前身であるセキュアソケットレイヤー（SSL）は、初期ハンドシェイクプロセスで非対称鍵暗号を使って対称鍵を確立し、その後の通信セッションで使用します。

2. 認証： 非対称鍵暗号はデジタル署名の作成に使用され、エンティティが特定の送信者からのデジタル文書やメッセージを認証できるようにします。ソフトウェアアップデートの検証から法的拘束力のあるデジタル契約まで、多くの場面で使用されています。

3. メール暗号化： PGP（Pretty Good Privacy）やそのオープンソース代替であるGPG（GNU Privacy Guard）などのメール暗号化プロトコルは、意図した受信者だけがメール内容を読めるよう非対称鍵暗号を使用します。

4. セキュアシェル（SSH）： SSHは、安全でないネットワーク上でのリモートログインやその他の安全なネットワークサービスのためのプロトコルです。非対称鍵暗号を使ってサーバーをクライアントに対して認証し、オプションでクライアントをサーバーに対して認証します。

5. VPN（仮想プライベートネットワーク）： 非対称鍵暗号はVPNにおける安全な接続の確立に使用され、パブリックネットワーク上での安全な通信を保証します。

6. ブロックチェーンと暗号通貨： BitcoinやEthereumを含むブロックチェーン技術は非対称鍵暗号を使用しています。たとえば、Bitcoinの所有権は非対称鍵暗号を使ったデジタル署名によって確立されます。

7. 認証局： 非対称鍵暗号は認証局（CA）がデジタル証明書を発行・署名するために使用され、TLS通信、コード署名、メール暗号化などで利用されます。デジタル証明書は公開鍵を特定のエンティティ（たとえば個人やサーバー）に結びつけます。

図5. 非対称鍵暗号を使ったデジタル証明書の発行と署名

非対称鍵暗号のセキュリティ

安全な非対称鍵暗号を実現するためには、いくつかの暗号学的概念が組み合わさっています：

秘密鍵の秘匿性： AKCの最も基本的なセキュリティ要件は、秘密鍵が秘密に保たれることです。しかし、秘密鍵は公開鍵と数学的に連携していなければならないため、秘密鍵の秘匿性には、公開鍵の知識から秘密鍵を導出することが計算上実現不可能であることも求められます。AKC内の鍵生成方式はこの要件を満たすために、計算上困難な数学的問題に依拠しています。

トラップドア機能： AKCでは、暗号化と復号の操作に単一鍵ペアの異なる補完的な鍵が関与します。一方の鍵（たとえば公開鍵）を使った暗号化で生成された暗号文は、第三者には解読不能でありながら、補完的な鍵（この場合は秘密鍵）の保持者には容易に復号できなければなりません。言い換えれば、暗号化はトラップドア一方向関数に似た動作をすべきであり、第三者は操作を逆転させて平文を取り出せない一方、秘密鍵が容易な逆転を可能にする秘密のトラップドアを提供します。一般的なAKCアルゴリズムは剰余指数演算を使ってトラップドア一方向関数の動作を実現しています。

ランダム性： 鍵生成プロセスはランダム性も活用し、鍵が予測不能であることを保証する必要があります。鍵生成にパターンや予測可能性があれば、攻撃者に悪用される可能性があります。ランダム性は暗号化時のパディングにも使われ、意味論的に安全な暗号文を生成します。また、デジタル署名方式において同じメッセージが複数回署名される場合でも固有の署名を生成するために使われます。そのため、強力な乱数生成器の使用はAKCの重要な部分です。

大きな鍵サイズ： SKCの場合と同様に、大きな鍵サイズはブルートフォース攻撃への保護を確保します。ただし、大きな鍵サイズは暗号化・復号プロセスの計算コストも増加させるため、最適な解決策はセキュリティと効率性のバランスを取る必要があります。以下の表は、さまざまな非対称鍵暗号プロトコルとアプリケーションの一般的な鍵サイズを示しています：

プロトコル	一般的な鍵サイズ（ビット）	アプリケーション
RSA	1024（非推奨）、2048、3072、4096	暗号化、デジタル署名
DSA	1024（非推奨）、2048、3072	デジタル署名
DH	2048、3072、4096	鍵交換
ECDH	224、256、384、521	鍵交換
ECDSA	224、256、384、521	デジタル署名

公開鍵基盤： AKCでは、秘密鍵は所有者が秘密に保ち、公開鍵はユーザー間で共有される必要があります。これらの公開鍵をユーザー間で管理・配布する安全なメカニズムが必要です。公開鍵基盤（PKI）はデジタル証明書を使ってこれを実現する方法を提供します。デジタル証明書は公開鍵の所有者のアイデンティティの証明を提供し、PKIの一部である認証局などの信頼できる機関によって発行されます。したがって、PKIはデジタル証明書の作成、管理、配布、失効によって大規模な鍵管理を可能にすることで、AKCを使用した現代のアプリケーションのセキュリティに不可欠な役割を果たしています。

非対称鍵暗号へのセキュリティリスク

上述の表に示されているように、RSAなどの現代の非対称鍵アルゴリズムは、AES-128などの一般的に使用される対称鍵の対応物よりも通常はるかに大きな鍵サイズを採用しています。ECCベースのプロトコル（ECDHとECDSA）は鍵サイズが小さいものの、最低でも224ビットの鍵を使用します。これは、正しい鍵を特定するために秘密鍵空間を網羅的に探索するブルートフォース攻撃が、近い将来においても計算上実現不可能であることを意味します。これは量子コンピューターがこの作業に使用された場合でも同様です。そのため、AKCに対する攻撃は通常、特定の暗号システムの他の潜在的な弱点を悪用することに焦点を当てています。よく知られた攻撃モードには次のものがあります：

1. アルゴリズムの弱点 ― 高度な数学的・計算的手段を使って、非対称鍵アルゴリズムの定式化に使われる困難性仮定を弱体化させる方法。たとえば、RSAのセキュリティは大きな素数の因数分解の困難さに基づいており、最近の計算の進歩により829ビットのRSA鍵の因数分解に成功した例があります。そのため、1024ビットのRSAは現在非推奨となっています。後述するように、量子コンピューターがAKCに与える主なリスクもこのカテゴリに該当します。

2. 不完全なランダム性 ― 鍵生成プロセスに弱点をもたらす可能性があります。たとえば、鍵の生成に使用される乱数生成器に欠陥があり、真にランダムではない鍵が生成された場合、攻撃者がその鍵を予測できるかもしれません。

3. 実装上の欠陥 ― 暗号アルゴリズムの実装における誤りが、鍵に関する情報を意図せず露出させることがあります。たとえば、不正確なパディングが鍵の詳細を明らかにする可能性があります。

4. サイドチャネル ― 暗号処理を実行する物理システムからの情報漏洩を指します。このような漏洩は、タイミング情報、消費電力、あるいは音の形を取ることがあり、いわゆるサイドチャネル攻撃に悪用される可能性があります。たとえば、暗号操作の実行時間を分析することで、バイナリ鍵の「1」の数を把握できる可能性があります。一見無害なこの情報漏洩は探索空間を大幅に狭め、当初は解決不可能に見えた問題への潜在的な解答を明らかにします。

5. 鍵交換 ― 中間者攻撃（MITM）などの手法で、交換中の鍵を傍受する方法。DHプロトコルは、追加の認証ステップが組み込まれていない場合、MITM攻撃に対して脆弱です。

6. 鍵の保管 ― セキュリティが不十分な保管場所から鍵を盗む方法。保管デバイスの操作や盗難などの物理的な攻撃も含まれます。

非対称鍵暗号システムをこれらの多様な攻撃から保護することは、数学的、ハードウェア、ソフトウェア、物流、および法律上の考慮事項を伴う重要な作業です。

RSA

RSA（Rivest-Shamir-Adleman）アルゴリズムは、最初の公開鍵暗号システムの一つであり、安全なデータ伝送に広く使用されています。これは暗号化、復号、デジタル署名、鍵交換を共通のフレームワーク内で実現するための必要な操作を提供する汎用性の高い暗号システムです。

このセクションでは、簡単な例を通じてRSAを使った非対称鍵暗号（AKC）を説明します。

AKCを使って安全に通信したい二者、アリスとボブという標準的なシナリオを使用します。

RSAアルゴリズム

基本的なRSAアルゴリズムは、鍵生成、鍵配布、暗号化、復号の4つの操作から成ります：

1. 鍵生成：

   公開鍵と秘密鍵は素数に関する数学的原理に基づいて生成されます。計算は容易ですが、逆は困難です。

   これらを以下のように呼びます：

   • 公開鍵: $(e, n)$
   • 秘密鍵: $(d, n)$

   $n$ は公開鍵と秘密鍵の両方に共通であり、法（モジュラス）と呼ばれます。これは後で使用します。

数学的詳細

• 二つの異なる素数 $p$ と $q$ を選びます。
  • セキュリティのためにランダムに選びます。
  • 因数分解を難しくするため、大きさは似ていても桁数がいくつか異なる方が良いです。
  • 素数は素数性テストを使って効率的に選択できます。
• $n = p*q$ を計算します。
  • $n$ は公開鍵と秘密鍵の両方の法です。
• トーシェント $φ$$(n) = (p-1)*(q-1)$ を計算します。
  • トーシェントは秘密に保たれ、鍵生成後は通常破棄されます。
• $1 < e <$$φ$$(n)$ かつ $gcd$$(e,$$φ$$(n)) = 1$ を満たす整数 $e$ を選びます。
  • つまり、$e$ と $φ$$(n)$ は互いに素であるべきです。
  • この数 $e$ は公開鍵の指数を形成し、計算効率のために通常小さな数として選ばれます。
  • 素数 $65537 = 2^{16} + 1$ がよく使用されます。
  • 合同関係 $d*e ≡ 1 ($$mod$$φ$$(n))$ を満たす $d$ を計算します。
    • つまり、$d$ は $φ$$(n)$ を法とする $e$ の乗法逆元です。
    • これは拡張ユークリッドアルゴリズムを使ってより効率的に計算できます。
    • この数 $d$ は秘密鍵の指数です。
• 公開鍵は $(e, n)$ で構成され、秘密鍵は $(d, n)$ です。

2. 鍵配布：

   • 公開鍵 $(e, n)$ はメッセージを送りたい人に公開されます。
   • 秘密鍵 $(d, n)$ は秘密に保たれます。

3. 暗号化：

   • アリスはボブにメッセージ $M$ を送りたいと思っています。この場合、単純な整数です。
   • アリスはボブの公開鍵 $(e, n)$ を使ってメッセージを暗号文 $C$ に暗号化します。
   数学的詳細

   • $M$ は整数 $0 ≤ M < n$ です。
   • $C ≡ M^e (mod n)$、ここで $C$ は暗号文です。

4. 復号：

   • ボブは暗号文 $C$ を受け取ります。
   • ボブは秘密鍵 $(d, n)$ を使ってメッセージをメッセージ $M$ に復号します。
   数学的詳細

   • $M ≡ C^d (mod n)$。

これがRSAの基本的な概要です。実際には、同じ平文が異なる暗号文を生成するように、暗号化前に平文 $M$ により高度なパディング方式が適用されます。これにより、RSAの素朴な実装に対するさまざまな攻撃を防ぎ、意味論的安全性が実現されます。

PythonによるRSAの例示

以下のコードセルでは、小さな整数を使ったRSAアルゴリズムの簡単な例を示し、その後RSAを実装するPythonライブラリを使った実用的な鍵配布とデジタル署名の応用例を示します。

備考

注意：このセクションでは、Pythonコードの一部として数学的計算の詳細を示します。

RSA鍵生成

小さな素数を使ったRSAアルゴリズムの簡単な例を順に見ていきましょう。

二つの整数が互いに素かどうかをテストするために必要となる、二つの整数の最大公約数を計算できる必要があります。

これを計算する簡単な方法を一つ説明しますが、大きな整数ではPythonの math.gcd 関数を使う方がはるかに効率的です。

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

import math

# Example function to compute the gcd (greatest common divisor)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# let's calculate some examples using algorithm
n1 = gcd(50, 10)
n2 = gcd(99, 33)
n3 = gcd(59, 9)

# do the same with the python library call

m1 = math.gcd(50, 10)
m2 = math.gcd(99, 33)
m3 = math.gcd(59, 9)

# Confirm they are the same
assert n1 == m1
assert n2 == m2
assert n3 == m3

# They are - print out the values for explanation
print("gcd(50,10) =", m1)
print("gcd(99,33) =", m2)
print("gcd(59,9) =", m3)

RSAワークフローの最初のフェーズは鍵生成です。これは、鍵を生成するエンティティが秘密に保つべき二つの素数を選ぶことから始まります。

# Choosing two prime numbers and keep them secret
p = 13
q = 19
print("The secret prime numbers p and q are:", p, q)

次に、選んだ二つの素数の積である法 $n$ を計算します。この法は公開鍵の一部として公開されます。

# Calculate n which is the modulus for both the public and private keys
n = p * q
print("modulus n (p*q)=", n)

次に、RSAにおける鍵の決定に使用される剰余乗法逆元演算に必要なオイラーのトーシェント関数 $\varphi(n)$ を計算します。$phi$ も秘密に保たれ、鍵生成後は通常破棄されます。

# Compute Euler's totient function, φ(n) and keep it secret
phi = (p - 1) * (q - 1)
print("The secret Euler's function (totient) [phi(n)]:", phi)

公開鍵と秘密鍵を計算する準備が整いました。RSAでは、それぞれ二つの整数のタプルで指定されます。各タプルの最初の要素は異なる整数であり、二番目の要素は両方の鍵に共通の法 $n$ です。

公開鍵の最初の要素は、$phi$ と互いに素であれば1より大きい任意の整数で構いません。二つの整数の最大公約数が1の場合、それらは互いに素です。そこで math.gcd 関数を使って $phi$ と互いに素な整数 $e$ を見つけます。

# Choose an integer e such that e and φ(n) are coprime
e = 2
while e < phi:
    if math.gcd(e, phi) == 1:
        break
    else:
        e += 1
print("Public Key (e):", e)

秘密鍵には整数 $d$ が必要です。これは $phi$ を法とする $e$ の乗法逆元、すなわち合同関係 $d*e\equiv 1 \pmod{\varphi(n)}$ を満たします。小さな整数を扱うこの簡単な例では、正の整数を順に調べて適切な $d$ を見つけることができます。実際の設定では、計算効率の高い拡張ユークリッドアルゴリズムがこの目的に使用されます。

# Compute a value for d such that (d * e) % φ(n) = 1
d = 1
while True:
    if (d * e) % phi == 1:
        break
    else:
        d += 1
print("Private Key (d):", d)

ここで公開鍵と秘密鍵をそれぞれ形成するタプル $(e, n)$、$(d, n)$ を作成します。公開鍵はその後公開され、秘密鍵は秘密に保たれます。

# Public and Private Key pair
public = (e, n)
private = (d, n)

print(f"The Public key is {public} and Private Key is {private}")

RSAの暗号化と復号化には、べき剰余演算が使用されます。また、公開鍵と秘密鍵は補完的な関係にあり、どちらか一方で暗号化したメッセージをもう一方で復号化できます。

ここでは、公開鍵 $(e,n)$ を暗号化に使用し、秘密鍵 $(d, n)$ を復号化に使用するケースを、それぞれの処理に対応するPython関数を定義することで説明します。

その後、整数メッセージ $msg$ を暗号化・復号化します。

# Encryption function
def encrypt(plain_text):
    return (plain_text**e) % n

# Decryption function
def decrypt(cipher_text):
    return (cipher_text**d) % n

# Simple message to encode
msg = 9

# encrypt then decrypt
enc_msg = encrypt(msg)
dec_msg = decrypt(enc_msg)

print("Original Message:", msg)
print("Encrypted Message:", enc_msg)
print("Decrypted Message:", dec_msg)

上記では理解しやすくするために小さな整数を使用しましたが、実際のアプリケーションではRSAは非常に大きな整数を必要とします。例えば、2048ビットRSAでは2048ビット長の法 $n$ を使用しており、その10進数での値は約10$^{616}$にもなります。このような非常に大きな数がRSAの実用的なセキュリティを確保するために不可欠です。

RSAによる対称鍵の交換

前述のように、AKCは通信を希望する二者が安全に共有秘密を確立することを可能にします。この共有秘密は、例えばその後の平文の大量暗号化に使用する対称暗号の秘密鍵として利用できます。

以下のシナリオを考えてみましょう。AliceとBobはSKCを使用してメッセージを暗号化・復号化したいと思っています。しかし、この処理を開始する前に、共通の秘密鍵を決める必要があります。一つの方法は、どちらかの当事者——例えばAlice——が秘密鍵を生成し、それをBobに安全に送信することです。この安全な転送を実現するために、AliceはRSAを鍵カプセル化メカニズム（KEM）として使用することにします。

この処理は以下のステップで構成されます：

• まず、AliceはBobと共有する予定のランダムな対称鍵を生成します。
• 次に、Bobは非対称鍵ペアを生成し、自身の公開鍵を適切なチャンネルで公開します。
• 続いて、AliceはBobの公開鍵を使用して対称鍵を暗号化し、暗号文としてカプセル化します。
• その後、Aliceは信頼性はあるが必ずしも安全ではないチャンネルで暗号文をブロードキャストします。
• 最後に、Bobは暗号文を受け取り、自身の秘密鍵を使って復号化します。これにより、BobはAliceが生成した対称鍵にアクセスできるようになります。

図1. RSAによる対称鍵の交換

PythonによるパディングベースのRSA鍵交換の例

RSAを利用したパディングベースの非対話型鍵交換の実用的なワークフローを、cryptography Pythonライブラリを使って説明します。

まず、cryptography Pythonライブラリから必要なモジュールをインポートします。必要に応じて、pip install cryptography コマンドでこのライブラリをインストールできます。

その後、AliceはBobに送信する予定のランダムな秘密鍵を生成します。

# pip install cryptography
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.fernet import Fernet
from cryptography.hazmat.primitives import hashes

symmetric_key = Fernet.generate_key()
print(f"\nSymmetric key generated by Alice: {symmetric_key}")

cryptography ライブラリの rsa モジュールを使用して、Bobは鍵ペアを生成し、自身の公開鍵をブロードキャストします。誰でもこの公開鍵を傍受して、鍵を構成する公開数値 $(e,n)$ を読み取ることができます。

# Bob generates a 2048-bit RSA key pair
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()
print(f"Public key broadcast by Bob: {bob_public_key}")
print(f"\nPublic numbers in Bobs' public key: {bob_public_key.public_numbers()}")

この時点で、AliceはBobがブロードキャストした公開鍵を受け取ったと仮定します。AliceはBobの公開鍵を使って symmetric_key を暗号化し、暗号文を生成できます。実際の設定では、AliceはBobとの通信の意味論的安全性を確保するために、OAEP などの追加のパディング手法も使用します。

# Encryption
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Ciphertext:", ciphertext)

Aliceはオープンチャンネルで暗号文をブロードキャストします。対応する秘密鍵を持つBobのみが復号化できると確信しています。Bobは暗号文を受け取り、自身の機密秘密鍵を使って復号化できます。

# Bob decrypts ciphertext to access the symmetric key
decrypted_symmetric_key = bob_private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted key:", decrypted_symmetric_key)
assert decrypted_symmetric_key == symmetric_key

この時点で、AliceとBobは両方とも秘密対称鍵にアクセスできるようになり、SKCアプリケーションに活用できます。

PythonでRSAを用いた鍵カプセル化メカニズムのシミュレーション

以下のワークフローでは、RSAを使用した鍵カプセル化メカニズム（KEM）のシミュレーションを説明します。このシミュレーションでは、十分に長いランダムな秘密メッセージを安全に交換し、その後KDFを使用して適切な長さの共有秘密に変換します。

再びAliceとBobは非対話型で共有秘密を確立したいと考えており、使用する秘密を決定するのはAliceです。

まず、必要なPythonライブラリをインポートします。

その後、BobはRSA鍵ペアを生成し、自身の公開鍵をブロードキャストします。

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from os import urandom

# Bob's RSA key pair
private_key_Bob = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key_Bob = private_key_Bob.public_key()

print("Bob's private and public keys created")

Aliceはまず、最終的に共有秘密が導出される長いランダムな秘密を生成します。純粋なKEMでは、この長い秘密は暗号システムの基礎となる代数構造からのランダムな要素になります。2048ビットRSAの場合、これは2048ビットのRSA法を法とするランダムな整数になります。純粋なKEMは追加のパディングを必要としませんが、この例ではRSAを使ったKEMのシミュレーションを行っており、cryptography ライブラリではRSAで暗号化する際にパディングの使用が必要です。そのため、標準的な256ビットAES鍵よりも十分に長い、やや短めの長い秘密を使用します。

Alice_long_secret = urandom(160)  # A 160 byte or 1280 bit random message
print("Alice's secret created")

次に、AliceはBobの公開鍵を使って長い秘密を暗号化し、暗号化された秘密をBobに送信します。

Alice_encrypted_secret = public_key_Bob.encrypt(
    Alice_long_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
print("Alice's secret encrypted")

Bobは自身の秘密鍵を使って、Aliceから受け取った暗号化された秘密を復号化します。

Bob_decrypted_secret = private_key_Bob.decrypt(
    Alice_encrypted_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

assert Alice_long_secret == Bob_decrypted_secret, "Secrets do not match!"

# if we get here they match
print("Secrets match")

最後に、AliceとBobはそれぞれ、事前に合意した鍵導出関数（KDF）を長い秘密に適用して、対称鍵を導出します。

なお、このプロセスにはハッシュプロトコルとランダムなソルトの使用が含まれており、長い秘密が再利用された場合（非推奨）でも共有対称鍵の一意性と予測不可能性を確保します。ただし、ソルト自体は秘密である必要はなく、例えばこの例ではAliceがランダムに生成したソルトを、暗号化された長い秘密と並行してBobにブロードキャストできます。

したがって、AliceとBobの両方が同じランダムなソルトにアクセスできると仮定します。

def key_derivation_function(secret, salt):
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=32,  # Desired key length
        salt=salt,
        info=None,
        backend=None,
    )
    return hkdf.derive(secret)

common_salt = urandom(16)  # Random salt accessible to both Alice and Bob

symmetric_key_Alice = key_derivation_function(Alice_long_secret, common_salt)
symmetric_key_Bob = key_derivation_function(Bob_decrypted_secret, common_salt)

assert symmetric_key_Alice == symmetric_key_Bob, "Derived keys do not match!"
print(
    f"A symmetric key of length {len(symmetric_key_Alice)*8} bits was successfully derived by both Alice and Bob!"
)

RSAによるデジタル署名

ここでは、AliceとBobの機密通信シナリオを拡張し、デジタル署名を用いた検証も含めた形に発展させます。

前述と同様に、Aliceは対称鍵をカプセル化したメッセージをBobに機密で送信しますが、さらにメッセージにデジタル署名も付与します。これにより、Bobはメッセージを受け取った際に、それがAliceから送られたものであること、また送信中にメッセージの内容が改ざんされていないことを確認できます。

より一般的には、機密性を損なうことなく検証を可能にすることが望ましい状況があります。この場合、実際の平文メッセージにアクセスできない当事者でも、特定の通信に関する完全性と真正性を確認し、否認防止を確立できます。

この一般的な設定では、以下のステップが含まれます：

• まず、BobとAliceの両方がオープンチャンネルで自身の公開鍵を公開します。
• 次に、AliceはBobの公開鍵を使って平文を暗号化し、暗号文を作成します。
• 続いて、Aliceはハッシュ関数を使って暗号文のハッシュを作成し、さらに自身の秘密鍵を使ってそのハッシュ化された暗号文を暗号化します。この暗号化されたハッシュが署名です。
• その後、AliceはオープンチャンネルでAliceが暗号文と署名の両方を送信します。
• 次に、BobはAliceの公開鍵を使って署名を復号化し、ハッシュ化された暗号文を取得します。
• さらに、Bobは暗号文自体にもアクセスできるため、Aliceが使用したものと同じハッシュ関数を使ってハッシュ化された暗号文の2番目のインスタンスを再作成します。後者がAliceの署名を復号化して得られたものと一致すれば、暗号文自体はまだ復号化されていなくても、メッセージが検証されたことになります。
• 最後に、Bobはメッセージを検証したうえで、自身の秘密鍵を使って暗号文を復号化します。

図2. RSAによるデジタル署名

このデジタル署名のワークフローを次に説明します。

再び、cryptography ライブラリから有用なモジュールをインポートします。前述と同様に、Aliceは対称鍵をBobに安全に送信したいと考えていますが、デジタル署名も付与したいと考えています。この場合、AliceとBobの両方の公開鍵が必要です。したがって、最初のステップとして、AliceとBobの両方がRSAを使って独自の鍵ペアを作成し、各自の公開鍵を公開します。

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed

# Generate keys for Bob
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()

# Generate keys for Alice
alice_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
alice_public_key = alice_private_key.public_key()

print("Private and Public keys generated for Bob and Alice.")

次のステップでは、前述と同様に、AliceはBobの公開鍵を使って対称鍵を暗号化し、暗号文を準備します。

# Alice encrypts the message using Bob's public key
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("ciphertext of symmetric key: ", ciphertext)

この段階で、Aliceは単に暗号文をブロードキャストするのではなく、自分がメッセージの送信者であることをBobに証明できるよう、デジタル署名を付与しようとしています。これは2つのステップで行われます：

1. ハッシュアルゴリズムを使って暗号文のハッシュを作成します。
2. Aliceの秘密鍵を使ってハッシュを暗号化します。これが署名となります。

# Alice signs the ciphertext using her private key
digest = hashes.Hash(hashes.SHA256())
digest.update(ciphertext)
hash_to_sign = digest.finalize()

signature = alice_private_key.sign(
    hash_to_sign,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    Prehashed(hashes.SHA256()),
)

print("signature: ", signature)

Aliceはネットワーク上で暗号文と署名の両方をブロードキャストし、Bobが両方を受け取れるようにします。

# Bob receives the ciphertext and signature
received_ciphertext = ciphertext
received_signature = signature

# Send signature and ciphertext here
print("Sending ciphertext and signature.....")

Bob側では、最初のタスクは受け取った暗号文の完全性と真正性を検証することです。これを行うために、BobはAliceが使用したものと同じハッシュアルゴリズムを使って受け取った暗号文のハッシュを作成します。

# Bob creates a hash of the ciphertext using the same algorithm used by Alice
digest = hashes.Hash(hashes.SHA256())
digest.update(received_ciphertext)
hash_to_verify = digest.finalize()

print("hash to verify: ", hash_to_verify)

次に、BobはAliceの公開鍵を使って受け取った署名を復号化します。AliceはAliceの秘密鍵を使って署名を作成したため、BobはAliceの公開鍵を使って復号化することができます。復号化された署名はAlice側で作成された暗号文のハッシュそのものです。Bobが作成したハッシュが復号化された署名と一致すれば、Bobは受け取った暗号文が改ざんされていないこと、そして暗号文に署名したのがAliceであることを確認できます。

以下のPythonコードでは、これらの処理がAliceの公開鍵に関連付けられたオブジェクトが提供する便利なユーティリティ関数 verify にまとめられています。

from cryptography.exceptions import InvalidSignature

def is_signature_valid(public_key, signature, data_hash):
    try:
        public_key.verify(
            signature,
            data_hash,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH
            ),
            Prehashed(hashes.SHA256()),
        )
        return True
    except InvalidSignature:
        return False

if is_signature_valid(alice_public_key, received_signature, hash_to_verify):
    print("The signature is valid.")
else:
    print("The signature is not valid.")

受け取った暗号文の完全性と真正性を検証したBobは、AliceがBobの公開鍵を使って暗号文を作成したため、自身の秘密鍵を使って復号化することができます。

# Bob decrypts the message using his private key
decrypted_message = bob_private_key.decrypt(
    received_ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted message:", decrypted_message.decode())

上記のデジタル署名シナリオでは、Bobだけでなく誰もがAliceが暗号文の送信者であることを確認できます。なぜなら、誰でもAliceの公開鍵、暗号文、デジタル署名にアクセスできるからです。さらに、暗号文と署名を送信した後、Aliceは後になってそれを否認することができません。なぜなら、署名はAliceの公開鍵のみを使って意味のあるハッシュに復号化できるからです。これにより否認防止が確立されます。

安全な鍵配布の実現と否認防止のサポートにより、公開鍵暗号は安全なデジタル通信のための強固な基盤を築いています。

RSAの解読

上述したRSAアルゴリズムの有用性とセキュリティは、2つの数学的仮定に基づいています：

1. $(e, n)$ のみへのアクセスが与えられた場合に、剰余乗法逆数 $d$ を求めることは計算上不可能です。

2. RSAの設定では、べき剰余演算は一方向トラップドア関数のように振る舞います。暗号化に使用した場合、解読不能な暗号文を生成し、秘密鍵へのアクセスなしに平文を暗号文から復元することは不可能です。しかし、トラップドアとして機能する秘密鍵へのアクセスがあれば、暗号文を容易に復号化できます。

RSAアルゴリズムに対する最も著名な攻撃は、法 $n$ を素因数分解することで秘密鍵番号 $d$ を効率的に復元し、仮定1を崩すことを目的としています。以下に示すように、素因数 $p$ と $q$、あるいはトーシェント $φ$$(n)$ のいずれかにアクセスできれば、$d$ を容易に復元できます。鍵生成時に $p$、$q$、および $φ$$(n)$ は秘密として保持され、その後破棄されることを思い出してください。古典コンピューターや量子コンピューターを使ってこれらの情報を復元した第三者は、事実上秘密鍵を解明することになり、RSAを破ることができます。したがって、素因数分解こそがRSAを破るために必要な重要な計算プリミティブです。

古典コンピューターとRSA

大きな整数の素因数分解は、古典コンピューター上では超多項式または準指数関数的スケーリングを示すことが知られています。$10^{100}$より大きな整数を因数分解するための最もよく知られた古典アルゴリズムは、一般数体ふるい法(GNFS)です。

数学的詳細

$L_n[\frac{1}{3}, (\frac{64}{9})^{(\frac{1}{3})}] = e^{[((\frac{64}{9})^{(\frac{1}{3})} + o(1)) (log(n))^{\frac{1}{3}}(log(log(n))^{\frac{2}{3}})]}$

これは、因数分解する整数 $n$ の関数として表されます。

このスケーリングは、$n$ を表すのに必要なビット数に対して超多項式的です。

したがって、素因数分解は古典コンピューター上では非効率とみなされます。

現在のところ、古典ハードウェアで因数分解された最大の整数は829ビット（10進数で250桁）の範囲にあります。過去数十年で目撃された古典コンピューティング性能の指数関数的な成長を踏まえると、1024ビットRSAは近い将来において安全とはみなされなくなり、現在は非推奨となっています。しかし、予見可能な将来において、$10^{617}$の範囲の大きさを持つ2048ビット整数の因数分解は、現在の古典システムでは実行不可能と考えられており、引き続き有効性があることを示唆しています。しかし、量子コンピューターの登場によって、この評価は覆されます。

ショアの量子アルゴリズムとRSA

今日おそらく最もよく知られた量子アルゴリズムは、整数の素因数を見つけるためのショアのアルゴリズムです。1994年にピーター・ショアが発表した際、これは素因数分解という実用上非常に重要な問題において、古典アルゴリズムに対して超多項式的な高速化をもたらした最初の量子アルゴリズムとして認識されました。

ショアのアルゴリズムは、$n$ がビット数であるとき、$O(n^2)$ で素因数分解を行うことができます。

ショアのアルゴリズムの数学的説明

RSAの文脈では、ショアのアルゴリズムは、べき剰余関数 $f(x) = a^x (mod~n)$ の周期性を利用し、法 $n$ の効率的な素因数分解を可能にする量子周期探索プリミティブを提供します。

RSAを破るためのショアの全体的な手順を簡略化して示すと、次のようになります。

1. 公開鍵の一部として公開されている法 $n$ が与えられたとき、$n$ と互いに素な数 $a$ を選びます。すなわち、$gcd(a,n) = 1$ とします。$n = p*q$ が正確に2つの素因数 $(p, q)$ を持つことがわかっているため、$n$ より小さいほぼどの数をランダムに選んでも、$n$ と互いに素になる可能性が高いです。

2. $a$ を選んだ後、$a^r \equiv 1 (mod~n)$ となる指数 $r$ を見つけます。これは $a^r - 1 \equiv 0 (mod~n)$ を意味します。上記の合同式が成り立つような指数 $r$ の存在は、べき剰余の周期性によって保証されています。

3. $r$ が偶数であれば、$a^r - 1 \equiv 0 (mod~n) \implies (a^{r/2} - 1) (a^{r/2} + 1) = \gamma*n$ となる整数 $\gamma$ が存在します。この後者の等式の左辺には、右辺が $p$ と $q$ を素因数として含むため、$p$ と $q$ も素因数として含まれなければなりません。$r$ が奇数の場合は、ステップ1に戻り、$a$ の別の値を試します。

4. $gcd((a^{r/2} - 1), n)$ または $gcd((a^{r/2} + 1), n)$ を求めるために拡張ユークリッドアルゴリズムを使います。計算されたGCDは、素因数 $p$ または $q$ の一方を特定する可能性が非常に高いです。$n$ をその素因数で割ることで、もう一方の素因数を求めます。

5. $p, q$ がわかったら、元のRSAアルゴリズムの手順を使って、オイラーのトーシェント関数 $\phi(n)$ を再構築し、既知の公開鍵数値 $e$ のモジュラー逆元として秘密鍵数値 $d$ を生成します。

2023年8月、オデッド・レゲフは多次元アプローチを用いたショアの原型に対する改良を発表し、$O(n^{1.5})$ を実現しました。ラガヴァンとヴァイクンタナタンらによる、時間・コスト・必要な量子ビット数を改善する可能性のある研究が続いています。実際のRSA暗号に対してこのようなアルゴリズムを実行することがいつ現実的になるかは断言できませんが、そのときは着実に近づいています。

RSA暗号解読を示すPythonの例

以下のコードセルでは、公開鍵だけを使って秘密鍵を見つける例を示します。ここでは古典的なブルートフォース計算を使いますが、大きな鍵を含めてショアのアルゴリズムがどのように使えるかを示しています。

備考

このセクションでは、Pythonコードの中で数学的な計算を詳細に示します。

この例では、公開鍵 $(5, 247)$ が与えられており、秘密鍵を復元します。

ステップ1: 最初のステップは、247と互いに素な数を選ぶことです。ほぼどの数でも使えます。ここでは6を選びます。

n = 247  # the modulus
e = 5  # public key number
a = 6  # an integer coprime to n
assert gcd(a, n) == 1
print(f"Checked {n} and {a} are coprime")

ステップ2: 次に、$6^r \equiv 1 (mod~247)$ となる周期 $r$ を見つける必要があります。この例では、ブルートフォースを使って古典的に $r$ を計算しますが、Qiskitを使って量子コンピューター上でショアのアルゴリズムを用いることもできます。

r = 0
rem = 100
while rem != 1:
    r += 1
    rem = (a**r) % n

print(f"period r is: {r}")
assert a**r % n == 1

print(f"Checked {a}^{r} mod {n} is 1")

ステップ3: 周期 $r = 36$ が偶数なので、$f1 = (a^{r/2}-1), f2=(a^{r/2}+1)$ を計算できます。

# explicitly use as integer
f1 = int(a ** (r / 2) - 1)
f2 = int(a ** (r / 2) + 1)

print(f"f1 = {f1}")
print(f"f2 = {f2}")

ステップ4: それらの因数のいずれかと $n$ のGCDを求めます。すでに見つかった素因数で $n$ を割るだけで、2番目の素因数が得られます。

q_found = gcd(f1, n)
print(f"One possible prime factor of n ({n}) is: {q_found}")

# explicit int (to avoid floating point)
p_found = int(n / q_found)
print(f"The second prime factor of n ({n}) is: {p_found}")

assert n == p_found * q_found

ステップ5: $n = 247$ の素因数が $p_{found}=13$ と $q_{found}=19$ であることがわかったので、トーシェント関数 $\phi_{found} = (p_{found}-1)*(q_{found}-1)$ を計算します。

秘密鍵は、公開鍵数値 $e=5$ のモジュラー逆元です。

# Compute the totient
phi_found = (p_found - 1) * (q_found - 1)
print(f"The totient is: {phi_found}")

# Recover the private key number d_found by satisfying (d_found * e) % phi_found = 1
d_found = 1
while True:
    if (d_found * e) % phi_found == 1:
        break
    else:
        d_found += 1
print("Private Key number:", d_found)

上記の手順において、ステップ2は重要な周期探索操作であり、ショアのアルゴリズムではこのために量子フーリエ変換と量子位相推定という2つの基本的な量子プリミティブを使用します。ショアのアルゴリズムの量子的側面の詳しい説明については、量子アルゴリズムの基礎の「位相推定と因数分解」のレッスンを参照してください。ステップ1およびステップ3〜5は、古典コンピューターで容易に実行できる比較的コストの低い操作です。

オプションとして、ショアのアルゴリズムの実装に関する詳細なビジュアルウォークスルーもあります。

量子コンピューター上では、ショアのアルゴリズムは法 $n$ に関して $O((log~n)^2 (log~log~n))$ という有利な多対数スケーリング、または $n$ を表すのに必要なビット数に関して多項式スケーリングを示すことができます。これは古典的なGNFSアルゴリズムと比べて超多項式的な高速化です。

最近のリソース推定によれば、ハードウェア構成に関する一定の仮定のもと、ショアのアルゴリズムを使って2048ビットRSAを破るには、数万から数百万の量子ビットが必要になるとされています。数万の量子ビットを持つ量子コンピューターが今後数年で利用可能になることは十分考えられ、リソース推定の下限が手の届く範囲になってきます。

Diffie-Hellman鍵交換とデジタル署名アルゴリズム

前のセクションでは、素因数分解の計算困難性に基づいてセキュリティが成り立つRSA暗号システムについて説明しました。ここでは、2つの一般的な非対称鍵暗号プロトコルであるDiffie-Hellman鍵交換（DH）とデジタル署名アルゴリズム（DSA）について説明します。これらはどちらも、離散対数問題（DLP）という異なる数学的問題に基づいています。

離散対数問題

次の方程式では、$e$、$M$、$c$ のみが与えられたとき、$a$ を求める必要があります。

$a^e$ $mod$ $M = c$

これは剰余算術を使用しているため、古典コンピューターでは困難であると信じられており、暗号アルゴリズムの良い数学的基盤となっています。

これは離散対数問題（DLP）として知られています。

離散対数問題の数学的詳細

DLPは通常、巡回群の文脈で定式化され、次のように述べられます。

生成元 $g \in G$ によって生成される巡回群 $G$ を考え、任意の元 $h \in G$ が与えられたとき、$h = g^{k}$ となる整数 $k$ を求めなさい。

ここで整数 $k \equiv log_{g}h$ が離散対数です。$G$ の巡回性により、すべての $h$ に対して有効な整数 $k$ が存在することが保証されています。

暗号学では、素数 $p$ を法とする整数の乗法群 $(\mathbb{Z}_p)^{\times}$ 上のDLPが有用です。$(\mathbb{Z}_p)^{\times}$ の元は、$p$ と互いに素な整数 $p$ を法とする合同類でラベル付けされています。

例えば：

$(\mathbb{Z}_5)^{\times} = \{[1],[2],[3],[4]\}~\mathrm{and}~(\mathbb{Z}_7)^{\times} = \{[1],[2],[3],[4],[5],[6]\}$

これらの群における乗算 $(\times)$ の演算は、単純に通常の整数乗算に $p$ による剰余還元を加えたものであり、整数 $k$ による冪乗は $k$ 回の乗算と $p$ による剰余還元の繰り返しです。

$(\mathbb{Z}_7)^{\times}$ 上のDLPの例を示しましょう。

この乗法群には2つの生成元 ${[3],[5]}$（原始根とも呼ばれます）があります。生成元として $[5]$ を使います。すなわち、5の連続した整数冪を使って $(\mathbb{Z}_7)^{\times}$ のすべての元を生成します。

#Generate elements of (Z_7)^{x} using generator [5].
g = 5
p = 7
print(f"Using generator {g}")
for k in range(3*p):
    print(f"{g}**{k} mod {p} ≡ {(g**k)%7}")

法7の算術では、5を連続した整数冪に上げることで、周期 $p-1 =6$ でサイクルが無限に繰り返される前に、$(\mathbb{Z}_7)^{\times}$ のすべての元がちょうど一度現れることがわかります。

したがって、生成元 $[5]$ を持つ $(\mathbb{Z}_7)^{\times}$ 上のDLPは次のようになります。

$\mathrm{Given}~h \in (\mathbb{Z}_7)^{\times} \mathrm{, find~} k \mathrm{~such~that~} 5^{k} \equiv h~(mod~7)$.

上記のPythonセルの出力から次のことがわかります。

$h = 2 \implies k=4 \mathrm{~or~} 4 = log_5(2) (mod~7)$

$h = 6 \implies k=3 \mathrm{~or~} 3 = log_5(6) (mod~7)$

通常の実数算術では、冪乗は単調関数であり、任意の底に対する任意の数の対数を求めることは計算上容易です。一方、上の単純な $(\mathbb{Z}_7)^{\times}$ の例から明らかなように、べき剰余は非単調であり、周期 $p-1$ で周期的ではあるものの、それ以外の点では非常に複雑です。したがって、その逆関数である離散対数を計算することは、古典コンピューター上では大きな $p$ に対して非効率になります。

この観察は、次のセクションで説明するDiffie-Hellman（DH）鍵交換とデジタル署名アルゴリズム（DSA）の両方の基礎となっています。

DLPは次のように巡回部分群に拡張できます。

• 上で定義した $(\mathbb{Z}_p)^{\times}$ と、素数位数 $r$ を持つ元 $g \in (\mathbb{Z}_p)^{\times}$、つまり $g^r \equiv 1 (~mod~p)$ を考えます。
• $g$ の整数冪の集合：$\{g^k~(mod~p) | 1 \le k \le r\} = \langle g \rangle$ は、群位数 $r$ を持つ $(\mathbb{Z}_p)^{\times}$ の巡回部分群です。
• $h \in \langle g \rangle$ を選び、$g^a~(mod~p) = h$ となる $1 \le a \le r$ を求めることで、$\langle g \rangle$ 上のDLPを指定できます。

Diffie-Hellman鍵交換

1976年、ウィットフィールド・ディフィーとマーティン・ヘルマンは、安全でない通信チャネル上で共有秘密鍵を生成するための鍵交換プロトコルを提案しました。この秘密鍵は、それを共有する当事者間での対称暗号化に使用できます。このアルゴリズムはDLPに依存しています。

図1. Diffie-Hellman鍵交換

Diffie-Hellman鍵交換の数学的詳細

アリスとボブを通信する2つの当事者として、プロトコルは次のように動作します。

• まず、アリスとボブは大きな素数 $p$ と原始根（生成元）$a$ に同意します。
• 次に、アリスは $1 \le k_A \le p-2$ の範囲でランダムに秘密指数 $k_A$ を選び、$h_A = a^{k_A}~(mod~p)$ を計算します。$k_A$ はアリスの秘密鍵、$h_A$ は公開鍵です。
• 続いて、ボブは $1 \le k_B \le p-2$ の範囲でランダムに秘密指数 $k_B$ を選び、$h_B = a^{k_B}~(mod~p)$ を計算します。$k_B$ はボブの秘密鍵、$h_B$ は公開鍵です。
• 次に、アリスはボブに $h_A$ を送り、ボブはアリスに $h_B$ を、信頼できるが必ずしも安全でないチャネルを通じて送ります。
• その後、アリスは受け取った $h_B$ を使って共有秘密鍵 $\kappa = h_B^{k_A}~(mod~p)$ を計算します。
• 最後に、ボブは受け取った $h_A$ を使って共有秘密鍵 $\kappa = h_A^{k_B}~(mod~p)$ を計算します。

このプロトコルにより、

• アリスとボブは必ず同じ秘密鍵 $\kappa$ を得ます。なぜなら $h_B^{k_A}~(mod~p) = (a^{k_B})^{k_A}~(mod~p) = a^{k_A k_B}~(mod~p) = (a^{k_A})^{k_B}~(mod~p) = h_A^{k_B}~(mod~p)$ だからです。
• $h_A$ や $h_B$ を傍受した第三者は、$k_B$ や $k_A$ にアクセスできないため、秘密鍵 $\kappa$ を構築することができません。
• 公開情報 $a$、$p$、$h_A$、$h_B$ を使って $k_A$ や $k_B$ を抽出することは、$(\mathbb{Z}_p)^{\times}$ 上のDLPを解くことと等価であるため、計算上困難です。

PythonでのDiffie-Hellmanプロトコルの例

小さな素数を使った簡単なDHプロトコルのPythonの例を見てみましょう。

備考

このセクションでは、Pythonコードの中で数学的な計算を詳細に示します。

ステップ1: アリスとボブは素数 $p$ と原始根 $a$ に同意します。$p=11, a=7$ を選びましょう。

# Step 1: Choose a prime `p` and a primitive root `a`
p = 11
a = 7

print(f"prime: {p}")
print(f"primitive root: {a}")

ステップ2、3: アリスは秘密指数 $k_A$ を選び、$h_A = a^{k_A}~(mod~p)$ を計算します。同様に、ボブは秘密指数 $k_B$ を選び、$h_B = a^{k_B}~(mod~p)$ を計算します。

k_A = 4  # Alice's private key
h_A = (a ** (k_A)) % p  # Alice's public key

print(f"Alice's private key is {k_A} and public key is {h_A}")

k_B = 8  # Bob's private key
h_B = (a ** (k_B)) % p  # Bob's public key

print(f"Bob's private key is {k_B} and public key is {h_B}")

ステップ4: 双方は自身の公開鍵 $h_A$ と $h_B$ をブロードキャストします。

ステップ5、6: 各当事者は自身の秘密鍵と相手の公開鍵を組み合わせて、共有秘密鍵を作成します。

secret_key_alice = h_B**k_A % p
secret_key_bob = h_A**k_B % p
assert secret_key_alice == secret_key_bob
print(f"The shared secret key is: {secret_key_bob}")

アリスとボブはこの共有秘密鍵を対称暗号化に使用できるようになります。

Diffie-Hellman鍵交換のセキュリティ

上述のように、DHのセキュリティは大きな素数 $p$ を使ったDLPを解くことの計算困難性に基づいています。典型的なアプリケーションでは、NISTはDH鍵交換に対して2048ビットまたは3072ビットの素数整数を推奨しており、これは古典コンピューターによるDLP解読の試みに対して十分に安全とみなされています。

中間者（MITM）攻撃: DHは共有秘密が一方の当事者の秘密鍵と他方の当事者の公開鍵を組み合わせることに依存するインタラクティブな方式であるため、いわゆる中間者（MITM）攻撃に対して脆弱です。

DHセキュリティとMITM攻撃の数学的詳細

このシナリオでは、第三者（例えばイブ）が送信中の公開鍵 $h_A, h_B$ を傍受し、それぞれ $h_A$ と $h_B$ の代わりに自身の公開鍵 $h_E$ を、ボブとアリスそれぞれに転送する前に差し替えます。

その結果、アリスは共有秘密を作成するために $h_B$ の代わりに $h_E$ を使うことになり、ボブの公開鍵を使っていると思い込みます。同様に、ボブも共有秘密を作成するために $h_A$ の代わりに $h_E$ を使い、アリスの公開鍵を使っていると思い込みます。

$h_E$ がアリス（ボブ）の共有秘密を作成するために使われたため、アリス（ボブ）が暗号化した平文はイブによって復号できます。

したがって、DH鍵交換は通常、各当事者が認証された公開鍵を使って共有秘密を作成することを保証するために、デジタル署名アルゴリズムと組み合わせて使用されます。

デジタル署名アルゴリズム（DSA）

RSAのような汎用暗号システムはデジタル署名機能を提供しますが、1994年にNISTは、べき剰余と離散対数問題に基づいた特化型の署名方式を連邦デジタル署名標準として採用しました。単純にデジタル署名アルゴリズム（DSA）として知られるようになったこの方式は、4つの異なるフェーズで構成されています。

1. 鍵生成:

   DSAの鍵は以下から生成されます。

   • 特定のルールを満たす2つの素数
     • $p$ - 通常256ビット（この長さを $N$ と呼びます）
     • $q$ - 通常3072ビット（この長さを $L$ と呼びます）
   • 長さ $L$ の文字列を $N$ に変換する暗号ハッシュ関数
   • 追加パラメーター $g$（詳細は後述）

   これらから、秘密鍵としてランダムな数 $x$ を選び、公開鍵 $y$ を計算できます。

   鍵生成の数学的詳細

   • パラメーター生成: 数学的に、DSAは素数位数 $q < p$ を持つ元 $g$ によって生成される $(\mathbb{Z}_p)^{\times}$ の巡回部分群を扱います。したがって、DSAの最初のステップは2つの素数 $p, q$ を選び、必要な数学的構造を設定することです。

     • $N$ビットの素数 $q$ を選びます。
     • $p-1$ が $q$ の倍数となるような $L$ビットの素数 $p$ を選びます。$p$ の選択により群 $(\mathbb{Z}_p)^{\times}$ が指定されます。
     • ランダムに整数 $1 < h < p-1$ を選び、$g = h^{(p-1)/q}~mod~p$ を計算します。まれに $g=1$ となる場合は、別の $h$ を試します。
     • $g^q~mod~p = 1$ を確認します。$g$ はこうして素数位数 $q$ を持つ $(\mathbb{Z}_p)^{\times}$ の巡回部分群 $\langle g \rangle$ の生成元となります。

     パラメーター $(q, p, g)$ はアルゴリズムのインスタンスを指定し、公開情報です。典型的な実際のアプリケーションでは、$N \sim 256$ かつ $L \sim 3072$ です。

     このプロトコルはまた、2進数の $L$ビット文字列を $N$ビット文字列にマッピングする暗号ハッシュ関数 $H : \{0,1\}^L \rightarrow \{0, 1\}^N$（例えばSHA-256）を必要とします。

   • 鍵ペアの生成: 署名者は自身の端末で鍵ペアを生成する必要があります。

     • ランダムな秘密整数 $x \in \{1,2...q-1\}$ を選びます。$x$ が秘密鍵です。
     • $y = g^{x}~mod~p$ を生成します。$y$ が署名者の公開鍵です。

2. 鍵配布:

   以下の情報は、署名を検証したいすべての人と共有されます。

   • アルゴリズムを記述するパラメーター $(p,q,g)$
   • ハッシュ関数 $H$
   • 公開鍵 $y$

3. 署名:

   • 署名者はメッセージ $m$ に署名できます。結果として得られる署名は $(r,s)$ です。
   • メッセージと署名は両方とも受信者に送られます。
   メッセージ署名の数学的詳細

   署名者はメッセージ $m$ を次のように署名します。

   • $\{1,2...q-1\}$ からランダムに秘密整数 $k$ を選びます。
   • $r = (g^k~mod~p)~mod~q$ を計算します。まれに $r=0$ となる場合は、別のランダムな $k$ を試します。
   • $s = (k^{-1} (H(m) + xr))~mod~q$ を計算します。まれに $s=0$ となる場合は、別のランダムな $k$ を試します。
   • 署名はタプル $(r, s)$ です。
   • 署名者はメッセージ $m$ と署名 $(r,s)$ を検証者に送信します。

   $r, s$ はどちらも $q$ を法とする整数なので、署名サイズは長い $L$ビットではなく $N$ビットのオーダーになります。

4. 検証:

   受信者は送信者の真正性を検証したいと考えています。 受信者は公開情報 $(q, p, g, H, y, (r,s), m)$ にアクセスできます。 受信者は、送信者が秘密鍵 $x$ にアクセスできることを証明する計算を実行できます。

   また、署名者が秘密鍵 $x$ にアクセスできる者であることを確認しようとします。

   DSA検証方式の数学的詳細

   • $0 \lt r \lt q$ かつ $0 \lt s \lt q$ であることを確認します。つまり、$r, s$ が有効な $q$ を法とする整数であることを確認します。
   • $w = s^{-1}~mod~q$ を計算します。
   • $u_1 = H(m)w~mod~q$ を計算します。
   • $u_2 = rw~mod~q$ を計算します。
   • $v = (g^{u_1}y^{u_2}~mod~p)~mod~q$ を計算します。
   • $v = r$ であれば署名が検証されます。

   正規の署名に対するDSAアルゴリズムの正しさは次のように容易に示されます。

   • 署名者側：$s = (k^{-1} (H(m) + xr))~mod~q \implies k = ((H(m) + xr)s^{-1})~mod~q$
   • 後者の等式の右辺を考えると、$s, q, m, H$ は公開情報なので、検証者は $s^{-1}, H(m)$ を計算できます。
   • したがって、検証者は $w = s^{-1}~mod~q$ と $u_1 = H(m)w~mod~q = H(m)s^{-1}~mod~q$ を計算します。
   • 検証者はまた、$r$ も公開なので $u_2 = rw~mod~q = rs^{-1}~mod~q$ を計算します。
   • $k = (u_1 + xu_2)~mod~q$ であることに注意してください。
   • しかし、検証者は $x$ が署名者の秘密鍵であるためアクセスできず、$k$ 自体を直接計算することはできません。このスキームは代わりに、検証者が $k$ を計算できなくても、正規の署名者であれば署名者の公開鍵 $y = g^{x}~mod~p$ の助けを借りて $(g^k~mod~p)~mod~q = r$ を再計算できるという事実に依存しています。
   • したがって、検証者は $v = (g^{u_1}y^{u_2}~mod~p)~mod~q = (g^{u_1}g^{xu_2}~mod~p)mod~q = (g^{u_1+xu_2}~mod~p)mod~q = (g^k~mod~p)mod~q$ を計算します。
   • 最後の等式は $g$ が位数 $q$ を持つことから成り立ち、有効な署名に対して $v = r$ が成立することを確立します。

PythonによるDSAの実例

この例では、小さな素数を使って、アリスがボブに署名付きメッセージを送るシナリオでDSAの処理を説明します。ここでは小さな整数を使用します。実際のシナリオでは、2048〜3072ビット程度のはるかに大きな素数が使われます。

備考

異なる値でこの例を再実行して、アルゴリズムの動作を確認することができますが、このセクションの最初のセルから実行を開始してください。

まず、必要なライブラリをインポートし、パラメータを選択します。 整数パラメータ $p$、$q$、$g$ は公開情報であり、以下のルールを満たす必要があります。

• $p$、$q$ はいずれも素数
• $(p-1) \mod\ q = 0$
• $g \ge 2$
• $g \le (p-2)$
• $g^{(p-1)/q} \mod\ p \neq 1$

from random import randint

# parameter generation: select the primes q, p and generator g:
# EXPERIMENT with the values, they must meet certain rules
# this example code does not verify p,q are prime

q = 11
p = 23
g = 4

assert (p - 1) % q == 0
assert g >= 2
assert g <= (p - 2)
assert (pow(g, (p - 1) / q) % p) != 1

print(f"Public information is good: q={p}, p={q}, g={g}")

次に、署名者であるアリスが秘密鍵を生成します。

秘密鍵 k（Pythonコードでは alice-private-key）は以下の条件を満たす必要があります。

• $k \ge 2$
• $k \le (q-1)$

# Alice chooses an integer randomly from {2..q-1}
# EXPERIMENT with the values

alice_private_key = randint(2, q - 1)
# alice_private_key =

assert alice_private_key >= 2
assert alice_private_key <= (q - 1)

print(f"Alice's private key is {alice_private_key}")

アリスは自分の秘密鍵を秘密にしておきます。

次に、アリスはべき乗剰余を使って公開鍵を計算します。このステップを逆算して秘密鍵を復元するのはDLPの一例であり、大きな素数を使う場合は古典コンピュータでの計算が困難です。

上記の数学的説明から、この計算には以下の式が使えることが分かります。

$y = g^{x} \mod\ p$

alice_public_key = pow(g, alice_private_key, p)
# Alternatively can use (g ** alice_private_key) % p

print(f"Alice's public key is {alice_public_key}")

通常どおり、アリスは必ずしも秘密でないチャネルを通じて公開鍵を公開します。

これでアリスはメッセージに署名できます。

デジタル署名スキームでは、署名するメッセージ $m$ のハッシュ $H(m)$ を生成する必要があります。

アリスとボブが、ハッシュ長 $N$ が $q$ のビット数と等しい特定のハッシュアルゴリズムを使うことに合意したとします。このシンプルな例では、モックハッシュ関数の出力を $q$ で制限します。ここで使うハッシュ関数は単純で、ランダムな整数を生成するだけです。

hash_dict = {}

def mock_hash_func(input_message):
    print(input_message)
    if input_message not in hash_dict:
        hash_dict[input_message] = randint(1, q)
    return hash_dict[input_message]

alice_message = "Inspection tomorrow!"
alice_hash = mock_hash_func(alice_message)  # In reality, you'd use a hash function
print(f"Alice's message hash is: {alice_hash}")

次に、アリスはメッセージごとにランダムな秘密数 $k$ と、署名を計算するためのその $q$ に対する乗法逆元を生成する必要があります。

モジュラー逆数の計算にはシンプルな総当たりアルゴリズムを使えますが、以下に示すように Python 組み込み関数の pow を使う方が適切です。

# brute-force implementation to find modular inverse
def modular_inverse(k, q):
    for i in range(0, q):
        if (k * i) % q == 1:
            return i
    print(f"error! no inverse found! for {k},{q}")
    return 0

# Let's compare this algorithm with the standard python 'pow' function

n1 = modular_inverse(3, 7)
n2 = modular_inverse(4, 11)
n3 = modular_inverse(7, 5)
m1 = pow(3, -1, 7)
m2 = pow(4, -1, 11)
m3 = pow(7, -1, 5)

assert n1 == m1
assert n2 == m2
# assert(n3==m3)

print(f"modular_inverse(3,7) = {m1}")
print(f"modular_inverse(4,11) = {m2}")
print(f"modular_inverse(7,5) = {m3}")

# Some numbers don't have modular inverses - our function throws an error
n4 = modular_inverse(2, 6)

# The python library will throw an exception, which must be caught
if math.gcd(2, 6) == 1:
    m4 = pow(2, -1, 6)
else:
    print("Exception from pow() - no modular inverse found!")

これでアリスは署名を計算できます。

• $r = (g^{k} \mod p) \mod\ q$
• $s = (k^{-1} (H(m) + xr)) \mod q$

$r$ または $s$ が $0$ になる場合は、$k$ に別の値を選ぶ必要があることに注意してください。その場合は新しい値を生成して繰り返します。

# Start an infinite loop; we will 'break' out of it once a valid signature is found.
while True:
    k = randint(1, q - 1)  # Should be different for every message
    print("Using random k =", k)

    r = pow(g, k, p) % q
    # If r is 0, the value is invalid. Try again with a new k.
    if r == 0:
        print(f"{k} is not a good random value to use to calculate r. Trying another k")
        continue

    s = (pow(k, -1, q) * (alice_hash + alice_private_key * r)) % q
    # If s is 0, the value is also invalid. Try again with a new k.
    if s == 0:
        print(f"{k} is not a good random value to use to calculate s. Trying another k")
        continue

    # If we've reached this point, both r and s are valid. Break the loop.
    signature = (r, s)
    print(f"Alice's signature is : {(r,s)}")
    break

# After the loop, the valid r and s values can be used here.
# print(f"Generated Signature -> r: {r}, s: {s}")

アリスはメッセージと署名を受信者または検証者であるボブにブロードキャストします。

ボブはあらかじめアリスの公開鍵を入手しており、署名を検証してメッセージを認証することができます。

そのためにボブはいくつかの確認を行い、アリスのブロードキャストメッセージのハッシュを再生成して補助量 $w, u_1, u_2$、$v$ を計算します。

• $0 < r < q$
• $0 < s < q$
• $w = s^{-1} \mod\ q$
• $u_{1} = H(m) . w \mod\ q$
• $u_{2} = r . w \mod\ q$
• $v = (g^{u1}y^{u2} \mod\ p) \mod\ q$

最後に、ボブは $v$ が $r$ と等しいかどうかを確認します。等しければ、署名が検証されます。

# Bob re-generates message hash using Alice's broadcast message
bob_hash = mock_hash_func(alice_message)

# Bob computes auxiliary quantities w (using modular inverse), u1, u2 and v
w = (pow(s, -1, q)) % q
u1 = (bob_hash * w) % q
u2 = (r * w) % q
v = ((g**u1 * alice_public_key**u2) % p) % q

if v == r:
    print("Signature is valid!")
else:
    print("Signature is invalid!")

DSAのセキュリティ

古典コンピューティングにおいて、DSAのセキュリティはいくつかの要因に影響されます。

1. 鍵のサイズ: 常にそうであるように、鍵のサイズはブルートフォース攻撃に対する基本的な保護を提供します。DSAを使用する現代のアプリケーションでは、少なくとも2048ビットの鍵サイズが使用されます。

2. $k$ の品質: DSAでは、各署名に一意でランダムかつ秘密の $k$ の値が必要です（上記参照）。$k$ の一意性、エントロピー、および秘密性は重要であり、これらのいずれかの側面に弱点があると、秘密鍵 $x$ が危険にさらされる可能性があります。$k$ の生成に使用される乱数生成器自体も安全である必要があります。

3. ハッシュ関数の強度: DSAは署名の生成と検証プロセスの一部としてハッシュ関数を使用するため、ハッシュ関数が弱いとデジタル署名のセキュリティが損なわれる可能性があります。例えば、DSAでのSHA-1の使用は非推奨であり、SHA-2以上が推奨されています。

これらに加えて、堅牢なDSA実装は、前述の非対称鍵暗号を標的とした他の種類の攻撃にも対処する必要があります。

Diffie-HellmanとDSAによる認証付き鍵交換

Transport Layer Security (TLS) をはじめとする現代のネットワークセキュリティプロトコルの多くは、鍵交換と認証の機能を組み合わせています。Diffie-Hellmanの文脈では、MITM攻撃を防ぐために認証が必要です。以下のコードセルでは、アリスとボブがDiffie-HellmanとDSAプロトコルを組み合わせて認証付き鍵交換を行う例を示します。ここでは cryptography Pythonライブラリを使用します。

図2. Diffie-HellmanとDSAによる認証付き鍵交換

まず、アリスとボブはDHパラメータのセットに合意し、DHの公開鍵・秘密鍵ペアを生成します。

# import necessary library modules
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh, dsa

# Generate DH parameters
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Generate Alice's DH private key and public key
alice_dh_private_key = parameters.generate_private_key()
alice_dh_public_key = alice_dh_private_key.public_key()

# Generate Bob's DH private key and public key
bob_dh_private_key = parameters.generate_private_key()
bob_dh_public_key = bob_dh_private_key.public_key()

print("Public and private keys generated for Bob and Alice")

DH公開鍵がブロードキャストされます。次に、アリスとボブはそれぞれDSA用の鍵ペアを生成します。これらの鍵は、交換されるDH公開鍵への署名に使用されます。

# Generate DSA keys for Alice and Bob
alice_dsa_private_key = dsa.generate_private_key(key_size=2048)
alice_dsa_public_key = alice_dsa_private_key.public_key()
bob_dsa_private_key = dsa.generate_private_key(key_size=2048)
bob_dsa_public_key = bob_dsa_private_key.public_key()

print("Additional key pair generated for signing")

アリスはDSA秘密鍵を使ってDH公開鍵に署名します。

# Alice signs
alice_public_bytes = alice_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
alice_signature = alice_dsa_private_key.sign(alice_public_bytes, hashes.SHA256())

print("Alice signed public key")

同様に、ボブはDSA秘密鍵を使ってDH公開鍵に署名します。

bob_public_bytes = bob_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
bob_signature = bob_dsa_private_key.sign(bob_public_bytes, hashes.SHA256())

print("Bob signed public key")

DH公開鍵と対応する署名がアリスとボブの双方からブロードキャストされます。相手方の公開鍵と署名を受け取ったそれぞれの当事者は、署名が有効であることを検証します。こうすることで、例えばアリスはボブのDH公開鍵が確かにボブによって署名されたことを確認できるため、MITM攻撃を防ぐことができます。

# Alice and Bob verify each other's DH public keys using DSA public keys
# An InvalidSignature exception will occur if they are not valid
alice_dsa_public_key.verify(alice_signature, alice_public_bytes, hashes.SHA256())
bob_dsa_public_key.verify(bob_signature, bob_public_bytes, hashes.SHA256())

print("Signatures are valid")

署名の検証が完了すると、アリスとボブは共有秘密を生成し、鍵交換が完了します。

# Perform key exchange
alice_shared_key = alice_dh_private_key.exchange(bob_dh_public_key)
bob_shared_key = bob_dh_private_key.exchange(alice_dh_public_key)

print("Shared secrets generated")

追加のセキュリティとして、アリスとボブはオプションで HKDF のような特殊な鍵導出関数を使って、鍵ストレッチング 技術により共有秘密からより安全な対称鍵を生成することができます。

# Derive a shared symmetric key using key-stretching
def derive_key(shared_key):
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=None,
    ).derive(shared_key)

alice_symmetric_key = derive_key(alice_shared_key)
bob_symmetric_key = derive_key(bob_shared_key)

assert alice_symmetric_key == bob_symmetric_key
print("Keys checked to be the same")

Diffie-HellmanとDSAの解読

Diffie-Hellman（DH）と DSA の両プロトコルは、秘密鍵 $x$ が離散対数となる $y = g^{x}~mod~p$ という形式の公開鍵の生成を含みます。

DLPのインスタンスを解くことができる攻撃者は、2者のうち一方の秘密鍵を暴露し、それを他方の公開鍵と組み合わせることで共有秘密にアクセスできます。DSAの場合、DLPを解くことができる攻撃者は署名者の秘密鍵を復元でき、デジタル署名の基本的な前提が無効になります。

古典コンピューティングシステムでは、DLPには多項式時間の解が存在しないと考えられています。しかし、ピーター・ショアが 1994年の原著論文 で示したように、ショアのアルゴリズムは量子コンピュータ上でDLPも多項式時間で解くことができます。

ショアのアルゴリズムと離散対数問題

ショアのアルゴリズムは、離散対数問題を多項式時間で解くことができます。主に、問題の入力に依存する関数の周期を求める量子アルゴリズムを活用することで効率性を実現し、それをより従来的な演算と組み合わせています。

ショアのアルゴリズムの数学的詳細

ショアのアルゴリズムは、DLPを隠れ部分群問題（HSP）として知られる群論のより一般的な問題に変換することで、効率的な解法を提供します。

HSPでは、代数群 $G$ と、$G$ から何らかの集合 $X$ への関数 $f: G \rightarrow X$ が与えられます。この関数 $f$ は $G$ のある部分群 $H$ の各剰余類において一定（異なる剰余類では異なる値）です。そして課題は $H$ を決定することです。量子コンピュータは、有限アーベル群上のHSPを $log~|G|$（$|G|$ は群の位数）の多項式時間で解けることが知られています。

このレッスンで取り上げた整数DLPのHSPへの変換は次のとおりです：

• $p$ を素数とし、$g$ が $(\mathbb{Z}_p)^{\times}$ の生成元である DLP $y = g^r~mod~p$ を考えます。$g^{p-1} \equiv 1~mod~p$ なので、$g$ の位数は $p-1$ です。
• $G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$（ここで $\mathbb{Z}_{p-1}$ は $(p-1)$ を法とする整数群）を選びます。
• $f : G \rightarrow (\mathbb{Z}_p)^{\times}$ を $f(a, b) = g^a y^{-b}~mod~p \equiv g^{a-rb}~mod~p$ と定義します。
• $f$ の核は部分群 $H_0 = \langle (r, 1) \rangle = \{(a,b) \in G | f(a,b) \equiv 1~mod~p\} = \{ (a, b) \in G | a - rb \equiv 0~mod~(p-1)\}$ となります。
• $f$ は剰余類 $(\delta, 0) + H_0$ 上で一定であり、部分群 $H_0$ を「隠す」ことでHSPを構成します。

以上を踏まえると、整数DLPに対するショアの量子アルゴリズムは、$G$ 上の一様重ね合わせを表す状態に対して関数 $f$ を評価する量子オラクルを使用し、続いて量子フーリエ変換と位相推定を用いた測定によって、$H_0$ の生成元 $(r, 1)$ を特定できる量子状態を生成します。これにより、求めたい離散対数 $r$ を取り出すことができます。

ショアのオリジナル論文にはアルゴリズムの詳細な説明があります。

楕円曲線暗号

楕円曲線暗号（ECC）は、楕円曲線の数学を基盤とした非対称鍵暗号の強力なアプローチです。ECCはRSAなどの方式と同等のセキュリティレベルを、より短い鍵で提供することが知られており、効率性が高く、組み込みシステムやモバイルデバイスなど鍵サイズの小型化によるストレージおよび計算量の節約が非常に望ましい、リソースが限られたシステムに特に適しています。

楕円曲線暗号の基本原理

楕円曲線は一般的に $y^2 = x^3 + ax + b$ の形をしており、いくつかの興味深い性質があります。

• 水平方向に対称です。そのため、曲線上の任意の点 $(x,y)$ に対して、その反転点 $(x,-y)$ も曲線上にあります。
• 垂直でない直線は、曲線と最大3点でしか交差しません。

図1. 楕円曲線上の加算とポイント倍算の演算。面1は P + Q = -R を定義しています。面2はポイント倍算 2Q = -P を示しています。面3は点の加法逆元をx軸に関する反転点として定義しています（すなわち P = -Q）。

楕円曲線暗号は、曲線上の点に対して一連の算術演算を適用することを利用しています。各演算は実質的に曲線上の新しい点へと移動します。これは一方向には追いやすい処理であり、鍵サイズが短いためRSAなど他のアルゴリズムよりも効率的ですが、逆方向への追跡は非常に困難であるため、暗号への応用が可能となっています。

楕円曲線暗号の数学的原理

代数体 $K$ 上の楕円曲線は、通常 $y^2 = x^3 + ax + b$ の形で表される数学的方程式によって定義され、係数 $a, b \in K$ を持ち、折れ目や自己交差のないという追加条件のもとで点 $(x, y) \in K \otimes K$ を表します。

楕円曲線の性質により、曲線上の点に関わる「加算」と「スカラー倍算」の演算を定義できます。

加算：$P$ と $Q$ が楕円曲線上の2点であるとき、$P + Q$ は次のように特定される一意の第3の点を表します。$P$ と $Q$ を通る直線を引き、その直線が曲線と再び交わる第3の点 $R$ を求めます。そして $P + Q = −R$、すなわち $R$ をx軸について反転した点を定義します（下図参照）。$P, Q$ を通る直線が有限の点 $(x, y)$ で曲線と交わらない場合、無限遠点 $\mathbf{O}$ で交わると言います。

楕円曲線の加算は、無限遠点を加法単位元とする代数的な群の性質を満たします。

倍算とスカラー乗算：$2$ によるスカラー乗算に対応するポイント倍算の演算は、加算演算において $P = Q$ と置くことで得られ、図形的には $P$ における接線が関与します。一般的な整数 $n$ によるスカラー乗算 $nP = P + P + ...~n$ 回は、繰り返し倍算と加算によって得られます。

楕円曲線離散対数問題

楕円曲線離散対数問題（ECDLP）は、前述の離散対数問題と多くの類似点を持っており、因数を見つける難しさを基盤としています。

楕円曲線上のスカラー乗算の演算により、楕円曲線離散対数問題を定義することができます：

楕円曲線上の点 $P, Q$ が $Q = nP$ を満たすとき、$n$ を求めよ。

この問題は大きな $n$ に対して古典コンピュータ上では解くことができないことが知られており、暗号セキュリティの基盤を提供します。

ECDLPの数学的説明

楕円曲線暗号は主に、特定の代数的な有限体上で定式化されたECDLPを基盤としています。1999年にNISTはECCで使用する10種類の有限体を推奨しました。それらは：

• サイズ $\{192, 224, 256, 384, 521\}$ ビットの素数 $p$ に対する5つの素数体 $\mathbb {F} _{p}$
• $n \in \{163, 233, 283, 409, 571\}$ に対する5つの2元体 $\mathbb {F} _{2^{n}}$

上記の設定のもと、素数体の場合のECCベースの非対称鍵暗号システムは次のように規定できます：

• NISTの推奨値リストから $p$ を選択して $\mathbb {F} _{p}$ を指定します。

• 楕円曲線のパラメータ $a, b$ を選択します。

• 曲線上で位数 $n$ の巡回部分群を「生成」するベース点 $G$ を選択します。つまり $nG = \mathbf{O}$ を満たす最小の整数です。

• 余因子 $h = |E(\mathbb {F} _{p})|/n$ を計算します（$|E(\mathbb {F} _{p})|$ は曲線上の点の数）。$h$ は通常、小さな整数です。

• ドメインパラメータ $(p, a, b, G, n, h)$ により、非対称鍵を次のように規定できます：

  • 秘密鍵は素数 $p$ と同じビット数のランダムに選択された整数 $d$ です。秘密に保つ必要があります。
  • 公開鍵はベース点 $G$ を秘密鍵 $d$ で「乗算」した結果であり、通常 $Q = dG$ と表されます。

$d$ を復元することはECDLPを解くことと等価であり、大きな $d$ に対しては解くことができないと仮定されています。したがってECDLPは、前述の $(\mathbb{Z}_p)^{\times}$ 上のDiffie-HellmanおよびDSAスキームと直接対比する形で、鍵交換およびデジタル署名スキームの基盤となっています。

ECCによる鍵交換

ECCの主な用途のひとつは、楕円曲線Diffie-Hellman（ECDH）として知られる鍵交換プロトコルです。ECDHでは、各当事者が秘密鍵と公開鍵のペアを生成し、その後公開鍵を交換します。各当事者は自分の秘密鍵と相手の公開鍵を使って共有秘密を計算し、これを対称暗号の鍵として使用できます。

楕円曲線上で点の加算を行い秘密鍵から公開鍵を導出することは比較的容易ですが、その逆、すなわち公開鍵から秘密鍵を導出することは計算上実行不可能です。この「一方向性」の振る舞いがECDH鍵交換のセキュリティを提供しています。

ここでは、PythonとライブラリI cryptography を使ってECDH鍵交換を実行する方法の例を示します。

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

# Each party generates a private key
private_key1 = ec.generate_private_key(ec.SECP384R1())
private_key2 = ec.generate_private_key(ec.SECP384R1())

# They exchange public keys
public_key1 = private_key1.public_key()
public_key2 = private_key2.public_key()

# Each party uses their own private key and the other party's public key
# to derive the shared secret
shared_key1 = private_key1.exchange(ec.ECDH(), public_key2)
shared_key2 = private_key2.exchange(ec.ECDH(), public_key1)

# The shared secrets are the same
assert shared_key1 == shared_key2
print("Keys checked to be the same")

ECCによるデジタル署名

ECCは楕円曲線デジタル署名アルゴリズム（ECDSA）を使用してデジタル署名を生成するためにも使用できます。ECDSAでは、署名者が秘密鍵を使って署名を作成し、他者が署名者の公開鍵を使って署名を検証できます。ECDHと同様に、ECDSAのセキュリティはECDLPに依存しています。署名者の秘密鍵にアクセスせずに署名を偽造することは計算上実行不可能です。

以下は、PythonとI cryptography を使ったECDSAによる簡単な署名と検証のトランザクションの例です。

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# Generate a private key for use in the signature
private_key = ec.generate_private_key(ec.SECP384R1())

message = b"A message to be signed"

# Sign the message
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# Anyone can verify the signature with the public key
public_key = private_key.public_key()

def check_ecdsa_signature(public_key, signature, message):
    try:
        public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
        return True
    except InvalidSignature:
        return False

if check_ecdsa_signature(public_key, signature, message):
    print("The signature is valid.")
else:
    print("The signature is invalid.")

上記のコードでは、署名後にメッセージを変更すると検証が失敗し、メッセージの真正性と完全性が保証されます。

ECDHとECDSAの解読

整数離散対数問題と同様に、ECDLPは古典コンピュータ上では解くことが困難ですが、量子コンピュータ上では再びショアのアルゴリズムによって効率的に解くことができます。ショアのアルゴリズムをECDLPのケースに一般化することに関する議論については、最近の文献を参照してください。

まとめ

このレッスンでは、まず非対称鍵暗号（AKC）の主な特性を確認し、非対称暗号システムを支える基本的なセキュリティの考慮事項について説明しました。特に、AKCの2つの主要な応用、すなわち鍵交換とデジタル署名を紹介しました。これらはどちらも現代のインターネットベースの通信に不可欠なコンポーネントです。

次に、RSA暗号システムを取り上げました。RSAは1970年代以来、シンプルで汎用性の高いフレームワーク内で鍵交換とデジタル署名を可能にすることにより、現代のデジタル通信のセキュリティ確保に多大な貢献をしてきました。古典計算に対するRSAの暗号セキュリティは、大きな整数の因数分解の困難さに基づいており、実用的なアプリケーションで使用される整数が因数分解に十分に抵抗できるようにするために、2048ビット程度の鍵サイズが必要です。

続いてDiffie-Hellman（DH）鍵交換とデジタル署名アルゴリズム（DSA）を取り上げました。これらのスキームのセキュリティは整数離散対数問題（DLP）に基づいており、公開鍵から秘密鍵を計算上導出することは困難で、古典コンピュータ上では多項式時間の解法がありません。ランダムで一意な鍵の使用は、攻撃に対するさらなるセキュリティを提供します。整数有限体と楕円曲線の両方のDHおよびDSAプロトコルは、現在TLS、SSHなどの多くの現代のデジタル通信プロトコルで広く使用されています。

最後に楕円曲線暗号を取り上げました。効率的な鍵サイズと強力なセキュリティ特性を持つECCは、鍵交換からデジタル署名まで、多くの暗号化アプリケーションに対して現在優れた選択肢となっています。

これらのアルゴリズムはすべて、その設計の前提となった数学的問題を解く手法が開発され得るため、量子アルゴリズムによる攻撃にさらされています。ショアのアルゴリズムはその一例です。そのため、これらは量子攻撃に対してより強靭であり、かつ古典アルゴリズムに対しても安全な、量子安全な非対称暗号システムに置き換える必要があります。これらが依拠する数学的問題は量子コンピュータによって効率的に解けるため、量子攻撃に耐えながら古典的なセキュリティを維持できる量子安全な非対称暗号システムの開発が求められています。

今後のレッスンでは、量子安全な暗号システムを取り上げ、暗号セキュリティを維持するための必要なアプローチについて説明します。