encryption - Big-O表記法：暗号化アルゴリズム

Question

私は現在、さまざまな暗号化アルゴリズムによるデータの暗号化に関する論文を完成させています。

私はジャーナルや論文を読むことに多くの時間を費やしましたが、まだそれらのパフォーマンスの複雑さの記録を見つけることができませんでした。

次のアルゴリズムのBig-Oの複雑さを知っている人はいますか？

• RSA
• DES
• トリプルDES（DESと同じオーダーになると思います）
• AES
• ふぐ

前もって感謝します; 評判が良く引用可能な情報源へのリンクを提供していただければ幸いです。

Answer 1

部分的な回答: RSA Laboratories は、rsa.com からアーカイブされたこの分析を提供し、RSA 操作と DES を比較しています。

RSA アルゴリズムの速度はどのくらいですか?

暗号化、復号化、署名、または検証のいずれであっても、「RSA 操作」は基本的に剰余累乗です。この計算は、一連の剰余乗算によって実行されます。

実際のアプリケーションでは、公開鍵に小さい公開指数を選択するのが一般的です。実際、ユーザーのグループ全体が同じ公開指数を使用できますが、それぞれ異なる係数が適用されます。(公開指数が固定されている場合、モジュラスの素因数にはいくつかの制限があります。) これにより、暗号化は復号化よりも高速になり、検証は署名よりも高速になります。RSA アルゴリズムの実装に使用される典型的な剰余累乗アルゴリズムでは、 公開鍵の操作に O(k^2) ステップ、秘密鍵の操作に O(k^3)ステップ、鍵の生成に O(k^4) ステップを要します。 k はモジュラスのビット数です。. 高速フーリエ変換 (FFT) に基づく方法などの「高速乗算」技法では、必要なステップが漸近的に少なくなります。ただし、実際には、ソフトウェアの複雑さが増し、一般的なキー サイズでは実際には遅くなる可能性があるため、それほど一般的ではありません。

RSA アルゴリズムの多くの市販ソフトウェアおよびハードウェア実装の速度と効率は急速に向上しています。最新の数値については、http://www.rsasecurity.com/を参照してください。

比較すると、DES (セクション 3.2 を参照) やその他のブロック暗号は、RSA アルゴリズムよりもはるかに高速です。DES は、実装にもよりますが、通常、ソフトウェアでは少なくとも 100 倍、ハードウェアでは 1,000 ～ 10,000 倍高速です。RSA アルゴリズムの実装は、需要が高いため、おそらく今後数年間でギャップを少し狭めるでしょうが、ブロック暗号も同様に高速になります。

Answer 2

注意すべきことの 1 つ (論文にコーディングするかどうかによって異なります): RSA の実際の実装のほとんどは、実際には RSA を使用して AES 鍵交換を行います。したがって、それぞれ暗号化/復号化の O(k^2) および O(k^3) 操作は、AES キーの暗号化に関してのみです。ソフトウェア/ハードウェアで 100 ～ 10K 倍高速な AES は、交換されるデータの実際のブロック暗号化を行います。このようにして、法外な計算コストを支払うことなく (RSA 経由で) PKI を利用できます。

Answer 3

対称暗号の複雑さは、1 つのブロックに対して O(1) です。

それはあなたのリストのRSAだけを残します、そして答えは非常に実装に依存します、大きな整数乗算がどれだけうまく実装されているか、指数の選択などに依存します...