RSA アルゴリズムが解読された場合、暗号化の将来はどうなるでしょうか?

インターネットのセキュリティ層に一夜にして巨大な亀裂が生じたらどうなるか考えたことがありますか? 亀裂が暗号アルゴリズムの数学的基礎の奥深くまで達したらどうなるでしょうか? 今、そのシナリオが現実になったようです。最近、ドイツの暗号学者クラウス・ペーター・シュノア氏は論文の中で、「RSA 暗号化システムを解読する方法」を発見したと主張した。

この問題は、暗号学および量子暗号学のコミュニティから幅広い注目を集めています。論文の内容は検証されていないが、情報セキュリティに対する要求が高い多くの分野で現在RSA非対称暗号化アルゴリズムが大規模に使用されているため、これが事実であれば、多くのアプリケーションにセキュリティ上の影響を与えることは避けられないだろう。

このような状況に直面して、私たちは2つの疑問について考えざるを得ません。第一に、論文の内容は真実なのでしょうか。第二に、暗号化の将来はどうなるのでしょうか。RSAに代わる、量子コンピューターの時代でも安全な暗号化システム（ポスト量子暗号）は存在するのでしょうか。

本稿執筆時点では、数学者と暗号学者が論文の内容の信憑性についてまだ議論と検証を行っている一方、2 番目の疑問についてはすでに多くの人が考えており、この壊滅的な脆弱性に対処するための計画を立案し始めています。彼らは、切り替えをより簡単にするために、複数のプロトコルに実装された複数のアルゴリズムに基づいて構築された、より強力な基盤の構築に取り組んでいます。

暗号学者の中には、RSA に代わるものを探している人もいます。なぜなら、この論文の結果が真実であるかどうかに関わらず、RSA のセキュリティ問題はすでに業界の注目を集めているからです。 2010 年 7 月には、アメリカ国立標準技術研究所 (NIST) は、ユーザーに対して 2010 年 12 月 31 日までに 1024 ビット RSA アルゴリズムの使用を停止することを義務付けました。 RSA の責任者によると、RSA 1024 ビット アルゴリズムが解読されたという証拠はないものの、解読されるのは時間の問題であり、そうなると暗号化された情報の漏洩、デジタル署名の偽造、通信の盗聴といった結果につながるだろうとのことです。

さらに、技術の継続的な発展と量子コンピュータの応用により、RSA セキュリティは再び課題に直面することになります。 Google CEOのサンダー・ピチャイ氏はかつてこう予測した。

暗号学者たちは、いつでも潜在的な脆弱性が多数出現する可能性があるため、世界はより機敏にならなければならないと考えている。

RSAアルゴリズムの課題

大きな素数の因数分解

論文のタイトルは「SVPアルゴリズムによる整数の高速因数分解」で、著者は2011年にヨハン・ヴォルフガング・ゲーテ大学を退職した77歳のクラウス・シュノル氏であると報じられている。彼は尊敬される暗号学者であり、シュノア署名アルゴリズムは彼にちなんで名付けられました。暗号化において、Schnorr 署名は、Schnorr 署名アルゴリズムによって生成されるデジタル署名です。Schnorr 署名アルゴリズムは、そのシンプルさと効率性で知られるデジタル署名方式です。そのセキュリティは、特定の離散対数問題の解決困難性に基づいています。 Schnorr署名アルゴリズムは、より効率的でプライベートなブロックチェーンシステムを構築できるため、常にブロックチェーン開発者の注目を集めています。

RSA は、長い歴史と幅広い応用を持つもう 1 つのアルゴリズムです。これは、1977 年に Ron Rivest、Adi Shamir、Leonard Adleman によって提案された暗号化アルゴリズムです。このアルゴリズムは、主に大きな素数を分解する複雑さを利用してセキュリティを実現します。大きな素数の積は分解が難しいため、パスワードを解読するのは困難です。

過去 40 年間、RSA アルゴリズムはさまざまな攻撃の課題に直面してきました。公開された文書によると、解読された最長の RSA キーは 768 バイナリ ビットです。言い換えれば、768 ビットより長いキーは、少なくともまだ公表されていない限り、解読されていません。

シュノア氏の最新の論文は、実は近年発表された一連の論文の補足および更新版であり、大きな素数を分解する問題を、数学者が「はるかに小さな数で定義された多次元格子内で正しいベクトルを探す」と呼ぶ問題に言い換えたものだと言われている。この論文は主に理論的な内容であるため、RSA アルゴリズムのセキュリティが本当に限界に達したのか疑問に思う人が多くいます。しかし、これまでのところ、このアプローチは公に実証されておらず、実際に試した人の中にも効果がないと言う人がいる。

RSAの修正の難しさ

新たに発見された攻撃によってもたらされる問題を解決することは、何も新しいことではありません。ソフトウェア企業は通常、脆弱性を修正するためのパッチをリリースし、バグレポートを公開して、人々が発見した問題を報告するよう促します。しかし、シュノア氏の論文が確認されれば、どの企業も責任を負っていないプロトコルの基礎の弱点が明らかになることになる。

「RSA」という会社が長い間このアルゴリズムを所有していましたが、その特許が期限切れになったため、現在インターネット上で使用されている RSA 実装のほとんどは、もはや同社のものではありません。多くの人気のあるライブラリはオープンソースであり、コミュニティによって管理されています。

さらに悪いことに、論文に記載されている脆弱性が現実のものである場合、数行の新しいコードで簡単に修正することはできません (多くの脆弱性やバグとは異なり)。アルゴリズムのテストと展開には時間がかかるため、効果的なソリューションのリリースには何年もかかる場合があります。

また、多くの暗号化ソフトウェア パッケージは、異なるキーの長さを持つさまざまなアルゴリズム オプションの使用をサポートしているため、新しいアルゴリズムに切り替えるプロセスは簡単ではない可能性があります。公開鍵の検証に使用される証明書の階層を維持する認証インフラストラクチャを更新すると、さらに深刻な課題が発生する可能性があります。一部の主要ブラウザの現在のバージョンには、さまざまな証明機関からのルート証明書が付属しており、そのほとんどは RSA アルゴリズムに依存しています。

ブラウザ (または他のツール) のルート証明書を置き換えるには、多くの場合、新しいバージョンのリリースが必要になります。ルート証明書は非常に強力であるため、問題は非常に厄介になります。たとえば、一部の攻撃では、攻撃者が他のサイトになりすますために偽の証明書を挿入します。これまで、Verisign、Amazon、GoDaddy、Entrust などの主要な認証局の証明書は RSA アルゴリズムに依存していました。

量子の問題が課題を増大させる

量子コンピューティングの時代がもたらす課題にどう対処するかは、RSA セキュリティが直面するもう 1 つの大きな問題です。暗号コミュニティは、量子コンピューティングの時代が間もなく到来するのではないかと懸念しており、数年前から量子コンピューティングに抵抗できる代替手段を模索してきました。これは RSA のようなアルゴリズムにとって脅威となるでしょう。なぜなら、ピーター・ショアによって開発された量子コンピューティングの最も有名なアルゴリズムの 1 つは整数の因数分解だからです。

では、量子コンピューティングはどれほど強力なのでしょうか。たとえば、400 桁の整数を因数分解する場合、現在の最速のスーパーコンピューターでも 60 万年かかりますが、量子コンピューターを使用すれば数時間しかかからず、数分で実行できると言う人もいます。研究者たちは、2012年には量子コンピュータを使って、7と3の積に21を因数分解することに成功したと発表していたが、この2つの数字はそれほど大きくない。ただし、RSA 暗号化アルゴリズムは、大きな整数の素因数を因数分解するために必要な計算量と時間に大きく依存します。 RSA アルゴリズムの基本的な設計は、クラッキングのコストを増やすことでセキュリティを向上させることです。したがって、計算速度を上げることができるあらゆる方法は、この一般的に使用されている暗号化アルゴリズムのセキュリティを脅かすことになります。量子コンピューターはショアのアルゴリズムを高速化することができ、セキュリティ専門家は、量子コンピューティングによってRSAが簡単に解読できるようになる日が来ると警告している。そして私たちはこの瞬間に備えなければなりません。

RSA以外の新しい暗号システムの探索

犯罪者が量子コンピュータを使って攻撃を仕掛けるのではないかという懸念から、プロトコルやアルゴリズムがハッキングされるのを防ぐために、アルゴリズムを継続的に強化し始めています。 NIST のアプローチは、「量子耐性」または「ポスト量子」アルゴリズムの新しいコレクションを構築することです。この暗号化競争はすでに始まっています。

NISTは昨年夏、2016年後半に始まったコンテストの第3ラウンドの初期結果を発表した。これまでに 69 種類の異なるアルゴリズムが開発されており、そのうち 26 種類は優れたものであり、15 種類は最高のものです。もちろん、これら 15 個のアルゴリズムのうち、最終的に突破したのは 7 個であり、残りの 8 個は引き続き開発と研究が行われるか、特殊な用途向けにさらに改良される必要があります。

第 3 ラウンドの候補アルゴリズム 7 つは次のとおりです。

公開鍵暗号/KEM

• クラシック・マケリース
• クリスタル-カイバー
• NTRU
• サーベル

デジタル署名

• クリスタル-ジリチウム
• ファルコン
• 虹

3 回目のレビュー後、NIST は標準策定の次のステップの参考にするために、上記の 7 つの最終候補アルゴリズムを引き続きレビューします。 CRYSTALS-KYBER、NTRU、SABER はすべて格子ベースの方式であるため、NIST は最大で 1 つを標準として選択する予定です。 CRYSTALS-DILITHIUM および FALCON 署名スキームについても同様です。 NIST の見解では、格子困難問題に基づくこれらの方式は、公開鍵暗号化/KEM およびデジタル署名方式にとって「最も有望な汎用アルゴリズム」です。

NIST は、1978 年に Robert McEliece によって開発された、古い署名方法である Classic McEliece も選択しました。これは、1978 年に Robert McEliece によって設計および開発されました。代数符号理論に基づく非対称暗号化アルゴリズムであり、一連のエラー訂正コード Goppa を使用します。この暗号化システムでは、ゴッパ コードを秘密鍵として使用し、それを公開鍵として線形コードにエンコードします。公開鍵を復号化するには、秘密鍵を知っている必要があります。

McEliece 暗号化システムは広く採用されていませんが、非常に強力で安定しています。唯一の欠点は、公開鍵が最大 219 ビットと大きすぎるため、暗号化された情報が平文情報よりもはるかに大きくなり、送信中のエラー率が増加することです。さらに、非対称性のため、この技術はデジタル認証や署名には使用できません。この暗号化システムは 30 年間にわたって攻撃され、解読されてきましたが、依然として堅牢なままです。

最後のファイナリストは Rainbow と呼ばれ、多変量多項式構造に基づくデジタル署名方式です。これは多変量暗号システムに属し、攻撃者が解読するのが困難です。

RSA のこれらの新しい潜在的な代替品により、置き換えプロセスが容易にならない可能性があります。かなり遅いものもあれば、署名の生成やデータの暗号化に同じオプションを提供しないものもあります。また、多くのキーは、おそらく 500 KB 以上の大きなキーに依存しており、これは現在の多くのキー (数百バイトしかない場合もあります) よりもはるかに大きいものです。

公開鍵暗号の開発に貢献した暗号学者ホイットフィールド・ディフィー氏は、新たな提案の構築にはより多くの計算が必要になる可能性が高いと指摘した。もう一人の数学者、マーティン・ヘルマン氏は、世界は複数の異なるアルゴリズムを組み合わせた新しいプロトコルの開発を望んでいるかもしれないと述べた。プロトコルは、単に 1 つのアルゴリズムに頼ってランダム キーを作成し、データを暗号化するのではなく、複数のアルゴリズムを実行し、それらすべてのキーを新しいキーに結合する必要があります (おそらく XOR 経由、またはより複雑な一方向関数を使用)。

ヘルマン氏は、たとえ暗号資産災害がまだ到来していなくても、災害復旧計画を策定しておくことで、長年にわたって進化し激化してきた脅威から身を守ることができると警告した。彼はこう言った。

この記事は以下から翻訳されています:

https://www.csoonline.com/article/3613550/whats-next-for-encryption-if-the-rsa-algorithm-is-broken.html