SHA3を実装してみた その2 自前実装の速度は?

というわけでその2です。今回は自前で実装した(コンパイラの最適化任せ+リファレンスコードを見ていない)ルーチンでテストした結果です。

昨日実装したコードと似ていますが少し最適化された物を使っています。

本格的に最適化されたコードを使用すればもう少し速度は向上できるはずですが、それでもやっぱり参考にはなると思いますので。

実行環境は前の環境と同じ

前回の各ハッシュアルゴリズムでの時間測定と同じです。

ただ、今回SHA3を実装したタイミングで、自前実装でのSHA3が予想より遅かったので、いくつかアルゴリズムの見直し(実装手順書にある処理の最適化についての指示により変更した物)や、ルーチンのインライン化などを行っています。

特に前回はバイトオーダーの調整処理がインライン化されておらず、リトルエンディアンの処理時に処理がないのに関数呼び出しが大量に入っていた関係で速度が低下していたことに気がついて

その部分をインライン化したことで前回から見れば速度が向上しています。

対象ファイルはFedora17 Live Desktopのイメージファイル(ISOイメージ)です。

x86版実行ファイルでの測定結果

filesize : 677380096 bytes. QPC Freq: 2603896 count per second.

CRC32 [ 4373375 count ( 1.68 sec)] : 31fef78a

MD5 [ 5194917 count ( 2.00 sec)] : a1519ac8688bfe7341999a48fc4a4088

SHA1 [ 9434550 count ( 3.62 sec)] : 5de301a65ff3217e953c72f283bf3374760374d8

SHA224 [ 14872597 count ( 5.71 sec)] : 99438deb60bab4d5f9ca578014fb301e94becea5c9f74efc798c48f4

SHA256 [ 14874567 count ( 5.71 sec)] : 26027f4d4686f1df186b31ce773dbb903db18f4b1aa37a1e37f0fa6ff4111f42

SHA384 [ 32544764 count ( 12.50 sec)] : cdd2d67af9fe397cae1407559fda12c7b01498c8eb8573f7239ec4b5945b887fe3c7057058622a9d4384259a1d06fb46

SHA512 [ 32537395 count ( 12.50 sec)] : 572eb8e2125f288beb18f47a86fc3b93222caea6cda16b05b5cea86d7ef8e99a0541479e7df7ce9f3c19fa49ed395c098e9ed0f3e4f3667040d7142984bee41e

SHA3_224 [ 56526528 count ( 21.71 sec)] : 035c1edd9029d06127575f3f53813f211a87a7f29fd35f05a238538f

SHA3_256 [ 59649771 count ( 22.91 sec)] : b1f62a89e86b3d3f01f725c51ca286c506d573acde6a6d9bb9d5a75df0631de0

SHA3_384 [ 77777575 count ( 29.87 sec)] : 2efa282b32eddd8d6c1b597f2bc7df130ec28f26406981fb85206680fc14b07512e15d54eb46f33892b50182b5733b7f

SHA3_512 [ 112423054 count ( 43.17 sec)] : 8527544560addd543ea99bfd72271a147d0995a1c5e3b6a9b42e59c415dffc6e3ebf77af8c1212429ec1afc1faadf953fda8d7ac08b9fba2fa723e8fb54f8161

RIPEMD128 [ 11602479 count ( 4.46 sec)] : 02384110c7356872fbdff4d0ea761a33

RIPEMD160 [ 16962856 count ( 6.51 sec)] : d8b649a6a64223f6c563dca7cfb89767b3245dbe

RIPEMD256 [ 13515557 count ( 5.19 sec)] : f7ae3634117f7ded469262d8777cefadf52fbf422b2658471e5449b32af8614c

RIPEMD320 [ 18259471 count ( 7.01 sec)] : deaa8ea84e2c361c5948f6b95a00ecb75437ba9e4d04090064a46b80ac37b3f0c0d2556c1349c5b3

Whirlpool [ 109347656 count ( 41.99 sec)] : 404cba5b0bee00850d65d99650e7a465ee0e494b4b5f06cd1d75ac0c48262feed7f763a4060f8f69e913cea1a09f1328a5903783f81c7047b2347f82fe1e9725

x64版実行ファイルでの測定結果

filesize : 677380096 bytes. QPC Freq: 2603896 count per second.

CRC32 [ 4820228 count ( 1.85 sec)] : 31fef78a

MD5 [ 4900039 count ( 1.88 sec)] : a1519ac8688bfe7341999a48fc4a4088

SHA1 [ 8031272 count ( 3.08 sec)] : 5de301a65ff3217e953c72f283bf3374760374d8

SHA224 [ 14879475 count ( 5.71 sec)] : 99438deb60bab4d5f9ca578014fb301e94becea5c9f74efc798c48f4

SHA256 [ 14882901 count ( 5.72 sec)] : 26027f4d4686f1df186b31ce773dbb903db18f4b1aa37a1e37f0fa6ff4111f42

SHA384 [ 9186387 count ( 3.53 sec)] : cdd2d67af9fe397cae1407559fda12c7b01498c8eb8573f7239ec4b5945b887fe3c7057058622a9d4384259a1d06fb46

SHA512 [ 9180756 count ( 3.53 sec)] : 572eb8e2125f288beb18f47a86fc3b93222caea6cda16b05b5cea86d7ef8e99a0541479e7df7ce9f3c19fa49ed395c098e9ed0f3e4f3667040d7142984bee41e

SHA3_224 [ 17582224 count ( 6.75 sec)] : 035c1edd9029d06127575f3f53813f211a87a7f29fd35f05a238538f

SHA3_256 [ 18623656 count ( 7.15 sec)] : b1f62a89e86b3d3f01f725c51ca286c506d573acde6a6d9bb9d5a75df0631de0

SHA3_384 [ 24140869 count ( 9.27 sec)] : 2efa282b32eddd8d6c1b597f2bc7df130ec28f26406981fb85206680fc14b07512e15d54eb46f33892b50182b5733b7f

SHA3_512 [ 35134557 count ( 13.49 sec)] : 8527544560addd543ea99bfd72271a147d0995a1c5e3b6a9b42e59c415dffc6e3ebf77af8c1212429ec1afc1faadf953fda8d7ac08b9fba2fa723e8fb54f8161

RIPEMD128 [ 7921398 count ( 3.04 sec)] : 02384110c7356872fbdff4d0ea761a33

RIPEMD160 [ 12470013 count ( 4.79 sec)] : d8b649a6a64223f6c563dca7cfb89767b3245dbe

RIPEMD256 [ 7935441 count ( 3.05 sec)] : f7ae3634117f7ded469262d8777cefadf52fbf422b2658471e5449b32af8614c

RIPEMD320 [ 12208959 count ( 4.69 sec)] : deaa8ea84e2c361c5948f6b95a00ecb75437ba9e4d04090064a46b80ac37b3f0c0d2556c1349c5b3

Whirlpool [ 31065831 count ( 11.93 sec)] : 404cba5b0bee00850d65d99650e7a465ee0e494b4b5f06cd1d75ac0c48262feed7f763a4060f8f69e913cea1a09f1328a5903783f81c7047b2347f82fe1e9725

というわけで

自前実装のせいだと思いますが、ちょっと速度が遅いです。

SHA3の特徴として、ダイジェスト長が短くなると同じ大きさのファイルのハッシュ取得時間が短くなると言う特徴があります。

これは、ハッシュの撹拌作業時に使っている「スポンジ構造」と呼ばれる構造とダイジェスト長による撹拌タイミングの変更があります。

SHA3として採用されているkeccakと呼ばれるアルゴリズムのうち、実際に使っているのはkeccak-f[1600]と言う形式になります。

後ろの[1600]はブロック全体のビット数であり、これを固定とし、

ブロック全体のビット数[b] = 一度に処理するデータビット数[r] + スポンジ構造の予備ビット数

で計算されます。で、SHA3では通常

スポンジ構造の予備ビット数 = 2 * ダイジェストビット数[n]

となるので、ダイジェスト長が短ければ短いほど一度に処理するデータビット数が大きくなるため時間が短くなる、と言うわけです。

(ちなみに、r <= 0となるとハッシュが計算できないので、そのときはダイジェスト長を無視してcを与えることでハッシュを取得することが出来ます)

また、x86版とx64版ではかなり速度が異なっていますが、これはkeccak-f[1600]ではワード長が64bitになっているため、x64と相性が良いからです。

SHA3では使われませんが、keccak-f[800]と言う形式ではワード長が32bitとなるため、x86でも高速になりますが現段階では使われません。

keccak-f[1600]以外は別の場所のハッシュルーチンとして使うとおもしろいかもしれません。

速度を改善しても今のところ使い道が・・・

ないんですね~。というかSHA3があまりに無名すぎるような気がします。

そのため、今のところは正しく計算できていることが確認できればまあいいか、と言う感覚ですね。

一応コンパイラによりコンパイルされたアセンブルコードも見ていますが、頑張ってforを展開していたり、レジスタの割り振りなので手が出せない状態ですので・・・。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

この記事のトラックバック用URL