ファイルを暗号化/復号化するアプリケーションを開発しました。ユーザーは、AES、Blowfish、または PBE の 3 つの異なるアルゴリズムから選択できます。そして、暗号化、復号化、および合計時間が表示されます。「時間」の要素に関して、3 つのアルゴリズムの効率を比較しようとしています。大学の教授から、これら 3 つのアルゴリズムの時間計算量を研究するように言われました。時間の複雑さを計算することに加えて、速度に関してアルゴリズムの効率を判断する他の方法は何ですか? 学習を開始して目的を達成できる特定のリソースはありますか? 私の目的は、特定のファイル形式で特定のタイプのアルゴリズムが別のアルゴリズムよりも高速に動作する理由を結論付けることです (たとえば、pdf ファイルに関しては、mp3 ファイルよりも aes の方が高速である可能性があります)。
[私の友人は、さまざまなプロセッサでアプリケーションを実行し、プロセッサの種類とアプリケーションのパフォーマンスの間に何らかの関係があるかどうかを判断することを提案しました。彼は正しいですか？] - ありがとう。
他の人がすでに指摘しているように、暗号化アルゴリズムの時間の複雑さは常に入力サイズに比例します。明らかに高速化することはできず、超線形の複雑さは実用的ではありません。また、速度が入力の種類に依存する暗号についても知りません。たとえば、10 MB の PDF ファイルを暗号化するか、10 MB の MP3 を暗号化するかにかかわらず、違いはありません。
したがって、速度の違いは、具体的なハードウェア アーキテクチャ上での暗号の具体的な実装の速さにのみ帰結します。人気のある OpenSSL ライブラリには、特定の実装の速度を示すベンチマーク ツールが組み込まれています。32 ビット Ubuntu を実行している Intel Atom プロセッサで AES-256 と Blowfish を比較する実行例を次に示します (PBE は暗号ではありません)。
$ openssl speed aes-256-cbc bf-cbc
Doing aes-256 cbc for 3s on 16 size blocks: 2156930 aes-256 cbc's in 3.00s
Doing aes-256 cbc for 3s on 64 size blocks: 563323 aes-256 cbc's in 3.00s
Doing aes-256 cbc for 3s on 256 size blocks: 142873 aes-256 cbc's in 3.00s
Doing aes-256 cbc for 3s on 1024 size blocks: 35857 aes-256 cbc's in 3.00s
Doing aes-256 cbc for 3s on 8192 size blocks: 4487 aes-256 cbc's in 3.00s
Doing blowfish cbc for 3s on 16 size blocks: 10063235 blowfish cbc's in 3.00s
Doing blowfish cbc for 3s on 64 size blocks: 2759400 blowfish cbc's in 3.00s
Doing blowfish cbc for 3s on 256 size blocks: 705523 blowfish cbc's in 3.00s
Doing blowfish cbc for 3s on 1024 size blocks: 177777 blowfish cbc's in 3.00s
Doing blowfish cbc for 3s on 8192 size blocks: 22266 blowfish cbc's in 3.00s
OpenSSL 1.0.1c 10 May 2012
built on: Tue Mar 19 19:10:21 UTC 2013
options:bn(64,32) rc4(8x,mmx) des(ptr,risc1,16,long) aes(partial) blowfish(idx)
compiler: cc -fPIC -DOPENSSL_PIC -DZLIB -DOPENSSL_THREADS -D_REENTRANT -DDSO_DLFCN -DHAVE_DLFCN_H -DL_ENDIAN -DTERMIO -g -O2 -fstack-protector --param=ssp-buffer-size=4 -Wformat -Werror=format-security -D_FORTIFY_SOURCE=2 -Wl,-Bsymbolic-functions -Wl,-z,relro -Wa,--noexecstack -Wall -DOPENSSL_NO_TLS1_2_CLIENT -DOPENSSL_MAX_TLS1_2_CIPHER_LENGTH=50 -DOPENSSL_BN_ASM_PART_WORDS -DOPENSSL_IA32_SSE2 -DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_GF2m -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DMD5_ASM -DRMD160_ASM -DAES_ASM -DVPAES_ASM -DWHIRLPOOL_ASM -DGHASH_ASM
The 'numbers' are in 1000s of bytes per second processed.
type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes
blowfish cbc 53670.59k 58867.20k 60204.63k 60681.22k 60801.02k
aes-256 cbc 11503.63k 12017.56k 12191.83k 12239.19k 12252.50k
特定の実装を使用している特定のマシンでは、Blowfish が AES-256 よりもかなり高速であることがわかります。しかし、それは 1 つのデータ ポイントにすぎません。
なぜある暗号が別の暗号よりも高速なのかという質問に答えるには、アルゴリズムの詳細とさまざまなハードウェア プラットフォームのパフォーマンス特性を調べる必要があります。また、最速の実装は、最大のパフォーマンスを引き出すためにアセンブリ言語で記述されることが多いことに注意してください。
問題の 3 つのような対称暗号化アルゴリズムでは、通常、アルゴリズムの開始に使用される一定の時間と、暗号化するデータの量に応じて変化する時間があります。1 つのアルゴリズムは起動が遅くても、開始時の暗号化は高速である場合があります。他のアルゴリズムは、起動は高速ですが、ビッグデータでは低速です。
したがって、目的に応じて最速のアルゴリズムを選択することは、暗号化/復号化する必要があるデータの量と、その量のデータでどれだけうまく機能するかに依存します.
これに加えて、各アルゴリズムの暗号化強度も考慮する必要があります。セキュリティ要件を満たすのに十分安全でない場合、最速のアルゴリズムを選択しても役に立ちません。
時間の複雑さを計算することに加えて、速度に関してアルゴリズムの効率を判断する他の方法は何ですか?
それぞれの実際の実装をベンチマーク/プロファイリングする以外は、それがほとんどの方法です。これにはまだ質問していないことがあると思います。