MD5/Implementation: Difference between revisions
Line 808: | Line 808: | ||
<lang coffeescript> |
<lang coffeescript> |
||
# Array sum helper function. |
# Array sum helper function. |
||
sum = ( |
sum = (array) -> |
||
array.reduce (x, y) -> x + y |
|||
x + y |
|||
, start |
|||
md5 = do -> |
md5 = do -> |
Revision as of 01:48, 24 March 2015
You are encouraged to solve this task according to the task description, using any language you may know.
The purpose of this task to code and validate an implementation of the MD5 Message Digest Algorithm by coding the algorithm directly (not using a call to a built-in or external hashing library). For details of the algorithm refer to MD5 on Wikipedia or the MD5 definition in IETF RFC (1321).
- The implementation needs to implement the key functionality namely producing a correct message digest for an input string. It is not necessary to mimic all of the calling modes such as adding to a digest one block at a time over subsequent calls.
- In addition to coding and verifying your implementation, note any challenges your language presented implementing the solution, implementation choices made, or limitations of your solution.
- Solutions on this page should implement MD5 directly and NOT use built in (MD5) functions, call outs to operating system calls or library routines written in other languages as is common in the original MD5 task.
- The following are acceptable:
- An original implementation from the specification, reference implementation, or pseudo-code
- A translation of a correct implementation from another language
- A library routine in the same language; however, the source must be included here.
The solutions shown here will provide practical illustrations of bit manipulation, unsigned integers, working with little-endian data. Additionally, the task requires an attention to details such as boundary conditions since being out by even 1 bit will produce dramatically different results. Subtle implementation bugs can result in some hashes being correct while others are wrong. Not only is it critical to get the individual sub functions working correctly, even small errors in padding, endianness, or data layout will result in failure.
The following verification strings and hashes come from RFC 1321:
hash code <== string 0xd41d8cd98f00b204e9800998ecf8427e <== "" 0x0cc175b9c0f1b6a831c399e269772661 <== "a" 0x900150983cd24fb0d6963f7d28e17f72 <== "abc" 0xf96b697d7cb7938d525a2f31aaf161d0 <== "message digest" 0xc3fcd3d76192e4007dfb496cca67e13b <== "abcdefghijklmnopqrstuvwxyz" 0xd174ab98d277d9f5a5611c2c9f419d9f <== "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789" 0x57edf4a22be3c955ac49da2e2107b67a <== "12345678901234567890123456789012345678901234567890123456789012345678901234567890"
In addition, intermediate outputs to aid in developing an implementation can be found here.
The MD5 Message-Digest Algorithm was developed by RSA Data Security, Inc. in 1991.
Ada
note: this could be dependent on the endianness of the machine it runs on - not tested on big endian.
md5.ads: <lang Ada>package MD5 is
type Int32 is mod 2 ** 32; type MD5_Hash is array (1 .. 4) of Int32; function MD5 (Input : String) return MD5_Hash;
-- 32 hexadecimal characters + '0x' prefix subtype MD5_String is String (1 .. 34); function To_String (Item : MD5_Hash) return MD5_String;
end MD5;</lang>
md5.adb: <lang Ada>with Ada.Unchecked_Conversion;
package body MD5 is
type Int32_Array is array (Positive range <>) of Int32;
function Rotate_Left (Value : Int32; Count : Int32) return Int32 is Bit : Boolean; Result : Int32 := Value; begin for I in 1 .. Count loop Bit := (2 ** 31 and Result) = 2 ** 31; Result := Result * 2; if Bit then Result := Result + 1; end if; end loop; return Result; end Rotate_Left;
function Pad_String (Item : String) return Int32_Array is -- always pad positive amount of Bytes Padding_Bytes : Positive := 64 - Item'Length mod 64; subtype String4 is String (1 .. 4); function String4_To_Int32 is new Ada.Unchecked_Conversion (Source => String4, Target => Int32); begin if Padding_Bytes <= 2 then Padding_Bytes := Padding_Bytes + 64; end if; declare Result : Int32_Array (1 .. (Item'Length + Padding_Bytes) / 4); Current_Index : Positive := 1; begin for I in 1 .. Item'Length / 4 loop Result (I) := String4_To_Int32 (Item (4 * (I - 1) + 1 .. 4 * I)); Current_Index := Current_Index + 1; end loop;
declare Last_String : String4 := (others => Character'Val (0)); Chars_Left : constant Natural := Item'Length mod 4; begin Last_String (1 .. Chars_Left) := Item (Item'Last - Chars_Left + 1 .. Item'Last); Last_String (Chars_Left + 1) := Character'Val (2#1000_0000#); Result (Current_Index) := String4_To_Int32 (Last_String); Current_Index := Current_Index + 1; end;
Result (Current_Index .. Result'Last) := (others => 0); -- append length as bit count Result (Result'Last - 1) := Item'Length * 2 ** 3; -- mod 2 ** 32; Result (Result'Last) := Item'Length / 2 ** (32 - 3); return Result; end; end Pad_String;
function Turn_Around (X : Int32) return Int32 is Result : Int32 := 0; begin for Byte in 1 .. 4 loop Result := Result * 16#100#; Result := Result + (X / (2 ** (8 * (Byte - 1)))) mod 16#100#; end loop; return Result; end Turn_Around;
function MD5 (Input : String) return MD5_Hash is function F (X, Y, Z : Int32) return Int32 is begin return Z xor (X and (Y xor Z)); end F; function G (X, Y, Z : Int32) return Int32 is begin return (X and Z) or (Y and (not Z)); end G; function H (X, Y, Z : Int32) return Int32 is begin return X xor Y xor Z; end H; function I (X, Y, Z : Int32) return Int32 is begin return Y xor (X or (not Z)); end I; T : constant Int32_Array := (16#d76aa478#, 16#e8c7b756#, 16#242070db#, 16#c1bdceee#, 16#f57c0faf#, 16#4787c62a#, 16#a8304613#, 16#fd469501#, 16#698098d8#, 16#8b44f7af#, 16#ffff5bb1#, 16#895cd7be#, 16#6b901122#, 16#fd987193#, 16#a679438e#, 16#49b40821#, 16#f61e2562#, 16#c040b340#, 16#265e5a51#, 16#e9b6c7aa#, 16#d62f105d#, 16#02441453#, 16#d8a1e681#, 16#e7d3fbc8#, 16#21e1cde6#, 16#c33707d6#, 16#f4d50d87#, 16#455a14ed#, 16#a9e3e905#, 16#fcefa3f8#, 16#676f02d9#, 16#8d2a4c8a#, 16#fffa3942#, 16#8771f681#, 16#6d9d6122#, 16#fde5380c#, 16#a4beea44#, 16#4bdecfa9#, 16#f6bb4b60#, 16#bebfbc70#, 16#289b7ec6#, 16#eaa127fa#, 16#d4ef3085#, 16#04881d05#, 16#d9d4d039#, 16#e6db99e5#, 16#1fa27cf8#, 16#c4ac5665#, 16#f4292244#, 16#432aff97#, 16#ab9423a7#, 16#fc93a039#, 16#655b59c3#, 16#8f0ccc92#, 16#ffeff47d#, 16#85845dd1#, 16#6fa87e4f#, 16#fe2ce6e0#, 16#a3014314#, 16#4e0811a1#, 16#f7537e82#, 16#bd3af235#, 16#2ad7d2bb#, 16#eb86d391#); A : Int32 := 16#67452301#; B : Int32 := 16#EFCDAB89#; C : Int32 := 16#98BADCFE#; D : Int32 := 16#10325476#; Padded_String : constant Int32_Array := Pad_String (Input); begin for Block512 in 1 .. Padded_String'Length / 16 loop declare Words : constant Int32_Array (1 .. 16) := Padded_String (16 * (Block512 - 1) + 1 .. 16 * Block512); AA : constant Int32 := A; BB : constant Int32 := B; CC : constant Int32 := C; DD : constant Int32 := D; begin -- round 1 A := B + Rotate_Left ((A + F (B, C, D) + Words (1) + T (1)), 7); D := A + Rotate_Left ((D + F (A, B, C) + Words (2) + T (2)), 12); C := D + Rotate_Left ((C + F (D, A, B) + Words (3) + T (3)), 17); B := C + Rotate_Left ((B + F (C, D, A) + Words (4) + T (4)), 22); A := B + Rotate_Left ((A + F (B, C, D) + Words (5) + T (5)), 7); D := A + Rotate_Left ((D + F (A, B, C) + Words (6) + T (6)), 12); C := D + Rotate_Left ((C + F (D, A, B) + Words (7) + T (7)), 17); B := C + Rotate_Left ((B + F (C, D, A) + Words (8) + T (8)), 22); A := B + Rotate_Left ((A + F (B, C, D) + Words (9) + T (9)), 7); D := A + Rotate_Left ((D + F (A, B, C) + Words (10) + T (10)), 12); C := D + Rotate_Left ((C + F (D, A, B) + Words (11) + T (11)), 17); B := C + Rotate_Left ((B + F (C, D, A) + Words (12) + T (12)), 22); A := B + Rotate_Left ((A + F (B, C, D) + Words (13) + T (13)), 7); D := A + Rotate_Left ((D + F (A, B, C) + Words (14) + T (14)), 12); C := D + Rotate_Left ((C + F (D, A, B) + Words (15) + T (15)), 17); B := C + Rotate_Left ((B + F (C, D, A) + Words (16) + T (16)), 22); -- round 2 A := B + Rotate_Left ((A + G (B, C, D) + Words (2) + T (17)), 5); D := A + Rotate_Left ((D + G (A, B, C) + Words (7) + T (18)), 9); C := D + Rotate_Left ((C + G (D, A, B) + Words (12) + T (19)), 14); B := C + Rotate_Left ((B + G (C, D, A) + Words (1) + T (20)), 20); A := B + Rotate_Left ((A + G (B, C, D) + Words (6) + T (21)), 5); D := A + Rotate_Left ((D + G (A, B, C) + Words (11) + T (22)), 9); C := D + Rotate_Left ((C + G (D, A, B) + Words (16) + T (23)), 14); B := C + Rotate_Left ((B + G (C, D, A) + Words (5) + T (24)), 20); A := B + Rotate_Left ((A + G (B, C, D) + Words (10) + T (25)), 5); D := A + Rotate_Left ((D + G (A, B, C) + Words (15) + T (26)), 9); C := D + Rotate_Left ((C + G (D, A, B) + Words (4) + T (27)), 14); B := C + Rotate_Left ((B + G (C, D, A) + Words (9) + T (28)), 20); A := B + Rotate_Left ((A + G (B, C, D) + Words (14) + T (29)), 5); D := A + Rotate_Left ((D + G (A, B, C) + Words (3) + T (30)), 9); C := D + Rotate_Left ((C + G (D, A, B) + Words (8) + T (31)), 14); B := C + Rotate_Left ((B + G (C, D, A) + Words (13) + T (32)), 20); -- round 3 A := B + Rotate_Left ((A + H (B, C, D) + Words (6) + T (33)), 4); D := A + Rotate_Left ((D + H (A, B, C) + Words (9) + T (34)), 11); C := D + Rotate_Left ((C + H (D, A, B) + Words (12) + T (35)), 16); B := C + Rotate_Left ((B + H (C, D, A) + Words (15) + T (36)), 23); A := B + Rotate_Left ((A + H (B, C, D) + Words (2) + T (37)), 4); D := A + Rotate_Left ((D + H (A, B, C) + Words (5) + T (38)), 11); C := D + Rotate_Left ((C + H (D, A, B) + Words (8) + T (39)), 16); B := C + Rotate_Left ((B + H (C, D, A) + Words (11) + T (40)), 23); A := B + Rotate_Left ((A + H (B, C, D) + Words (14) + T (41)), 4); D := A + Rotate_Left ((D + H (A, B, C) + Words (1) + T (42)), 11); C := D + Rotate_Left ((C + H (D, A, B) + Words (4) + T (43)), 16); B := C + Rotate_Left ((B + H (C, D, A) + Words (7) + T (44)), 23); A := B + Rotate_Left ((A + H (B, C, D) + Words (10) + T (45)), 4); D := A + Rotate_Left ((D + H (A, B, C) + Words (13) + T (46)), 11); C := D + Rotate_Left ((C + H (D, A, B) + Words (16) + T (47)), 16); B := C + Rotate_Left ((B + H (C, D, A) + Words (3) + T (48)), 23); -- round 4 A := B + Rotate_Left ((A + I (B, C, D) + Words (1) + T (49)), 6); D := A + Rotate_Left ((D + I (A, B, C) + Words (8) + T (50)), 10); C := D + Rotate_Left ((C + I (D, A, B) + Words (15) + T (51)), 15); B := C + Rotate_Left ((B + I (C, D, A) + Words (6) + T (52)), 21); A := B + Rotate_Left ((A + I (B, C, D) + Words (13) + T (53)), 6); D := A + Rotate_Left ((D + I (A, B, C) + Words (4) + T (54)), 10); C := D + Rotate_Left ((C + I (D, A, B) + Words (11) + T (55)), 15); B := C + Rotate_Left ((B + I (C, D, A) + Words (2) + T (56)), 21); A := B + Rotate_Left ((A + I (B, C, D) + Words (9) + T (57)), 6); D := A + Rotate_Left ((D + I (A, B, C) + Words (16) + T (58)), 10); C := D + Rotate_Left ((C + I (D, A, B) + Words (7) + T (59)), 15); B := C + Rotate_Left ((B + I (C, D, A) + Words (14) + T (60)), 21); A := B + Rotate_Left ((A + I (B, C, D) + Words (5) + T (61)), 6); D := A + Rotate_Left ((D + I (A, B, C) + Words (12) + T (62)), 10); C := D + Rotate_Left ((C + I (D, A, B) + Words (3) + T (63)), 15); B := C + Rotate_Left ((B + I (C, D, A) + Words (10) + T (64)), 21); -- increment A := A + AA; B := B + BB; C := C + CC; D := D + DD; end; end loop; return (Turn_Around (A), Turn_Around (B), Turn_Around (C), Turn_Around (D)); end MD5;
function To_String (Item : MD5_Hash) return MD5_String is Hex_Chars : constant array (0 .. 15) of Character := ('0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'); Result : MD5_String := (1 => '0', 2 => 'x', others => '0'); Temp : Int32; Position : Natural := Result'Last; begin for Part in reverse Item'Range loop Temp := Item (Part); while Position > Result'Last - (5 - Part) * 8 loop Result (Position) := Hex_Chars (Natural (Temp mod 16)); Position := Position - 1; Temp := Temp / 16; end loop; end loop; return Result; end To_String;
end MD5;</lang>
tester.adb: <lang Ada>with Ada.Strings.Unbounded; with Ada.Text_IO; with MD5;
procedure Tester is
use Ada.Strings.Unbounded; type String_Array is array (Positive range <>) of Unbounded_String; Sources : constant String_Array := (To_Unbounded_String (""), To_Unbounded_String ("a"), To_Unbounded_String ("abc"), To_Unbounded_String ("message digest"), To_Unbounded_String ("abcdefghijklmnopqrstuvwxyz"), To_Unbounded_String ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"), To_Unbounded_String ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") ); Digests : constant String_Array := (To_Unbounded_String ("0xd41d8cd98f00b204e9800998ecf8427e"), To_Unbounded_String ("0x0cc175b9c0f1b6a831c399e269772661"), To_Unbounded_String ("0x900150983cd24fb0d6963f7d28e17f72"), To_Unbounded_String ("0xf96b697d7cb7938d525a2f31aaf161d0"), To_Unbounded_String ("0xc3fcd3d76192e4007dfb496cca67e13b"), To_Unbounded_String ("0xd174ab98d277d9f5a5611c2c9f419d9f"), To_Unbounded_String ("0x57edf4a22be3c955ac49da2e2107b67a"));
begin
for I in Sources'Range loop Ada.Text_IO.Put_Line ("MD5 (""" & To_String (Sources (I)) & """):"); Ada.Text_IO.Put_Line (MD5.To_String (MD5.MD5 (To_String (Sources (I))))); Ada.Text_IO.Put_Line (To_String (Digests (I)) & " (correct value)"); end loop;
end Tester;</lang>
output:
MD5 (""): 0xd41d8cd98f00b204e9800998ecf8427e 0xd41d8cd98f00b204e9800998ecf8427e (correct value) MD5 ("a"): 0x0cc175b9c0f1b6a831c399e269772661 0x0cc175b9c0f1b6a831c399e269772661 (correct value) MD5 ("abc"): 0x900150983cd24fb0d6963f7d28e17f72 0x900150983cd24fb0d6963f7d28e17f72 (correct value) MD5 ("message digest"): 0xf96b697d7cb7938d525a2f31aaf161d0 0xf96b697d7cb7938d525a2f31aaf161d0 (correct value) MD5 ("abcdefghijklmnopqrstuvwxyz"): 0xc3fcd3d76192e4007dfb496cca67e13b 0xc3fcd3d76192e4007dfb496cca67e13b (correct value) MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"): 0xd174ab98d277d9f5a5611c2c9f419d9f 0xd174ab98d277d9f5a5611c2c9f419d9f (correct value) MD5 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890"): 0x57edf4a22be3c955ac49da2e2107b67a 0x57edf4a22be3c955ac49da2e2107b67a (correct value)
AutoHotkey
See the implementation at MD5#AutoHotkey.
BBC BASIC
<lang bbcbasic> PRINT FN_MD5("")
PRINT FN_MD5("a") PRINT FN_MD5("abc") PRINT FN_MD5("message digest") PRINT FN_MD5("abcdefghijklmnopqrstuvwxyz") PRINT FN_MD5("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") PRINT FN_MD5(STRING$(8,"1234567890")) END DEF FN_MD5(message$) LOCAL a%, b%, c%, d%, f%, g%, h0%, h1%, h2%, h3%, i%, bits%, chunk%, temp% LOCAL r&(), k%(), w%() DIM r&(63), k%(63), w%(15) REM r specifies the per-round shift amounts: r&() = 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, \ \ 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, \ \ 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, \ \ 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21 REM Use binary integer part of the sines of integers (Radians) as constants: FOR i% = 0 TO 63 k%(i%) = FN32(INT(ABS(SIN(i% + 1.0#)) * 2^32)) NEXT REM Initialize variables: h0% = &67452301 h1% = &EFCDAB89 h2% = &98BADCFE h3% = &10325476 bits% = LEN(message$)*8 REM Append '1' bit to message: message$ += CHR$&80 REM Append '0' bits until message length in bits = 448 (mod 512): WHILE (LEN(message$) MOD 64) <> 56 message$ += CHR$0 ENDWHILE REM Append length of message (before pre-processing), in bits, as REM 64-bit little-endian integer: FOR i% = 0 TO 56 STEP 8 message$ += CHR$(bits% >>> i%) NEXT REM Process the message in successive 512-bit chunks: FOR chunk% = 0 TO LEN(message$) DIV 64 - 1 REM Break chunk into sixteen 32-bit little-endian words: FOR i% = 0 TO 15 w%(i%) = !(!^message$ + 64*chunk% + 4*i%) NEXT i% REM Initialize hash value for this chunk: a% = h0% b% = h1% c% = h2% d% = h3% REM Main loop: FOR i% = 0 TO 63 CASE TRUE OF WHEN i% <= 15: f% = d% EOR (b% AND (c% EOR d%)) g% = i% WHEN 16 <= i% AND i% <= 31: f% = c% EOR (d% AND (b% EOR c%)) g% = (5 * i% + 1) MOD 16 WHEN 32 <= i% AND i% <= 47: f% = b% EOR c% EOR d% g% = (3 * i% + 5) MOD 16 OTHERWISE: f% = c% EOR (b% OR (NOT d%)) g% = (7 * i%) MOD 16 ENDCASE temp% = d% d% = c% c% = b% b% = FN32(b% + FNlrot(FN32(a% + f%) + FN32(k%(i%) + w%(g%)), r&(i%))) a% = temp% NEXT i% REM Add this chunk's hash to result so far: h0% = FN32(h0% + a%) h1% = FN32(h1% + b%) h2% = FN32(h2% + c%) h3% = FN32(h3% + d%) NEXT chunk% = FNrevhex(h0%) + FNrevhex(h1%) + FNrevhex(h2%) + FNrevhex(h3%) DEF FNrevhex(A%) SWAP ?(^A%+0),?(^A%+3) SWAP ?(^A%+1),?(^A%+2) = RIGHT$("0000000"+STR$~A%,8) DEF FNlrot(n#, r%) n# = FN32(n#) = (n# << r%) OR (n# >>> (32 - r%)) DEF FN32(n#) WHILE n# > &7FFFFFFF : n# -= 2^32 : ENDWHILE WHILE n# < &80000000 : n# += 2^32 : ENDWHILE = n#</lang>
C
See the implementation at MD5#C. Also, RFC 1321 already provides C code.
C#
Handwritten implementation ([1]): <lang csharp> public class MD5 { /***********************VARIABLES************************************/
/***********************Statics**************************************/
/// <summary>
/// lookup table 4294967296*sin(i)
/// </summary>
protected readonly static uint [] T =new uint[64]
{ 0xd76aa478,0xe8c7b756,0x242070db,0xc1bdceee,
0xf57c0faf,0x4787c62a,0xa8304613,0xfd469501,
0x698098d8,0x8b44f7af,0xffff5bb1,0x895cd7be, 0x6b901122,0xfd987193,0xa679438e,0x49b40821,
0xf61e2562,0xc040b340,0x265e5a51,0xe9b6c7aa,
0xd62f105d,0x2441453,0xd8a1e681,0xe7d3fbc8, 0x21e1cde6,0xc33707d6,0xf4d50d87,0x455a14ed,
0xa9e3e905,0xfcefa3f8,0x676f02d9,0x8d2a4c8a,
0xfffa3942,0x8771f681,0x6d9d6122,0xfde5380c, 0xa4beea44,0x4bdecfa9,0xf6bb4b60,0xbebfbc70, 0x289b7ec6,0xeaa127fa,0xd4ef3085,0x4881d05,
0xd9d4d039,0xe6db99e5,0x1fa27cf8,0xc4ac5665,
0xf4292244,0x432aff97,0xab9423a7,0xfc93a039, 0x655b59c3,0x8f0ccc92,0xffeff47d,0x85845dd1, 0x6fa87e4f,0xfe2ce6e0,0xa3014314,0x4e0811a1,
0xf7537e82,0xbd3af235,0x2ad7d2bb,0xeb86d391};
/*****instance variables**************/ /// <summary> /// X used to proces data in /// 512 bits chunks as 16 32 bit word /// </summary> protected uint [] X = new uint [16];
/// <summary> /// the finger print obtained. /// </summary> protected Digest dgFingerPrint;
/// <summary> /// the input bytes /// </summary> protected byte [] m_byteInput;
/**********************EVENTS AND DELEGATES*******************************************/
public delegate void ValueChanging (object sender,MD5ChangingEventArgs Changing); public delegate void ValueChanged (object sender,MD5ChangedEventArgs Changed);
public event ValueChanging OnValueChanging;
public event ValueChanged OnValueChanged;
/********************************************************************/ /***********************PROPERTIES ***********************/ /// <summary> ///gets or sets as string /// </summary> public string Value { get { string st ; char [] tempCharArray= new Char[m_byteInput.Length];
for(int i =0; i<m_byteInput.Length;i++) tempCharArray[i]=(char)m_byteInput[i];
st= new String(tempCharArray); return st; } set { /// raise the event to notify the changing if (this.OnValueChanging !=null) this.OnValueChanging(this,new MD5ChangingEventArgs(value));
m_byteInput=new byte[value.Length];
for (int i =0; i<value.Length;i++)
m_byteInput[i]=(byte)value[i];
dgFingerPrint=CalculateMD5Value();
/// raise the event to notify the change if (this.OnValueChanged !=null) this.OnValueChanged(this,new MD5ChangedEventArgs(value,dgFingerPrint.ToString()));
} }
/// <summary> /// get/sets as byte array /// </summary> public byte [] ValueAsByte { get { byte [] bt = new byte[m_byteInput.Length]; for (int i =0; i<m_byteInput.Length;i++) bt[i]=m_byteInput[i]; return bt;
}
set { /// raise the event to notify the changing if (this.OnValueChanging !=null) this.OnValueChanging(this,new MD5ChangingEventArgs(value));
m_byteInput=new byte[value.Length]; for (int i =0; i<value.Length;i++) m_byteInput[i]=value[i]; dgFingerPrint=CalculateMD5Value();
/// notify the changed value
if (this.OnValueChanged !=null)
this.OnValueChanged(this,new MD5ChangedEventArgs(value,dgFingerPrint.ToString()));
}
}
//gets the signature/figner print as string public string FingerPrint { get { return dgFingerPrint.ToString(); } }
/*************************************************************************/
/// <summary>
/// Constructor
/// </summary>
public MD5()
{
Value="";
}
/******************************************************************************/
/*********************METHODS**************************/
/// <summary> /// calculat md5 signature of the string in Input /// </summary> /// <returns> Digest: the finger print of msg</returns> protected Digest CalculateMD5Value() { /***********vairable declaration**************/ byte [] bMsg; //buffer to hold bits uint N; //N is the size of msg as word (32 bit) Digest dg =new Digest(); // the value to be returned
// create a buffer with bits padded and length is alos padded bMsg=CreatePaddedBuffer();
N=(uint)(bMsg.Length*8)/32; //no of 32 bit blocks
for (uint i=0; i<N/16;i++) { CopyBlock(bMsg,i); PerformTransformation(ref dg.A,ref dg.B,ref dg.C,ref dg.D); } return dg; }
/******************************************************** * TRANSFORMATIONS : FF , GG , HH , II acc to RFC 1321 * where each Each letter represnets the aux function used *********************************************************/
/// <summary> /// perform transformatio using f(((b&c) | (~(b)&d)) /// </summary> protected void TransF(ref uint a, uint b, uint c, uint d,uint k,ushort s, uint i ) { a = b + MD5Helper.RotateLeft((a + ((b&c) | (~(b)&d)) + X[k] + T[i-1]), s); }
/// <summary> /// perform transformatio using g((b&d) | (c & ~d) ) /// </summary> protected void TransG(ref uint a, uint b, uint c, uint d,uint k,ushort s, uint i ) { a = b + MD5Helper.RotateLeft((a + ((b&d) | (c & ~d) ) + X[k] + T[i-1]), s); }
/// <summary> /// perform transformatio using h(b^c^d) /// </summary> protected void TransH(ref uint a, uint b, uint c, uint d,uint k,ushort s, uint i ) { a = b + MD5Helper.RotateLeft((a + (b^c^d) + X[k] + T[i-1]), s); }
/// <summary> /// perform transformatio using i (c^(b|~d)) /// </summary> protected void TransI(ref uint a, uint b, uint c, uint d,uint k,ushort s, uint i ) { a = b + MD5Helper.RotateLeft((a + (c^(b|~d))+ X[k] + T[i-1]), s); }
/// <summary> /// Perform All the transformation on the data /// </summary> /// <param name="A">A</param> /// <param name="B">B </param> /// <param name="C">C</param> /// <param name="D">D</param> protected void PerformTransformation(ref uint A,ref uint B,ref uint C, ref uint D) { //// saving ABCD to be used in end of loop
uint AA,BB,CC,DD;
AA=A; BB=B; CC=C; DD=D;
/* Round 1 * [ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4] * [ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8] * [ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12] * [ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16] * * */ TransF(ref A,B,C,D,0,7,1);TransF(ref D,A,B,C,1,12,2);TransF(ref C,D,A,B,2,17,3);TransF(ref B,C,D,A,3,22,4); TransF(ref A,B,C,D,4,7,5);TransF(ref D,A,B,C,5,12,6);TransF(ref C,D,A,B,6,17,7);TransF(ref B,C,D,A,7,22,8); TransF(ref A,B,C,D,8,7,9);TransF(ref D,A,B,C,9,12,10);TransF(ref C,D,A,B,10,17,11);TransF(ref B,C,D,A,11,22,12); TransF(ref A,B,C,D,12,7,13);TransF(ref D,A,B,C,13,12,14);TransF(ref C,D,A,B,14,17,15);TransF(ref B,C,D,A,15,22,16); /** rOUND 2 **[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20] *[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24] *[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28] *[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32] */ TransG(ref A,B,C,D,1,5,17);TransG(ref D,A,B,C,6,9,18);TransG(ref C,D,A,B,11,14,19);TransG(ref B,C,D,A,0,20,20); TransG(ref A,B,C,D,5,5,21);TransG(ref D,A,B,C,10,9,22);TransG(ref C,D,A,B,15,14,23);TransG(ref B,C,D,A,4,20,24); TransG(ref A,B,C,D,9,5,25);TransG(ref D,A,B,C,14,9,26);TransG(ref C,D,A,B,3,14,27);TransG(ref B,C,D,A,8,20,28); TransG(ref A,B,C,D,13,5,29);TransG(ref D,A,B,C,2,9,30);TransG(ref C,D,A,B,7,14,31);TransG(ref B,C,D,A,12,20,32); /* rOUND 3 * [ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36] * [ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40] * [ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44] * [ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48] * */ TransH(ref A,B,C,D,5,4,33);TransH(ref D,A,B,C,8,11,34);TransH(ref C,D,A,B,11,16,35);TransH(ref B,C,D,A,14,23,36); TransH(ref A,B,C,D,1,4,37);TransH(ref D,A,B,C,4,11,38);TransH(ref C,D,A,B,7,16,39);TransH(ref B,C,D,A,10,23,40); TransH(ref A,B,C,D,13,4,41);TransH(ref D,A,B,C,0,11,42);TransH(ref C,D,A,B,3,16,43);TransH(ref B,C,D,A,6,23,44); TransH(ref A,B,C,D,9,4,45);TransH(ref D,A,B,C,12,11,46);TransH(ref C,D,A,B,15,16,47);TransH(ref B,C,D,A,2,23,48); /*ORUNF 4 *[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52] *[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56] *[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60] *[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64] * */ TransI(ref A,B,C,D,0,6,49);TransI(ref D,A,B,C,7,10,50);TransI(ref C,D,A,B,14,15,51);TransI(ref B,C,D,A,5,21,52); TransI(ref A,B,C,D,12,6,53);TransI(ref D,A,B,C,3,10,54);TransI(ref C,D,A,B,10,15,55);TransI(ref B,C,D,A,1,21,56); TransI(ref A,B,C,D,8,6,57);TransI(ref D,A,B,C,15,10,58);TransI(ref C,D,A,B,6,15,59);TransI(ref B,C,D,A,13,21,60); TransI(ref A,B,C,D,4,6,61);TransI(ref D,A,B,C,11,10,62);TransI(ref C,D,A,B,2,15,63);TransI(ref B,C,D,A,9,21,64);
A=A+AA;
B=B+BB;
C=C+CC;
D=D+DD;
}
/// <summary>
/// Create Padded buffer for processing , buffer is padded with 0 along
/// with the size in the end
/// </summary>
/// <returns>the padded buffer as byte array</returns>
protected byte[] CreatePaddedBuffer()
{
uint pad; //no of padding bits for 448 mod 512
byte [] bMsg; //buffer to hold bits
ulong sizeMsg; //64 bit size pad
uint sizeMsgBuff; //buffer size in multiple of bytes
int temp=(448-((m_byteInput.Length*8)%512)); //temporary
pad = (uint )((temp+512)%512); //getting no of bits to be pad
if (pad==0) ///pad is in bits
pad=512; //at least 1 or max 512 can be added
sizeMsgBuff= (uint) ((m_byteInput.Length)+ (pad/8)+8); sizeMsg=(ulong)m_byteInput.Length*8; bMsg=new byte[sizeMsgBuff]; ///no need to pad with 0 coz new bytes // are already initialize to 0 :)
////copying string to buffer
for (int i =0; i<m_byteInput.Length;i++)
bMsg[i]=m_byteInput[i];
bMsg[m_byteInput.Length]|=0x80; ///making first bit of padding 1,
//wrting the size value for (int i =8; i >0;i--) bMsg[sizeMsgBuff-i]=(byte) (sizeMsg>>((8-i)*8) & 0x00000000000000ff);
return bMsg; }
/// <summary>
/// Copies a 512 bit block into X as 16 32 bit words
/// </summary>
/// <param name="bMsg"> source buffer</param>
/// <param name="block">no of block to copy starting from 0</param>
protected void CopyBlock(byte[] bMsg,uint block)
{
block=block<<6; for (uint j=0; j<61;j+=4) { X[j>>2]=(((uint) bMsg[block+(j+3)]) <<24 ) | (((uint) bMsg[block+(j+2)]) <<16 ) | (((uint) bMsg[block+(j+1)]) <<8 ) | (((uint) bMsg[block+(j)]) ) ;
} } }
</lang>
Standard library-based implementation: <lang csharp> System.Security.Cryptography.MD5CryptoServiceProvider x = new System.Security.Cryptography.MD5CryptoServiceProvider(); byte[] bs = System.Text.Encoding.UTF8.GetBytes(password); bs = x.ComputeHash(bs); System.Text.StringBuilder s = new System.Text.StringBuilder(); foreach (byte b in bs) {
s.Append(b.ToString("x2").ToLower());
} password = s.ToString(); </lang>
CoffeeScript
<lang coffeescript>
- Array sum helper function.
sum = (array) ->
array.reduce (x, y) -> x + y
md5 = do ->
# Per-round shift amounts. s = [738695, 669989, 770404, 703814] s = (s[i >> 4] >> i % 4 * 5 & 31 for i in [0..63]) # Constants cache generated by sine. K = (Math.floor 2**32 * Math.abs Math.sin i for i in [1..64]) # Bitwise left rotate helper function. lrot = (x, y) -> x << y | x >>> 32 - y; (input) -> # Initialize values. d0 = 0x10325476; a0 = 0x67452301; b0 = ~d0 c0 = ~a0; # Convert the message to 32-bit words, little-endian. M = for i in [0...input.length] by 4 sum (input.charCodeAt(i + j) << j*8 for j in [0..3]) # Pre-processing: append a 1 bit, then message length % 2^64. len = input.length * 8 M[len >> 5] |= 128 << len % 32 M[(len + 64 >>> 9 << 4) + 14] = len # Process the message in chunks of 16 32-bit words. for x in [0...M.length] by 16 [A, B, C, D] = [a0, b0, c0, d0] # Main loop. for i in [0..63] if i < 16 F = B & C | ~B & D g = i else if i < 32 F = B & D | C & ~D g = i * 5 + 1 else if i < 48 F = B ^ C ^ D g = i * 3 + 5 else F = C ^ (B | ~D) g = i * 7 [A, B, C, D] = [D, B + lrot(A + F + K[i] + (M[x + g % 16] ? 0), s[i]), B, C] a0 += A b0 += B c0 += C d0 += D # Convert the four words back to a string. return ( for x in [a0, b0, c0, d0] (String.fromCharCode x >>> 8 * y & 255 for y in [0..3]).join ).join
</lang>
This implementation is more focused towards brevity rather than speed. Use a javascript MD5 implementation if speed is desired. Fork this code on github.
Note: this only works on byte strings. To use arbitrary Javascript strings, you must first encode as UTF-8.
And tests:
<lang coffeescript> str2hex = do ->
hex = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'] hex = (hex[x >> 4] + hex[x & 15] for x in [0..255]) (str) -> (hex[c.charCodeAt()] for c in str).join
console.log str2hex md5 message for message in [
"" "a" "abc" "message digest" "abcdefghijklmnopqrstuvwxyz" "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789" "12345678901234567890123456789012345678901234567890123456789012345678901234567890"
] </lang>
Output:
d41d8cd98f00b204e9800998ecf8427e 0cc175b9c0f1b6a831c399e269772661 900150983cd24fb0d6963f7d28e17f72 f96b697d7cb7938d525a2f31aaf161d0 c3fcd3d76192e4007dfb496cca67e13b d174ab98d277d9f5a5611c2c9f419d9f 57edf4a22be3c955ac49da2e2107b67a
D
The standard library Phobos included an MD5 module.
This code generates x86 assembly code by compile time functions, then mix-in the assembly code. It only works on x86 machine. <lang d>import std.bitmanip, core.stdc.string, std.conv, std.math, std.array,
std.string;
version (D_InlineAsm_X86) {} else {
static assert(false, "For X86 machine only.");
}
// CTFE construction of transform expressions. uint S(in uint n) pure nothrow @safe @nogc {
static immutable aux = [7u, 12, 17, 22, 5, 9, 14, 20, 4, 11, 16, 23, 6, 10, 15, 21]; return aux[(n / 16) * 4 + (n % 4)];
}
uint K(in uint n) pure nothrow @safe @nogc {
uint r = 0; if (n <= 15) r = n; else if (n <= 31) r = 5 * n + 1; else if (n <= 47) r = 3 * n + 5; else r = 7 * n; return r % 16;
}
uint T(in uint n) pure nothrow @nogc {
return cast(uint)(abs(sin(n + 1.0L)) * (2UL ^^ 32));
}
string[] ABCD(in int n) pure nothrow {
enum abcd = ["EAX", "EBX", "ECX", "EDX"]; return abcd[(64 - n) % 4 .. 4] ~ abcd[0 .. (64 - n) % 4];
}
string SUB(in int n, in string s) pure nothrow {
return s .replace("ax", n.ABCD[0]) .replace("bx", n.ABCD[1]) .replace("cx", n.ABCD[2]) .replace("dx", n.ABCD[3]);
}
// FF, GG, HH & II expressions part 1 (F, G, H, I). string fghi1(in int n) pure nothrow @nogc {
switch (n / 16) { case 0: // (bb & cc) | (~bb & dd) return q{ mov ESI, bx; mov EDI, bx; not ESI; and EDI, cx; and ESI, dx; or EDI, ESI; add ax, EDI; }; case 1: // (dd & bb) | (~dd & cc) return q{ mov ESI, dx; mov EDI, dx; not ESI; and EDI, bx; and ESI, cx; or EDI, ESI; add ax, EDI; }; case 2: // (bb ^ cc ^ dd) return q{ mov EDI, bx; xor EDI, cx; xor EDI, dx; add ax, EDI; }; case 3: // (cc ^ (bb | ~dd)) return q{ mov EDI, dx; not EDI; or EDI, bx; xor EDI, cx; add ax, EDI; }; default: assert(false); }
}
// FF, GG, HH & II expressions part 2. string fghi2(in int n) pure nothrow {
return q{ add ax, [EBP + 4 * KK]; add ax, TT; } ~ n.fghi1;
}
// FF, GG, HH & II expressions prepended with previous parts // & subsitute ABCD. string FGHI(in int n) pure nothrow {
// aa = ((aa << SS)|( aa >>> (32 - SS))) + bb = ROL(aa, SS) + bb return SUB(n, n.fghi2 ~ q{ rol ax, SS; add ax, bx; });
}
string genExpr(uint n) pure nothrow {
return FGHI(n) .replace("SS", n.S.text) .replace("KK", n.K.text) .replace("TT", "0x" ~ to!string(n.T, 16));
}
string genTransformCode(int n) pure nothrow {
return (n < 63) ? n.genExpr ~ genTransformCode(n + 1) : n.genExpr;
}
enum string coreZMD5 = 0.genTransformCode;
struct ZMD5 {
uint[4] state = [0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476]; ulong count; ubyte[64] buffer;
ubyte[64] padding = [ 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
private void transform(ubyte* block) pure nothrow @nogc { uint[16] x = void;
version (BigEndian) { foreach (immutable i; 0 .. 16) x[i] = littleEndianToNative!uint(*cast(ubyte[4]*)&block[i * 4]); } else { (cast(ubyte*)x.ptr)[0 .. 64] = block[0 .. 64]; }
auto pState = state.ptr; auto pBuffer = x.ptr;
asm pure nothrow @nogc { mov ESI, pState[EBP]; mov EDX, [ESI + 3 * 4]; mov ECX, [ESI + 2 * 4]; mov EBX, [ESI + 1 * 4]; mov EAX, [ESI + 0 * 4]; push EBP; push ESI;
mov EBP, pBuffer[EBP]; }
mixin("asm pure nothrow @nogc { " ~ coreZMD5 ~ "}");
asm pure nothrow @nogc { pop ESI; pop EBP; add [ESI + 0 * 4], EAX; add [ESI + 1 * 4], EBX; add [ESI + 2 * 4], ECX; add [ESI + 3 * 4], EDX; } x[] = 0; }
void update(in void[] input) pure nothrow @nogc { auto inputLen = input.length; uint index = (count >> 3) & 0b11_1111U; count += inputLen * 8; immutable uint partLen = 64 - index;
uint i; if (inputLen >= partLen) { memcpy(&buffer[index], input.ptr, partLen); transform(buffer.ptr); for (i = partLen; i + 63 < inputLen; i += 64) transform((cast(ubyte[])input)[i .. i + 64].ptr); index = 0; } else i = 0;
if (inputLen - i) memcpy(&buffer[index], &input[i], inputLen - i); }
void finish(ref ubyte[16] digest) pure nothrow @nogc { ubyte[8] bits = void; bits[0 .. 8] = nativeToLittleEndian(count)[];
immutable uint index = (count >> 3) & 0b11_1111U; immutable uint padLen = (index < 56) ? (56 - index) : (120 - index); update(padding[0 .. padLen]); update(bits);
digest[0 .. 4] = nativeToLittleEndian(state[0])[]; digest[4 .. 8] = nativeToLittleEndian(state[1])[]; digest[8 .. 12] = nativeToLittleEndian(state[2])[]; digest[12 .. 16] = nativeToLittleEndian(state[3])[];
// Zeroize sensitive information. memset(&this, 0, ZMD5.sizeof); }
}
string getDigestString(in void[][] data...) pure {
ZMD5 ctx; foreach (datum; data) ctx.update(datum); ubyte[16] digest; ctx.finish(digest); return format("%-(%02X%)", digest);
}
void main() { // Benchmark code --------------
import std.stdio, std.datetime, std.digest.md;
writefln(`md5 digest("") = %-(%02X%)`, "".md5Of); writefln(`zmd5 digest("") = %s`, "".getDigestString);
enum megaBytes = 512; writefln("\nTest performance / message size %dMBytes:", megaBytes); auto data = new float[megaBytes * 0x40000 + 13];
StopWatch sw; sw.start; immutable d1 = data.md5Of; sw.stop; immutable time1 = sw.peek.msecs / 1000.0; writefln("digest(data) = %-(%02X%)", d1); writefln("std.md5: %8.2f M/sec ( %8.2f secs)", megaBytes / time1, time1);
sw.reset; sw.start; immutable d2 = data.getDigestString; sw.stop; immutable time2 = sw.peek.msecs / 1000.0; writefln("digest(data) = %s", d2); writefln("zmd5 : %8.2f M/sec ( %8.2f secs)", megaBytes / time2, time2);
}</lang>
- Output (dmd compiler):
md5 digest("") = D41D8CD98F00B204E9800998ECF8427E zmd5 digest("") = D41D8CD98F00B204E9800998ECF8427E Test performance / message size 512MBytes: digest(data) = A36190ECA92203A477EFC4DAB966CE6F std.md5: 45.85 M/sec ( 11.17 secs) digest(data) = A36190ECA92203A477EFC4DAB966CE6F zmd5 : 244.86 M/sec ( 2.09 secs)
- Output (ldc2 compiler):
md5 digest("") = D41D8CD98F00B204E9800998ECF8427E zmd5 digest("") = D41D8CD98F00B204E9800998ECF8427E Test performance / message size 512MBytes: digest(data) = A36190ECA92203A477EFC4DAB966CE6F std.md5: 310.12 M/sec ( 1.65 secs) digest(data) = A36190ECA92203A477EFC4DAB966CE6F zmd5 : 277.06 M/sec ( 1.85 secs)
As you see this asm is much faster than the D code compiled by dmd, but the D code compiled by ldc2 is a little faster still.
Go
A limitation from RFC 1321 is that the function md5 takes a string which is a number of whole bytes. Messages of arbitrary bit length are not supported. <lang go>package main
import (
"fmt" "math" "bytes" "encoding/binary"
)
type testCase struct {
hashCode string string
}
var testCases = []testCase{
{"d41d8cd98f00b204e9800998ecf8427e", ""}, {"0cc175b9c0f1b6a831c399e269772661", "a"}, {"900150983cd24fb0d6963f7d28e17f72", "abc"}, {"f96b697d7cb7938d525a2f31aaf161d0", "message digest"}, {"c3fcd3d76192e4007dfb496cca67e13b", "abcdefghijklmnopqrstuvwxyz"}, {"d174ab98d277d9f5a5611c2c9f419d9f", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"}, {"57edf4a22be3c955ac49da2e2107b67a", "12345678901234567890" + "123456789012345678901234567890123456789012345678901234567890"},
}
func main() {
for _, tc := range testCases { fmt.Printf("%s\n%x\n\n", tc.hashCode, md5(tc.string)) }
}
var shift = [...]uint{7, 12, 17, 22, 5, 9, 14, 20, 4, 11, 16, 23, 6, 10, 15, 21} var table [64]uint32
func init() {
for i := range table { table[i] = uint32((1 << 32) * math.Abs(math.Sin(float64(i + 1)))) }
}
func md5(s string) (r [16]byte) {
padded := bytes.NewBuffer([]byte(s)) padded.WriteByte(0x80) for padded.Len() % 64 != 56 { padded.WriteByte(0) } messageLenBits := uint64(len(s)) * 8 binary.Write(padded, binary.LittleEndian, messageLenBits)
var a, b, c, d uint32 = 0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476 var buffer [16]uint32 for binary.Read(padded, binary.LittleEndian, buffer[:]) == nil { // read every 64 bytes a1, b1, c1, d1 := a, b, c, d for j := 0; j < 64; j++ { var f uint32 bufferIndex := j round := j >> 4 switch round { case 0: f = (b1 & c1) | (^b1 & d1) case 1: f = (b1 & d1) | (c1 & ^d1) bufferIndex = (bufferIndex*5 + 1) & 0x0F case 2: f = b1 ^ c1 ^ d1 bufferIndex = (bufferIndex*3 + 5) & 0x0F case 3: f = c1 ^ (b1 | ^d1) bufferIndex = (bufferIndex * 7) & 0x0F } sa := shift[(round<<2)|(j&3)] a1 += f + buffer[bufferIndex] + table[j] a1, d1, c1, b1 = d1, c1, b1, a1<<sa|a1>>(32-sa)+b1 } a, b, c, d = a+a1, b+b1, c+c1, d+d1 }
binary.Write(bytes.NewBuffer(r[:0]), binary.LittleEndian, []uint32{a, b, c, d}) return
}</lang> Output:
d41d8cd98f00b204e9800998ecf8427e d41d8cd98f00b204e9800998ecf8427e 0cc175b9c0f1b6a831c399e269772661 0cc175b9c0f1b6a831c399e269772661 900150983cd24fb0d6963f7d28e17f72 900150983cd24fb0d6963f7d28e17f72 f96b697d7cb7938d525a2f31aaf161d0 f96b697d7cb7938d525a2f31aaf161d0 c3fcd3d76192e4007dfb496cca67e13b c3fcd3d76192e4007dfb496cca67e13b d174ab98d277d9f5a5611c2c9f419d9f d174ab98d277d9f5a5611c2c9f419d9f 57edf4a22be3c955ac49da2e2107b67a 57edf4a22be3c955ac49da2e2107b67a
Haskell
<lang haskell>import Control.Monad (replicateM)
import qualified Data.ByteString.Lazy as BL import qualified Data.ByteString.Lazy.Char8 as BLC import Data.Binary.Get import Data.Binary.Put import Data.Bits
import Data.Array (Array, listArray, (!)) import Data.List (foldl) import Data.Word (Word32)
import Numeric (showHex)
-- functions
type Fun = Word32 -> Word32 -> Word32 -> Word32
funF, funG, funH, funI :: Fun funF x y z = (x .&. y) .|. (complement x .&. z) funG x y z = (x .&. z) .|. (complement z .&. y) funH x y z = x `xor` y `xor` z funI x y z = y `xor` (complement z .|. x)
idxF, idxG, idxH, idxI :: Int -> Int idxF i = i idxG i = (5 * i + 1) `mod` 16 idxH i = (3 * i + 5) `mod` 16 idxI i = 7 * i `mod` 16
-- arrays
funA :: Array Int Fun
funA = listArray (1,64) $ replicate 16 =<< [funF, funG, funH, funI]
idxA :: Array Int Int idxA = listArray (1,64) $ zipWith ($) (replicate 16 =<< [idxF, idxG, idxH, idxI]) [0..63]
rotA :: Array Int Int rotA = listArray (1,64) $ concat . replicate 4 =<<
[[7, 12, 17, 22], [5, 9, 14, 20], [4, 11, 16, 23], [6, 10, 15, 21]]
sinA :: Array Int Word32 sinA = listArray (1,64) $ map (floor . (*mult) . abs . sin) [1..64]
where mult = 2 ** 32 :: Double
-- to lazily calculate MD5 sum for standart input:
-- main = putStrLn . md5sum =<< BL.getContents
main :: IO () main = mapM_ (putStrLn . md5sum . BLC.pack)
[ "" , "a" , "abc" , "message digest" , "abcdefghijklmnopqrstuvwxyz" , "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789" , "12345678901234567890123456789012345678901234567890123456789012345678901234567890" ]
md5sum :: BL.ByteString -> String
md5sum input =
let MD5 a b c d = getMD5 initial `runGet` input in foldr hex [] . BL.unpack . runPut $ mapM_ putWord32le [a,b,c,d] where initial = MD5 0x67452301 0xEFCDAB89 0x98BADCFE 0x10325476
hex x s | x < 16 = '0' : showHex x s -- quick hack: like "%02x" | otherwise = showHex x s
data MD5 = MD5
{ a :: {-# UNPACK #-} !Word32 , b :: {-# UNPACK #-} !Word32 , c :: {-# UNPACK #-} !Word32 , d :: {-# UNPACK #-} !Word32 }
getMD5 :: MD5 -> Get MD5
getMD5 md5 = do
chunk <- getLazyByteString 64 let len = BL.length chunk
if len == 64 then getMD5 $! md5 <+> chunk -- apply and process next chunk
else do -- input is totally eaten, finalize bytes <- bytesRead let fin = runPut . putWord64le $ fromIntegral (bytes - 64 + len) * 8 pad n = chunk `BL.append` (0x80 `BL.cons` BL.replicate (n - 1) 0x00)
return $ if len >= 56 then md5 <+> pad (64 - len) <+> BL.replicate 56 0x00 `BL.append` fin else md5 <+> pad (56 - len) `BL.append` fin
(<+>) :: MD5 -> BL.ByteString -> MD5
infixl 5 <+>
md5@(MD5 a b c d) <+> bs =
let datA = listArray (0,15) $ replicateM 16 getWord32le `runGet` bs MD5 a' b' c' d' = foldl' (md5round datA) md5 [1..64] in MD5 (a + a') (b + b') (c + c') (d + d')
md5round :: Array Int Word32 -> MD5 -> Int -> MD5
md5round datA (MD5 a b c d) i =
let f = funA ! i w = datA ! (idxA ! i) a' = b + (a + f b c d + w + sinA ! i) `rotateL` rotA ! i in MD5 d a' b c</lang>
Icon and Unicon
The following program is based on part on the Wikipedia pseudo-code and in part on the reference implementation in RFC 1321. The implementation uses large integers. The solution works in both Icon and Unicon. One limitation of this implementation is that will not handle arbitrary (bit) length messages - all are byte aligned. Another small challenge was that Icon/Unicon bit manipulation functions work on signed integers (and large integers), as a result there are no native rotation and negation functions. <lang Icon>procedure main() # validate against the RFC test strings and more
testMD5("The quick brown fox jumps over the lazy dog", 16r9e107d9d372bb6826bd81d3542a419d6) testMD5("The quick brown fox jumps over the lazy dog.", 16re4d909c290d0fb1ca068ffaddf22cbd0) testMD5("", 16rd41d8cd98f00b204e9800998ecf8427e) #R = MD5 test suite from RFC testMD5("a", 16r0cc175b9c0f1b6a831c399e269772661) #R testMD5("abc", 16r900150983cd24fb0d6963f7d28e17f72) #R testMD5("message digest", 16rf96b697d7cb7938d525a2f31aaf161d0) #R testMD5("abcdefghijklmnopqrstuvwxyz", 16rc3fcd3d76192e4007dfb496cca67e13b) #R testMD5("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", 16rd174ab98d277d9f5a5611c2c9f419d9f) #R testMD5("12345678901234567890123456789012345678901234567890123456789012345678901234567890", 16r57edf4a22be3c955ac49da2e2107b67a) #R
end
procedure testMD5(s,rh) # compute the MD5 hash and compare it to reference value
write("Message(length=",*s,") = ",image(s)) write("Digest = ",hexstring(h := MD5(s)),if h = rh then " matches reference hash" else (" does not match reference hash = " || hexstring(rh)),"\n")
end
link hexcvt # for testMD5
$define B32 4 # 32 bits $define B64 8 # 64 bits in bytes $define B512 64 # 512 bits in bytes $define M32 16r100000000 # 2^32 $define M64 16r10000000000000000 # 2^64
procedure MD5(s) #: return MD5 hash of message s local w,a,b,c,d,i,t,m local mlength,message,hash static rs,ks,istate,maxpad,g
initial {
every (rs := []) |||:= (t := [ 7, 12, 17, 22] | [ 5, 9, 14, 20] | [ 4, 11, 16, 23] | [ 6, 10, 15, 21]) ||| t ||| t ||| t every put(ks := [],integer(M32 * abs(sin(i := 1 to 64)))) istate := [ 16r67452301, 16rEFCDAB89, 16r98BADCFE, 16r10325476 ] # "Magic" IV maxpad := left(char(16r80),B512+B64,char(16r00)) # maximum possible padding g := [] every i := 0 to 63 do # precompute offsets case round := i/16 of { 0 : put(g,i + 1) 1 : put(g,(5*i+1) % 16 + 1)
2 : put(g,(3*i+5) % 16 + 1)
3 : put(g,(7*i) % 16 + 1) } if not (*rs = *ks = 64) then runerr(500,"MD5 setup error") } # 1. Construct prefix t := (*s*8)%M64 # original message length s ||:= maxpad # append maximum padding s[0-:*s%B512] := "" # trim to final length s[0-:B64] := reverse(unsigned2string(t,B64) ) # as little endian length message := [] # 2. Subdivide message s ? while put(message,move(B512)) # into 512 bit blocks
# 3. Transform message ... state := copy(istate) # Initialize hashes every m := !message do { # For each message block w := [] m ? while put(w,unsigned(reverse(move(B32)))) # break into little-endian words
a := state[1] # pick up hashes b := state[2] c := state[3] d := state[4]
every i := 1 to 64 do { # Process 4 rounds of hashes case round := (i-1)/16 of {
0 : a +:= ixor(d, iand(b,ixor(c,d))) # 0..15 - alternate F
1 : a +:= ixor(c,iand(d,ixor(b,c))) # 16..31 - alternate G 2 : a +:= ixor(b,ixor(c,d)) # 32..47 - H 3 : a +:= ixor(c,ior(b,ixor(d,16rffffffff))) # 48..64 - alternate I
} # Core of FF, GG, HH, II
a +:= ks[i] + w[g[i]] # and the rest a %:= M32 a := ior( ishift(a,rs[i]), ishift(a,-(32-rs[i]))) # 32bit rotate a +:= b a :=: b :=: c :=: d # rotate variables
}
state[1] +:= a # Add back new hashes state[2] +:= b state[3] +:= c state[4] +:= d every !state %:= M32 # mod 2^32 } every (hash := "") ||:= reverse(unsigned2string(!state,4)) # little-endian digest return unsigned(hash)
end
procedure unsigned2string(i,w) # uint to string pad to w bytes local s
if i < 0 then runerr(500,i) s := "" while (0 < i) | (*s < \w) do { s ||:= char(i % 256) i /:= 256 } return reverse(s)
end
link unsigned # string to unsigned integer</lang>
The
provides unsigned and hexcvt Sample Output (abridged):
Message(length=43) = "The quick brown fox jumps over the lazy dog" Digest = 9E107D9D372BB6826BD81D3542A419D6 matches reference hash Message(length=44) = "The quick brown fox jumps over the lazy dog." Digest = E4D909C290D0FB1CA068FFADDF22CBD0 matches reference hash Message(length=0) = "" Digest = D41D8CD98F00B204E9800998ECF8427E matches reference hash Message(length=1) = "a" Digest = CC175B9C0F1B6A831C399E269772661 matches reference hash ...
J
Note: the following code was originally extracted from http://www.jsoftware.com/trac/addons/browser/trunk/convert/misc/md5.ijs
<lang j>NB. RSA Data Security, Inc. MD5 Message-Digest Algorithm NB. version: 1.0.2 NB. NB. See RFC 1321 for license details NB. J implementation -- (C) 2003 Oleg Kobchenko; NB. NB. 09/04/2003 Oleg Kobchenko NB. 03/31/2007 Oleg Kobchenko j601, JAL
require 'convert'
NB. lt= (*. -.)~ gt= *. -. ge= +. -. xor= ~: '`lt gt ge xor'=: (20 b.)`(18 b.)`(27 b.)`(22 b.) '`and or rot sh'=: (17 b.)`(23 b.)`(32 b.)`(33 b.) add=: (+&(_16&sh) (16&sh@(+ _16&sh) or and&65535@]) +&(and&65535))"0 hexlist=: tolower@:,@:hfd@:,@:(|."1)@(256 256 256 256&#:)
cmn=: 4 : 0
'x s t'=. x [ 'q a b'=. y b add s rot (a add q) add (x add t)
)
ff=: cmn (((1&{ and 2&{) or 1&{ lt 3&{) , 2&{.) gg=: cmn (((1&{ and 3&{) or 2&{ gt 3&{) , 2&{.) hh=: cmn (((1&{ xor 2&{)xor 3&{ ) , 2&{.) ii=: cmn (( 2&{ xor 1&{ ge 3&{ ) , 2&{.) op=: ff`gg`hh`ii
I=: ".;._2(0 : 0)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 6 11 0 5 10 15 4 9 14 3 8 13 2 7 12 5 8 11 14 1 4 7 10 13 0 3 6 9 12 15 2 0 7 14 5 12 3 10 1 8 15 6 13 4 11 2 9
) S=: 4 4$7 12 17 22 5 9 14 20 4 11 16 23 6 10 15 21
T=: |:".;._2(0 : 0)
_680876936 _165796510 _378558 _198630844 _389564586 _1069501632 _2022574463 1126891415 606105819 643717713 1839030562 _1416354905 _1044525330 _373897302 _35309556 _57434055 _176418897 _701558691 _1530992060 1700485571 1200080426 38016083 1272893353 _1894986606 _1473231341 _660478335 _155497632 _1051523 _45705983 _405537848 _1094730640 _2054922799 1770035416 568446438 681279174 1873313359 _1958414417 _1019803690 _358537222 _30611744 _42063 _187363961 _722521979 _1560198380 _1990404162 1163531501 76029189 1309151649 1804603682 _1444681467 _640364487 _145523070 _40341101 _51403784 _421815835 _1120210379 _1502002290 1735328473 530742520 718787259 1236535329 _1926607734 _995338651 _343485551
)
norm=: 3 : 0
n=. 16 * 1 + _6 sh 8 + #y b=. n#0 [ y=. a.i.y for_i. i. #y do. b=. ((j { b) or (8*4|i) sh i{y) (j=. _2 sh i) } b end. b=. ((j { b) or (8*4|i) sh 128) (j=._2 sh i=.#y) } b _16]\ (8 * #y) (n-2) } b
)
NB.*md5 v MD5 Message-Digest Algorithm NB. diagest=. md5 message md5=: 3 : 0
X=. norm y q=. r=. 1732584193 _271733879 _1732584194 271733878 for_x. X do. for_j. i.4 do. l=. ((j{I){x) ,. (16$j{S) ,. j{T for_i. i.16 do. r=. _1|.((i{l) (op@.j) r),}.r end. end. q=. r=. r add q end. hexlist r
)</lang>
<lang j> md5 d41d8cd98f00b204e9800998ecf8427e
md5'a'
0cc175b9c0f1b6a831c399e269772661
md5'abc'
900150983cd24fb0d6963f7d28e17f72
md5'message digest'
f96b697d7cb7938d525a2f31aaf161d0
md5'abcdefghijklmnopqrstuvwxyz'
c3fcd3d76192e4007dfb496cca67e13b
md5'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'
d174ab98d277d9f5a5611c2c9f419d9f
md5'12345678901234567890123456789012345678901234567890123456789012345678901234567890'
57edf4a22be3c955ac49da2e2107b67a </lang>
Java
Based on RFC-1321. <lang java>class MD5 {
private static final int INIT_A = 0x67452301; private static final int INIT_B = (int)0xEFCDAB89L; private static final int INIT_C = (int)0x98BADCFEL; private static final int INIT_D = 0x10325476; private static final int[] SHIFT_AMTS = { 7, 12, 17, 22, 5, 9, 14, 20, 4, 11, 16, 23, 6, 10, 15, 21 }; private static final int[] TABLE_T = new int[64]; static { for (int i = 0; i < 64; i++) TABLE_T[i] = (int)(long)((1L << 32) * Math.abs(Math.sin(i + 1))); } public static byte[] computeMD5(byte[] message) { int messageLenBytes = message.length; int numBlocks = ((messageLenBytes + 8) >>> 6) + 1; int totalLen = numBlocks << 6; byte[] paddingBytes = new byte[totalLen - messageLenBytes]; paddingBytes[0] = (byte)0x80; long messageLenBits = (long)messageLenBytes << 3; for (int i = 0; i < 8; i++) { paddingBytes[paddingBytes.length - 8 + i] = (byte)messageLenBits; messageLenBits >>>= 8; } int a = INIT_A; int b = INIT_B; int c = INIT_C; int d = INIT_D; int[] buffer = new int[16]; for (int i = 0; i < numBlocks; i ++) { int index = i << 6; for (int j = 0; j < 64; j++, index++) buffer[j >>> 2] = ((int)((index < messageLenBytes) ? message[index] : paddingBytes[index - messageLenBytes]) << 24) | (buffer[j >>> 2] >>> 8); int originalA = a; int originalB = b; int originalC = c; int originalD = d; for (int j = 0; j < 64; j++) { int div16 = j >>> 4; int f = 0; int bufferIndex = j; switch (div16) { case 0: f = (b & c) | (~b & d); break; case 1: f = (b & d) | (c & ~d); bufferIndex = (bufferIndex * 5 + 1) & 0x0F; break; case 2: f = b ^ c ^ d; bufferIndex = (bufferIndex * 3 + 5) & 0x0F; break; case 3: f = c ^ (b | ~d); bufferIndex = (bufferIndex * 7) & 0x0F; break; } int temp = b + Integer.rotateLeft(a + f + buffer[bufferIndex] + TABLE_T[j], SHIFT_AMTS[(div16 << 2) | (j & 3)]); a = d; d = c; c = b; b = temp; } a += originalA; b += originalB; c += originalC; d += originalD; } byte[] md5 = new byte[16]; int count = 0; for (int i = 0; i < 4; i++) { int n = (i == 0) ? a : ((i == 1) ? b : ((i == 2) ? c : d)); for (int j = 0; j < 4; j++) { md5[count++] = (byte)n; n >>>= 8; } } return md5; } public static String toHexString(byte[] b) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < b.length; i++) { sb.append(String.format("%02X", b[i] & 0xFF)); } return sb.toString(); }
public static void main(String[] args) { String[] testStrings = { "", "a", "abc", "message digest", "abcdefghijklmnopqrstuvwxyz", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", "12345678901234567890123456789012345678901234567890123456789012345678901234567890" }; for (String s : testStrings) System.out.println("0x" + toHexString(computeMD5(s.getBytes())) + " <== \"" + s + "\""); return; }
}</lang>
Output:
0xD41D8CD98F00B204E9800998ECF8427E <== "" 0x0CC175B9C0F1B6A831C399E269772661 <== "a" 0x900150983CD24FB0D6963F7D28E17F72 <== "abc" 0xF96B697D7CB7938D525A2F31AAF161D0 <== "message digest" 0xC3FCD3D76192E4007DFB496CCA67E13B <== "abcdefghijklmnopqrstuvwxyz" 0xD174AB98D277D9F5A5611C2C9F419D9F <== "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789" 0x57EDF4A22BE3C955AC49DA2E2107B67A <== "12345678901234567890123456789012345678901234567890123456789012345678901234567890"
Using ByteBuffer
s
<lang java>import java.nio.ByteBuffer;
import java.nio.ByteOrder;
class MD5 {
private static final int INIT_A = 0x67452301; private static final int INIT_B = (int)0xEFCDAB89L; private static final int INIT_C = (int)0x98BADCFEL; private static final int INIT_D = 0x10325476; private static final int[] SHIFT_AMTS = { 7, 12, 17, 22, 5, 9, 14, 20, 4, 11, 16, 23, 6, 10, 15, 21 }; private static final int[] TABLE_T = new int[64]; static { for (int i = 0; i < 64; i++) TABLE_T[i] = (int)(long)((1L << 32) * Math.abs(Math.sin(i + 1))); } public static byte[] computeMD5(byte[] message) { ByteBuffer padded = ByteBuffer.allocate((((message.length + 8) / 64) + 1) * 64).order(ByteOrder.LITTLE_ENDIAN); padded.put(message); padded.put((byte)0x80); long messageLenBits = (long)message.length * 8; padded.putLong(padded.capacity() - 8, messageLenBits);
padded.rewind();
int a = INIT_A; int b = INIT_B; int c = INIT_C; int d = INIT_D; while (padded.hasRemaining()) { // obtain a slice of the buffer from the current position, // and view it as an array of 32-bit ints IntBuffer chunk = padded.slice().order(ByteOrder.LITTLE_ENDIAN).asIntBuffer(); int originalA = a; int originalB = b; int originalC = c; int originalD = d; for (int j = 0; j < 64; j++) { int div16 = j >>> 4; int f = 0; int bufferIndex = j; switch (div16) { case 0: f = (b & c) | (~b & d); break; case 1: f = (b & d) | (c & ~d); bufferIndex = (bufferIndex * 5 + 1) & 0x0F; break; case 2: f = b ^ c ^ d; bufferIndex = (bufferIndex * 3 + 5) & 0x0F; break; case 3: f = c ^ (b | ~d); bufferIndex = (bufferIndex * 7) & 0x0F; break; } int temp = b + Integer.rotateLeft(a + f + chunk.get(bufferIndex) + TABLE_T[j], SHIFT_AMTS[(div16 << 2) | (j & 3)]); a = d; d = c; c = b; b = temp; } a += originalA; b += originalB; c += originalC; d += originalD; padded.position(padded.position() + 64); } ByteBuffer md5 = ByteBuffer.allocate(16).order(ByteOrder.LITTLE_ENDIAN); for (int n : new int[]{a, b, c, d}) { md5.putInt(n); } return md5.array(); } public static String toHexString(byte[] b) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < b.length; i++) { sb.append(String.format("%02X", b[i] & 0xFF)); } return sb.toString(); }
public static void main(String[] args) { String[] testStrings = { "", "a", "abc", "message digest", "abcdefghijklmnopqrstuvwxyz", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", "12345678901234567890123456789012345678901234567890123456789012345678901234567890" }; for (String s : testStrings) System.out.println("0x" + toHexString(computeMD5(s.getBytes())) + " <== \"" + s + "\""); return; }
}</lang>
Output:
0xD41D8CD98F00B204E9800998ECF8427E <== "" 0x0CC175B9C0F1B6A831C399E269772661 <== "a" 0x900150983CD24FB0D6963F7D28E17F72 <== "abc" 0xF96B697D7CB7938D525A2F31AAF161D0 <== "message digest" 0xC3FCD3D76192E4007DFB496CCA67E13B <== "abcdefghijklmnopqrstuvwxyz" 0xD174AB98D277D9F5A5611C2C9F419D9F <== "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789" 0x57EDF4A22BE3C955AC49DA2E2107B67A <== "12345678901234567890123456789012345678901234567890123456789012345678901234567890"
Liberty BASIC
See the implementation at MD5#Liberty BASIC.
Mathematica
<lang Mathematica>md5[string_String] :=
Module[{r = {7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21}, k = Table[Floor[2^32*Abs@Sin@i], {i, 1, 64}], h0 = 16^^67452301, h1 = 16^^efcdab89, h2 = 16^^98badcfe, h3 = 16^^10325476, data = Partition[ Join[FromDigits[Reverse@#, 256] & /@ Partition[ PadRight[Append[#, 128], Mod[56, 64, Length@# + 1]], 4], Reverse@IntegerDigits[8 Length@#, 2^32, 2]] &@ ImportString[string, "Binary"], 16], a, b, c, d, f, g}, Do[{a, b, c, d} = {h0, h1, h2, h3}; Do[Which[1 <= i <= 16, f = BitOr[BitAnd[b, c], BitAnd[BitNot[b], d]]; g = i - 1, 17 <= i <= 32, f = BitOr[BitAnd[d, b], BitAnd[BitNot[d], c]]; g = Mod[5 i - 4, 16], 33 <= i <= 48, f = BitXor[b, c, d]; g = Mod[3 i + 2, 16], 49 <= i <= 64, f = BitXor[c, BitOr[b, BitNot[d] + 2^32]]; g = Mod[7 i - 7, 16]]; {a, b, c, d} = {d, BitOr[BitShiftLeft[#1, #2], BitShiftRight[#1, 32 - #2]] &[ Mod[a + f + ki + wg + 1, 2^32], ri] + b, b, c}, {i, 1, 64}]; {h0, h1, h2, h3} = Mod[{h0, h1, h2, h3} + {a, b, c, d}, 2^32], {w, data}]; "0x" ~~ IntegerString[ FromDigits[ Flatten[Reverse@IntegerDigits[#, 256, 4] & /@ {h0, h1, h2, h3}], 256], 16, 32]]
</lang> Example: <lang Mathematica>md5["12345678901234567890123456789012345678901234567890123456789012345678901234567890"]</lang> Output: <lang Mathematica>0x57edf4a22be3c955ac49da2e2107b67a</lang>
MATLAB / Octave
See the implementation at MD5#MATLAB.
Modula-3
<lang modula3>INTERFACE MD5;
IMPORT Word;
TYPE Digest = ARRAY [0..15] OF CHAR; TYPE Buffer = ARRAY [0..63] OF CHAR;
TYPE T = RECORD
state: ARRAY [0..3] OF Word.T; count: ARRAY [0..1] OF Word.T; buffer: Buffer;
END;
PROCEDURE Init(VAR md5ctx: T); PROCEDURE Update(VAR md5ctx: T; input: TEXT); PROCEDURE Final(VAR md5ctx: T): Digest; PROCEDURE ToText(hash: Digest): TEXT;
END MD5.</lang> <lang modula3>MODULE MD5;
IMPORT Word, Text, Fmt;
CONST S11 = 7; S12 = 12; S13 = 17; S14 = 22;
S21 = 5; S22 = 9; S23 = 14; S24 = 20; S31 = 4; S32 = 11; S33 = 16; S34 = 23; S41 = 6; S42 = 10; S43 = 15; S44 = 21; pad1 = "\200\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000"; pad2 = "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000"; pad3 = "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000"; pad4 = "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000"; padding = pad1 & pad2 & pad3 & pad4;
PROCEDURE Init(VAR md5ctx: T) =
BEGIN <*ASSERT Word.Size = 32*> md5ctx.count[0] := 0; md5ctx.count[1] := 0;
md5ctx.state[0] := 16_67452301; md5ctx.state[1] := 16_efcdab89; md5ctx.state[2] := 16_98badcfe; md5ctx.state[3] := 16_10325476; END Init;
PROCEDURE Transform(VAR state: ARRAY [0..3] OF Word.T;
VAR input: Buffer) = VAR a, b, c, d: INTEGER; x: ARRAY [0..15] OF INTEGER;
PROCEDURE Decode(VAR x: ARRAY [0..15] OF INTEGER; VAR input: Buffer) = BEGIN FOR i := 0 TO 15 DO x[i] := Word.Insert(x[i], ORD(input[4*i+0]), 0, 8); x[i] := Word.Insert(x[i], ORD(input[4*i+1]), 8, 8); x[i] := Word.Insert(x[i], ORD(input[4*i+2]), 16, 8); x[i] := Word.Insert(x[i], ORD(input[4*i+3]), 24, 8); END; END Decode;
PROCEDURE FF(VAR a: INTEGER; b, c, d, x, s, ac: INTEGER) = PROCEDURE F(x, y, z: INTEGER): INTEGER = BEGIN RETURN Word.Or(Word.And(x, y), Word.And(Word.Not(x), z)); END F; BEGIN a := b + Word.Rotate(a + F(b, c, d) + x + ac, s); END FF;
PROCEDURE GG(VAR a: INTEGER; b, c, d, x, s, ac: INTEGER) = PROCEDURE G(x, y, z: INTEGER): INTEGER = BEGIN RETURN Word.Or(Word.And(x, z), Word.And(y, Word.Not(z))); END G; BEGIN a := b + Word.Rotate(a + G(b, c, d) + x + ac, s); END GG;
PROCEDURE HH(VAR a: INTEGER; b, c, d, x, s, ac: INTEGER) = PROCEDURE H(x, y, z: INTEGER): INTEGER = BEGIN RETURN Word.Xor(x, Word.Xor(y,z)); END H; BEGIN a := b + Word.Rotate(a + H(b, c, d) + x + ac, s); END HH;
PROCEDURE II(VAR a: INTEGER; b, c, d, x, s, ac: INTEGER) = PROCEDURE I(x, y, z: INTEGER): INTEGER = BEGIN RETURN Word.Xor(y, Word.Or(x, Word.Not(z))) END I; BEGIN a := b + Word.Rotate(a + I(b, c, d) + x + ac, s) END II;
BEGIN Decode(x, input); a := state[0]; b := state[1]; c := state[2]; d := state[3]; (* Round 1 *) FF(a, b, c, d, x[ 0], S11, 16_d76aa478); (* 1 *) FF(d, a, b, c, x[ 1], S12, 16_e8c7b756); (* 2 *) FF(c, d, a, b, x[ 2], S13, 16_242070db); (* 3 *) FF(b, c, d, a, x[ 3], S14, 16_c1bdceee); (* 4 *) FF(a, b, c, d, x[ 4], S11, 16_f57c0faf); (* 5 *) FF(d, a, b, c, x[ 5], S12, 16_4787c62a); (* 6 *) FF(c, d, a, b, x[ 6], S13, 16_a8304613); (* 7 *) FF(b, c, d, a, x[ 7], S14, 16_fd469501); (* 8 *) FF(a, b, c, d, x[ 8], S11, 16_698098d8); (* 9 *) FF(d, a, b, c, x[ 9], S12, 16_8b44f7af); (* 10 *) FF(c, d, a, b, x[10], S13, 16_ffff5bb1); (* 11 *) FF(b, c, d, a, x[11], S14, 16_895cd7be); (* 12 *) FF(a, b, c, d, x[12], S11, 16_6b901122); (* 13 *) FF(d, a, b, c, x[13], S12, 16_fd987193); (* 14 *) FF(c, d, a, b, x[14], S13, 16_a679438e); (* 15 *) FF(b, c, d, a, x[15], S14, 16_49b40821); (* 16 *)
(* Round 2 *) GG(a, b, c, d, x[ 1], S21, 16_f61e2562); (* 17 *) GG(d, a, b, c, x[ 6], S22, 16_c040b340); (* 18 *) GG(c, d, a, b, x[11], S23, 16_265e5a51); (* 19 *) GG(b, c, d, a, x[ 0], S24, 16_e9b6c7aa); (* 20 *) GG(a, b, c, d, x[ 5], S21, 16_d62f105d); (* 21 *) GG(d, a, b, c, x[10], S22, 16_02441453); (* 22 *) GG(c, d, a, b, x[15], S23, 16_d8a1e681); (* 23 *) GG(b, c, d, a, x[ 4], S24, 16_e7d3fbc8); (* 24 *) GG(a, b, c, d, x[ 9], S21, 16_21e1cde6); (* 25 *) GG(d, a, b, c, x[14], S22, 16_c33707d6); (* 26 *) GG(c, d, a, b, x[ 3], S23, 16_f4d50d87); (* 27 *) GG(b, c, d, a, x[ 8], S24, 16_455a14ed); (* 28 *) GG(a, b, c, d, x[13], S21, 16_a9e3e905); (* 29 *) GG(d, a, b, c, x[ 2], S22, 16_fcefa3f8); (* 30 *) GG(c, d, a, b, x[ 7], S23, 16_676f02d9); (* 31 *) GG(b, c, d, a, x[12], S24, 16_8d2a4c8a); (* 32 *)
(* Round 3 *) HH(a, b, c, d, x[ 5], S31, 16_fffa3942); (* 33 *) HH(d, a, b, c, x[ 8], S32, 16_8771f681); (* 34 *) HH(c, d, a, b, x[11], S33, 16_6d9d6122); (* 35 *) HH(b, c, d, a, x[14], S34, 16_fde5380c); (* 36 *) HH(a, b, c, d, x[ 1], S31, 16_a4beea44); (* 37 *) HH(d, a, b, c, x[ 4], S32, 16_4bdecfa9); (* 38 *) HH(c, d, a, b, x[ 7], S33, 16_f6bb4b60); (* 39 *) HH(b, c, d, a, x[10], S34, 16_bebfbc70); (* 40 *) HH(a, b, c, d, x[13], S31, 16_289b7ec6); (* 41 *) HH(d, a, b, c, x[ 0], S32, 16_eaa127fa); (* 42 *) HH(c, d, a, b, x[ 3], S33, 16_d4ef3085); (* 43 *) HH(b, c, d, a, x[ 6], S34, 16_04881d05); (* 44 *) HH(a, b, c, d, x[ 9], S31, 16_d9d4d039); (* 45 *) HH(d, a, b, c, x[12], S32, 16_e6db99e5); (* 46 *) HH(c, d, a, b, x[15], S33, 16_1fa27cf8); (* 47 *) HH(b, c, d, a, x[ 2], S34, 16_c4ac5665); (* 48 *)
(* Round 4 *) II(a, b, c, d, x[ 0], S41, 16_f4292244); (* 49 *) II(d, a, b, c, x[ 7], S42, 16_432aff97); (* 50 *) II(c, d, a, b, x[14], S43, 16_ab9423a7); (* 51 *) II(b, c, d, a, x[ 5], S44, 16_fc93a039); (* 52 *) II(a, b, c, d, x[12], S41, 16_655b59c3); (* 53 *) II(d, a, b, c, x[ 3], S42, 16_8f0ccc92); (* 54 *) II(c, d, a, b, x[10], S43, 16_ffeff47d); (* 55 *) II(b, c, d, a, x[ 1], S44, 16_85845dd1); (* 56 *) II(a, b, c, d, x[ 8], S41, 16_6fa87e4f); (* 57 *) II(d, a, b, c, x[15], S42, 16_fe2ce6e0); (* 58 *) II(c, d, a, b, x[ 6], S43, 16_a3014314); (* 59 *) II(b, c, d, a, x[13], S44, 16_4e0811a1); (* 60 *) II(a, b, c, d, x[ 4], S41, 16_f7537e82); (* 61 *) II(d, a, b, c, x[11], S42, 16_bd3af235); (* 62 *) II(c, d, a, b, x[ 2], S43, 16_2ad7d2bb); (* 63 *) II(b, c, d, a, x[ 9], S44, 16_eb86d391); (* 64 *)
state[0] := Word.Plus(state[0], a); state[1] := Word.Plus(state[1], b); state[2] := Word.Plus(state[2], c); state[3] := Word.Plus(state[3], d); END Transform;
PROCEDURE Update(VAR md5ctx: T; input: TEXT) =
VAR index, i, j, partLen: Word.T; locbuff: Buffer;
BEGIN index := Word.And(Word.Shift(md5ctx.count[0], -3), 16_3F); md5ctx.count[0] := Word.Plus(md5ctx.count[0], Word.Shift(Text.Length(input), 3));
IF md5ctx.count[0] < Text.Length(input) THEN INC(md5ctx.count[1]); END; md5ctx.count[1] := md5ctx.count[1] + Word.Shift(Text.Length(input), -29); partLen := 64 - index; IF Text.Length(input) >= partLen THEN FOR i := index TO 63 DO md5ctx.buffer[i] := Text.GetChar(input, i-index); END; Transform(md5ctx.state, md5ctx.buffer); i := partLen; WHILE (i + 63) < Text.Length(input) DO FOR j := 0 TO 63 DO locbuff[j] := Text.GetChar(input, i+j); END; Transform(md5ctx.state, locbuff); INC(i, 64); END; index := 0; ELSE i := 0; END;
j := 0; WHILE i+j < Text.Length(input) DO md5ctx.buffer[j+index] := Text.GetChar(input, i+j); INC(j); END; END Update;
PROCEDURE Final(VAR md5ctx: T): Digest=
VAR bits: ARRAY [0..7] OF CHAR; index, padLen: INTEGER; digest: Digest;
PROCEDURE Encode(VAR output: ARRAY OF CHAR; VAR input: ARRAY OF Word.T; count: INTEGER) = BEGIN FOR i := 0 TO count DO output[i*4+0] := VAL(Word.Extract(input[i], 0, 8), CHAR); output[i*4+1] := VAL(Word.Extract(input[i], 8, 8), CHAR); output[i*4+2] := VAL(Word.Extract(input[i], 16, 8), CHAR); output[i*4+3] := VAL(Word.Extract(input[i], 24, 8), CHAR) END; END Encode; BEGIN Encode(bits, md5ctx.count, 1); index := Word.And(Word.Shift(md5ctx.count[0], -3), 16_3F); IF index < 56 THEN padLen := 56 - index; ELSE padLen := 120 - index; END; Update(md5ctx, Text.Sub(padding, 0, padLen)); Update(md5ctx, Text.FromChars(bits)); Encode(digest, md5ctx.state, 3); RETURN digest; END Final;
PROCEDURE ToText(hash: Digest): TEXT =
VAR buf: TEXT := ""; BEGIN FOR i := 0 TO 15 DO buf := buf & Fmt.Pad(Fmt.Int(ORD(hash[i]), 16), 2, '0'); END; RETURN buf; END ToText;
BEGIN END MD5.</lang> Example usage: <lang modula3>MODULE Main;
IMPORT MD5, IO;
VAR md5ctx: MD5.T;
BEGIN
MD5.Init(md5ctx); MD5.Update(md5ctx, "The quick brown fox jumped over the lazy dog's back"); IO.Put(MD5.ToText(MD5.Final(md5ctx)) & "\n");
END Main.</lang> Output:
e38ca1d920c4b8b8d3946b2c72f01680
Perl 6
<lang perl6>use Test;
sub prefix:<¬>(\x) { (+^ x) % 2**32 } sub infix:<⊞>(\x, \y) { (x + y) % 2**32 } sub infix:«<<<»(\x, \n) { (x +< n) % 2**32 +| (x +> (32-n)) }
constant FGHI = -> \X, \Y, \Z { (X +& Y) +| (¬X +& Z) },
-> \X, \Y, \Z { (X +& Z) +| (Y +& ¬Z) }, -> \X, \Y, \Z { X +^ Y +^ Z }, -> \X, \Y, \Z { Y +^ (X +| ¬Z) };
constant S = (7, 12, 17, 22) xx 4,
(5, 9, 14, 20) xx 4, (4, 11, 16, 23) xx 4, (6, 10, 15, 21) xx 4;
constant T = (floor(abs(sin($_ + 1)) * 2**32) for ^64);
constant k = ( $_ for ^16),
((5*$_ + 1) % 16 for ^16), ((3*$_ + 5) % 16 for ^16), ((7*$_ ) % 16 for ^16);
sub little-endian($w, $n, *@v) { (@v X+> ($w X* ^$n)) X% (2 ** $w) }
sub md5-pad(Blob $msg) {
my \bits = 8 * $msg.elems; my @padded = $msg.list, 0x80, 0x00 xx (-(bits div 8 + 1 + 8) % 64); @padded.map({ :256[$^d,$^c,$^b,$^a] }), little-endian(32, 2, bits);
}
sub md5-block(@H is rw, @X) {
my ($A, $B, $C, $D) = @H; for ^64 -> \i { my \f = FGHI[i div 16]($B, $C, $D); ($A, $B, $C, $D) = ($D, $B ⊞ (($A ⊞ f ⊞ T[i] ⊞ @X[k[i]]) <<< S[i]), $B, $C); } @H «⊞=» ($A, $B, $C, $D);
}
sub md5(Blob $msg --> Blob) {
my @M = md5-pad($msg); my @H = 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476; md5-block(@H, @M[$_ .. $_+15]) for 0, 16 ...^ +@M; Blob.new: little-endian(8, 4, @H);
}
for 'd41d8cd98f00b204e9800998ecf8427e', ,
'0cc175b9c0f1b6a831c399e269772661', 'a', '900150983cd24fb0d6963f7d28e17f72', 'abc', 'f96b697d7cb7938d525a2f31aaf161d0', 'message digest', 'c3fcd3d76192e4007dfb496cca67e13b', 'abcdefghijklmnopqrstuvwxyz', 'd174ab98d277d9f5a5611c2c9f419d9f', 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789', '57edf4a22be3c955ac49da2e2107b67a', '12345678901234567890123456789012345678901234567890123456789012345678901234567890'
-> $expected, $msg {
my $digest = md5($msg.encode('ascii')).list».fmt('%02x').join; is($digest, $expected, "$digest is MD5 digest of '$msg'");
}</lang>
- Output:
ok 1 - d41d8cd98f00b204e9800998ecf8427e is MD5 digest of '' ok 2 - 0cc175b9c0f1b6a831c399e269772661 is MD5 digest of 'a' ok 3 - 900150983cd24fb0d6963f7d28e17f72 is MD5 digest of 'abc' ok 4 - f96b697d7cb7938d525a2f31aaf161d0 is MD5 digest of 'message digest' ok 5 - c3fcd3d76192e4007dfb496cca67e13b is MD5 digest of 'abcdefghijklmnopqrstuvwxyz' ok 6 - d174ab98d277d9f5a5611c2c9f419d9f is MD5 digest of 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789' ok 7 - 57edf4a22be3c955ac49da2e2107b67a is MD5 digest of '12345678901234567890123456789012345678901234567890123456789012345678901234567890'
PicoLisp
This is an implementation of the pseudo-code in the Wikipedia article. Special care had to be taken with modulo 32-bit arithmetics, as PicoLisp supports only numbers of unspecified size. <lang PicoLisp>(scl 12) (load "@lib/math.l") # For 'sin'
(de *Md5-R
7 12 17 22 7 12 17 22 7 12 17 22 7 12 17 22 5 9 14 20 5 9 14 20 5 9 14 20 5 9 14 20 4 11 16 23 4 11 16 23 4 11 16 23 4 11 16 23 6 10 15 21 6 10 15 21 6 10 15 21 6 10 15 21 )
(de *Md5-K
~(make (for I 64 (link (/ (* (abs (sin (* I 1.0))) `(** 2 32)) 1.0) ) ) ) )
(de mod32 (N)
(& N `(hex "FFFFFFFF")) )
(de not32 (N)
(x| N `(hex "FFFFFFFF")) )
(de add32 @
(mod32 (pass +)) )
(de leftRotate (X C)
(| (mod32 (>> (- C) X)) (>> (- 32 C) X)) )
(de md5 (Str)
(let Len (length Str) (setq Str (conc (need (- 8 (* 64 (/ (+ Len 1 8 63) 64))) # Pad to 64-8 bytes (conc (mapcar char (chop Str)) # Works only with ASCII characters (cons `(hex "80")) ) # '1' bit 0 ) # Pad with '0' (make (setq Len (* 8 Len)) (do 8 (link (& Len 255)) (setq Len (>> 8 Len )) ) ) ) ) ) (let (H0 `(hex "67452301") H1 `(hex "EFCDAB89") H2 `(hex "98BADCFE") H3 `(hex "10325476") ) (while Str (let (A H0 B H1 C H2 D H3 W (make (do 16 (link (apply | (mapcar >> (0 -8 -16 -24) (cut 4 'Str)) ) ) ) ) ) (use (Tmp F G) (for I 64 (cond ((>= 16 I) (setq F (| (& B C) (& (not32 B) D)) G I ) ) ((>= 32 I) (setq F (| (& D B) (& (not32 D) C)) G (inc (& (inc (* 5 (dec I))) 15)) ) ) ((>= 48 I) (setq F (x| B C D) G (inc (& (+ 5 (* 3 (dec I))) 15)) ) ) (T (setq F (x| C (| B (not32 D))) G (inc (& (* 7 (dec I)) 15)) ) ) ) (setq Tmp D D C C B B (add32 B (leftRotate (add32 A F (get *Md5-K I) (get W G)) (get *Md5-R I) ) ) A Tmp ) ) ) (setq H0 (add32 H0 A) H1 (add32 H1 B) H2 (add32 H2 C) H3 (add32 H3 D) ) ) ) (pack (make (for N (list H0 H1 H2 H3) (do 4 # Convert to little endian hex string (link (pad 2 (hex (& N 255)))) (setq N (>> 8 N)) ) ) ) ) ) )</lang>
Output:
: (md5 "") -> "D41D8CD98F00B204E9800998ECF8427E" : (md5 "a") -> "0CC175B9C0F1B6A831C399E269772661" : (md5 "abc") -> "900150983CD24FB0D6963F7D28E17F72" : (md5 "message digest") -> "F96B697D7CB7938D525A2F31AAF161D0" : (md5 "abcdefghijklmnopqrstuvwxyz") -> "C3FCD3D76192E4007DFB496CCA67E13B" : (md5 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") -> "D174AB98D277D9F5A5611C2C9F419D9F" : (md5 "12345678901234567890123456789012345678901234567890123456789012345678901234567890") -> "57EDF4A22BE3C955AC49DA2E2107B67A"
Python
Note that the following code focuses on brevity and elegance instead of performance, since Python isn't very good at number crunching anyway. If performance is important, the best solution is to use the built-in md5 module, written in C.
<lang python>import math
rotate_amounts = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21]
constants = [int(abs(math.sin(i+1)) * 2**32) & 0xFFFFFFFF for i in range(64)]
init_values = [0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476]
functions = 16*[lambda b, c, d: (b & c) | (~b & d)] + \
16*[lambda b, c, d: (d & b) | (~d & c)] + \ 16*[lambda b, c, d: b ^ c ^ d] + \ 16*[lambda b, c, d: c ^ (b | ~d)]
index_functions = 16*[lambda i: i] + \
16*[lambda i: (5*i + 1)%16] + \ 16*[lambda i: (3*i + 5)%16] + \ 16*[lambda i: (7*i)%16]
def left_rotate(x, amount):
x &= 0xFFFFFFFF return ((x<<amount) | (x>>(32-amount))) & 0xFFFFFFFF
def md5(message):
message = bytearray(message) #copy our input into a mutable buffer orig_len_in_bits = (8 * len(message)) & 0xffffffffffffffff message.append(0x80) while len(message)%64 != 56: message.append(0) message += orig_len_in_bits.to_bytes(8, byteorder='little')
hash_pieces = init_values[:]
for chunk_ofst in range(0, len(message), 64): a, b, c, d = hash_pieces chunk = message[chunk_ofst:chunk_ofst+64] for i in range(64): f = functions[i](b, c, d) g = index_functions[i](i) to_rotate = a + f + constants[i] + int.from_bytes(chunk[4*g:4*g+4], byteorder='little') new_b = (b + left_rotate(to_rotate, rotate_amounts[i])) & 0xFFFFFFFF a, b, c, d = d, new_b, b, c for i, val in enumerate([a, b, c, d]): hash_pieces[i] += val hash_pieces[i] &= 0xFFFFFFFF return sum(x<<(32*i) for i, x in enumerate(hash_pieces))
def md5_to_hex(digest):
raw = digest.to_bytes(16, byteorder='little') return '{:032x}'.format(int.from_bytes(raw, byteorder='big'))
if __name__=='__main__':
demo = [b"", b"a", b"abc", b"message digest", b"abcdefghijklmnopqrstuvwxyz", b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", b"12345678901234567890123456789012345678901234567890123456789012345678901234567890"] for message in demo: print(md5_to_hex(md5(message)),' <= "',message.decode('ascii'),'"', sep=)
</lang>
Implementation notes:
- The code works with whole bytes, arbitrary message length is not supported.
- Instead of doing an if-else chain in the inner loop, we build a list of functions to use for each iteration. An if-else chain would probably be faster, but this shows off the language features better.
- Python integers don't ever overflow (they are implemented internally as bignums), so the code actually has to emulate 32-bit overflow by masking manually where it matters. On the other hand, this allows us to return the digest as a regular 128-bit number instead of a bytes object.
- The code makes heavy use of int.from_bytes() and int.to_bytes() to convert between bytes and integers. These methods were introduced in Python 3.2. In earlier versions, you needed to use more cumbersome ways to convert between the two types.
- The multiple assignment feature allows us to easily decompose the four items in hash_pieces into individual variables, and to shuffle around the four helper variables at the end of every iteration without introducing a temporary variable.
Racket
For an implementation of md5 in Racket see: github.com/plt/racket/blob/master/collects/file/md5.rkt <lang racket>
- lang racket
(require file/md5) (md5 #"Rosetta Code") </lang> Output: <lang racket>
- "cca1bf66b09554e10f837838c3d3efb1"
</lang>
REXX
<lang rexx>/*REXX program to test the MD5 procedure as per the test suite in the */ /* IETF RFC (1321) ─── The MD5 Message─Digest Algorithm. April 1992. */
/*─────────────────────────────────────Md5 test suite (from above doc). */ msg.1= msg.2='a' msg.3='abc' msg.4='message digest' msg.5='abcdefghijklmnopqrstuvwxyz' msg.6='ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789' msg.7='12345678901234567890123456789012345678901234567890123456789012345678901234567890' msg.0=7
do m=1 for msg.0 say ' in =' msg.m say 'out =' MD5(msg.m) say end /*m*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────MD5 subroutine──────────────────────*/ MD5: procedure; parse arg !; numeric digits 20 /*insure enough digits.*/ parse value '67452301'x 'efcdab89'x '98badcfe'x '10325476'x with a b c d
- =length(!)
L=#*8 // 512
select when L<448 then plus=448-L when L>448 then plus=960-L when L=448 then plus=512 end /*select*/
$=!||'80'x||copies('0'x,plus%8-1)reverse(right(d2c(8*#),4,'0'x))||'00000000'x
do j=0 to length($)%64-1 /*process message (lots of steps)*/ a_=a; b_=b; c_=c; d_=d chunk=j*64 do k=1 for 16 /*process the message in chunks. */ !.k=reverse(substr($,chunk+1+4*(k-1),4)) end /*k*/
a=.part1(a,b,c,d, 0, 7,3614090360) /* 1*/ d=.part1(d,a,b,c, 1,12,3905402710) /* 2*/ c=.part1(c,d,a,b, 2,17, 606105819) /* 3*/ b=.part1(b,c,d,a, 3,22,3250441966) /* 4*/ a=.part1(a,b,c,d, 4, 7,4118548399) /* 5*/ d=.part1(d,a,b,c, 5,12,1200080426) /* 6*/ c=.part1(c,d,a,b, 6,17,2821735955) /* 7*/ b=.part1(b,c,d,a, 7,22,4249261313) /* 8*/ a=.part1(a,b,c,d, 8, 7,1770035416) /* 9*/ d=.part1(d,a,b,c, 9,12,2336552879) /*10*/ c=.part1(c,d,a,b,10,17,4294925233) /*11*/ b=.part1(b,c,d,a,11,22,2304563134) /*12*/ a=.part1(a,b,c,d,12, 7,1804603682) /*13*/ d=.part1(d,a,b,c,13,12,4254626195) /*14*/ c=.part1(c,d,a,b,14,17,2792965006) /*15*/ b=.part1(b,c,d,a,15,22,1236535329) /*16*/ a=.part2(a,b,c,d, 1, 5,4129170786) /*17*/ d=.part2(d,a,b,c, 6, 9,3225465664) /*18*/ c=.part2(c,d,a,b,11,14, 643717713) /*19*/ b=.part2(b,c,d,a, 0,20,3921069994) /*20*/ a=.part2(a,b,c,d, 5, 5,3593408605) /*21*/ d=.part2(d,a,b,c,10, 9, 38016083) /*22*/ c=.part2(c,d,a,b,15,14,3634488961) /*23*/ b=.part2(b,c,d,a, 4,20,3889429448) /*24*/ a=.part2(a,b,c,d, 9, 5, 568446438) /*25*/ d=.part2(d,a,b,c,14, 9,3275163606) /*26*/ c=.part2(c,d,a,b, 3,14,4107603335) /*27*/ b=.part2(b,c,d,a, 8,20,1163531501) /*28*/ a=.part2(a,b,c,d,13, 5,2850285829) /*29*/ d=.part2(d,a,b,c, 2, 9,4243563512) /*30*/ c=.part2(c,d,a,b, 7,14,1735328473) /*31*/ b=.part2(b,c,d,a,12,20,2368359562) /*32*/ a=.part3(a,b,c,d, 5, 4,4294588738) /*33*/ d=.part3(d,a,b,c, 8,11,2272392833) /*34*/ c=.part3(c,d,a,b,11,16,1839030562) /*35*/ b=.part3(b,c,d,a,14,23,4259657740) /*36*/ a=.part3(a,b,c,d, 1, 4,2763975236) /*37*/ d=.part3(d,a,b,c, 4,11,1272893353) /*38*/ c=.part3(c,d,a,b, 7,16,4139469664) /*39*/ b=.part3(b,c,d,a,10,23,3200236656) /*40*/ a=.part3(a,b,c,d,13, 4, 681279174) /*41*/ d=.part3(d,a,b,c, 0,11,3936430074) /*42*/ c=.part3(c,d,a,b, 3,16,3572445317) /*43*/ b=.part3(b,c,d,a, 6,23, 76029189) /*44*/ a=.part3(a,b,c,d, 9, 4,3654602809) /*45*/ d=.part3(d,a,b,c,12,11,3873151461) /*46*/ c=.part3(c,d,a,b,15,16, 530742520) /*47*/ b=.part3(b,c,d,a, 2,23,3299628645) /*48*/ a=.part4(a,b,c,d, 0, 6,4096336452) /*49*/ d=.part4(d,a,b,c, 7,10,1126891415) /*50*/ c=.part4(c,d,a,b,14,15,2878612391) /*51*/ b=.part4(b,c,d,a, 5,21,4237533241) /*52*/ a=.part4(a,b,c,d,12, 6,1700485571) /*53*/ d=.part4(d,a,b,c, 3,10,2399980690) /*54*/ c=.part4(c,d,a,b,10,15,4293915773) /*55*/ b=.part4(b,c,d,a, 1,21,2240044497) /*56*/ a=.part4(a,b,c,d, 8, 6,1873313359) /*57*/ d=.part4(d,a,b,c,15,10,4264355552) /*58*/ c=.part4(c,d,a,b, 6,15,2734768916) /*59*/ b=.part4(b,c,d,a,13,21,1309151649) /*60*/ a=.part4(a,b,c,d, 4, 6,4149444226) /*61*/ d=.part4(d,a,b,c,11,10,3174756917) /*62*/ c=.part4(c,d,a,b, 2,15, 718787259) /*63*/ b=.part4(b,c,d,a, 9,21,3951481745) /*64*/ a=.a(a_,a); b=.a(b_,b); c=.a(c_,c); d=.a(d_,d) end /*j*/
return c2x(reverse(a))c2x(reverse(b))c2x(reverse(c))c2x(reverse(d)) /*─────────────────────────────────────subroutines──────────────────────*/ .part1: procedure expose !.; parse arg w,x,y,z,n,m,_; n=n+1
return .a(.lR(right(d2c(_+c2d(w)+c2d(.f(x,y,z))+c2d(!.n)),4,'0'x),m),x)
.part2: procedure expose !.; parse arg w,x,y,z,n,m,_; n=n+1
return .a(.lR(right(d2c(_+c2d(w)+c2d(.g(x,y,z))+c2d(!.n)),4,'0'x),m),x)
.part3: procedure expose !.; parse arg w,x,y,z,n,m,_; n=n+1
return .a(.lR(right(d2c(_+c2d(w)+c2d(.h(x,y,z))+c2d(!.n)),4,'0'x),m),x)
.part4: procedure expose !.; parse arg w,x,y,z,n,m; n=n+1
return .a(.lR(right(d2c(c2d(w)+c2d(.i(x,y,z))+c2d(!.n)+arg(7)),4,'0'x),m),x)
.h: procedure; parse arg x,y,z; return bitxor(bitxor(x,y),z) .i: return bitxor(arg(2),bitor(arg(1),bitxor(arg(3),'ffffffff'x))) .a: return right(d2c(c2d(arg(1))+c2d(arg(2))),4,'0'x) .f: procedure; parse arg x,y,z
return bitor(bitand(x,y),bitand(bitxor(x,'ffffffff'x),z))
.g: procedure; parse arg x,y,z
return bitor(bitand(x,z),bitand(y,bitxor(z,'ffffffff'x)))
.lR: procedure; parse arg _,#; if #==0 then return _ /*left rotate.*/
?=x2b(c2x(_)); return x2c(b2x(right(?||left(?,#),length(?))))</lang>
output
in = out = D41D8CD98F00B204E9800998ECF8427E in = a out = 0CC175B9C0F1B6A831C399E269772661 in = abc out = 900150983CD24FB0D6963F7D28E17F72 in = message digest out = F96B697D7CB7938D525A2F31AAF161D0 in = abcdefghijklmnopqrstuvwxyz out = C3FCD3D76192E4007DFB496CCA67E13B in = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789 out = D174AB98D277D9F5A5611C2C9F419D9F in = 12345678901234567890123456789012345678901234567890123456789012345678901234567890 out = 57EDF4A22BE3C955AC49DA2E2107B67A
Seed7
The example below contains the implementation of the function md5 from the library msgdigest.s7i.
<lang seed7>$ include "seed7_05.s7i";
include "bytedata.s7i"; include "bin32.s7i"; include "float.s7i"; include "math.s7i";
- Use binary integer part of the sines of integers (Radians) as constants:
const func array integer: createMd5Table is func
result var array integer: k is 64 times 0; local var integer: index is 0; begin for index range 1 to 64 do k[index] := trunc(abs(sin(flt(index))) * 2.0 ** 32); end for; end func;
const func string: md5 (in var string: message) is func
result var string: digest is ""; local # Specify the per-round shift amounts const array integer: shiftAmount is [] ( 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21); const array integer: k is createMd5Table; var integer: length is 0; var integer: chunkIndex is 0; var integer: index is 0; var array bin32: m is 16 times bin32.value; var integer: a0 is 16#67452301; # a var integer: b0 is 16#efcdab89; # b var integer: c0 is 16#98badcfe; # c var integer: d0 is 16#10325476; # d var bin32: a is bin32(0); var bin32: b is bin32(0); var bin32: c is bin32(0); var bin32: d is bin32(0); var bin32: f is bin32(0); var integer: g is 0; var bin32: temp is bin32(0); begin length := length(message); # Append the bit '1' to the message. message &:= '\16#80;'; # Append '0' bits, so that the resulting bit length is congruent to 448 (mod 512). message &:= "\0;" mult 63 - (length + 8) mod 64; # Append length of message (before pre-processing), in bits, as 64-bit little-endian integer. message &:= int64AsEightBytesLe(8 * length);
# Process the message in successive 512-bit chunks: for chunkIndex range 1 to length(message) step 64 do # Break chunk into sixteen 32-bit little-endian words. for index range 1 to 16 do m[index] := bin32(bytes2Int(message[chunkIndex + 4 * pred(index) len 4], UNSIGNED, LE)); end for;
a := bin32(a0 mod 16#100000000); b := bin32(b0 mod 16#100000000); c := bin32(c0 mod 16#100000000); d := bin32(d0 mod 16#100000000);
for index range 1 to 64 do if index <= 16 then f := d >< (b & (c >< d)); g := index; elsif index <= 32 then f := c >< (d & (b >< c)); g := (5 * index - 4) mod 16 + 1; elsif index <= 48 then f := b >< c >< d; g := (3 * index + 2) mod 16 + 1; else f := c >< (b | (bin32(16#ffffffff) >< d)); g := (7 * pred(index)) mod 16 + 1; end if;
temp := d; d := c; c := b; b := bin32((ord(b) + ord(rotLeft(bin32((ord(a) + ord(f) + k[index] + ord(m[g])) mod 16#100000000), shiftAmount[index]))) mod 16#100000000); a := temp; end for;
# Add this chunk's hash to result so far: a0 +:= ord(a); b0 +:= ord(b); c0 +:= ord(c); d0 +:= ord(d); end for;
# Produce the final hash value: digest := int32AsFourBytesLe(a0) & int32AsFourBytesLe(b0) & int32AsFourBytesLe(c0) & int32AsFourBytesLe(d0); end func;
const func boolean: checkMd5 (in string: message, in string: hexMd5) is
return hex(md5(message)) = hexMd5;
const proc: main is func
begin if checkMd5("", "d41d8cd98f00b204e9800998ecf8427e") and checkMd5("a", "0cc175b9c0f1b6a831c399e269772661") and checkMd5("abc", "900150983cd24fb0d6963f7d28e17f72") and checkMd5("message digest", "f96b697d7cb7938d525a2f31aaf161d0") and checkMd5("abcdefghijklmnopqrstuvwxyz", "c3fcd3d76192e4007dfb496cca67e13b") and checkMd5("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", "d174ab98d277d9f5a5611c2c9f419d9f") and checkMd5("12345678901234567890123456789012345678901234567890123456789012345678901234567890", "57edf4a22be3c955ac49da2e2107b67a") then writeln("md5 is computed correct"); else writeln("There is an error in the md5 function"); end if; end func;</lang>
Original source: [2]
- Output:
md5 is computed correct
Swift
Swift implementation of the pseudo-code found in the Wikipedia article.
Original source: CryptoSwift
<lang swift>
import Foundation public class MD5 { /** specifies the per-round shift amounts */ private let s: [UInt32] = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21] /** binary integer part of the sines of integers (Radians) */ private let K: [UInt32] = (0 ..< 64).map { UInt32(0x100000000 * abs(sin(Double($0 + 1)))) } let a0: UInt32 = 0x67452301 let b0: UInt32 = 0xefcdab89 let c0: UInt32 = 0x98badcfe let d0: UInt32 = 0x10325476 private var message: NSData //MARK: Public public init(_ message: NSData) { self.message = message } public func calculate() -> NSData? { var tmpMessage: NSMutableData = NSMutableData(data: message) let wordSize = sizeof(UInt32) var aa = a0 var bb = b0 var cc = c0 var dd = d0 // Step 1. Append Padding Bits tmpMessage.appendBytes([0x80]) // append one bit (Byte with one bit) to message // append "0" bit until message length in bits ≡ 448 (mod 512) while tmpMessage.length % 64 != 56 { tmpMessage.appendBytes([0x00]) } // Step 2. Append Length a 64-bit representation of lengthInBits var lengthInBits = (message.length * 8) var lengthBytes = lengthInBits.bytes(64 / 8) tmpMessage.appendBytes(reverse(lengthBytes)); // Process the message in successive 512-bit chunks: let chunkSizeBytes = 512 / 8 var leftMessageBytes = tmpMessage.length for var i = 0; i < tmpMessage.length; i = i + chunkSizeBytes, leftMessageBytes -= chunkSizeBytes { let chunk = tmpMessage.subdataWithRange(NSRange(location: i, length: min(chunkSizeBytes,leftMessageBytes))) // break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15 // println("wordSize \(wordSize)"); var M:[UInt32] = [UInt32](count: 16, repeatedValue: 0) for x in 0..<M.count { var range = NSRange(location:x * wordSize, length: wordSize) chunk.getBytes(&M[x], range:range); } // Initialize hash value for this chunk: var A:UInt32 = a0 var B:UInt32 = b0 var C:UInt32 = c0 var D:UInt32 = d0 var dTemp:UInt32 = 0 // Main loop for j in 0...63 { var g = 0 var F:UInt32 = 0 switch (j) { case 0...15: F = (B & C) | ((~B) & D) g = j break case 16...31: F = (D & B) | (~D & C) g = (5 * j + 1) % 16 break case 32...47: F = B ^ C ^ D g = (3 * j + 5) % 16 break case 48...63: F = C ^ (B | (~D)) g = (7 * j) % 16 break default: break } dTemp = D D = C C = B B = B &+ rotateLeft((A &+ F &+ K[j] &+ M[g]), s[j]) A = dTemp } aa = aa &+ A bb = bb &+ B cc = cc &+ C dd = dd &+ D }
var buf: NSMutableData = NSMutableData(); buf.appendBytes(&aa, length: wordSize) buf.appendBytes(&bb, length: wordSize) buf.appendBytes(&cc, length: wordSize) buf.appendBytes(&dd, length: wordSize) return buf.copy() as? NSData; }
//MARK: Class class func calculate(message: NSData) -> NSData? { return MD5(message).calculate(); } //MARK: Private private func rotateLeft(x:UInt32, _ n:UInt32) -> UInt32 { return (x &<< n) | (x &>> (32 - n)) } }
</lang>
From-scratch implementation based on the solutions on this page without needing any external libraries: <lang swift>import Foundation
let shift : [UInt32] = [7, 12, 17, 22, 5, 9, 14, 20, 4, 11, 16, 23, 6, 10, 15, 21] let table: [UInt32] = (0 ..< 64).map { UInt32(0x100000000 * abs(sin(Double($0 + 1)))) }
func md5(var message: [UInt8]) -> [UInt8] {
var messageLenBits = UInt64(message.count) * 8 message.append(0x80) while message.count % 64 != 56 { message.append(0) } var lengthBytes = [UInt8](count: 8, repeatedValue: 0) UnsafeMutablePointer<UInt64>(lengthBytes).memory = messageLenBits.littleEndian message += lengthBytes var a : UInt32 = 0x67452301 var b : UInt32 = 0xEFCDAB89 var c : UInt32 = 0x98BADCFE var d : UInt32 = 0x10325476 for chunkOffset in stride(from: 0, to: message.count, by: 64) { let chunk = UnsafePointer<UInt32>(UnsafePointer<UInt8>(message) + chunkOffset) let originalA = a let originalB = b let originalC = c let originalD = d for j in 0 ..< 64 { var f : UInt32 = 0 var bufferIndex = j let round = j >> 4 switch round { case 0: f = (b & c) | (~b & d) case 1: f = (b & d) | (c & ~d) bufferIndex = (bufferIndex*5 + 1) & 0x0F case 2: f = b ^ c ^ d bufferIndex = (bufferIndex*3 + 5) & 0x0F case 3: f = c ^ (b | ~d) bufferIndex = (bufferIndex * 7) & 0x0F default: assert(false) } let sa = shift[(round<<2)|(j&3)] let tmp = a &+ f &+ UInt32(littleEndian: chunk[bufferIndex]) &+ table[j] a = d d = c c = b b = b &+ (tmp << sa | tmp >> (32-sa)) } a = a &+ originalA b = b &+ originalB c = c &+ originalC d = d &+ originalD } var result = [UInt8](count: 16, repeatedValue: 0) for (i, n) in enumerate([a, b, c, d]) { UnsafeMutablePointer<UInt32>(result)[i] = n.littleEndian } return result
}
func toHexString(bytes: [UInt8]) -> String {
return "".join(bytes.map { String(format:"%02x", $0) })
}
for (hashCode, string) in [
("d41d8cd98f00b204e9800998ecf8427e", ""), ("0cc175b9c0f1b6a831c399e269772661", "a"), ("900150983cd24fb0d6963f7d28e17f72", "abc"), ("f96b697d7cb7938d525a2f31aaf161d0", "message digest"), ("c3fcd3d76192e4007dfb496cca67e13b", "abcdefghijklmnopqrstuvwxyz"), ("d174ab98d277d9f5a5611c2c9f419d9f", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"), ("57edf4a22be3c955ac49da2e2107b67a", "12345678901234567890" + "123456789012345678901234567890123456789012345678901234567890")] { println(hashCode) println(toHexString(md5(Array(string.utf8)))) println()
}</lang swift>
- Output:
d41d8cd98f00b204e9800998ecf8427e d41d8cd98f00b204e9800998ecf8427e 0cc175b9c0f1b6a831c399e269772661 0cc175b9c0f1b6a831c399e269772661 900150983cd24fb0d6963f7d28e17f72 900150983cd24fb0d6963f7d28e17f72 f96b697d7cb7938d525a2f31aaf161d0 f96b697d7cb7938d525a2f31aaf161d0 c3fcd3d76192e4007dfb496cca67e13b c3fcd3d76192e4007dfb496cca67e13b d174ab98d277d9f5a5611c2c9f419d9f d174ab98d277d9f5a5611c2c9f419d9f 57edf4a22be3c955ac49da2e2107b67a 57edf4a22be3c955ac49da2e2107b67a
Tcl
This code is extracted from the md5
package in
, and is originally due to Don Libes's transcription of the code in the MD5 specification. It should not be deployed in production normally; the md5
package should be used in preference as it is usually built to be faster.
<lang tcl># We just define the body of md5::md5 here; later we regsub to inline a few
- function calls for speed
variable ::md5::md5body {
### Step 1. Append Padding Bits
set msgLen [string length $msg]
set padLen [expr {56 - $msgLen%64}] if {$msgLen % 64 > 56} {
incr padLen 64
}
# pad even if no padding required if {$padLen == 0} {
incr padLen 64
}
# append single 1b followed by 0b's append msg [binary format "a$padLen" \200]
### Step 2. Append Length
# RFC doesn't say whether to use little- or big-endian; code demonstrates # little-endian. # This step limits our input to size 2^32b or 2^24B append msg [binary format "i1i1" [expr {8*$msgLen}] 0]
### Step 3. Initialize MD Buffer
set A [expr 0x67452301] set B [expr 0xefcdab89] set C [expr 0x98badcfe] set D [expr 0x10325476]
### Step 4. Process Message in 16-Word Blocks
# process each 16-word block # RFC doesn't say whether to use little- or big-endian; code says # little-endian. binary scan $msg i* blocks
# loop over the message taking 16 blocks at a time
foreach {X0 X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X13 X14 X15} $blocks {
# Save A as AA, B as BB, C as CC, and D as DD. set AA $A set BB $B set CC $C set DD $D
# Round 1. # Let [abcd k s i] denote the operation # a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). # [ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4] set A [expr {$B + [<<< [expr {$A + [F $B $C $D] + $X0 + $T01}] 7]}] set D [expr {$A + [<<< [expr {$D + [F $A $B $C] + $X1 + $T02}] 12]}] set C [expr {$D + [<<< [expr {$C + [F $D $A $B] + $X2 + $T03}] 17]}] set B [expr {$C + [<<< [expr {$B + [F $C $D $A] + $X3 + $T04}] 22]}] # [ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8] set A [expr {$B + [<<< [expr {$A + [F $B $C $D] + $X4 + $T05}] 7]}] set D [expr {$A + [<<< [expr {$D + [F $A $B $C] + $X5 + $T06}] 12]}] set C [expr {$D + [<<< [expr {$C + [F $D $A $B] + $X6 + $T07}] 17]}] set B [expr {$C + [<<< [expr {$B + [F $C $D $A] + $X7 + $T08}] 22]}] # [ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12] set A [expr {$B + [<<< [expr {$A + [F $B $C $D] + $X8 + $T09}] 7]}] set D [expr {$A + [<<< [expr {$D + [F $A $B $C] + $X9 + $T10}] 12]}] set C [expr {$D + [<<< [expr {$C + [F $D $A $B] + $X10 + $T11}] 17]}] set B [expr {$C + [<<< [expr {$B + [F $C $D $A] + $X11 + $T12}] 22]}] # [ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16] set A [expr {$B + [<<< [expr {$A + [F $B $C $D] + $X12 + $T13}] 7]}] set D [expr {$A + [<<< [expr {$D + [F $A $B $C] + $X13 + $T14}] 12]}] set C [expr {$D + [<<< [expr {$C + [F $D $A $B] + $X14 + $T15}] 17]}] set B [expr {$C + [<<< [expr {$B + [F $C $D $A] + $X15 + $T16}] 22]}]
# Round 2. # Let [abcd k s i] denote the operation # a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). # Do the following 16 operations. # [ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20] set A [expr {$B + [<<< [expr {$A + [G $B $C $D] + $X1 + $T17}] 5]}] set D [expr {$A + [<<< [expr {$D + [G $A $B $C] + $X6 + $T18}] 9]}] set C [expr {$D + [<<< [expr {$C + [G $D $A $B] + $X11 + $T19}] 14]}] set B [expr {$C + [<<< [expr {$B + [G $C $D $A] + $X0 + $T20}] 20]}] # [ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24] set A [expr {$B + [<<< [expr {$A + [G $B $C $D] + $X5 + $T21}] 5]}] set D [expr {$A + [<<< [expr {$D + [G $A $B $C] + $X10 + $T22}] 9]}] set C [expr {$D + [<<< [expr {$C + [G $D $A $B] + $X15 + $T23}] 14]}] set B [expr {$C + [<<< [expr {$B + [G $C $D $A] + $X4 + $T24}] 20]}] # [ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28] set A [expr {$B + [<<< [expr {$A + [G $B $C $D] + $X9 + $T25}] 5]}] set D [expr {$A + [<<< [expr {$D + [G $A $B $C] + $X14 + $T26}] 9]}] set C [expr {$D + [<<< [expr {$C + [G $D $A $B] + $X3 + $T27}] 14]}] set B [expr {$C + [<<< [expr {$B + [G $C $D $A] + $X8 + $T28}] 20]}] # [ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32] set A [expr {$B + [<<< [expr {$A + [G $B $C $D] + $X13 + $T29}] 5]}] set D [expr {$A + [<<< [expr {$D + [G $A $B $C] + $X2 + $T30}] 9]}] set C [expr {$D + [<<< [expr {$C + [G $D $A $B] + $X7 + $T31}] 14]}] set B [expr {$C + [<<< [expr {$B + [G $C $D $A] + $X12 + $T32}] 20]}]
# Round 3. # Let [abcd k s t] [sic] denote the operation # a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). # Do the following 16 operations. # [ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36] set A [expr {$B + [<<< [expr {$A + [H $B $C $D] + $X5 + $T33}] 4]}] set D [expr {$A + [<<< [expr {$D + [H $A $B $C] + $X8 + $T34}] 11]}] set C [expr {$D + [<<< [expr {$C + [H $D $A $B] + $X11 + $T35}] 16]}] set B [expr {$C + [<<< [expr {$B + [H $C $D $A] + $X14 + $T36}] 23]}] # [ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40] set A [expr {$B + [<<< [expr {$A + [H $B $C $D] + $X1 + $T37}] 4]}] set D [expr {$A + [<<< [expr {$D + [H $A $B $C] + $X4 + $T38}] 11]}] set C [expr {$D + [<<< [expr {$C + [H $D $A $B] + $X7 + $T39}] 16]}] set B [expr {$C + [<<< [expr {$B + [H $C $D $A] + $X10 + $T40}] 23]}] # [ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44] set A [expr {$B + [<<< [expr {$A + [H $B $C $D] + $X13 + $T41}] 4]}] set D [expr {$A + [<<< [expr {$D + [H $A $B $C] + $X0 + $T42}] 11]}] set C [expr {$D + [<<< [expr {$C + [H $D $A $B] + $X3 + $T43}] 16]}] set B [expr {$C + [<<< [expr {$B + [H $C $D $A] + $X6 + $T44}] 23]}] # [ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48] set A [expr {$B + [<<< [expr {$A + [H $B $C $D] + $X9 + $T45}] 4]}] set D [expr {$A + [<<< [expr {$D + [H $A $B $C] + $X12 + $T46}] 11]}] set C [expr {$D + [<<< [expr {$C + [H $D $A $B] + $X15 + $T47}] 16]}] set B [expr {$C + [<<< [expr {$B + [H $C $D $A] + $X2 + $T48}] 23]}]
# Round 4. # Let [abcd k s t] [sic] denote the operation # a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). # Do the following 16 operations. # [ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52] set A [expr {$B + [<<< [expr {$A + [I $B $C $D] + $X0 + $T49}] 6]}] set D [expr {$A + [<<< [expr {$D + [I $A $B $C] + $X7 + $T50}] 10]}] set C [expr {$D + [<<< [expr {$C + [I $D $A $B] + $X14 + $T51}] 15]}] set B [expr {$C + [<<< [expr {$B + [I $C $D $A] + $X5 + $T52}] 21]}] # [ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56] set A [expr {$B + [<<< [expr {$A + [I $B $C $D] + $X12 + $T53}] 6]}] set D [expr {$A + [<<< [expr {$D + [I $A $B $C] + $X3 + $T54}] 10]}] set C [expr {$D + [<<< [expr {$C + [I $D $A $B] + $X10 + $T55}] 15]}] set B [expr {$C + [<<< [expr {$B + [I $C $D $A] + $X1 + $T56}] 21]}] # [ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60] set A [expr {$B + [<<< [expr {$A + [I $B $C $D] + $X8 + $T57}] 6]}] set D [expr {$A + [<<< [expr {$D + [I $A $B $C] + $X15 + $T58}] 10]}] set C [expr {$D + [<<< [expr {$C + [I $D $A $B] + $X6 + $T59}] 15]}] set B [expr {$C + [<<< [expr {$B + [I $C $D $A] + $X13 + $T60}] 21]}] # [ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64] set A [expr {$B + [<<< [expr {$A + [I $B $C $D] + $X4 + $T61}] 6]}] set D [expr {$A + [<<< [expr {$D + [I $A $B $C] + $X11 + $T62}] 10]}] set C [expr {$D + [<<< [expr {$C + [I $D $A $B] + $X2 + $T63}] 15]}] set B [expr {$C + [<<< [expr {$B + [I $C $D $A] + $X9 + $T64}] 21]}]
# Then perform the following additions. (That is increment each of the # four registers by the value it had before this block was started.) incr A $AA incr B $BB incr C $CC incr D $DD
}
### Step 5. Output
# ... begin with the low-order byte of A, and end with the high-order byte # of D.
return [bytes $A][bytes $B][bytes $C][bytes $D]
}
- Here we inline/regsub the functions F, G, H, I and <<<
namespace eval ::md5 {
#proc md5pure::F {x y z} {expr {(($x & $y) | ((~$x) & $z))}} regsub -all -- {\[ *F +(\$.) +(\$.) +(\$.) *\]} $md5body {((\1 \& \2) | ((~\1) \& \3))} md5body
#proc md5pure::G {x y z} {expr {(($x & $z) | ($y & (~$z)))}} regsub -all -- {\[ *G +(\$.) +(\$.) +(\$.) *\]} $md5body {((\1 \& \3) | (\2 \& (~\3)))} md5body
#proc md5pure::H {x y z} {expr {$x ^ $y ^ $z}} regsub -all -- {\[ *H +(\$.) +(\$.) +(\$.) *\]} $md5body {(\1 ^ \2 ^ \3)} md5body
#proc md5pure::I {x y z} {expr {$y ^ ($x | (~$z))}} regsub -all -- {\[ *I +(\$.) +(\$.) +(\$.) *\]} $md5body {(\2 ^ (\1 | (~\3)))} md5body
# inline <<< (bitwise left-rotate) regsub -all -- {\[ *<<< +\[ *expr +({[^\}]*})\] +([0-9]+) *\]} $md5body {(([set x [expr \1]] << \2) | (($x >> R\2) \& S\2))} md5body
# now replace the R and S variable map {} variable i foreach i {
7 12 17 22 5 9 14 20 4 11 16 23 6 10 15 21
} {
lappend map R$i [expr {32 - $i}] S$i [expr {0x7fffffff >> (31-$i)}]
}
# inline the values of T variable tName variable tVal foreach tName {
T01 T02 T03 T04 T05 T06 T07 T08 T09 T10 T11 T12 T13 T14 T15 T16 T17 T18 T19 T20 T21 T22 T23 T24 T25 T26 T27 T28 T29 T30 T31 T32 T33 T34 T35 T36 T37 T38 T39 T40 T41 T42 T43 T44 T45 T46 T47 T48 T49 T50 T51 T52 T53 T54 T55 T56 T57 T58 T59 T60 T61 T62 T63 T64
} tVal {
0xd76aa478 0xe8c7b756 0x242070db 0xc1bdceee 0xf57c0faf 0x4787c62a 0xa8304613 0xfd469501 0x698098d8 0x8b44f7af 0xffff5bb1 0x895cd7be 0x6b901122 0xfd987193 0xa679438e 0x49b40821
0xf61e2562 0xc040b340 0x265e5a51 0xe9b6c7aa 0xd62f105d 0x2441453 0xd8a1e681 0xe7d3fbc8 0x21e1cde6 0xc33707d6 0xf4d50d87 0x455a14ed 0xa9e3e905 0xfcefa3f8 0x676f02d9 0x8d2a4c8a
0xfffa3942 0x8771f681 0x6d9d6122 0xfde5380c 0xa4beea44 0x4bdecfa9 0xf6bb4b60 0xbebfbc70 0x289b7ec6 0xeaa127fa 0xd4ef3085 0x4881d05 0xd9d4d039 0xe6db99e5 0x1fa27cf8 0xc4ac5665
0xf4292244 0x432aff97 0xab9423a7 0xfc93a039 0x655b59c3 0x8f0ccc92 0xffeff47d 0x85845dd1 0x6fa87e4f 0xfe2ce6e0 0xa3014314 0x4e0811a1 0xf7537e82 0xbd3af235 0x2ad7d2bb 0xeb86d391
} {
lappend map \$$tName $tVal
} set md5body [string map $map $md5body]
# Finally, define the proc proc md5 {msg} $md5body
# unset auxiliary variables unset md5body tName tVal map
proc byte0 {i} {expr {0xff & $i}} proc byte1 {i} {expr {(0xff00 & $i) >> 8}} proc byte2 {i} {expr {(0xff0000 & $i) >> 16}} proc byte3 {i} {expr {((0xff000000 & $i) >> 24) & 0xff}} proc bytes {i} { format %0.2x%0.2x%0.2x%0.2x [byte0 $i] [byte1 $i] [byte2 $i] [byte3 $i] }
}</lang> Demonstration code: <lang tcl>foreach {hash <- string} {
0xd41d8cd98f00b204e9800998ecf8427e ==> "" 0x0cc175b9c0f1b6a831c399e269772661 ==> "a" 0x900150983cd24fb0d6963f7d28e17f72 ==> "abc" 0xf96b697d7cb7938d525a2f31aaf161d0 ==> "message digest" 0xc3fcd3d76192e4007dfb496cca67e13b ==> "abcdefghijklmnopqrstuvwxyz" 0xd174ab98d277d9f5a5611c2c9f419d9f ==> "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789" 0x57edf4a22be3c955ac49da2e2107b67a ==> "12345678901234567890123456789012345678901234567890123456789012345678901234567890"
} {
puts "“$string” -> [md5::md5 $string] (officially: $hash)"
}</lang>
x86 Assembly
Uses DOS interrupts for display.
<lang asm>section .text org 0x100 mov di, md5_for_display mov si, test_input_1 mov cx, test_input_1_len call compute_md5 call display_md5 mov si, test_input_2 mov cx, test_input_2_len call compute_md5 call display_md5 mov si, test_input_3 mov cx, test_input_3_len call compute_md5 call display_md5 mov si, test_input_4 mov cx, test_input_4_len call compute_md5 call display_md5 mov si, test_input_5 mov cx, test_input_5_len call compute_md5 call display_md5 mov si, test_input_6 mov cx, test_input_6_len call compute_md5 call display_md5 mov si, test_input_7 mov cx, test_input_7_len call compute_md5 call display_md5 mov ax, 0x4c00 int 21h
md5_for_display times 16 db 0 HEX_CHARS db '0123456789ABCDEF'
display_md5: mov ah, 9 mov dx, display_str_1 int 0x21 push cx push si mov cx, 16 mov si, di xor bx, bx .loop: lodsb mov bl, al and bl, 0x0F push bx mov bl, al shr bx, 4 mov ah, 2 mov dl, [HEX_CHARS + bx] int 0x21 pop bx mov dl, [HEX_CHARS + bx] int 0x21 dec cx jnz .loop mov ah, 9 mov dx, display_str_2 int 0x21 pop si pop cx test cx, cx jz do_newline mov ah, 2 display_string: lodsb mov dl, al int 0x21 dec cx jnz display_string do_newline: mov ah, 9 mov dx, display_str_3 int 0x21 ret;
compute_md5: ; si --> input bytes, cx = input len, di --> 16-byte output buffer ; assumes all in the same segment cld pusha push di push si mov [message_len], cx
mov bx, cx shr bx, 6 mov [ending_bytes_block_num], bx mov [num_blocks], bx inc word [num_blocks] shl bx, 6 add si, bx and cx, 0x3f push cx mov di, ending_bytes rep movsb mov al, 0x80 stosb pop cx sub cx, 55 neg cx jge add_padding add cx, 64 inc word [num_blocks] add_padding: mov al, 0 rep stosb xor eax, eax mov ax, [message_len] shl eax, 3 mov cx, 8 store_message_len: stosb shr eax, 8 dec cx jnz store_message_len pop si mov [md5_a], dword INIT_A mov [md5_b], dword INIT_B mov [md5_c], dword INIT_C mov [md5_d], dword INIT_D block_loop: push cx cmp cx, [ending_bytes_block_num] jne backup_abcd ; switch buffers if towards the end where padding needed mov si, ending_bytes backup_abcd: push dword [md5_d] push dword [md5_c] push dword [md5_b] push dword [md5_a] xor cx, cx xor eax, eax main_loop: push cx mov ax, cx shr ax, 4 test al, al jz pass0 cmp al, 1 je pass1 cmp al, 2 je pass2 ; pass3 mov eax, [md5_c] mov ebx, [md5_d] not ebx or ebx, [md5_b] xor eax, ebx jmp do_rotate
pass0: mov eax, [md5_b] mov ebx, eax and eax, [md5_c] not ebx and ebx, [md5_d] or eax, ebx jmp do_rotate
pass1: mov eax, [md5_d] mov edx, eax and eax, [md5_b] not edx and edx, [md5_c] or eax, edx jmp do_rotate
pass2: mov eax, [md5_b] xor eax, [md5_c] xor eax, [md5_d] do_rotate: add eax, [md5_a] mov bx, cx shl bx, 1 mov bx, [BUFFER_INDEX_TABLE + bx] add eax, [si + bx] mov bx, cx shl bx, 2 add eax, dword [TABLE_T + bx] mov bx, cx ror bx, 2 shr bl, 2 rol bx, 2 mov cl, [SHIFT_AMTS + bx] rol eax, cl add eax, [md5_b] push eax push dword [md5_b] push dword [md5_c] push dword [md5_d] pop dword [md5_a] pop dword [md5_d] pop dword [md5_c] pop dword [md5_b] pop cx inc cx cmp cx, 64 jb main_loop ; add to original values pop eax add [md5_a], eax pop eax add [md5_b], eax pop eax add [md5_c], eax pop eax add [md5_d], eax ; advance pointers add si, 64 pop cx inc cx cmp cx, [num_blocks] jne block_loop mov cx, 4 mov si, md5_a pop di rep movsd popa ret
section .data
INIT_A equ 0x67452301 INIT_B equ 0xEFCDAB89 INIT_C equ 0x98BADCFE INIT_D equ 0x10325476
SHIFT_AMTS db 7, 12, 17, 22, 5, 9, 14, 20, 4, 11, 16, 23, 6, 10, 15, 21
TABLE_T dd 0xD76AA478, 0xE8C7B756, 0x242070DB, 0xC1BDCEEE, 0xF57C0FAF, 0x4787C62A, 0xA8304613, 0xFD469501, 0x698098D8, 0x8B44F7AF, 0xFFFF5BB1, 0x895CD7BE, 0x6B901122, 0xFD987193, 0xA679438E, 0x49B40821, 0xF61E2562, 0xC040B340, 0x265E5A51, 0xE9B6C7AA, 0xD62F105D, 0x02441453, 0xD8A1E681, 0xE7D3FBC8, 0x21E1CDE6, 0xC33707D6, 0xF4D50D87, 0x455A14ED, 0xA9E3E905, 0xFCEFA3F8, 0x676F02D9, 0x8D2A4C8A, 0xFFFA3942, 0x8771F681, 0x6D9D6122, 0xFDE5380C, 0xA4BEEA44, 0x4BDECFA9, 0xF6BB4B60, 0xBEBFBC70, 0x289B7EC6, 0xEAA127FA, 0xD4EF3085, 0x04881D05, 0xD9D4D039, 0xE6DB99E5, 0x1FA27CF8, 0xC4AC5665, 0xF4292244, 0x432AFF97, 0xAB9423A7, 0xFC93A039, 0x655B59C3, 0x8F0CCC92, 0xFFEFF47D, 0x85845DD1, 0x6FA87E4F, 0xFE2CE6E0, 0xA3014314, 0x4E0811A1, 0xF7537E82, 0xBD3AF235, 0x2AD7D2BB, 0xEB86D391 BUFFER_INDEX_TABLE dw 0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 4, 24, 44, 0, 20, 40, 60, 16, 36, 56, 12, 32, 52, 8, 28, 48, 20, 32, 44, 56, 4, 16, 28, 40, 52, 0, 12, 24, 36, 48, 60, 8, 0, 28, 56, 20, 48, 12, 40, 4, 32, 60, 24, 52, 16, 44, 8, 36 ending_bytes_block_num dw 0 ending_bytes times 128 db 0 message_len dw 0 num_blocks dw 0 md5_a dd 0 md5_b dd 0 md5_c dd 0 md5_d dd 0
display_str_1 db '0x$' display_str_2 db ' <== "$' display_str_3 db '"', 13, 10, '$'
test_input_1: test_input_1_len equ $ - test_input_1 test_input_2 db 'a' test_input_2_len equ $ - test_input_2 test_input_3 db 'abc' test_input_3_len equ $ - test_input_3 test_input_4 db 'message digest' test_input_4_len equ $ - test_input_4 test_input_5 db 'abcdefghijklmnopqrstuvwxyz' test_input_5_len equ $ - test_input_5 test_input_6 db 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789' test_input_6_len equ $ - test_input_6 test_input_7 db '12345678901234567890123456789012345678901234567890123456789012345678901234567890' test_input_7_len equ $ - test_input_7</lang>
Output:
0xD41D8CD98F00B204E9800998ECF8427E <== "" 0x0CC175B9C0F1B6A831C399E269772661 <== "a" 0x900150983CD24FB0D6963F7D28E17F72 <== "abc" 0xF96B697D7CB7938D525A2F31AAF161D0 <== "message digest" 0xC3FCD3D76192E4007DFB496CCA67E13B <== "abcdefghijklmnopqrstuvwxyz" 0xD174AB98D277D9F5A5611C2C9F419D9F <== "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789" 0x57EDF4A22BE3C955AC49DA2E2107B67A <== "12345678901234567890123456789012345678901234567890123456789012345678901234567890"