キーサイズ

暗号化では、キー サイズまたはキーの長さは、暗号化アルゴリズム (暗号など)で使用されるキーのビット数を指します。

キーの長さは、アルゴリズムのセキュリティの上限を定義します(つまり、アルゴリズムに対する既知の最速の攻撃の対数測定)。これは、すべてのアルゴリズムのセキュリティがブルート フォース攻撃によって侵害される可能性があるためです。理想的には、アルゴリズムのセキュリティの下限は、設計上、キーの長さと等しくなります (つまり、アルゴリズムの設計により、キーの長さに固有のセキュリティの程度が損なわれることはありません)。

ほとんどの対称鍵アルゴリズムは、その鍵の長さと同じセキュリティを持つように設計されています。ただし、設計後に新しい攻撃が発見される可能性があります。たとえば、トリプル DES は168 ビットの鍵を持つように設計されましたが、現在では複雑度 2 ¹¹²の攻撃が知られています (つまり、トリプル DES のセキュリティは現在 112 ビットのみであり、鍵の 168 ビットのうち 56 ビットは攻撃によってセキュリティに対して「無効」になっています)。ただし、セキュリティ (「アクセスするのにかかる労力」として理解される) が特定のアプリケーションに対して十分である限り、鍵の長さとセキュリティが一致しているかどうかは問題ではありません。これは非対称鍵アルゴリズムにとって重要です。なぜなら、この特性を満たすアルゴリズムは知られていないからです。楕円曲線暗号は、鍵の長さの約半分の有効セキュリティで最も近いものです。

キーは暗号の動作を制御するために使用され、正しいキーだけが暗号化されたテキスト (暗号文)を平文に変換できます。一般的に使用されているすべての暗号は、公開されているアルゴリズムに基づいているか、オープンソースであるため、分析攻撃 (つまり、使用されているアルゴリズムまたはプロトコルの「構造上の弱点」) がなく、キーが他の方法で入手できない (盗難、恐喝、またはコンピュータ システムの侵害など) と仮定すると、システムのセキュリティを決定するのはキーの入手の難しさだけです。システムのセキュリティはキーのみに依存するという広く受け入れられている概念は、オーギュスト ケルクホフス(1880 年代) とクロード シャノン(1940 年代) によって明確に定式化されており、それぞれケルクホフスの原理とシャノンの格言として知られています。

したがって、鍵は、ブルートフォース攻撃（どの暗号化アルゴリズムに対しても可能）が実行不可能なほど十分に長くなければなりません。つまり、実行に時間がかかりすぎたり、メモリを大量に消費したりしないということです。シャノンの情報理論に関する研究は、いわゆる「完全な秘密性」を実現するには、鍵の長さが少なくともメッセージと同じで、一度だけ使用する必要があることを示しました（このアルゴリズムはワンタイムパッドと呼ばれます）。これと、そのような長い鍵を管理する実際上の困難を考慮して、現代の暗号化の実践では、暗号化の要件としての完全な秘密性の概念を放棄し、代わりに計算セキュリティに焦点を合わせています。計算セキュリティでは、暗号化されたテキストを解読するための計算要件は、攻撃者にとって実行不可能でなければなりません。

暗号化システムは、多くの場合、ファミリーにグループ化されます。一般的なファミリーには、対称システム（AESなど）と非対称システム（RSAや楕円曲線暗号[ECC]など）が含まれます。これらは、使用される中心アルゴリズム（ECCやFeistel暗号など）に従ってグループ化されることもあります。これらはそれぞれ暗号化の複雑さのレベルが異なるため、使用されるアルゴリズムに応じて、同じレベルのセキュリティに対して異なるキーサイズを持つことが一般的です。たとえば、非対称RSAを使用した1024ビットキーで利用できるセキュリティは、対称アルゴリズムの80ビットキーとほぼ同等のセキュリティであると考えられています。^[1]

実際のセキュリティの程度は、より多くの計算能力とより強力な数学的分析方法が利用可能になるにつれて、時間の経過とともに変化します。このため、暗号学者は、アルゴリズムまたはキーの長さが潜在的な脆弱性の兆候を示しているという指標を調べ、より長いキー サイズまたはより難しいアルゴリズムに移行する傾向があります。たとえば、2007 年 5 月の時点で^{[アップデート]}、1039 ビットの整数は、11 か月かけて 400 台のコンピューターを使用して、特殊数体ふるいで因数分解されました。 ^[2]因数分解された数は特殊な形式であり、特殊数体ふるいは RSA キーには使用できません。この計算は、700 ビットの RSA キーを破ることとほぼ同等です。ただし、これは、安全なオンライン商取引で使用される 1024 ビットの RSA キーは、近い将来に破られる可能性があるため、廃止されるべきであるという事前の警告である可能性があります。暗号学教授のアージェン・レンストラは、「前回、特別な数字から非特別な因数分解が難しい数字まで一般化するのに9年かかった」と述べ、1024ビットのRSA鍵は死んだのかと尋ねられたとき、「その質問への答えは、無条件にイエスです」と答えた。^[3]

2015年のLogjam攻撃は、 1024ビット以下の一般的な素数係数が1つまたは数個しか使用されていない場合にDiffie-Hellman鍵交換を使用することのさらなる危険性を明らかにしました。当時はやや一般的だったこの手法により、少数の素数を攻撃する代償として大量の通信が危険にさらされる可能性がありました。^{[4] [5]}

対称暗号が、そのアルゴリズムの構造的な弱点を悪用することで現時点では解読不可能であるとしても、ブルート フォース攻撃と呼ばれる方法でキーの空間全体を調べることは可能かもしれません。対称鍵が長くなると、ブルート フォース検索に指数関数的に多くの作業が必要になるため、対称鍵が十分に長いと、この攻撃方法は非現実的になります。

長さがnビットのキーの場合、2 ^{n 通り}のキーが考えられます。この数はnが増加するにつれて急速に増加します。128 ビットのキーをすべて試すために必要な膨大な操作数 (2 ¹²⁸ ) は、当面は従来のデジタル コンピューティング技術では実現不可能と広く考えられています。 ^[6]ただし、グローバーのアルゴリズムを実行できる量子コンピューターは、可能性のあるキーをより効率的に検索できます。適切なサイズの量子コンピューターであれば、128 ビットのキーを 64 ビットのセキュリティに縮小でき、これはほぼDESに相当します。これが、 AES が256 ビット以上のキー長をサポートしている理由の 1 つです。^[a]

IBM のLucifer 暗号は、1974 年にデータ暗号化標準となるもののベースとして選ばれました。Lucifer の鍵長は 128 ビットから56 ビットに短縮されましたが、NSAと NIST は、当時は非政府機関の保護にはこれで十分だと主張しました。NSA は大規模な計算リソースと多額の予算を持っています。Whitfield DiffieやMartin Hellmanなどの暗号学者は、このため暗号が弱くなり、NSA のコンピューターは総当たり並列計算によって DES 鍵を 1 日で解読できると不満を述べました。NSA はこれに異議を唱え、総当たり DES には「約 91 年」かかると主張しました。^[7]

しかし、1990年代後半になると、大企業や政府が購入できるような特注のハードウェアを使えば、DESは数日で解読できることが明らかになりました。^{[8] [9]} Cracking DES (O'Reilly and Associates)という本には、1998年に限られたリソースを持つサイバー人権団体がブルートフォース攻撃で56ビットDESを破ることに成功したことが記されています。EFF DES crackerを参照してください。そのデモンストレーション以前から、56ビットは一般的な用途の対称アルゴリズムキーとしては長さが不十分であると考えられていました。このため、ほとんどのセキュリティアプリケーションではDESがトリプルDESに置き換えられました。トリプルDESは、168ビットのキー（トリプルキー）を使用すると112ビットのセキュリティになります。^[1]

2001年に発行されたAdvanced Encryption Standardでは、128、192、または256ビットのキーサイズが使用されています。多くの観察者は、量子コンピュータが利用可能になるまで、 AES品質の対称アルゴリズムには128ビットで十分であると考えています。 ^[要出典]しかし、2015年現在、米国国家安全保障局は量子コンピューティング耐性アルゴリズムに切り替える計画のガイダンスを発行しており、現在、最高機密に分類されるデータには256ビットのAESキーが必要です。^[10]

2003年、米国国立標準技術研究所（NIST）は、 2015年までに80ビットキーを段階的に廃止することを提案しました。2005年時点では、80ビットキーは2010年までしか許可されていませんでした。^[11]

2015年以降、NISTのガイダンスでは「鍵共有に112ビット未満のセキュリティ強度を提供する鍵の使用は禁止されています」とされています。NISTが承認した対称暗号化アルゴリズムには、3鍵トリプルDESとAESがあります。2鍵トリプルDESとSkipjackの承認は2015年に取り消されました。NSAのFortezzaプログラムで使用されているSkipjackアルゴリズムは80ビットの鍵を採用しています。^[1]

公開鍵暗号システムの有効性は、整数因数分解などの特定の数学的問題の扱いにくさ（計算上および理論上）に依存します。これらの問題は解決に時間がかかりますが、通常、ブルートフォースですべての可能なキーを試すよりも高速です。したがって、非対称キーは、対称アルゴリズムキーと同等の攻撃耐性を得るためには、より長くする必要があります。最も一般的な方法は、将来、 十分に強力な量子コンピューターに対して脆弱であると想定されています。

2015年以来、NISTはRSAに対して最低2048ビットの鍵を推奨している。^[12]これは少なくとも2002年以来広く受け入れられている最低1024ビットの推奨事項の更新である。^[13]

1024ビットのRSA鍵は80ビットの対称鍵と強度が同等で、2048ビットのRSA鍵は112ビットの対称鍵と、3072ビットのRSA鍵は128ビットの対称鍵と、15360ビットのRSA鍵は256ビットの対称鍵と同等です。^[14] 2003年にRSA Securityは、1024ビットの鍵は2006年から2010年の間に解読可能になる可能性が高いが、2048ビットの鍵は2030年まで十分であると主張しました。^[15] 2020年現在、^{[アップデート]}解読されたことが公に知られている最大のRSA鍵は829ビットのRSA-250です。 ^[16]

有限体Diffie-Hellmanアルゴリズムは、同じキー サイズの場合、RSA とほぼ同じキー強度を持ちます。Diffie-Hellman を破るための作業係数は離散対数問題に基づいていますが、これは RSA の強度の基盤となる整数因数分解問題に関連しています。したがって、2048 ビットの Diffie-Hellman キーは、2048 ビットの RSA キーとほぼ同じ強度を持ちます。

楕円曲線暗号（ECC）は、より短い鍵で同等の安全性を持つ非対称アルゴリズムの代替セットであり、同等の対称アルゴリズムの約2倍のビットしか必要としません。256ビットの楕円曲線Diffie-Hellman （ECDH）鍵は、128ビットのAES鍵とほぼ同じ安全係数を持っています。^[12 ] 109ビット長の鍵を使用して楕円鍵アルゴリズムで暗号化されたメッセージは、2004年に解読されました。^[17]

NSAは以前、SECRETレベルまでの機密情報の保護には256ビットのECCを推奨し、TOP SECRETには384ビットを推奨していた。^[10] 2015年には、2024年までに量子耐性アルゴリズムに移行する計画を発表し、それまではすべての機密情報に384ビットを推奨している。^[18]

最もよく知られている 2 つの量子コンピューティング攻撃は、ショアのアルゴリズムとグローバーのアルゴリズムに基づいています。この 2 つのうち、ショアのアルゴリズムの方が現在のセキュリティ システムにとって大きなリスクをもたらします。

ショアのアルゴリズムの派生は、 RSA、ディフィー・ヘルマン、楕円曲線暗号など、主流の公開鍵アルゴリズムすべてに対して有効であると広く推測されている。量子コンピューティングの専門家であるジル・ブラサード教授によると、「RSA 整数を因数分解するのに必要な時間は、同じ整数を単一の RSA 暗号化の係数として使用するのに必要な時間と同程度です。言い換えると、量子コンピュータで RSA を破るのにかかる時間 (乗法定数まで) は、従来のコンピュータで正当に使用するのにかかる時間と同じである」。ショアのアルゴリズムを実行できる十分に大きな量子コンピュータが利用可能になった場合、これらの公開鍵アルゴリズムはどの鍵サイズでも安全ではないというのが一般的な見解です。この攻撃が意味するのは、電子商取引やインターネット バンキングを保護するために使用されるユビキタスSSLや、機密性の高いコンピューティング システムへのアクセスを保護するために使用されるSSHなど、現在の標準ベースのセキュリティ システムを使用して暗号化されたすべてのデータが危険にさらされるということです。公開鍵アルゴリズムを使用して保護された暗号化データはアーカイブすることができ、後で解読される可能性があります。これは一般に、遡及的/遡及的復号化または「今すぐ収集、後で復号化」と呼ばれます。

主流の対称暗号 ( AESやTwofishなど) と衝突耐性ハッシュ関数 ( SHAなど) は、既知の量子コンピューティング攻撃に対してより優れたセキュリティを提供すると広く推測されています。これらは、グローバーのアルゴリズムに対して最も脆弱であると広く考えられています。ベネット、バーンスタイン、ブラッサード、およびヴァジラニは 1996 年に、量子コンピュータでのブルートフォース キー検索は、基礎となる暗号化アルゴリズムの約 2 ^{n /2}回の呼び出しよりも高速にはできないことを証明しました。これは、従来のケースでの約 2 ^{nと比較して高速です。 [19]}したがって、大規模な量子コンピュータでは、nビットのキーは少なくともn /2 ビットのセキュリティを提供できます。量子ブルート フォースは、キーの長さを 2 倍にすることで簡単に破られ、通常の使用では追加の計算コストは​​ほとんどありません。これは、量子コンピュータに対して 128 ビットのセキュリティ評価を達成するには、少なくとも 256 ビットの対称キーが必要であることを意味します。前述のように、NSAは2015年に量子耐性アルゴリズムへの移行を計画していると発表した。^[10]

2016 年の量子コンピューティングに関する FAQ で、NSA は次のように断言しました。

「十分に大きな量子コンピュータが構築されれば、鍵の確立とデジタル署名に使用されている、広く普及しているすべての公開鍵アルゴリズムを破ることができるだろう。[...] 量子コンピューティング技術は、現在広く使用されている公開鍵アルゴリズムよりも対称アルゴリズムに対してはるかに効果が低いことが一般的に認められている。公開鍵暗号化では、将来の量子コンピュータから保護するために基本設計の変更が必要であるが、対称鍵アルゴリズムは、十分に大きな鍵サイズが使用されている限り安全であると考えられている。[...] 公開鍵アルゴリズム ( RSA、Diffie-Hellman、[楕円曲線 Diffie–Hellman] ECDH、および[楕円曲線デジタル署名アルゴリズム] ECDSA ) はすべて、十分に大きな量子コンピュータによる攻撃に対して脆弱である。[...] NSA の外部では、興味深い量子耐性のある公開鍵アルゴリズムがいくつか提案されているが、NISTによって標準化されたものはなく、NSA は現時点で商用の量子耐性標準を指定していない。 NSA は、NIST が広く受け入れられ、標準化された量子耐性アルゴリズムの開発に主導的な役割を果たすことを期待しています。[...] 暗号コミュニティの関心の高さを考えると、今後 10 年間で量子耐性アルゴリズムが広く利用できるようになることを期待しています。[...] AES-256 および SHA-384 アルゴリズムは対称的であり、大規模な量子コンピューターによる攻撃に対して安全であると考えられています。」^[20]

2022年のプレスリリースで、NSAは次のように通知しました。

「暗号解読に関連する量子コンピュータ（CRQC）は、現在使用されている公開鍵システム（非対称暗号と呼ばれることもある）を破る可能性がある。量子コンピューティングにおける外国の取り組みを考えると、CRQCが実現可能になった場合に国家安全保障システム（NSS）と関連資産の持続的な保護を保証するために、今こそ[量子耐性] QRアルゴリズムへの移行を計画、準備し、予算を組むべき時である。」^[21]

2022年9月以降、NSAは2016年1月に最初にリリースされた商用国家安全保障アルゴリズムスイート（現在はCNSA 1.0と呼ばれています）から商用国家安全保障アルゴリズムスイート2.0（CNSA 2.0）に移行しており、その概要は以下のとおりです。^{[22] [b]}

CNSA2.0 について

CNSA1.0

• キーストレッチ

• 鍵管理に関する推奨事項 - パート 1: 一般、NIST 特別出版物 800-57。2007 年 3 月
• Blaze, Matt、Diffie, Whitfield、Rivest, Ronald L.、他「適切な商用セキュリティを提供する対称暗号の最小キー長」1996 年 1 月
• Arjen K. Lenstra、Eric R. Verheul: 暗号鍵サイズの選択。J. Cryptology 14(4): 255-293 (2001) — Citeseer リンク

• www.keylength.com: オンラインのキー長計算機
• 量子コンピューティングの影響について議論する記事
• NIST 暗号化ツールキット
• Burt Kaliski : TWIRL と RSA キー サイズ (2003 年 5 月)