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

Question

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

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

次のアルゴリズムのBig-Oの複雑さは誰にも分かりますか？

• RSA
• DES
• （私はDESと同じオーダーであることが期待される）トリプルDES
• AES
• フグ

は事前にありがとうございます。あなたが評判が良く、引用可能な情報源へのリンクを提供できれば、非常に感謝します。

Answer 1

部分的な答え：RSA研究所は、暗号化復号化、署名、または検証することは、本質的にべき乗剰余演算であるかどうか「RSA操作」DES

アン対RSAオペレーションを比較すると、この分析http://www.rsa.com/rsalabs/node.asp?id=2215を提供します。この計算は、一連のモジュラ乗算によって実行されます。

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

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

比較すると、DES（3.2節を参照）、他のブロック暗号はRSAアルゴリズムよりもはるかに高速です。 DESは、ソフトウェアによっては一般的には100倍、ハードウェアでは1,000〜10,000倍の速さで実装されます。 RSAアルゴリズムの実装は、需要の高まりから、今後数年間に少しのギャップを狭めるでしょうが、ブロック暗号も高速化するでしょう。

Answer 2

対称暗号の複雑さは1つのブロックでO（1）です。

あなたのリストの唯一のRSAを残し

、と答えは、大きな整数乗算が実装されているどれだけに依存し、非常に実装に依存し、指数の選択は、等...

Answer 3

一つのことに注意する（場合によってはあなたの論文にコーディングしています）：RSAの実際の実装のほとんどは、実際にRSAを使用してAES鍵交換を行います。したがって、暗号化/復号化のためのO（k^2）およびO（k^3）操作はそれぞれ、AES鍵の暗号化に関してのみ行われます。ソフトウェア/ハードウェアで100-10K倍高速化されたAESは、交換されるデータの実際のブロック暗号を実行します。この方法では、過度の計算コストをかけずにPKI（RSA経由）を利用できます。