MD5/Implementation: Difference between revisions

From Rosetta Code
< MD5
Content added Content deleted
mNo edit summary
No edit summary
Line 146: Line 146:
Digest = CC175B9C0F1B6A831C399E269772661 matches reference hash
Digest = CC175B9C0F1B6A831C399E269772661 matches reference hash
...</pre>
...</pre>

=={{header|Tcl}}==
<small>This code is extracted from the <code>md5</code> package in {{libheader|tcllib}}</small>
<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 {

#
# 3.1 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]

#
# 3.2 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]
#
# 3.3 Step 3. Initialize MD Buffer
#

set A [expr 0x67452301]
set B [expr 0xefcdab89]
set C [expr 0x98badcfe]
set D [expr 0x10325476]

#
# 3.4 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
}
# 3.5 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

# bitwise left-rotate

# inline <<<
regsub -all -- {\[ *<<< +\[ *expr +({[^\}]*})\] +([0-9]+) *\]} $md5body {(([set x [expr \1]] << \2) | (($x >> R\2) \& S\2))} md5body

# now replace the R and S
set map {}
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
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 ::md5::byte0 {i} {expr {0xff & $i}}
proc ::md5::byte1 {i} {expr {(0xff00 & $i) >> 8}}
proc ::md5::byte2 {i} {expr {(0xff0000 & $i) >> 16}}
proc ::md5::byte3 {i} {expr {((0xff000000 & $i) >> 24) & 0xff}}

proc ::md5::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>

Revision as of 09:05, 29 September 2010

MD5/Implementation is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

The purpose of this task to code and validate an implementation of the MD5 Message Digest Algorithm using native facilities within your language. 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 NOT use built in functions, call outs to operating system calls or library routines written in other languages. For these see MD5.
  • An implementation taken from a native source library and shown on this site is acceptable.

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: 

   0xd41d8cd98f00b204e9800998ecf8427e ==> ""  
   0x0cc175b9c0f1b6a831c399e269772661 ==> "a"
   0x900150983cd24fb0d6963f7d28e17f72 ==> "abc"
   0xf96b697d7cb7938d525a2f31aaf161d0 ==> "message digest"
   0xc3fcd3d76192e4007dfb496cca67e13b ==> "abcdefghijklmnopqrstuvwxyz"
   0xd174ab98d277d9f5a5611c2c9f419d9f ==> "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
   0x57edf4a22be3c955ac49da2e2107b67a ==> "12345678901234567890123456789012345678901234567890123456789012345678901234567890"

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. <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 static maxpad

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
  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] := map("01234567","76543210",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 := 0 to 63 do  {                      # Process 4 rounds of hashes	
        case round := i/16 of {

0 : { # 0..15 f := ixor(d, iand(b,ixor(c,d))) # alternate F 

              g := i

} 

           1 : {                                   # 16..31
              f := ixor(c,iand(d,ixor(b,c)))       # alternate G	
              g := (5*i+1) % 16

} 

           2 : {                                   # 32..47
              f := ixor(b,ixor(c,d))               # H
              g := (3*i+5) % 16
              }		 
           3 : {                                   # 48..64
              f := ixor(c,ior(b,ixor(d,16rffffffff)))  # I
              g := (7*i) % 16 
              }

} 

        a +:= (f + ks[i+1] + w[g+1])               # Core of FF, GG, HH, II
        a %:= M32

a := ior( ishift(a,rs[i+1]), ishift(a,-(32-rs[i+1]))) # 32bit rotate a +:= b a %:= M32 

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

Tcl

This code is extracted from the md5 package in

Library: tcllib

<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 {

       #
       # 3.1 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]

       #
       # 3.2 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]
       
       #
       # 3.3 Step 3. Initialize MD Buffer
       #

       set A [expr 0x67452301]
       set B [expr 0xefcdab89]
       set C [expr 0x98badcfe]
       set D [expr 0x10325476]

       #
       # 3.4 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
       }
       # 3.5 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

       # bitwise left-rotate

       # inline <<<
       regsub -all -- {\[ *<<< +\[ *expr +({[^\}]*})\] +([0-9]+) *\]} $md5body {(([set x [expr \1]] << \2) |  (($x >> R\2) \& S\2))} md5body

       # now replace the R and S
       set map {}
       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
       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 ::md5::byte0 {i} {expr {0xff & $i}}
   proc ::md5::byte1 {i} {expr {(0xff00 & $i) >> 8}}
   proc ::md5::byte2 {i} {expr {(0xff0000 & $i) >> 16}}
   proc ::md5::byte3 {i} {expr {((0xff000000 & $i) >> 24) & 0xff}}

   proc ::md5::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=157647"