MD5 implementation in SDLBASIC: pls help me : (

[Arcap94]

Hi @ all

i want to make a function that returns the MD5 checksum of a string.
Since there arent any endians in sdlbasic and there isnt the function leftrotate im stuck.
i was following the pseudocode @ http://en.wikipedia.org/wiki/MD5
this is my code:

Code:

Function MD5(message)
dim r[]
dim k[]
dim w[]
r[0]=7:r[1]=12:r[2]=17:r[3]=22:r[4]=7:r[5]=12:r[6]=17:r[7]=22:r[8]=7:r[9]=12:r[10]=17:r[11]=22:r[12]=7:r[13]=12:r[14]=17:r[15]=22
r[16]=5:r[17]=9:r[18]=14:r[19]=20:r[20]=5:r[21]=9:r[22]=14:r[23]=20:r[24]=5:r[25]=9:r[26]=14:r[27]=20:r[28]=5:r[29]=9:r[30]=14:r[31]=20
r[32]=4:r[33]=11:r[34]=16:r[35]=23:r[36]=4:r[37]=11:r[38]=16:r[39]=23:r[40]=4:r[41]=11:r[42]=16:r[43]=23:r[44]=4:r[45]=11:r[46]=16:r[47]=23
r[48]=6:r[49]=10:r[50]=15:r[51]=21:r[52]=6:r[53]=10:r[54]=16:r[55]=21:r[56]=6:r[57]=10:r[58]=15:r[59]=21:r[60]=6:r[61]=10:r[62]=15:r[63]=21

k[0]=7:k[1]=12:k[2]=17:k[3]=22:k[4]=7:k[5]=12:k[6]=17:k[7]=22:k[8]=7:k[9]=12:k[10]=17:k[11]=22:k[12]=7:k[13]=12:k[14]=17:k[15]=22
k[16]=5:k[17]=9:k[18]=14:k[19]=20:k[20]=5:k[21]=9:k[22]=14:k[23]=20:k[24]=5:k[25]=9:k[26]=14:k[27]=20:k[28]=5:k[29]=9:k[30]=14:k[31]=20
k[32]=4:k[33]=11:k[34]=16:k[35]=23:k[36]=4:k[37]=11:k[38]=16:k[39]=23:k[40]=4:k[41]=11:k[42]=16:k[43]=23:k[44]=4:k[45]=11:k[46]=16:k[47]=23
k[48]=6:k[49]=10:k[50]=15:k[51]=21:k[52]=6:k[53]=10:k[54]=16:k[55]=21:k[56]=6:k[57]=10:k[58]=15:k[59]=21:k[60]=6:k[61]=10:k[62]=15:k[63]=21

//I hate for^^
i=0
while 1
     if i=64 then : exit while : end if
k[i] = floor(abs(sin(i + 1)) * 2^32)
i=i+1
wend


h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476

//converting string --> bin code
i=1
b=""
while 1
if i> len(message) then : exit while : end if
b=b&bin(asc(mid(message,i,1)))
i=i+1
wend
message=b

//adding bit 1 to message
message=message&"1"

//filling message up with "0" until  frac(length(message)/512) != 0

while frac(length(message)/512) != 0
message=message&"0"
wend

message=message&bin(length(message)) //This isnt right, is it?
//... stuck here
end function

Can you pls help me?

[Derek]

Hi,

this is the first time I've studied MD5 sums in any detail but I'l give it a shot

Code:

message=message&bin(length(message)) //this isnt right, is it?

I don't believe it is. bin(length(message)) needs padding out with zeros to the left to make it 64 bits. It also says that it is little-endian so the length will have to be reversed (big endian 2 = 00000010, little endian 2 = 01000000 *Scratches head* I think that's right. I really couldn't explain little and big endian if my life depended upon it. Bi-endian? Give me a break.)

You then need to go through the binary message in 512 bit chunks (hence the need to ensure that the length of the message is divisible by 512).

Code:

for i = 1 to length_of_message step 512

then the 512 bit chunk is split into four 64 bit chunks and operated on.

I believe that I have got this correct but I could be wrong. I hope someone will come along and correct anything I've messed up.

Derek.

Edit:
10 (ten) padded to 64 bits looks like this (big endian)
0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1010
little endian:
0101 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000

There must be mathematical way of calculating this but I don't know it.

[Arcap94]

Hi,

this is the first time I've studied MD5 sums in any detail but I'l give it a shot

Code:

message=message&bin(length(message)) //this isnt right, is it?

I don't believe it is. bin(length(message)) needs padding out with zeros to the left to make it 64 bits. It also says that it is little-endian so the length will have to be reversed (big endian 2 = 00000010, little endian 2 = 01000000 *Scratches head* I think that's right. I really couldn't explain little and big endian if my life depended upon it. Bi-endian? Give me a break.)

You then need to go through the binary message in 512 bit chunks (hence the need to ensure that the length of the message is divisible by 512).

Code:

for i = 1 to length_of_message step 512

then the 512 bit chunk is split into four 64 bit chunks and operated on.

I believe that I have got this correct but I could be wrong. I hope someone will come along and correct anything I've messed up.

Derek.

Edit:
10 (ten) padded to 64 bits looks like this (big endian)
0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1010
little endian:
0101 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000

There must be mathematical way of calculating this but I don't know it.

thank you for your response.
this is what i did now:

Code:

msadd=bin(message_laenge)
while len(msadd) != 64
msadd=msadd&"0"
wend

pt1=mid(msadd,1,4) : pt2=mid(msadd,5,4) : pt3=mid(msadd,9,4) : pt4=mid(msadd,13,4) : pt5=mid(msadd,17,4) : pt6=mid(msadd,21,4) : pt7=mid(msadd,25,4) : pt8=mid(msadd,29,4) : pt9=mid(msadd,33,4) : pt10=mid(msadd,37,4) : pt11=mid(msadd,41,4)
pt12=mid(msadd,45,4) : pt13=mid(msadd,49,4) : pt14=mid(msadd,53,4) : pt15=mid(msadd,57,4) : pt16=mid(msadd,61,4)
msadd=pt16&pt15&pt14&pt13&pt12&pt11&pt10&pt9&pt8&pt7&pt6&pt5&pt4&pt3&pt2&pt1
message=message&msadd

it works as you said.
but now its said: "for each 512-bit chunk of message
    break chunk into sixteen 32-bit little-endian words w, 0 ? i ? 15"
does that mean you only spilt etc. if theres a full 512 bit chunk? will the rest be spiltted to0 or will it be left like it is?
So hard...

[Derek]

Hi,

the binary string you build from the message will be a multiple of 512 bits. If it isn't then the preliminary stages have a bug. Check the length of the string divided by 512. The result has to be an integer.

Derek.

[Arcap94]

Hi,

the binary string you build from the message will be a multiple of 512 bits. If it isn't then the preliminary stages have a bug. Check the length of the string divided by 512. The result has to be an integer.

Derek.

but what about:
"append bit /* bit, not byte */ length of unpadded message as 64-bit little-endian integer to message"
for example: 512bit +64bit wouldnt that make 576bit what isnt a multiple of 512

[Derek]

This is followed by as many zeros as are required to bring the length of the message up to 64 bits fewer than a multiple of 512. The remaining bits are filled up with a 64-bit integer representing the length of the original message, in bits.

You may also need to pad the binary values of the characters of the message to 8 bits.

As you say it's complicated but I know I'm learning something this evening

Derek.

[Arcap94]

this is my new code:

Code:

Function SwapEndian32Bit(e)
temp=""
i=29
while 1
if i<=-4 then : exit while : end if
temp=temp&mid(e,i,4)
i=i-4
wend
return temp
end function

Function SwapEndian64Bit(e)
temp=""
i=61
while 1
if i<=-4 then : exit while : end if
temp=temp&mid(e,i,4)
i=i-4
wend
return temp
end function

Function leftrotate(s,n)
while 1
if n=0 then : exit while : end if
s=mid(s,2,len(s))&left(s,1)
n=n-1
if key(K_return) then : prints(n) : end if
wait(1)
wend
return s
end Function

Function MD5(message)
//Definiere r und k wie folgt:
dim r[]
dim k[]
dim w[]
r[0]=7:r[1]=12:r[2]=17:r[3]=22:r[4]=7:r[5]=12:r[6]=17:r[7]=22:r[8]=7:r[9]=12:r[10]=17:r[11]=22:r[12]=7:r[13]=12:r[14]=17:r[15]=22
r[16]=5:r[17]=9:r[18]=14:r[19]=20:r[20]=5:r[21]=9:r[22]=14:r[23]=20:r[24]=5:r[25]=9:r[26]=14:r[27]=20:r[28]=5:r[29]=9:r[30]=14:r[31]=20
r[32]=4:r[33]=11:r[34]=16:r[35]=23:r[36]=4:r[37]=11:r[38]=16:r[39]=23:r[40]=4:r[41]=11:r[42]=16:r[43]=23:r[44]=4:r[45]=11:r[46]=16:r[47]=23
r[48]=6:r[49]=10:r[50]=15:r[51]=21:r[52]=6:r[53]=10:r[54]=16:r[55]=21:r[56]=6:r[57]=10:r[58]=15:r[59]=21:r[60]=6:r[61]=10:r[62]=15:r[63]=21

k[0]=7:k[1]=12:k[2]=17:k[3]=22:k[4]=7:k[5]=12:k[6]=17:k[7]=22:k[8]=7:k[9]=12:k[10]=17:k[11]=22:k[12]=7:k[13]=12:k[14]=17:k[15]=22
k[16]=5:k[17]=9:k[18]=14:k[19]=20:k[20]=5:k[21]=9:k[22]=14:k[23]=20:k[24]=5:k[25]=9:k[26]=14:k[27]=20:k[28]=5:k[29]=9:k[30]=14:k[31]=20
k[32]=4:k[33]=11:k[34]=16:k[35]=23:k[36]=4:k[37]=11:k[38]=16:k[39]=23:k[40]=4:k[41]=11:k[42]=16:k[43]=23:k[44]=4:k[45]=11:k[46]=16:k[47]=23
k[48]=6:k[49]=10:k[50]=15:k[51]=21:k[52]=6:k[53]=10:k[54]=16:k[55]=21:k[56]=6:k[57]=10:k[58]=15:k[59]=21:k[60]=6:k[61]=10:k[62]=15:k[63]=21

// Verwende den binären Vorkommateil vom 2^32-fachen Betrag des Sinus
// von Integerwerten als Konstanten:
i=0
while 1
if i=64 then : exit while : end if
k[i] = floor(abs(sin(i + 1)) * 2^32)
i=i+1
wend

// Initialisiere die Variablen:
h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
//prints(h1)
//wandle message binärcode:
i=1
b=""
while 1
if i> len(message) then : exit while : end if
b=b&bin(asc(mid(message,i,1)))
i=i+1
wend
message=b
//message vorbereitung:
message_laenge=len(message)
//prints(message_laenge)
message=message&"1"
while length(message) != (message_laenge/512 - frac(message_laenge/512)+1)*512 - 64
message=message&"0"
wend
//prints(len(message))
msadd=bin(message_laenge)
while len(msadd) != 64
msadd=msadd&"0"
wend
msadd=Swapendian64Bit(msadd)
message=message&msadd

i=0
while 1
if i=16 then : exit while : end if
w[i]=mid(message,i*32+1,32)
i=i+1
wend



a=h0
b=h1
c=h2
d=h3

l=0
while 1
if l=len(message) then : exit while : end if
i=0

while 1
if i=16 then : exit while : end if
w[i]=mid(message,i*32+1,32)
i=i+1
wend

l=l+512
i=0
while 1
if i=64 then : exit while : end if
if 0 <= i <= 15 then
f = (b and c) or ((not b) and d)
g = i           : end if
if 16 <= i <= 31 then
f = (d and b) or ((not d) and c)
g = (5*i + 1) mod 16      : end if
if 32 <= i <= 47  then
f = b xor c xor d
g = (3*i + 5) mod 16     : end if
if 48 <= i <= 63 then
f = c xor (b or (not d))
g = (7*i) mod 16       : end if

temp = d
d = c
c = b
b = b + leftrotate((a + f + k[i] + w[g]) , r[i])
a = temp


h0 = h0 + a
h1 = h1 + b
h2 = h2 + c
h3 = h3 + d
i=i+1

wend

wend
return h0 & h1 & h2 & h3

end function

prints( MD5("Hallo"))

waitkey(K_return)

when i start it it shows me and error saying:"Fatal signal: Segmentation Fault (SDL Parachute Deployed)"
this is because of the line
"b = b + leftrotate((a + f + k + w[g]) , r)"
because it wont crash if i comment this line out.
then it the programm shows me some strange negative numbers.

You may also need to pad the binary values of the characters of the message to 8 bits.

As you say it's complicated but I know I'm learning something this evening

Derek.

hmm ill try

[Derek]

Hi,

I haven't had time to study what you've just posted to any depth but I believe you may be mixing binary and decimal numbers. Hmmm, perhaps giving decimal variables a "d" prefix and binary variables a "b" prefix will help you (and me ) understand the problem.

I also get a segfault from the line you posted which suggests that SdlBasic isn't doing enough error checking before executing that line.

I may try doing this in Yabasic just for the fun of it

Derek.

[Derek]

Hi,

how are you getting on with this? The negative numbers are caused by the fact that the hexadecimal numbers are so vast they are being misrepresented by SDLBasic and interpreted as negative values.

You probably have to add the hex numbers together in a way that the language can cope. I have written a routine in Yabasic that should show you how to do it in SDLBasic.
If you wish I'll convert it to SDLBasic.

Derek.

Code:

sub HexAdd$(iH1$, iH2$)
local A, B, i, iCarry, iMax, j
local iAnswer$, iRes$
local iH$(2)
iMax = max(len(iH1$), len(iH2$))
for i = 1 to iMax
iH$(1) = iH$(1) + "0"
next i
iH$(2) = iH$(1)
right$(iH$(1), len(iH1$)) = iH1$
right$(iH$(2), len(iH2$)) = iH2$
for i = 1 to 2
iH$(i) = upper$(iH$(i))
next i
for i = iMax to 1 step - 1
A = dec(mid$(iH$(1), i, 1))
B = dec(mid$(iH$(2), i, 1))
iRes$ = hex$(A + B)
if iCarry then
iRes$ = HexAdd$("1", iRes$)
end if
iCarry = 0
if len(iRes$) = 2 then
iCarry = 1
end if
iAnswer$ = right$(iRes$, 1) + iAnswer$
next i
if iCarry = 1 then
iAnswer$ = left$(iRes$, 1) + iAnswer$
end if
return iAnswer$
end sub

[Arcap94]

Hey Derek,

Thanks alot that you´ve spend sime time trying to help me.
That would be very nice if you could translate that into sdlbasic.
BTW: Sry for my bad english. im not a native english speaker.

[Derek]

Hi,

I'll give it a go. I haven't written anything much in this language so it may take some time; please be patient

Derek.

[Derek]

Hi,

this is the first time I've used sdlBasic seriously and I must say that I don't like the way numeric and string vars can be used interchangeably. It appears to me that if a string = "123" sdlBasic believes the variable to be numeric which makes debugging confusing. Anyway I've managed to write something that works. I noticed that there is a function to convert decimal to hex but not hex to dec so I wrote my own though it only works if the hex number is in capitals.

I added a loop for debugging purposes and left it in so you can test it to ensure that it works in all cases. You won't need that in the MD5 routine. HexAdd() uses the function dec() so make sure you copy that across. Bare in mind that I ignored any error checking so it will attempt to add any strings together which will cause some very bizarre behaviour.

Finally it can only add two numbers so you will have string multiple calculations together:

Code:

h1 = HexAdd("23", "AE")
total = HexAdd(h1, "ED")

HTH,

Derek.

Code:

function dec(iVal)
if iVal>="0" and iVal<="9" then
iNum=asc(iVal)-48
else
iNum=asc(iVal)-55
end if
return iNum
end function

function HexAdd(iH1, iH2)
dim iH[2]
iMax = max(length(iH1), length(iH2))
LiH1=iMax-length(iH1)
LiH2=iMax-length(iH2)
iH[1]=string$(LiH1,"0")
iH[2]=string$(LiH2,"0")
iH[1]=iH[1]+iH1
iH[2]=iH[2]+iH2
for i = 1 to 2
iH[i] = ucase(iH[i])
next
iAnswer=""
for i = iMax to 1 step - 1
A = dec(mid$(iH[1], i,1))
B = dec(mid$(iH[2], i,1))
-- print mid$(iH[1], i,1);", ";mid$(iH[2], i,1)
-- print A;", ";B
iRes =hex(A+B)
-- print "iRes = ";iRes
if iCarry then
iRes = HexAdd("1", iRes)
end if
iCarry = 0
if len(iRes) = 2 then
iCarry = 1
end if
iAnswer = str$(right$(iRes, 1)) + str$(iAnswer)
-- print "iAnswer = ";iAnswer
next
if iCarry = 1 then
iAnswer = str$(left$(iRes, 1)) + str$(iAnswer)
end if
return iAnswer
end function

do
iter = 0
h1=str$(inputS( "H1: ", ""))
h2=str$(inputS("H2: ",""))
printS(HexAdd(h1, h2))
loop