主要目标是提高性能。这意味着尽量减少网络流量。安全不是问题。
同时,必须避免"零"碰撞,因为我不想错误地将两个不同的文件视为相同。虽然从理论上讲总会有碰撞,但我希望实际上遇到它们的机率绝对可以忽略不计。
所以我的问题是:哪种.NET哈希函数最适合此任务?
我考虑使用缓冲读取器和MD5CryptoServiceProvider
(因为CNG可能并不适用于所有客户端)。
是否有比这更好的性能方法?(也许使用一些外部库?)
所以我的问题是:哪种.NET哈希函数最适合此任务?
我考虑使用缓冲读取器和MD5CryptoServiceProvider
(因为CNG可能并不适用于所有客户端)。
是否有比这更好的性能方法?(也许使用一些外部库?)
我曾遇到需要 .NET 哈希算法的类似情况。我需要用于服务器响应缓存,速度比安全性更重要。当我进入这个主题时,我注意到有关算法选择和32位与64位执行性能差异的推测。为了在这场辩论中引入一些科学,我编写了一些代码来实际测试可用算法。我决定测试内置的 MD5、SHA1、SHA256 和 SHA512 算法。我还包括了force-net 的 CRC32 实现和DamienGKit 的 CRC64 实现。对于一个约 115MB 的文件,我的结果如下:
在 32 位模式下运行。
预热阶段:
CRC32:296 MiB/s [9C54580A],耗时 390ms。
CRC64:95 MiB/s [636BCF1455BC885A],耗时 1212ms。
MD5:191 MiB/s [mm/JVFusWMKcT/P+IR4BjQ==],耗时 604ms。
SHA1:165 MiB/s [WSFkGbnYte5EXb7kgp1kqbi2...],耗时 699ms。
SHA256:93 MiB/s [USKMHQmfMil8/KL/ASyE6rm/...],耗时 1240ms。
SHA512:47 MiB/s [Cp9cazN7WsydTPn+k4Xu359M...],耗时 2464ms。
最终运行:
CRC32:279 MiB/s [9C54580A],耗时 414ms。
CRC64:96 MiB/s [636BCF1455BC885A],耗时 1203ms。
MD5:197 MiB/s [mm/JVFusWMKcT/P+IR4BjQ==],耗时 588ms。
SHA1:164 MiB/s [WSFkGbnYte5EXb7kgp1kqbi2...],耗时 707ms。
SHA256:96 MiB/s [USKMHQmfMil8/KL/ASyE6rm/...],耗时 1200ms。
SHA512:47 MiB/s [Cp9cazN7WsydTPn+k4Xu359M...],耗时 2441ms。
在64位模式下运行.
预热阶段:
CRC32: 310 MiB/s [9C54580A],用时373ms。
CRC64: 117 MiB/s [636BCF1455BC885A],用时986ms。
MD5: 198 MiB/s [mm/JVFusWMKcT/P+IR4BjQ==],用时584ms。
SHA1: 184 MiB/s [WSFkGbnYte5EXb7kgp1kqbi2...],用时627ms。
SHA256: 104 MiB/s [USKMHQmfMil8/KL/ASyE6rm/...],用时1112ms。
SHA512: 149 MiB/s [Cp9cazN7WsydTPn+k4Xu359M...],用时778ms。
最终运行:
CRC32: 292 MiB/s [9C54580A],用时396ms。
CRC64: 119 MiB/s [636BCF1455BC885A],用时975ms。
MD5: 199 MiB/s [mm/JVFusWMKcT/P+IR4BjQ==],用时582ms。
SHA1: 192 MiB/s [WSFkGbnYte5EXb7kgp1kqbi2...],用时601ms。
SHA256: 106 MiB/s [USKMHQmfMil8/KL/ASyE6rm/...],用时1091ms。
SHA512: 157 MiB/s [Cp9cazN7WsydTPn+k4Xu359M...],用时738ms。
这些结果来自一个编译好的 Release-build ASP.NET 项目,在运行 .NET v4.5.2 的环境下。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。有趣的是,选择 DamienGKit 的 CRC64 并没有在性能上带来优势,反而不如内置的 MD5 或 SHA1。64位执行似乎对 SHA512 有很大的帮助,但对其他算法的影响却有限。
回答楼上的问题,似乎内置的MD5或SHA1提供了最好的冲突避免和性能平衡。 我的代码如下:要回答开发者的问题,似乎使用内置的 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
是您的碰撞算法中的比特数。
由于现实世界中的哈希函数并非完美,因此您有两个选择:优化速度和优化避免碰撞。
在第一种情况下,您将要使用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
的结果。
我将进一步分析内置PHP哈希的性能,除了Michael在这里提到的分析之外(请参见上面的帖子),因为这个主题非常有趣,并且具有意想不到的结果。
结果并不是那么显而易见,甚至令人惊讶。一个简单的算法 - CRC32或CRC16,比复杂的算法 - MD5要慢。现代CPU似乎不喜欢某些旧的算法,会执行得非常缓慢,至少当这些算法没有以新的方式实现,利用现代CPU架构时是如此。 在早期只有300BPS拨号调制解调器的好日子里,CRC16 CCITT算法相对快速和有效。现在有专门为新硬件设计的现代算法,在相同的硬件上可能比旧算法更快,这些旧算法根本不适合新硬件,即使您尝试优化它们,它们也将相对缓慢,例如每个字节都依赖于前一个字节的算法,您无法利用乱序执行或64位寄存器并行处理多个比特。
您可以从其他加密库中看到与我们在PHP中看到的相同的结果-即CRC32 IEEE几乎具有与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
您还可以展开此代码,这样每个字节只需5个CPU指令:
xor dl,bl
shr rbx,8
mov al,dl
shr edx,8
xor edx,dword ptr [r8+rax*4]
您只需将下一个8个字节的数据加载到rbx
寄存器中,然后重复此代码8次,直到需要将下一个8个字节加载到rbx
64位寄存器。
这是计算整个字符串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 条汇编指令,令人惊讶的是,在 Intel Core i5-6600 上,即使在循环展开后,这些指令的速度也比上面的汇编代码稍微快一点。如您所见,所有实现 CRC32 IEEE 的指令都是直接的,没有循环或比较,每个字节末尾只有一次比较。这只是编译后的 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 汇编代码的变体,每个字节只需 5 条处理器指令,而不是11条,但它本质上与上述汇编代码相同,只使用不同的寄存器并避免了“loop”命令,该命令在i5-6600上比两个不同的指令更快。您可以在CRC32 assembler function called from C console app 中找到整个代码。
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
现在将其与MD5进行比较,使用Peter Sawatzki的高度优化的汇编代码:
; 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
你可以在https://github.com/maximmasiutin/MD5_Transform-x64找到此代码的32位和64位版本。
在IA-32或x86-64下,通过Skylake计算MD5时,此代码的性能为每字节4.94个CPU周期。
上述代码一次处理64个字节的传入数据。 它从主要例程中调用,而该例程执行准备步骤:
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;
请注意,在我的示例中,我仅使用了5KB的缓冲区,以适应处理器的缓存并排除较慢的RAM对摘要计算速度的影响。现代处理器有快速实现CRC32算法的方法,不使用CRC32操作码,而是利用乱序执行(包括通过寄存器重命名进行的推测执行)。这种实现的示例是CRC32 Slicing-By-8。IA-32或x86-64汇编器代码每字节数据需要1.20个CPU时钟周期(在Skylake上)。您可以在https://github.com/maximmasiutin/CRC32-Slicing-x64-Asm-Pas找到这样的实现。即使在PHP 7版本中,似乎也没有支持CRC32的硬件加速,尽管自很久以来英特尔和AMD处理器就支持这些指令。自2008年11月(Nehalem(微架构))起,英特尔支持CRC32,而AMD似乎自2013年起支持。 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
我随后在 Intel Core i5-6600 上,使用 Windows 10 下的 64 位 PHP7 运行相同的 PHP 脚本。以下是结果:
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的一半。唯一的例外是,在使用Intel Core i5-6600和PHP7进行5000个5000字节消息的测试中,CRC32甚至比MD5花费更长的时间(!)。在我的测试中,这个奇怪的结果总是可以重复出现。我找不到一个合理的解释。
此外,在PHP上,除了在Ubuntu中使用PHP5进行的5000个5000字节消息测试中,几乎没有注意到MD5和SHA1之间的速度差异,其中MD5快了两倍。
以下是Intel i5-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算法在时间消耗方面是否本质相同。
以下是我们 Delphi 库在 Windows 10 64位 Intel Core i5-6600 上的测试结果,所测试的代码是一个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需要0.046208秒,而使用SHA-1需要0.050259秒。
至于Delphi,使用MD5对5000个5字节的消息进行摘要需要0.0005015秒,而使用SHA1需要0.0050118秒。对于5000字节的消息 - 使用MD5需要0.0376252秒,而使用SHA-1需要0.1830871秒。如您所见,MD5在Delphi中运行速度更快,但SHA-1则大约相同。此外,在5字节消息方面,Delphi大约快10倍,但在5000字节消息方面,它与SHA-1相同甚至更慢。
但是,当涉及到CRC32和CRC32C时,Delphi是无法匹敌的,比PHP快10到1000倍。
PHP本质上在循环和小操作上非常慢。因此,如果你需要计算一个小消息的哈希值,调用哪个哈希函数并不重要。但是如果需要摘要大消息,则算法速度的差异开始显现:例如,MD2的性能约为MD5的十倍。无论如何,今天完全没有理由使用MD2。对于PHP用户而言,MD2与MD5相比没有任何优势。至于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();
}
?>
我认为你误解了哈希在这种情况下的用途。
它是为了进行快速的 "这些不相同" 检测。哈希不能告诉你两个东西是否相等,因为它们会发生碰撞。
因此,考虑到一个简单的 CRC 很少会产生碰撞,而且它在大量文件上的速度更快,那么这是一个更好的解决方案。
如果两个哈希或 CRC 相同,则您的反应应该是完全相同的:通过实际内容验证相等性。甚至可以对相等大小的子集进行哈希/CRC - 并检查文件大小 - 以进行快速的 "排除" 检查,在 CRC 匹配后。
如果您期望有许多相等的文件,哈希仍然不能消除需要进行其他检查的需求,但可以减少需要进行的次数。您仍然需要进行其他一些检查。哈希相等,加上文件长度匹配,再加上部分哈希相等(例如哈希文件的前 x
字节)可能足以满足您的需求。
这会导致非常长的密钥,大约60个字符或更多。
对于“memcached”守护程序,数据存储在固定大小的记录(块)的slab中,密钥+值的长度构成单个块的大小,因此96字节、120字节和192字节的小块几乎为空,而第一个真正使用的块是304字节的块。为避免较长密钥的低效率,您可以约定始终使用预定的哈希函数(如MD5)对所有这些密钥进行摘要。如果所有开发人员都使用相同的密钥格式,并始终通过某个哈希函数对这些密钥进行哈希,那么在这个可信环境中,密钥可能重叠的实际风险就不存在了。您只需对MD的二进制输出进行base-64编码,并剥离尾随的“=”填充,如果需要,将Base64中使用的加号和减号字符替换为其他字符(如下划线和破折号),以便获得以下漂亮的“memcached”密钥列表:
Suj5_RxNfIq4u-36o03afg
StRL3WgcNM6AjTSW4ozf8g
i4Ev9nJNFpmf928PrkWbIw
b_GE6cp9c-PT_PLwwYbDXQ
Znci1Nj3HprfFLa0cQNi5g
6ns__XWR7xlsvPgGwZJLBQ
9_Yse6hFEyzgl5y5fnZaUg
LYoIQyhNpmAHqY4r-fgZXg
Y1fVl2rBaan0sKz-qrb8lQ
CiLmDZwUVNW09fQaTv_qSg
easjBIYq27dijGr2o01-5Q
让我也向您展示哈希性能测试结果的另一种方式:按经过的时间分割,因此您可以看到每个哈希在KB / S中的特定吞吐量:
我相信您已经发现哈希问题非常重要,确实如此!
c/2^N
,其中c是您的哈希数(文件数),N是您的位数(例如MD5的128位)。我建议使用MD5,因为它是最快速、广泛可用的算法之一,并且在您不需要安全性的情况下很好。请注意,您将始终需要处理冲突(即使将其留给用户),因为每个哈希函数都可能发生冲突。CRC32也是广泛可用和快速的,但仅使用32位,因此发生冲突的可能性更大。 - dtech2^128
确实非常大。即使你有2^32+1
(约43亿)个文件,机会仍然很小(1/2^100
),而CRC32总会至少有一个碰撞。 - dtech