ネットワーク上で多くのファイル（大きいものもあれば小さいものもあります）を比較する必要があります。そのため、すべてのクライアントですべてのファイルをハッシュし、ハッシュ値のみをネットワーク経由で送信することを計画しています。
ここでの主な目標はパフォーマンスです。これは、最小限のネットワークトラフィックを意味します。セキュリティは問題ではありません。また、2つの異なるファイルを誤って同一と見なしたくないので、
「ゼロ」の衝突があるはずです。そうは言っても、理論的には常に衝突が発生することはわかっていますが、実際に衝突に遭遇する機会は絶対に無視できるものにしたいと思っています。
だから私の質問は：このタスクに最適な.netハッシュ関数はどれですか？
私はバッファ付きリーダーを使用することを考えていましたMD5CryptoServiceProvider（CNGはすべてのクライアントで利用できるとは限らないため）。
それよりも優れたパフォーマンスを得る方法はありますか？（おそらく外部ライブラリを使用していますか？）
私は、.NETハッシュアルゴリズムが必要な同様の状況にありました。セキュリティよりも速度が重要なサーバー応答キャッシュに必要でした。このスレッドにたどり着いたとき、アルゴリズムの選択と32ビットと64ビットの実行のパフォーマンスの違いについての憶測に気づきました。この議論に科学を取り入れるために、利用可能なアルゴリズムのいくつかを実際にテストするためのコードを作成しました。組み込みのMD5、SHA1、SHA256、およびSHA512アルゴリズムをテストすることにしました。また、 force-netのCRC32実装とDamienGKitのCRC64実装も含めました。〜115MBのファイルでの私の結果は次のとおりです。
32ビットモードで実行しています。
ウォームアップフェーズ：
CRC32：390msで296 MiB /s[9C54580A]。
CRC64：1212msで95 MiB /s[636BCF1455BC885A]。
MD5：604msで191 MiB / s [mm / JVFusWMKcT / P +IR4BjQ==]。
SHA1：699msで165 MiB / s[WSFkGbnYte5EXb7kgp1kqbi2...]。
SHA256：1240msで93 MiB / s [USKMHQmfMil8 / KL / ASyE6rm/...]。
SHA512：2464msで47 MiB / s [Cp9cazN7WsydTPn +k4Xu359M...]。
最終実行：
CRC32：414msで279 MiB /s[9C54580A]。
CRC64：1203msで96 MiB /s[636BCF1455BC885A]。
MD5：588msで197 MiB / s [mm / JVFusWMKcT / P +IR4BjQ==]。
SHA1：707msで164 MiB / s[WSFkGbnYte5EXb7kgp1kqbi2...]。
SHA256：1200msで96 MiB / s [USKMHQmfMil8 / KL / ASyE6rm/...]。
SHA512：2441msで47 MiB / s [Cp9cazN7WsydTPn +k4Xu359M...]。
64ビットモードで実行しています。
ウォームアップフェーズ：
CRC32：373msで310 MiB /s[9C54580A]。
CRC64：986msで117 MiB /s[636BCF1455BC885A]。
MD5：584msで198 MiB / s [mm / JVFusWMKcT / P +IR4BjQ==]。
SHA1：627msで184 MiB / s[WSFkGbnYte5EXb7kgp1kqbi2...]。
SHA256：1112msで104 MiB / s [USKMHQmfMil8 / KL / ASyE6rm/...]。
SHA512：778msで149 MiB / s [Cp9cazN7WsydTPn +k4Xu359M...]。
最終実行：
CRC32：396msで292 MiB /s[9C54580A]。
CRC64：975msで119 MiB /s[636BCF1455BC885A]。
MD5：582msで199 MiB / s [mm / JVFusWMKcT / P +IR4BjQ==]。
SHA1：601msで192 MiB / s[WSFkGbnYte5EXb7kgp1kqbi2...]。
SHA256：1091msで106 MiB / s [USKMHQmfMil8 / KL / ASyE6rm/...]。
SHA512：738msで157 MiB / s [Cp9cazN7WsydTPn +k4Xu359M...]。
これらの結果は、.NETv4.5.2を実行しているコンパイル済みのリリースビルドASP.NETプロジェクトから取得されました。32ビットと64ビットの両方の結果は同じマシンからのものです。Visual Studioで、プロジェクトのTools > Options > Projects and Solutions > Web Projects > Use the 64 bit version of IIS Expressを変更するとともに、を介してモードを変更しました。Platform target
結果は実行ごとに少し変動しますが、CRC32（force-netによる）が最も速く、MicrosoftのMD5とSHA1がそれに続きます。不思議なことに、組み込みのMD5またはSHA1よりもDamienGKitのCRC64を選択しても、パフォーマンス上の利点はありません。64ビット実行はSHA512で大いに役立つようですが、他のものでは適度にしか役立ちません。
OPの質問に答えるには、組み込みのMD5またはSHA1が、衝突回避とパフォーマンスの最適なバランスを提供する可能性があるように思われます。
私のコードは次のとおりです。
Stopwatch timer = new Stopwatch();
Force.Crc32.Crc32Algorithm hasherCRC32 = new Force.Crc32.Crc32Algorithm();
System.Security.Cryptography.MD5Cng hasherMD5 = new System.Security.Cryptography.MD5Cng();
System.Security.Cryptography.SHA1Cng hasherSHA1 = new System.Security.Cryptography.SHA1Cng();
System.Security.Cryptography.SHA256Cng hasherSHA256 = new System.Security.Cryptography.SHA256Cng();
System.Security.Cryptography.SHA512Cng hasherSHA512 = new System.Security.Cryptography.SHA512Cng();
String result = "";
String rate = "";
Status.Text += "Running in " + ((IntPtr.Size == 8) ? "64" : "32") + "-bit mode.<br /><br />";
Status.Text += "Warm-up phase:<br />";
timer.Restart();
result = BitConverter.ToUInt32(hasherCRC32.ComputeHash(ImageUploader.FileBytes), 0).ToString("X8");
timer.Stop();
rate = ((double)ImageUploader.FileBytes.Length / timer.ElapsedMilliseconds / 1.024 / 1024).ToString("0");
Status.Text += "CRC32: " + rate + " MiB/s [" + result + "] in " + timer.ElapsedMilliseconds + "ms" + ".<br />";
timer.Restart();
result = DamienG.Security.Cryptography.Crc64Iso.Compute(ImageUploader.FileBytes).ToString("X16");
timer.Stop();
rate = ((double)ImageUploader.FileBytes.Length / timer.ElapsedMilliseconds / 1.024 / 1024).ToString("0");
Status.Text += "CRC64: " + rate + " MiB/s [" + result + "] in " + timer.ElapsedMilliseconds + "ms" + ".<br />";
timer.Restart();
result = Convert.ToBase64String(hasherMD5.ComputeHash(ImageUploader.FileBytes));
timer.Stop();
rate = ((double)ImageUploader.FileBytes.Length / timer.ElapsedMilliseconds / 1.024 / 1024).ToString("0");
Status.Text += "MD5: " + rate + " MiB/s [" + result + "] in " + timer.ElapsedMilliseconds + "ms" + ".<br />";
timer.Restart();
result = Convert.ToBase64String(hasherSHA1.ComputeHash(ImageUploader.FileBytes));
timer.Stop();
rate = ((double)ImageUploader.FileBytes.Length / timer.ElapsedMilliseconds / 1.024 / 1024).ToString("0");
Status.Text += "SHA1: " + rate + " MiB/s [" + result + "] in " + timer.ElapsedMilliseconds + "ms" + ".<br />";
timer.Restart();
result = Convert.ToBase64String(hasherSHA256.ComputeHash(ImageUploader.FileBytes));
timer.Stop();
rate = ((double)ImageUploader.FileBytes.Length / timer.ElapsedMilliseconds / 1.024 / 1024).ToString("0");
Status.Text += "SHA256: " + rate + " MiB/s [" + result + "] in " + timer.ElapsedMilliseconds + "ms" + ".<br />";
timer.Restart();
result = Convert.ToBase64String(hasherSHA512.ComputeHash(ImageUploader.FileBytes));
timer.Stop();
rate = ((double)ImageUploader.FileBytes.Length / timer.ElapsedMilliseconds / 1.024 / 1024).ToString("0");
Status.Text += "SHA512: " + rate + " MiB/s [" + result + "] in " + timer.ElapsedMilliseconds + "ms" + ".<br />";
Status.Text += "<br />Final run:<br />";
timer.Restart();
result = BitConverter.ToUInt32(hasherCRC32.ComputeHash(ImageUploader.FileBytes), 0).ToString("X8");
timer.Stop();
rate = ((double)ImageUploader.FileBytes.Length / timer.ElapsedMilliseconds / 1.024 / 1024).ToString("0");
Status.Text += "CRC32: " + rate + " MiB/s [" + result + "] in " + timer.ElapsedMilliseconds + "ms" + ".<br />";
timer.Restart();
result = DamienG.Security.Cryptography.Crc64Iso.Compute(ImageUploader.FileBytes).ToString("X16");
timer.Stop();
rate = ((double)ImageUploader.FileBytes.Length / timer.ElapsedMilliseconds / 1.024 / 1024).ToString("0");
Status.Text += "CRC64: " + rate + " MiB/s [" + result + "] in " + timer.ElapsedMilliseconds + "ms" + ".<br />";
timer.Restart();
result = Convert.ToBase64String(hasherMD5.ComputeHash(ImageUploader.FileBytes));
timer.Stop();
rate = ((double)ImageUploader.FileBytes.Length / timer.ElapsedMilliseconds / 1.024 / 1024).ToString("0");
Status.Text += "MD5: " + rate + " MiB/s [" + result + "] in " + timer.ElapsedMilliseconds + "ms" + ".<br />";
timer.Restart();
result = Convert.ToBase64String(hasherSHA1.ComputeHash(ImageUploader.FileBytes));
timer.Stop();
rate = ((double)ImageUploader.FileBytes.Length / timer.ElapsedMilliseconds / 1.024 / 1024).ToString("0");
Status.Text += "SHA1: " + rate + " MiB/s [" + result + "] in " + timer.ElapsedMilliseconds + "ms" + ".<br />";
timer.Restart();
result = Convert.ToBase64String(hasherSHA256.ComputeHash(ImageUploader.FileBytes));
timer.Stop();
rate = ((double)ImageUploader.FileBytes.Length / timer.ElapsedMilliseconds / 1.024 / 1024).ToString("0");
Status.Text += "SHA256: " + rate + " MiB/s [" + result + "] in " + timer.ElapsedMilliseconds + "ms" + ".<br />";
timer.Restart();
result = Convert.ToBase64String(hasherSHA512.ComputeHash(ImageUploader.FileBytes));
timer.Stop();
rate = ((double)ImageUploader.FileBytes.Length / timer.ElapsedMilliseconds / 1.024 / 1024).ToString("0");
Status.Text += "SHA512: " + rate + " MiB/s [" + result + "] in " + timer.ElapsedMilliseconds + "ms" + ".<br />";
それはあなたが持っているファイルの数に依存します。
P(collision) = c/2^N（完全なハッシュ関数での）衝突の可能性。ここcで、はメッセージ（ファイル）Nの数であり、は衝突アルゴリズムのビット数です。
実際のハッシュ関数は完全ではないため、速度を最適化する方法と衝突回避を最適化する方法の2つのオプションがあります。
最初のケースでは、CRC32を使用する必要があります。CRC32は非常に一般的ですが、ファイルの数によっては十分ではない場合があります。最大43億メッセージ（32有効ビット）で衝突することが保証されていますが、実際には最初の衝突が発生する可能性があります。 〜1000万メッセージで。CRC32の実装は非常に高速です（SSE 4.2にはハードウェア命令もあります）。CRC64は衝突の可能性がはるかに低いですが、広く使用されていないため、CRC32よりも多くの衝突回避が必要な場合は、暗号化ハッシュ関数を検討することをお勧めします。
速度を犠牲にして衝突を回避したい場合は、暗号化ハッシュ関数が必要になります。そのうち、MD5（128ビット）、SHA-1（160ビット）、およびSHA-2（通常はSHA-256またはSHA-512）が最も広く使用されています。迅速な実装があります。MD5の非常に効率的なハッシュ衝突検出アルゴリズムが利用可能ですが、ランダムなメッセージを入力するとP(collision) = c/2^128、妥当な時間で実行している間、これまでに得ようとしているものに限りなく近づくことができます。
このトピックは非常に興味深く、予期しない結果をもたらすため、ここでMichaelが以前に行った分析（上記の投稿を参照）に加えて、組み込みのPHPハッシュのパフォーマンスをさらに分析します。
結果はそれほど明白ではなく、驚くべきことでもありません。単純なアルゴリズム（CRC32またはCRC16）は、複雑なアルゴリズム（MD5）よりも低速です。最新のCPUは、特定の古いアルゴリズムを好まないため、実行速度が非常に遅いようです。少なくとも、アルゴリズムが新しい方法で実装されていない場合は、最新のCPUアーキテクチャを利用します。CRC16 CCITTアルゴリズムは、300のBPSダイヤルアップモデムがあった古き良き時代には比較的高速で効率的でした。現在、新しいハードウェア用に特別に設計された最新のアルゴリズムがあり、古いアルゴリズムよりも同じハードウェアではるかに高速に動作する可能性があります。これらのアルゴリズムは、本質的に新しいハードウェアには適合せず、最適化しようとしても、とにかく比較的遅くなります。例えば、
PHPで見られるものを確認する他の暗号化ライブラリから、CRC32IEEEの速度はMD5とほぼ同じであることがわかります。別のライブラリの結果へのリンクは次のとおりです：https ：//www.cryptopp.com/benchmarks.html
OpenSSLも同様の結果を示しています。CRC32のアルゴリズムはMD5のアルゴリズムよりもはるかに単純であるため、一見不合理に思えるかもしれませんが、現実にはその逆が示されています。
CRC32関数がいかに単純であるかを示したいだけです。
次の着信バイト（Delphi）でCRCR32カウンターを更新するコードは次のとおりです。
// Returns an updated CRC32
function UpdateCrc32(CurByte: Byte; CurCrc: Cardinal): Cardinal; inline;
begin
UpdateCrc32 := Crc32Table[Byte(CurCrc xor CurByte)] xor (CurCrc shr 8);
end;
アセンブリに関するこのコードは次のとおりです。
@calc_crc32:
xor dl,[esi]
mov al,dl
shr edx,8
xor edx,dword ptr [edi+eax*4]
inc esi
loop @calc_crc32
このコードを展開して、1バイトあたりわずか5つのCPU命令を取得することもできます。
xor dl,bl
shr rbx,8
mov al,dl
shr edx,8
xor edx,dword ptr [r8+rax*4]
次の8バイトのデータをレジスタにロードしてrbxから、次の8バイトをrbx64ビットレジスタにロードする必要があるまで、このコードを8回繰り返す必要があります。
文字列全体のCRC32を計算するルーチンは次のとおりです。
function CalcCRC32(const B; Size: NativeUINT;
const
InitialValue: Cardinal = CRC32_INIT): Cardinal;
var
C: Cardinal;
P: PAnsiChar;
i: NativeUINT;
begin
C := InitialValue;
if Size > 0 then
begin
P := @B;
for i := 0 to Size - 1 do
C := UpdateCrc32(Byte(P[i]), C);
end;
Result := C;
end;
そして、Delphiによってマシンコードにコンパイルされる方法は次のとおりです。非常に最適ではありませんが、非常に単純です。バイトごとに11のアセンブリ命令があります。これは、驚くべきことに、IntelCorei5-6600では上記のアセンブラコードよりも少し速く動作します。ループ展開。ご覧のとおり、CRC32 IEEEを実装するためのこれらすべての命令は単純で、ループや比較はなく、各バイトの最後に1つの比較しかありません。これは、コンパイルされたDelphiコードの単なるデバッガ出力であり、人間が作成したアセンブリコードではありません。
CRC32.pas.78: begin
push esi
push edi
CRC32.pas.80: if Size > 0 then
test edx,edx
jbe $00500601
CRC32.pas.82: P := @B;
mov edi,eax
CRC32.pas.83: for i := 0 to Size - 1 do
mov eax,edx
dec eax
test eax,eax
jb $00500601
inc eax
xor esi,esi
CRC32.pas.84: C := UpdateCrc32(Byte(P[i]), C);
movzx edx,[edi+esi]
xor dl,cl
movzx edx,dl
mov edx,[edx*4+$517dec]
shr ecx,$08
xor edx,ecx
mov ecx,edx
inc esi
CRC32.pas.83: for i := 0 to Size - 1 do
dec eax
jnz $005005e6
CRC32.pas.86: Result := C;
mov eax,ecx
CRC32.pas.87: end;
pop edi
pop esi
ret
これはCRC32のアセンブラコードの別のバリエーションで、バイトごとに11ではなく5つのプロセッサコマンドですが、基本的に上記のアセンブラコードと同じで、異なるレジスタを使用し、i5-にある「ループ」コマンドを回避します。 2つの異なる命令よりも6600高速です。コード全体は、Cコンソールアプリから呼び出されるCRC32アセンブラ関数で見つけることができます
586
.model flat, stdcall
.xmm
.data
.code
CRC32 proc sizeOfFile:DWORD, file:DWORD
push esi
push ecx
push edx
mov esi, file
xor edx, edx
or eax, -1
mov ecx, sizeOfFile
CRC32_loop:
mov dl, byte ptr [esi]
xor dl, al
shr eax, 8
xor eax, dword ptr [crc32_table + 4*edx]
inc esi
dec ecx
jnz CRC32_loop
not eax
pop edx
pop ecx
pop esi
ret
次に、Peter Sawatzkiによるこの高度に最適化されたアセンブラコードを使用して、MD5と比較します。
; MD5_386.Asm - 386 optimized helper routine for calculating
; MD Message-Digest values
; written 2/2/94 by
;
; Peter Sawatzki
; Buchenhof 3
; D58091 Hagen, Germany Fed Rep
;
; EMail: Peter@Sawatzki.de
; EMail: 100031.3002@compuserve.com
; WWW: http://www.sawatzki.de
;
;
; original C Source was found in Dr. Dobbs Journal Sep 91
; MD5 algorithm from RSA Data Security, Inc.
.386
.MODEL FLAT
.CODE
R1 = ESi
R2 = EDi
FF Macro a,b,c,d,x,s,ac
; a:= ROL (a+x+ac + (b And c Or Not b And d), s) + b
Add a, [EBp+(4*x)]
Add a, ac
Mov R1, b
Not R1
And R1, d
Mov R2, c
And R2, b
Or R1, R2
Add a, R1
Rol a, s
Add a, b
EndM
GG Macro a,b,c,d,x,s,ac
; a:= ROL (a+x+ac + (b And d Or c And Not d), s) + b
Add a, [EBp+(4*x)]
Add a, ac
Mov R1, d
Not R1
And R1, c
Mov R2, d
And R2, b
Or R1, R2
Add a, R1
Rol a, s
Add a, b
EndM
HH Macro a,b,c,d,x,s,ac
; a:= ROL (a+x+ac + (b Xor c Xor d), s) + b
Add a, [EBp+(4*x)]
Add a, ac
Mov R1, d
Xor R1, c
Xor R1, b
Add a, R1
Rol a, s
Add a, b
EndM
II Macro a,b,c,d,x,s,ac
; a:= ROL (a+x+ac + (c Xor (b Or Not d)), s) + b
Add a, [EBp+(4*x)]
Add a, ac
Mov R1, d
Not R1
Or R1, b
Xor R1, c
Add a, R1
Rol a, s
Add a, b
EndM
Transform Proc
Public Transform
;Procedure Transform (Var Accu; Const Buf); Register;
; save registers that Delphi requires to be restored
Push EBx
Push ESi
Push EDi
Push EBp
Mov EBp, EDx ; Buf -> EBp
Push EAx ; Accu -> Stack
Mov EDx, [EAx+12]
Mov ECx, [EAx+8]
Mov EBx, [EAx+4]
Mov EAx, [EAx]
FF EAx,EBx,ECx,EDx, 0, 7, 0d76aa478h ; 1
FF EDx,EAx,EBx,ECx, 1, 12, 0e8c7b756h ; 2
FF ECx,EDx,EAx,EBx, 2, 17, 0242070dbh ; 3
FF EBx,ECx,EDx,EAx, 3, 22, 0c1bdceeeh ; 4
FF EAx,EBx,ECx,EDx, 4, 7, 0f57c0fafh ; 5
FF EDx,EAx,EBx,ECx, 5, 12, 04787c62ah ; 6
FF ECx,EDx,EAx,EBx, 6, 17, 0a8304613h ; 7
FF EBx,ECx,EDx,EAx, 7, 22, 0fd469501h ; 8
FF EAx,EBx,ECx,EDx, 8, 7, 0698098d8h ; 9
FF EDx,EAx,EBx,ECx, 9, 12, 08b44f7afh ; 10
FF ECx,EDx,EAx,EBx, 10, 17, 0ffff5bb1h ; 11
FF EBx,ECx,EDx,EAx, 11, 22, 0895cd7beh ; 12
FF EAx,EBx,ECx,EDx, 12, 7, 06b901122h ; 13
FF EDx,EAx,EBx,ECx, 13, 12, 0fd987193h ; 14
FF ECx,EDx,EAx,EBx, 14, 17, 0a679438eh ; 15
FF EBx,ECx,EDx,EAx, 15, 22, 049b40821h ; 16
GG EAx,EBx,ECx,EDx, 1, 5, 0f61e2562h ; 17
GG EDx,EAx,EBx,ECx, 6, 9, 0c040b340h ; 18
GG ECx,EDx,EAx,EBx, 11, 14, 0265e5a51h ; 19
GG EBx,ECx,EDx,EAx, 0, 20, 0e9b6c7aah ; 20
GG EAx,EBx,ECx,EDx, 5, 5, 0d62f105dh ; 21
GG EDx,EAx,EBx,ECx, 10, 9, 002441453h ; 22
GG ECx,EDx,EAx,EBx, 15, 14, 0d8a1e681h ; 23
GG EBx,ECx,EDx,EAx, 4, 20, 0e7d3fbc8h ; 24
GG EAx,EBx,ECx,EDx, 9, 5, 021e1cde6h ; 25
GG EDx,EAx,EBx,ECx, 14, 9, 0c33707d6h ; 26
GG ECx,EDx,EAx,EBx, 3, 14, 0f4d50d87h ; 27
GG EBx,ECx,EDx,EAx, 8, 20, 0455a14edh ; 28
GG EAx,EBx,ECx,EDx, 13, 5, 0a9e3e905h ; 29
GG EDx,EAx,EBx,ECx, 2, 9, 0fcefa3f8h ; 30
GG ECx,EDx,EAx,EBx, 7, 14, 0676f02d9h ; 31
GG EBx,ECx,EDx,EAx, 12, 20, 08d2a4c8ah ; 32
HH EAx,EBx,ECx,EDx, 5, 4, 0fffa3942h ; 33
HH EDx,EAx,EBx,ECx, 8, 11, 08771f681h ; 34
HH ECx,EDx,EAx,EBx, 11, 16, 06d9d6122h ; 35
HH EBx,ECx,EDx,EAx, 14, 23, 0fde5380ch ; 36
HH EAx,EBx,ECx,EDx, 1, 4, 0a4beea44h ; 37
HH EDx,EAx,EBx,ECx, 4, 11, 04bdecfa9h ; 38
HH ECx,EDx,EAx,EBx, 7, 16, 0f6bb4b60h ; 39
HH EBx,ECx,EDx,EAx, 10, 23, 0bebfbc70h ; 40
HH EAx,EBx,ECx,EDx, 13, 4, 0289b7ec6h ; 41
HH EDx,EAx,EBx,ECx, 0, 11, 0eaa127fah ; 42
HH ECx,EDx,EAx,EBx, 3, 16, 0d4ef3085h ; 43
HH EBx,ECx,EDx,EAx, 6, 23, 004881d05h ; 44
HH EAx,EBx,ECx,EDx, 9, 4, 0d9d4d039h ; 45
HH EDx,EAx,EBx,ECx, 12, 11, 0e6db99e5h ; 46
HH ECx,EDx,EAx,EBx, 15, 16, 01fa27cf8h ; 47
HH EBx,ECx,EDx,EAx, 2, 23, 0c4ac5665h ; 48
II EAx,EBx,ECx,EDx, 0, 6, 0f4292244h ; 49
II EDx,EAx,EBx,ECx, 7, 10, 0432aff97h ; 50
II ECx,EDx,EAx,EBx, 14, 15, 0ab9423a7h ; 51
II EBx,ECx,EDx,EAx, 5, 21, 0fc93a039h ; 52
II EAx,EBx,ECx,EDx, 12, 6, 0655b59c3h ; 53
II EDx,EAx,EBx,ECx, 3, 10, 08f0ccc92h ; 54
II ECx,EDx,EAx,EBx, 10, 15, 0ffeff47dh ; 55
II EBx,ECx,EDx,EAx, 1, 21, 085845dd1h ; 56
II EAx,EBx,ECx,EDx, 8, 6, 06fa87e4fh ; 57
II EDx,EAx,EBx,ECx, 15, 10, 0fe2ce6e0h ; 58
II ECx,EDx,EAx,EBx, 6, 15, 0a3014314h ; 59
II EBx,ECx,EDx,EAx, 13, 21, 04e0811a1h ; 60
II EAx,EBx,ECx,EDx, 4, 6, 0f7537e82h ; 61
II EDx,EAx,EBx,ECx, 11, 10, 0bd3af235h ; 62
II ECx,EDx,EAx,EBx, 2, 15, 02ad7d2bbh ; 63
II EBx,ECx,EDx,EAx, 9, 21, 0eb86d391h ; 64
Pop ESi ; get Accu from stack
Add [ESi], EAx
Add [ESi+4], EBx
Add [ESi+8], ECx
Add [ESi+12], EDx
; restore registers for Delphi
Pop EBp
Pop EDi
Pop ESi
Pop EBx
Ret
Transform EndP
End
このコードの32ビットバージョンと64ビットバージョンはhttps://github.com/maximmasiutin/MD5_Transform-x64にあります。
IA-32またはx86-64でのこのコードのパフォーマンスは、MD5を計算するためのデータのバイトあたり4.94 CPUサイクル（Skylake上）です。
上記のコードは、64バイトの着信データを1回の呼び出しで処理します。これは、準備手順を実行するメインルーチンから呼び出されます。
procedure CiphersMD5Update(var Context: TMD5Ctx; const ChkBuf; len: UInt32);
var
BufPtr: ^Byte;
Left: UInt32;
begin
If Context.Count[0] + UInt32(len) shl 3 < Context.Count[0] then
Inc(Context.Count[1]);
Inc(Context.Count[0], UInt32(len) shl 3);
Inc(Context.Count[1], UInt32(len) shr 29);
BufPtr := @ChkBuf;
if Context.BLen > 0 then
begin
Left := 64 - Context.BLen;
if Left > len then
Left := len;
Move(BufPtr^, Context.Buffer[Context.BLen], Left);
Inc(Context.BLen, Left);
Inc(BufPtr, Left);
If Context.BLen < 64 then
Exit;
Transform(Context.State, @Context.Buffer);
Context.BLen := 0;
Dec(len, Left)
end;
while len >= 64 do
begin
Transform(Context.State, BufPtr);
Inc(BufPtr, 64);
Dec(len, 64)
end;
if len > 0 then
begin
Context.BLen := len;
Move(BufPtr^, Context.Buffer[0], Context.BLen)
end
end;
また、プロセッサがCRC32オペコード（SSE 4.2）をサポートしている場合は、次のコードを使用してチェックサムを10倍速く計算できます。
function crc32csse42(crc: cardinal; buf: Pointer; len: NativeUInt): cardinal;
asm // ecx=crc, rdx=buf, r8=len
.NOFRAME
mov eax,ecx
not eax
test r8,r8; jz @0
test rdx,rdx; jz @0
@7: test rdx,7; jz @8 // align to 8 bytes boundary
crc32 eax,byte ptr [rdx]
inc rdx
dec r8; jz @0
test rdx,7; jnz @7
@8: mov rcx,r8
shr r8,3
jz @2
@1: crc32 eax,qword ptr [rdx] // calculate CRC of 8 bytes, aligned
dec r8
lea rdx,rdx+8
jnz @1
@2: // less than 8 bytes remaining
and rcx,7; jz @0
cmp rcx,4; jb @4
crc32 eax,dword ptr [rdx] // calculate CRC of 4 bytes
sub rcx,4
lea rdx,rdx+4
jz @0
@4: // less than 4 bytes remaining
crc32 eax,byte ptr [rdx]
dec rcx; jz @0
crc32 eax,byte ptr [rdx+1]
dec rcx; jz @0
crc32 eax,byte ptr [rdx+2]
@0: not eax
end;
私の例では、プロセッサのキャッシュに収まり、ダイジェスト計算の速度に対するRAMの速度低下の影響を排除するために、わずか5KBのバッファを使用していることに注意してください。
CRC32オペコードを使用しない最新のプロセッサ用のCRC32アルゴリズムの高速実装がありますが、レジスタの名前変更による投機的実行など、アウトオブオーダー実行を利用します。このような実装の例は、CRC32Slicing-By-8です。IA-32またはx86-64アセンブラコードには、データのバイトあたり1,20 CPUクロックサイクル（Skylake上）があります。このような実装はhttps://github.com/maximmasiutin/CRC32-Slicing-x64-Asm-Pasにあります。
PHPでは、バージョン7でも、CRC32のハードウェアアクセラレーションはサポートされていないようですが、これらの命令は古くからIntelおよびAMDプロセッサでサポートされています。Intelは2008年11月からCRC32（Nehalem（マイクロアーキテクチャ））をサポートしており、AMDは2013年からCRC32をサポートしているようです。
さまざまな構成でさまざまなPHPハッシュ関数をテストしました：（1）PHP5を搭載したUbuntuでAMDFX-8320（2012年にリリース）、（2）PHP7を搭載したWindowsで2015年にリリースされたIntelCorei5-6600このIntelCorei5-6600でOpenSSLテストを実行します。その上、私はソフトウェア「TheBat！」で使用する暗号化ルーチンのテストを実行します。Delphiで書かれています。メインソフトウェアはDelphiで記述されていますが、使用する暗号化ルーチンは、Intelプロセッサ用のアセンブラ（32ビットまたは64ビット）またはCで記述されています。
私たちのDelphiコードは、さまざまなハッシュ関数とデータサイズの間で非常に大きな速度の違いを示していることがわかりました。これは、PHPとは対照的です。ここでは、ある程度、まれな例外を除いて、最も単純なCRC32からかつて暗号化された強力なMD5までのすべてのハッシュ関数のスルー出力速度がほぼ同じです。
それで、これが私がAMD FX-8320、PHP5、Ubuntuで行った測定です。2つのテストケースを作成しました。最初に、5000回の反復を実行して、わずか5バイトで構成されるメッセージをハッシュしました。この小さなメッセージサイズによって、さまざまなアルゴリズムの初期化/終了ステップの期間と、それが全体的なパフォーマンスにどのように影響するかをテストすることを意図しました。CRC32などの一部のアルゴリズムでは、3つは実質的にファイナライズステップではありません。ダイジェストは、各バイトの後に常に準備ができています。SHA1やMD5などの暗号的に強力な関数には、より大きなコンテキストをより小さな最終ダイジェストに圧縮するファイナライズステップがあります。次に、5000回の反復を実行して、5000バイトの長さのメッセージをハッシュします。両方のメッセージは、事前に疑似ランダムバイトで埋められていました（各反復後に再埋められることはありませんでした。プログラムの開始時に一度だけ埋められました）。
PHPコードを変更し、PHP5とPHP7の両方で機能するようにしました。これらの関数は、さまざまなバージョンのPHPでランダムデータを生成するためのさまざまな関数です。5バイトのメッセージを5000回繰り返し、次に5000バイトのメッセージを5000回ハッシュするのに必要な時間を測定しました。結果は次のとおりです。
Legend:
(1) 5b x 5000, AMD FX-8320, PHP5
(2) 5000b x 5000, AMD FX-8320, PHP5
PHP hash (1) (2)
-------- ------------ ------------
md2 0.021267 sec 2.602651 sec
md4 0.002684 sec 0.035243 sec
md5 0.002570 sec 0.055548 sec
sha1 0.003346 sec 0.106432 sec
sha224 0.004945 sec 0.210954 sec
sha256 0.004735 sec 0.238030 sec
sha384 0.005848 sec 0.144015 sec
sha512 0.006085 sec 0.142884 sec
ripemd128 0.003385 sec 0.120959 sec
ripemd160 0.004164 sec 0.174045 sec
ripemd256 0.003487 sec 0.121477 sec
ripemd320 0.004206 sec 0.177473 sec
whirlpool 0.009713 sec 0.509682 sec
tiger128,3 0.003414 sec 0.059028 sec
tiger160,3 0.004354 sec 0.059335 sec
tiger192,3 0.003379 sec 0.058891 sec
tiger128,4 0.003514 sec 0.073468 sec
tiger160,4 0.003602 sec 0.072329 sec
tiger192,4 0.003507 sec 0.071856 sec
snefru 0.022101 sec 1.190888 sec
snefru256 0.021972 sec 1.217704 sec
gost 0.013961 sec 0.653600 sec
adler32 0.001459 sec 0.038849 sec
crc32 0.001429 sec 0.068742 sec
crc32b 0.001553 sec 0.063308 sec
fnv132 0.001431 sec 0.038256 sec
fnv164 0.001586 sec 0.060622 sec
joaat 0.001569 sec 0.062947 sec
haval128,3 0.006747 sec 0.174759 sec
haval160,3 0.005810 sec 0.166154 sec
haval192,3 0.006129 sec 0.168382 sec
haval224,3 0.005918 sec 0.166792 sec
haval256,3 0.006119 sec 0.173360 sec
haval128,4 0.007364 sec 0.233829 sec
haval160,4 0.007917 sec 0.240273 sec
haval192,4 0.007676 sec 0.245864 sec
haval224,4 0.007580 sec 0.245249 sec
haval256,4 0.007442 sec 0.241091 sec
haval128,5 0.008651 sec 0.281248 sec
haval160,5 0.009304 sec 0.278619 sec
haval192,5 0.008972 sec 0.281235 sec
haval224,5 0.008917 sec 0.274923 sec
haval256,5 0.008853 sec 0.282171 sec
次に、同じPHPスクリプトをIntel Core i5-6600で実行し、64ビットバージョンのPHP7をWindows10で実行します。結果は次のとおりです。
Legend:
(1) 5b x 5000, Intel Core i5-6600, PHP7
(2) 5000b x 5000, Intel Core i5-6600, PHP7
PHP hash (1) (2)
--------- ------------ ------------
md2 0.016131 sec 2.308100 sec
md4 0.001218 sec 0.040803 sec
md5 0.001284 sec 0.046208 sec
sha1 0.001499 sec 0.050259 sec
sha224 0.002683 sec 0.120510 sec
sha256 0.002297 sec 0.119602 sec
sha384 0.002792 sec 0.080670 sec
ripemd128 0.001984 sec 0.094280 sec
ripemd160 0.002514 sec 0.128295 sec
ripemd256 0.002015 sec 0.093887 sec
ripemd320 0.002748 sec 0.128955 sec
whirlpool 0.003402 sec 0.271102 sec
tiger128,3 0.001282 sec 0.038638 sec
tiger160,3 0.001305 sec 0.037155 sec
tiger192,3 0.001309 sec 0.037684 sec
tiger128,4 0.001618 sec 0.050690 sec
tiger160,4 0.001571 sec 0.049656 sec
tiger192,4 0.001711 sec 0.050682 sec
snefru 0.010949 sec 0.865108 sec
snefru256 0.011587 sec 0.867685 sec
gost 0.008968 sec 0.449647 sec
adler32 0.000588 sec 0.014345 sec
crc32 0.000609 sec 0.079202 sec
crc32b 0.000636 sec 0.074408 sec
fnv132 0.000570 sec 0.028157 sec
fnv164 0.000566 sec 0.028776 sec
joaat 0.000623 sec 0.042127 sec
haval128,3 0.002972 sec 0.084010 sec
haval160,3 0.002968 sec 0.083213 sec
haval192,3 0.002943 sec 0.082217 sec
haval224,3 0.002798 sec 0.084726 sec
haval256,3 0.002995 sec 0.082568 sec
haval128,4 0.003659 sec 0.112680 sec
haval160,4 0.003858 sec 0.111462 sec
haval192,4 0.003526 sec 0.112510 sec
haval224,4 0.003671 sec 0.111656 sec
haval256,4 0.003636 sec 0.111236 sec
haval128,5 0.004488 sec 0.140130 sec
haval160,5 0.005095 sec 0.137777 sec
haval192,5 0.004117 sec 0.140711 sec
haval224,5 0.004311 sec 0.139564 sec
haval256,5 0.004382 sec 0.138345 sec
ご覧のとおり、PHPでメッセージのCRC32を計算するには、ほとんどすべてのテストで、同じメッセージのMD5を計算するのにかかる時間の約半分の時間がかかります。唯一の例外は、PHP7を搭載したIntel Core i5-6600で5000バイトの5000メッセージをテストした場合、CRC32はMD5（！）よりも時間がかかったことです。この奇妙な結果は、私の場合は常に再現可能でした。もっともらしい説明が見つかりませんでした。
また、PHPでは、5000バイトの5000メッセージのテストでMD5が2倍高速であった、PHP5を使用したUbuntuを除いて、MD5とSHA1の間に目立った速度の違いはほとんどありませんでした。
Inteli5-660でのOpenSSLのテストは次のとおりです。データの表示方法が異なります。これらは、特定のデータセットをダイジェストするのにかかった時間を示していませんが、その逆です。OpenSSLが3秒でハッシュできたデータの量を示しています。したがって、値が高いほど良いです。
Legend:
(1) OpenSSL 1.1.0 on Intel Core i5-6600, number of 16-bytes messages processed in 3 seconds
(2) OpenSSL 1.1.0 on Intel Core i5-6600, number of 8192-bytes messages processed in 3 seconds
Algorighm (1) (2)
--------- --------- ----------
md4 50390.16k 817875.48k
md5 115875.35k 680700.59k
sha1 118158.30k 995986.09k
ripemd160 30308.79k 213224.11k
whirlpool 39605.02k 182072.66k
繰り返しになりますが、md5とsha1の間にほとんど違いはありません。これは奇妙であり、MD5とSHA-1アルゴリズムが時間の消費に関して本質的に同じであるかどうかをさらに調査する必要があります。
これは、Windows1064ビットでのIntelCorei5-6600上のDelphiライブラリの結果です。テストされたコードは、32ビットのWin32アプリケーションでした。
Legend:
(1) Delphi, 5b x 5000 iterations
(2) Delphi, 5000b x 5000 iterations
Algorighm (1) (2)
--------------- -------------- --------------
md2 0.0381010 secs 5.8495807 secs
md5 0.0005015 secs 0.0376252 secs
sha1 0.0050118 secs 0.1830871 secs
crc32 >0.0000001 secs 0.0581535 secs
crc32c (intel hw) >0.0000001 secs 0.0055349 secs
ご覧のとおり、MD2は他のハッシュよりもはるかにシャワーです。PHPコードと同じ結果ですが、MD5はSHA-1よりもはるかに高速であり、Delphiで同じマシンで同じことを行うのにかかる時間は全体的に短くなりました。たとえば、PHP7は、MD5で5000の5バイトメッセージをダイジェストするのに0.001284秒かかり、SHA1で0.001499秒かかりました。約5000バイトのメッセージとして– MD5ではPHP70.046208秒、SHA-1では0.050259秒かかりました。
Delphiについては、MD5で5000の5バイトメッセージをダイジェストするのに0.0005015秒かかり、SHA1で0.0050118秒かかりました。約5000バイトのメッセージとして– DelphiはMD5では0.0376252秒、SHA-1では0.1830871秒かかりました。ご覧のとおり、DelphiではMD5の方がはるかに高速に動作しますが、SHA-1はほぼ同じです。また、Delphiは5バイトのメッセージで約10倍高速ですが、約5000バイトのメッセージと同様に、SHA-1とほぼ同じかそれ以上遅くなります。
しかし、CRC32とCRC32Cに関しては、DelphiはPHPよりも10倍から1000倍高速で無敵です。
PHPは、ループや小さな操作では本質的に非常に低速です。したがって、小さなメッセージのハッシュを計算する必要がある場合は、PHPでどのハッシュ関数を呼び出すかは重要ではありません。しかし、大きなメッセージを消化する必要がある場合は、アルゴリズムの速度の違いがそれらを示し始めました。たとえば、MD2のパフォーマンスはMD5の場合の約10分の1です。とにかく、今日MD2を使用する理由はまったくありません。MD5よりもMD2のPHPユーザーにとっての利点はありません。MD5については、最初は暗号化ハッシュ関数として設計され、RFC-1991でPGPによって使用されていましたが、暗号化では使用できなくなりましたが、ETagやその他の手段などの信頼できる環境でチェックサムとして使用できます。この関数は、正しく実装されている場合は非常に高速であり（PHPでは、少なくとも遅くはありません）、MD5は他の関数と比較して非常にコンパクトなダイジェストを生成します。これらのベンチマークを作成した私のPHPコードは次のとおりです。Michaelによる元のコードサンプルに基づいて作成しました（上記を参照）。
<?
define (TRAILING_ZEROS, 6);
$strlens = array(5, 30, 90, 1000, 5000);
$hashes = hash_algos();
function generate_bytes($len)
{
if (function_exists('random_bytes')) {$fn='random_bytes';$str = random_bytes($len);} else // for php 5
if (function_exists('openssl_random_pseudo_bytes')) {$fn='openssl_random_pseudo_bytes';$str = openssl_random_pseudo_bytes($strlen);} else // for php 7
{
flush();
ob_start () ;
phpinfo () ;
$str = str_pad(substr(ob_get_contents (), 0, $len), $len) ;
ob_end_clean () ;
$fn = 'phpinfo';
}
return array(0=>$str, 1=>$fn);
}
foreach ($strlens as $strlen)
{
$loops = 5000;
echo "<h1>$loops iterations on $strlen bytes message</h1>".PHP_EOL;
echo '<p>';
$r = generate_bytes($strlen);
$str = $r[0];
$gotlen = strlen($str);
while ($gotlen < $strlen)
{
// for some uncodumented reason, the openssl_random_pseudo_bytes returned less bytes than needed
$left = $strlen-$gotlen;
echo "The ".$r[1]."() function returned $left byes less, trying again to get these remaining bytes only<br>";
$r = generate_bytes($left);
$str.= $r[0];
$gotlen = strlen($str);
};
echo "Got the whole string of ".strlen($str)." bytes!";
echo '</p>';
echo PHP_EOL;
echo "<pre>";
foreach ($hashes as $hash)
{
$tss = microtime(true);
for($i=0; $i<$loops; $i++)
{
$x = hash($hash, $str, true);
}
$tse = microtime(true);
echo "\n".str_pad($hash, 15, ' ')."\t" . str_pad(round($tse-$tss, TRAILING_ZEROS), TRAILING_ZEROS+2, '0') . " sec \t" . bin2hex($x);
}
echo PHP_EOL."</pre>".PHP_EOL;
flush();
}
?>
この場合、ハッシュの目的を誤解していると思います。
「これらは同じではない」という簡単なチェックを行うことです。ハッシュは、2つのものが衝突するため、等しいかどうかを判断できません。
したがって、単純なCRCが衝突することはめったになく、多数のファイルに対してどれだけ高速になるかを考えると、これはより優れたソリューションです。
2つのハッシュまたはCRCが同じである場合、反応はまったく同じである必要があります。実際のコンテンツによって同等であることを確認してください。次に、同じサイズのサブセットをハッシュ/ CRCし、ファイルサイズをチェックして、CRCの一致後にすばやく「除外」チェックすることもできます。
等しいファイルが多数あると予想される場合でも、ハッシュによって他の方法でチェックする必要がなくなるわけではありませんが、必要性は減ります。あなたはまだ他の種類のチェックをしたいと思うでしょう。必要に応じて、ハッシュの同等性、ファイルの長さの一致、および部分的なハッシュの同等性（xたとえば、ファイルの最初のバイトをハッシュする）で十分な場合があります。
単一の投稿サイズの制限に遭遇したので、この2番目の投稿を続けます。
「最高のパフォーマンスを得るためにハッシュ関数を選択する」という元の質問について、私の意見は次のとおりです。PHPを使用している場合は、さまざまなハッシュとダイジェストの計算にMD5を使用することを検討してください。少なくとも現在PHP5および7で実装されている方法では、CRC32と比較して速度にほとんど違いはありません。一般に、PHPを使用する場合、MD5は、PHPで利用可能な他のハッシュと比較してパフォーマンスに大きな違いがあります。より大きなメッセージ。MD5の利点は、生成されるダイジェストサイズが比較的小さく、非常に高速であることです。
AES（AES-NI）のハードウェア実装がある場合は、CBCモードでAESを使用してダイジェストを生成できます。同じダイジェストサイズ（128ビット）で、MD-5よりもはるかに高速になります。
ヒント：さらに小さいダイジェストが必要であるが、PHPのテキスト形式である場合は、md5のバイナリ出力のbase64_encodeを使用すると、デフォルトで使用される16進エンコードよりも短い結果文字列が生成されます。
DelphiやC++などのプログラミング言語を使用している場合は、IntelおよびAMDの最新プロセッサでハードウェアアクセラレーションを使用して実行できるCRC32Cの適切な実装を見つけてください。
Delphiのテスト結果からわかるように、コードは5000メッセージのチェックサムを計算しました。各メッセージの長さは5000バイトで、全体の所要時間はわずか0.0055349秒です。これは、ハードウェア以外のCRC32の実装よりも約10倍高速であり、PHPで実装されたものよりもはるかに高速です。
CRC32が生成する4バイトだけでなく、少なくとも16バイトのより大きなダイジェストが必要な場合は、高性能のMD5実装を見つけ、MD5を使用してダイジェストを生成することを検討してください。MD5は暗号化ハッシュ関数として開発され、PGP暗号化とデジタル署名で使用されました。暗号化にはもはや適していませんが、メッセージダイジェストにはまだ問題ありません。このハッシュ関数は、衝突が非常に簡単に検出されるため、暗号化には使用できなくなりましたが、衝突攻撃が問題にならない独自のチェックサムにのみ使用する必要がある場合は、2017年の今日でもMD5を使用することをお勧めします。この有名なハッシュ関数の高速実装を見つけました。衝突を恐れて、AES（AES-NI）のハードウェア実装がある場合は、ダイジェストにAES-CBCを使用します。
一見したところ、たった4バイトのCRC32のように、短いダイジェストサイズを使用できるのに、16バイトなどの大きなダイジェストサイズのハッシュ関数が必要になる理由を説明しましょう。
より大きなハッシュが問題でなければ、「最高のパフォーマンスを得るためのハッシュ関数の選択」のような質問はありません（最初の投稿を参照）。
アプリケーションサーバーと「memcached」サーバーの信頼できる環境があり、すべてのアプリケーションが「memcached」デーモンを実行しているサーバーで使用されるすべてのデータにアクセスでき、データには単純なテキストキーでアクセスできるとします。キーが異なるレルム、アプリケーション間で一意になるように、つまり重複しないように、人々がより長い文字列を発明するのを見ました。したがって、クラスターまたはクラスターのグループを維持するすべてのプログラマーと管理者の慣例により、キーは次のような異なる必須セグメントで構成する必要があることに一般的に同意します。$ UniqueKey = "$ Namespace | $ Realm | $ Application | $ AppComonent | $ User | $ Key ";
これは、約60文字以上の非常に長いキーになります。
「memcached」デーモンの場合、データは固定サイズのレコード（チャンク）のスラブに格納され、単一のチャンクのサイズを構成するのはキーと値の長さであるため、96バイトの小さなチャンクのスラブ、120バイトと192バイトはほとんど空ですが、実際に使用される最初のスラブは304バイトのチャンク用です。この長いキーの非効率性を回避するために、慣例により、MD5などの事前定義されたハッシュ関数によってこれらすべてのキーを常にダイジェストすることに同意できます。すべての開発者が同じ形式のキーを使用し、常に特定のハッシュ関数によってこれらのキーをハッシュする場合、この信頼できる環境でキーが重複する可能性があるという実際的なリスクはありません。MDのバイナリ出力をbase-64-encodeし、末尾の「=」パディングを削除します。オプションで、
Suj5_RxNfIq4u-36o03afg
StRL3WgcNM6AjTSW4ozf8g
i4Ev9nJNFpmf928PrkWbIw
b_GE6cp9c-PT_PLwwYbDXQ
Znci1Nj3HprfFLa0cQNi5g
6ns__XWR7xlsvPgGwZJLBQ
9_Yse6hFEyzgl5y5fnZaUg
LYoIQyhNpmAHqY4r-fgZXg
Y1fVl2rBaan0sKz-qrb8lQ
CiLmDZwUVNW09fQaTv_qSg
easjBIYq27dijGr2o01-5Q
また、ハッシュパフォーマンステストの結果をさまざまな方法で示します。経過時間で割ると、KB/Sで特定のハッシュスルー出力が表示されます。
ハッシュの問題は非常に重要であるとあなたは確信しているので、そうです！