「PythonとLinuxでのポスト量子暗号化」

PythonとLinuxでのポスト量子暗号化

初心者向けガイド

もしEdward Snowdenの言葉を信じるなら、暗号化は「監視に対する唯一の真の保護手段」です[1]。しかし、量子技術の進歩によってこの保護手段が危険にさらされる可能性があります。本記事では、なぜ量子コンピューティングがデータセキュリティに脅威をもたらすのか、そしてそれに対処する方法について議論します。純粋に理論的な分析ではなく、Python、C、およびLinuxを使用したコード例に基づいています。

量子の基礎

Googleの科学者が2019年に量子優位性の最初の事例を報告したことで、大きな興奮が起こりました。量子コンピューティングが大きな影響を与える可能性がある分野の1つは暗号化です。この問題を理解するためには、いくつかの基礎を説明する必要があります。

古典的なコンピュータとは異なり、量子コンピュータのアルゴリズムはビットではなくキュビットに依存しています。ビットは0または1の状態を取ることができます。ビットを何度も測定すると、必ず同じ結果が得られます。しかし、キュビットでは状態0と1の両方の値を同時に取ることができます。何度も測定すると、結果0または1が得られる確率があります。キュビットの初期状態では、0を測定する確率は通常100％です。しかし、重ね合わせによって異なる確率分布を生成することができます。これは量子力学に起因し、通常の「普通の」生活とは異なる法則に従います。

量子コンピュータの主な利点は、確率的な性質にあります。古典的なコンピュータは、信頼性のある単一の結果が必要な問題に優れています。一方、量子マシンは確率と組み合わせ論の扱いに優れています。重ね合わせ状態のキュビットに対して操作を行うと、値0と1の両方に同時に適用されます。キュビットの数が増えると、古典的なコンピュータに比べて利点が増します。3つのキュビットを持つ量子マシンは、8つの値（2³）を同時に処理できます。すなわち、バイナリ数値の000、001、010、011、100、101、110、111です。

科学文献は、量子コンピュータが以前は解決が困難と思われていた問題の解決に役立つと一致しています。しかし、最適な量子マシンはまだ存在しません。現在の量子コンピュータの世代は、ノイズのある中規模の量子（NISQ）と呼ばれています。このようなマシンは処理能力が制限されており、エラーに敏感です。現代のデバイスは数百のキュビットを提供しています。IBMが2022年に導入した433キュビットのOspreyチップがその一例です。同社は2033年までに10万キュビットのマシンを開発する計画です。

本記事では、この進化がデータセキュリティにどのような脅威をもたらすのかを説明します。コード例を使用して、量子コンピュータが特定の暗号を破る可能性がある理由と回避策について説明します。ソースコードはGitHubで利用できます。Python 3.10を使用したAnacondaを使用して、Kali Linux 2023.2で開発されました。

暗号化と素因数

メッセージを暗号化する際、比較的簡単な方法は対称アルゴリズムを適用することです。この方法では、平文の暗号化と暗号文の復号に同じ鍵を使用します。このアプローチの主な課題は、送信者と受信者の間で鍵を安全に交換することです。秘密鍵が第三者に知られてしまうと、メッセージを傍受して復号する機会が生じます。

非対称暗号化はこの問題の解決策として考えられました。RSAなどの方法では、暗号化と復号に異なる鍵を使用します。ここでは、受信者が誰にでも公開可能な1つ以上の公開鍵で暗号化を行います。復号には、受信者が自身だけが知っている秘密鍵を使用します。このように、送信者は公開鍵をリスクなく取得できます。なぜなら、公開鍵はどちらにせよ秘密ではないからです。秘密鍵のみを保護する必要があります。しかし、潜在的な攻撃者が公開鍵を知っている場合、この手順をどのように強化できるのでしょうか？そのために、非対称アルゴリズムは素因数分解などの数学的な問題に依存しています。

素因数分解は例を通じて理解するのが最も良いです。Pythonでは、SymPyライブラリのfactorint関数を使用して、特定の整数の素因数を求めることができます。

>>> import sympy>>> sympy.factorint(10){2: 1, 5: 1}>>> 2**1 * 5**110>>> sympy.factorint(1000){2: 3, 5: 3}>>> 2**3 * 5**31000>>> sympy.factorint(55557){3: 2, 6173: 1}>>> 3**2 * 6173**155557>>>

上記のコンソール出力は、すべての自然数を素数の積として表すことができることを示しています。これらは素因数と呼ばれます。学校の授業を思い出すと、素数は1とそれ自身のみで割り切れる数です。例えば、数値10は10=2¹ * 5¹と表すことができます。したがって、数値10の素因数は2と5です。同様に、数値55557は55557=3² * 6173¹という式で表すことができます。したがって、数値55557の素因数は3と6173です。与えられた整数の素因数を見つけるプロセスは、素因数分解と呼ばれます。

古典的なコンピュータでは、小さな数に対しては素因数分解は簡単ですが、大きな整数に対してはますます困難になります。追加の数値ごとに可能な組み合わせの数が急激に増加します。ある程度の数値を超えると、古典的なコンピュータが素因数を決定することはほぼ不可能になります。例えば、RSA Factoring Challengeで終了した以下の数値（RSA-260）を考えてみてください。執筆時点では、まだ素因数分解されていません。

#!/usr/bin/env pythonimport sympyrsa_260 = 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199print("素因数分解を開始します...")factors = sympy.factorint(rsa_260)# 到達されることはおそらくないprint(factors)

RSAのような非対称アルゴリズムは、素因数分解や類似の問題の計算的な困難さを利用して暗号を保護します。残念ながら、量子世界は独自の法則に従います。

量子アルゴリズム

暗号に関しては、2つの量子アルゴリズムが特に懸念されています。ショアのアルゴリズムは、素因数分解の効率的な方法を提供します。大規模な量子デバイスで実行される場合、RSAなどの非対称方法を理論的に破ることができます。実践的な観点からは、このシナリオは将来の話です。2023年のNatureの記事では、少なくとも1,000,000キュービットが必要とされています。ハードウェアに加えて、大規模な量子マシンで信頼性のあるスケーリングを行うアルゴリズムの実装を見つけることも困難です。IBMのフレームワークQiskitは、関数を実装しようとしましたが、バージョン0.22.0で非推奨となりました。ただし、Shorのアルゴリズムの実験的な実装はオンラインで見つけることができます。

グローバーのアルゴリズムは、対称暗号に対する脅威となります。量子探索アルゴリズムとも呼ばれ、与えられた関数の入力の非構造化探索に対して高速化を提供します。量子コンピュータは、これを使用して対称暗号で暗号化された情報の総当たり攻撃を加速することができます。ただし、Shorのアルゴリズムとは異なり、提供される高速化は指数的ではありません。簡単に言えば、暗号化に使用される鍵の長さを増やすと、検索にかかるコストが極端に増加します。例えば、128ビットの鍵に対する総当たり攻撃では最大2¹²⁸回の繰り返しが必要です。グローバーの探索によってこの数が2⁶⁴まで減少すると仮定すると、鍵長を256ビットに倍増させると再び2¹²⁸回の繰り返しが必要になります。これにより、回避策の可能性が生まれます。

対称回避策

特定の条件下では、対称暗号化は量子アルゴリズムに対抗するためのすぐに利用できる簡単な方法です。グローバーの探索は指数的にスケールしないため、ショアのアルゴリズムも非対称アプローチにのみ脅威を与えます。現在の知識によれば、高い硬度を持つ対称アルゴリズムは、量子耐性とみなすことができます。現在、アメリカのNISTとドイツのBSIの両方がAES-256をこのカテゴリに含めています[2][3]。AESとはAdvanced Encryption Standardの略であり、256は鍵のビット長を表しています。Linuxでは、AES-256をGNU Privacy Guard（GnuPG）が実装しています。以下のシェルスクリプトは、ファイルをAES-256で暗号化し、復号化する方法を示しています。

# 暗号化gpg --output encrypted.gpg --symmetric --cipher-algo AES256 plain.txt# 復号化gpg --output decrypted.txt --decrypt encrypted.gpg

上記のスクリプトは、ファイル「plain.txt」の内容を暗号化し、「encrypted.gpg」というドキュメントに暗号文を書き込み、それを復号化して最終的に「decrypted.txt」というファイルに出力します。暗号化の前に、GnuPGは秘密鍵を生成するためのパスフレーズを求めます。セキュリティ上の理由から、強力なパスフレーズを選択し、秘密に保つことが重要です。GnuPGはパスフレーズをキャッシュする場合があり、復号化時に再度尋ねられないことがあります。キャッシュをクリアするには、次のシェルコマンドを実行します。

gpg-connect-agent reloadagent /bye

PythonにGnuPGを統合するのは、subprocessモジュールを使うことで比較的簡単です。以下のコード断片には、AES-256での暗号化のプロトタイプ実装が示されています。

#!/usr/bin/env pythonimport subprocessimport getpass# パスフレーズの入力passphrase = getpass.getpass("パスフレーズ：")passphrase2 = getpass.getpass("パスフレーズの確認：")if passphrase != passphrase2:  raise ValueError("パスフレーズが一致しません！")# 暗号化を実行print("暗号化中...")args = [  "gpg",  "--batch",  "--passphrase-fd", "0",  "--output", "encrypted.gpg",  "--symmetric",  "--yes",  "--cipher-algo", "AES256",  "plain.txt",]result = subprocess.run(  args, input=passphrase.encode(),  capture_output=True)if result.returncode != 0:  raise ValueError(result.stderr)

上記のスクリプトでは、getpassモジュールを使用してパスフレーズを取得しています。確認後、パスフレーズは標準入力を介してGnuPGに送信されます。これは引数passphrase-fd 0で示されています。代わりに、パスフレーズを文字列でGnuPGに送信するか、コマンドライン引数でファイルとして送信することも可能です。ただし、これらの引数は他のユーザーに見えるため、プロトタイプではどちらのオプションも却下されました。より安全な方法としては、GPG-Agentを使用する方法があります。どのオプションを選択するかは、望むセキュリティレベルによります。ここでは、暗号化と復号を含む概念実証が提供されています。GnuPGの代わりに、他のAES-256の実装もあります。信頼できるソースを選ぶことが重要です。

非対称の回避策

非対称な解決策を探すために、NIST Post-Quantum Cryptography Standardizationプログラムは良い出発点です。2016年以来、このプログラムは量子耐性アルゴリズムの複数の候補を評価してきました。その中の一つがKyberです。このシステムは、いわゆるセキュアキーのカプセル化メカニズムを実装しています。他のアルゴリズムと同様、Kyberも2者間の鍵交換を保護するために解きにくい問題に依存しています。素因数分解ではなく、「誤りの学習」と呼ばれる問題に基づいています。Kyberが提供する保護レベルは、鍵の長さによって異なります。例えば、Kyber-1024は「AES-256とほぼ同等のセキュリティレベル」を目指しています[4]。

Cで書かれたKyberのリファレンス実装は、GitHubで入手できます。Linuxでは、以下のシェルコマンドを実行することでフレームワークをクローンしてビルドすることができます。インストールにはいくつかの前提条件が必要ですが、これらはプロジェクトのREADMEに記載されています。

git clone https://github.com/pq-crystals/kyber.gitcd kyber/ref && make

リファレンス実装をPythonに統合する方法はいくつかあります。その1つは、Cプログラムを書いて呼び出す方法です。以下のC関数は、Kyberを使用して架空の2つの当事者、AliceとBobの間で鍵交換を行います。完全なソースコードについては、こちらを参照してください。

#include <stddef.h>#include <stdio.h>#include <string.h>#include "kem.h"#include "randombytes.h"void round_trip(void) {    uint8_t pk[CRYPTO_PUBLICKEYBYTES];    uint8_t sk[CRYPTO_SECRETKEYBYTES];    uint8_t ct[CRYPTO_CIPHERTEXTBYTES];    uint8_t key_a[CRYPTO_BYTES];    uint8_t key_b[CRYPTO_BYTES];    //Aliceが公開鍵を生成    crypto_kem_keypair(pk, sk);    print_key("Aliceの公開鍵", pk);    //Bobは秘密鍵を派生し、応答を作成    crypto_kem_enc(ct, key_b, pk);    print_key("Bobの共有鍵", key_b);    print_key("Bobの応答鍵", ct);    //AliceはBobの応答を使用して自身の共有鍵を取得    crypto_kem_dec(key_a, ct, sk);    print_key("Aliceの共有鍵", key_a);}

詳細には触れませんが、Kyberは複数の公開鍵と秘密鍵を使用しています。上記の例では、Aliceが公開鍵（pk）と秘密鍵（sk）を生成します。次に、Bobは公開鍵（pk）を使用して共有鍵（key_b）と応答鍵（ct）を派生します。後者はAliceに返されます。最後に、Aliceは応答鍵（ct）と秘密鍵（sk）を使用して共有鍵（key_a）のインスタンスを生成します。両当事者が秘密鍵と共有鍵を秘密に保てば、アルゴリズムは保護を提供します。プログラムを実行すると、以下のような出力が得られます。

Aliceの公開鍵：F0476B9B5867DD226588..Bobの共有鍵：ADC41F30B665B1487A51..Bobの応答鍵：9329C7951AF80028F42E..Aliceの共有鍵：ADC41F30B665B1487A51..

C言語の関数をPythonから呼び出すために、subprocessモジュールを使用することができます。また、共有ライブラリをビルドし、ctypesモジュールで呼び出すことも可能です。以下のPythonスクリプトでは、2番目のオプションが実装されています。Kyber Cコードから生成された共有ライブラリをロードした後、round_trip手続きは他のPython関数と同様に呼び出されます。

#!/usr/bin/env python
import os
import ctypes
# 共有ライブラリをロード
libname = f"{os.getcwd()}/execute_round_trip1024.so"
clib = ctypes.CDLL(libname, mode=1)
print("共有ライブラリが正常にロードされました:")
print(clib)
# round_trip関数を呼び出す
print("ラウンドトリップを実行中:")
clib.round_trip()

Kyberのリファレンス実装に加えて、他のプロバイダも同様のアルゴリズムを実装しています。オープンソースプロジェクトBotanやOpen Quantum Safeなどがその例です。

結論

私たちの分析によれば、量子技術はまだ初期段階にあります。しかし、暗号化や署名などの他の暗号化方式に対する脅威を過小評価すべきではありません。破壊的なイノベーションはいつでも開発を加速させることができます。攻撃者は現在メッセージを保存し、後で解読することができます。したがって、すぐにセキュリティ対策を講じる必要があります。特に回避策が利用可能な場合はさらに重要です。AES-256のような対称アルゴリズムは、適切に使用すると量子耐性があるとされています。また、Kyberのような非対称解決策も進化しています。どの代替案を使用するかはアプリケーションによります。ゼロトラストモデルに従い、複数のアプローチを組み合わせることが最良の保護を提供します。これにより、量子の脅威は自己崩壊する予言のようなものになるかもしれません — Y2K問題のように。

著者について

クリスチャン・コッホはBWI GmbHのエンタープライズアーキテクトであり、ニュルンベルク工科大学ジョージ・サイモン・オーム校の講師です。

ルーシー・コーゲルハイデはBWI GmbHのポスト量子暗号のテクノロジーリードであり、同社の量子安全な暗号への移行プロセスの立ち上げを担当しています。

ラファエル・ローレンツはLorenz Systemsの創設者兼CISOであり、ホリスティックなセキュリティソリューションに特化しています。

参考文献

Snowden, Edward: Permanent Record. Macmillan, 2019.
National Institute of Standards and Technology: NIST Post-Quantum Cryptography: FAQS. 29 June 2023. Accessed: 02 August 2023.
Federal Office for Information Security (BSI): Quantum-safe cryptography — fundamentals, current developments and recommendations (PDF). October 2021. Accessed: 02 August 2023.
CRYSTALS — Cryptographic Suite for Algebraic Lattices: Kyber Home. December 2020. Accessed: 02 August 2023.

免責事項

情報セキュリティは重要なトピックであり、著者は公開されたコンテンツに対して一切の保証を提供していませんのでご了承ください。

We will continue to update VoAGI; if you have any questions or suggestions, please contact us!

CybersecurityEncryptionLinuxPythonQuantum computing

Was this article helpful?

93 out of 132 found this helpful