MD5/Implementation: Difference between revisions

From Rosetta Code
< MD5
Content added Content deleted
(Added PicoLisp)
(Move Modula-3 MD5 implementation here)
Line 386: Line 386:
57edf4a22be3c955ac49da2e2107b67a
57edf4a22be3c955ac49da2e2107b67a
</lang>
</lang>

=={{header|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:
<pre>
e38ca1d920c4b8b8d3946b2c72f01680
</pre>


=={{header|PicoLisp}}==
=={{header|PicoLisp}}==

Revision as of 20:53, 26 December 2010

Task
MD5/Implementation
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"

The MD5 Message-Digest Algorithm was developed by RSA Data Security, Inc. in 1991.

Warning
Rosetta Code is not a place you should rely on for examples of code in critical roles, including security.
Also, please note that MD5 is no longer considered fully secure and should not be used in high security applications. For these consider SHA1 or SHA2.
A competition is currently underway to find an algorithm to become SHA3 in 2012.

D

The standard library Phobos included an MD5 module, Phobos MD5 module sources.

The following implementation is a modification of the standard one, with only replacing the critical part (transform method) of the code to improve performance. The idea is to generate x86 assembly code by compile time template function, then mixin the assembly code into the critical part. It only work on x86 machine.

The assembly part: <lang d>module md5asm ; import std.string ; import std.conv ; import std.math ;

version(D_InlineAsm_X86) {} else { static assert(0,"For X86 machine only") ; }

// ctfe construction of transform expressions uint S(uint n) { 

   return [7u,12,17,22,5,9,14,20,4,11,16,23,6,10,15,21][(n/16)*4 + (n % 4)] ;

} uint K(uint n) { 

   return ((n<=15)? n : (n <=31) ? 5*n+1 : (n<=47) ? (3*n+5) : (7*n)) % 16 ;

} uint T(uint n) { return cast(uint) (abs(sin(n+1.0L))*(2UL^^32)) ; } enum abcd = ["EAX", "EBX", "ECX", "EDX"] ; string[] ABCD(int n) { return abcd[(64 - n)%4..4] ~ abcd[0..(64 - n)%4] ; } string SUB(int n, string s) { 

   return s.replace("ax", ABCD(n)[0]).replace("bx", ABCD(n)[1]).
            replace("cx", ABCD(n)[2]).replace("dx", ABCD(n)[3]) ;

} // FF, GG, HH & II expressions part 1 (F,G,H,I) string fghi1(int n) { 

   switch(n / 16) {
       case 0: return // (bb & cc)|(~bb & dd)
           q{mov ESI,bx;mov EDI,bx;not ESI;and EDI,cx;and ESI,dx;or EDI,ESI;add ax,EDI;} ;
       case 1: return // (dd & bb)|(~dd & cc)
           q{mov ESI,dx;mov EDI,dx;not ESI;and EDI,bx;and ESI,cx;or EDI,ESI;add ax,EDI;} ;
       case 2: return // (bb ^ cc ^ dd)
           q{mov EDI,bx;xor EDI,cx;xor EDI,dx;add ax,EDI;} ;
       case 3: return // (cc ^ (bb | ~dd))
           q{mov EDI,dx;not EDI;or EDI,bx;xor EDI,cx;add ax,EDI;} ;
   }

} // FF, GG, HH & II expressions part 2 string fghi2(int n) { return q{add ax,[EBP + 4*KK];add ax,TT;} ~ fghi1(n) ; } // FF, GG, HH & II expressions prepended with previous parts & subsitute ABCD string FGHI(int n) { 

       return SUB(n, fghi2(n) ~ q{rol ax,SS;add ax,bx;}) ;
           // aa = ((aa << SS)|( aa >>> (32 - SS))) + bb = ROL(aa, SS) + bb

} string EXPR(uint n) { 

   return FGHI(n).replace("SS", to!string(S(n))).
                  replace("KK", to!string(K(n))).
                  replace("TT", "0x"~to!string(T(n),16)) ;

} string TRANSFORM(int n) { return (n < 63) ? EXPR(n) ~ TRANSFORM(n+1) : EXPR(n) ; }

// main steps of transform , to be mixing const string Transform = TRANSFORM(0) ; </lang>

The modified transform method on new module: <lang d>module zmd5 ; private import md5asm ;

/* 

 duplicated codes from standard module
  • /
   private void transform(ubyte* block) {

       uint[16] x;

       Decode (x.ptr, block, 64);

       auto pState  = state.ptr ;
       auto pBuffer = x.ptr ;

       asm{
           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 { "~md5asm.Transform~"}") ;

       asm{
           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 ;
   }

/* 

 duplicated codes from standard module
  • /

</lang>

This test the performance difference: <lang d>import std.stdio ; import std.perf ; private import std.md5 ; private import zmd5 ; private import md5asm ;

void main() { writefln("digest(\"\") = %s", std.md5.getDigestString("")) ; writefln("digest(\"\") = %s", zmd5.getDigestString("")) ;

const MBytes = 512 ; float[] MSG = new float[](MBytes * 0x40000 + 13) ; auto pf = new PerformanceCounter ;

writefln("\nTest performance / message size %dMBytes", MBytes) ; pf.start() ; writefln("digest(MSG) = %s", std.md5.getDigestString(MSG)) ; 

       pf.stop() ; auto time = pf.milliseconds/1000.0 ;

writefln("std.md5 : %8.2f M/sec ( %8.2fsecs)", MBytes/time, time) ;

pf.start() ; writefln("digest(MSG) = %s", zmd5.getDigestString(MSG)) ; pf.stop() ; time = pf.milliseconds/1000.0 ; writefln("zmd5  : %8.2f M/sec ( %8.2fsecs)", MBytes/time, time) ; }</lang>

output: 

digest("")  = D41D8CD98F00B204E9800998ECF8427E
digest("")  = D41D8CD98F00B204E9800998ECF8427E
Test performance / message size 512MBytes
digest(MSG) = A36190ECA92203A477EFC4DAB966CE6F
std.md5 :    27.18 M/sec  (    18.84secs)
digest(MSG) = A36190ECA92203A477EFC4DAB966CE6F
zmd5    :   111.50 M/sec  (     4.59secs)

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

Library: Icon Programming Library

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>

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

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"

Tcl

This code is extracted from the md5 package in

Library: tcllib

, 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

  1. 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]

}

      1. 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>

Retrieved from "https://rosettacode.org/wiki/MD5/Implementation?oldid=157673"