Blog

Nov09

MD5-Summengenerator für Turbo-BASIC (update: läuft!)

Auf Grund einer Forendiskussion kam mir die Idee, einen MD5-Prüfsummengenerator für Turbo-BASIC zu portieren. Dazu habe ich den Pseudocode von Wikipedia direkt zu einem Turbo-BASIC-Listing umgeschrieben, um auf keinen Fall Tippfehler bei den vorgegebenen Initial-Werten zu machen. Das Ergebnis ist unten zu sehen und kann in Atari800MacX direkt eingefügt werden (im Browser markieren und CMD+C drücken, im Atari800MacX CMD+V drücken). In Altirra sollte es auch gehen, das habe ich lediglich noch nicht getestet. Die nun vorliegende Fassung generiert aus dem Test-Text "Wurstwasser" (ohne Anführungszeichen) die nunmehr korrekte MD5-Summe, nachdem ich heute die Fehlersuche beendet habe.

Zwei Fehler haben mir die Fehlersuche bis zum Schluss schwer gemacht: Einmal gab Wikipedia nicht an, dass die Länge der ursprünglichen Nachricht in Bits an das Ende der Nachricht angefügt wird (also 88 Bits Länge statt 11 Bytes). Der zweite Fehler war eher marginal, nachdem meine Zwischenwerte denen des C-Programms glichen. Die Summen-Werte werden nach der Berechnung ebenfalls in Little-Endian ausgegeben, d.h. die zwei Hex-Stellen des niederwertigsten Byte kommt zuerst, dann die anderen und zum Schluss das höchstwertige.

Das Programm bildet jetzt zumindest von der Nachricht "Wurstwasser" den richtigen MD5-Code. Andere String probiere ich lieber nicht aus, macht Ihr das mal und schaut, ob es stimmt.

0 mm=16000
10 dim mem$(mm)
20 dim f$(256)
30 mem$="Wurstwasser"
35 .echo -n Wurstwasser | md5 (Mac), md5sum (Linux): 2895766f3f4249c3ae39c635e4ac0c74
40 OxFFFFFFFF=2^32 - 1
41 OxFFFF=2^16 - 1
42 Ox100=2^8
43 Ox10000=2^16
44 Ox1000000=2^24
45 Ox80000000=2^31
46 Ox100000000=2^32
100 .Beachte: Alle Variablen sind vorzeichenlose (unsigned) 32-Bit-Werte und
110 .verhalten sich bei Berechnungen kongruent (≡) modulo 2^32
120 .
130 .s definiert die Anzahl der Bits, die pro Runde rotiert werden:
140 dim s(64)
150 res.150
160 f.p=0 to 63:read q:s(p)=q:n.p
170 d.7,12,17,22,7,12,17,22,7,12,17,22,7,12,17,22
171 d.5,9,14,20,5,9,14,20,5,9,14,20,5,9,14,20
172 d.4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23
173 d.6,10,15,21,6,10,15,21,6,10,15,21,6,10,15,21
179 .
180 .Verwende den binären Vorkommateil vom 2^32-fachen Betrag des Sinus
181 .von Integerwerten als Konstanten:
182 .fuer alle i von 0 bis 63
183 .(
184 .____K[i] := floor(abs(sin(i + 1)) × 2^32)
185 .)
186 .
187 .Alternativ kann man auch folgende Tabelle nutzen:
189 res.190
190 dim k(64),k$(10)
200 f.p=%0 to 63
210 read k$
215 f.q=%3 to 10:if k$(q,q)>="a" and k$(q,q)<="f":k$(q,q)=chr$(asc(k$(q))-32):endif:n.q
220 k(p)=dec(k$(%3,6))*Ox10000+dec(k$(7,10))
230 n.p
240 d.0xd76aa478,0xe8c7b756,0x242070db,0xc1bdceee
241 d.0xf57c0faf,0x4787c62a,0xa8304613,0xfd469501
242 d.0x698098d8,0x8b44f7af,0xffff5bb1,0x895cd7be
243 d.0x6b901122,0xfd987193,0xa679438e,0x49b40821
244 d.0xf61e2562,0xc040b340,0x265e5a51,0xe9b6c7aa
245 d.0xd62f105d,0x02441453,0xd8a1e681,0xe7d3fbc8
246 d.0x21e1cde6,0xc33707d6,0xf4d50d87,0x455a14ed
247 d.0xa9e3e905,0xfcefa3f8,0x676f02d9,0x8d2a4c8a
248 d.0xfffa3942,0x8771f681,0x6d9d6122,0xfde5380c
249 d.0xa4beea44,0x4bdecfa9,0xf6bb4b60,0xbebfbc70
250 d.0x289b7ec6,0xeaa127fa,0xd4ef3085,0x04881d05
251 d.0xd9d4d039,0xe6db99e5,0x1fa27cf8,0xc4ac5665
252 d.0xf4292244,0x432aff97,0xab9423a7,0xfc93a039
253 d.0x655b59c3,0x8f0ccc92,0xffeff47d,0x85845dd1
254 d.0x6fa87e4f,0xfe2ce6e0,0xa3014314,0x4e0811a1
255 d.0xf7537e82,0xbd3af235,0x2ad7d2bb,0xeb86d391
259 .
260 .Initialisiere die Variablen: (lt. RFC 1321)
270 a0=$6745*Ox10000+$2301
271 b0=$EFCD*Ox10000+$AB89
272 c0=$98BA*Ox10000+$DCFE
273 d0=$1032*Ox10000+$5476
279 .
280 .Vorbereitung der Nachricht 'message':
290 .var uint message_laenge := bit_length(message)
300 message_laenge=len(mem$):des_len=int(message_laenge/64+%1)*64
305 .?"len=";message_laenge
306 .?"des_len=";des_len
309 .erweitere message um bit "1"
310 mem$(len(mem$)+%1)=chr$(128)
319 .erweitere message um bits "0" bis Länge von message in bits ≡ 448 (mod 512)
320 .ich fuelle alles mit Nullen; die Laenge als 64-Bit-Wert endet auf dem A8 immer mit 0x00000000
321 f.p=len(mem$)+%1 to des_len:mem$(p)=chr$(%0):n.p
329 .erweitere message um message_laenge (in Bits) als 64-Bit little-endian Integer
330 l=message_laenge*8
340 ch=int(l/Ox1000000):mem$(des_len-4,des_len-4)=chr$(ch):l=l-ch*Ox1000000
350 ch=int(l/Ox10000):mem$(des_len-5,des_len-5)=chr$(ch):l=l-ch*Ox10000
360 ch=int(l/Ox100):mem$(des_len-6,des_len-6)=chr$(ch):l=l-ch*Ox100
370 mem$(des_len-7,des_len-7)=chr$(l)
375 .?"mem$=""";mem$;""""
376 .f.p=%1 to len(mem$):?hex$(asc(mem$(p)));" ";:n.p:?
380 .Verarbeite die Nachricht in aufeinander folgenden 512-Bit-Blöcken:
390 .für alle 512-Bit Block von message
400 f.block=%0 to des_len/64-%1:.512 Bit = 64 Byte
410 .?"Block=";block
420 .unterteile Block in 16 32-bit little-endian Worte M[i], 0 ≤ i ≤ 15
430 .Initialisiere den Hash-Wert für diesen Block:
440 A=a0:.?A
450 B=b0:.?B
460 C=c0:.?C
470 D=d0:.?D
480 .
490 .Hauptschleife:
500 .not Operator entspricht dem Einerkomplement
510 .für alle i von 0 bis 63
520 f.i=0 to 63:.?"i=";i
529 . 32-Bit-Werte B, C und D in H und L (je 16 Bit) unterteilen, um TB-Binaer-Ops zu ermoeglichen
530 Bh=int(B/Ox10000):Bl=B-Bh*Ox10000
531 Ch=int(C/Ox10000):Cl=C-Ch*Ox10000
532 Dh=int(D/Ox10000):Dl=D-Dh*Ox10000
540ifi<16thenF=((Bh&Ch)!((OxFFFF-Bh)&Dh))*Ox10000+((Bl&Cl)!((OxFFFF-Bl)&Dl)):g=i:go#if_end
550ifi<32thenF=((Bh&Dh)!(Ch&(OxFFFF-Dh)))*Ox10000+((Bl&Dl)!(Cl&(OxFFFF-Dl))):g=(5*i+1)mod16:go#if_end
560ifi<48thenF=(Bh exorCh exorDh)*Ox10000+(Bl exorCl exorDl):g=(3*i+5)mod16:go#if_end
570F=(Ch exor(Bh!(OxFFFF-Dh)))*Ox10000+(Cl exor(Bl!(OxFFFF-Dl))):g=(7*i) mod 16
580 #if_end
590 temp=D
591 D=C
592 C=B
595 .   B := B + lrot((A + F + K[i] + M[g]), s[i])
596 Ah=int(A/Ox10000):Al=A-Ah*Ox10000
597 Fh=int(F/Ox10000):Fl=F-Fh*Ox10000
598 Kh=int(K(i)/Ox10000):Kl=K(i)-Kh*Ox10000
600 Mi=block*64+g*4:.?"Mi=";Mi
601 M_g=asc(mem$(Mi+4))*Ox1000000+asc(mem$(Mi+%3))*Ox10000+asc(mem$(Mi+%2))*Ox100+asc(mem$(Mi+%1))
602 .?"g=";g;" M[g]=";M_g
604 .p_lrot_x=(A+F+K(i)+M_g) mod Ox100000000:g.609
605 x32=A:y32=F:exec add32mod:.p_add32mod_return=A+F
606 x32=p_add32mod_return:y32=K(i):exec add32mod:.p_add32mod_return=A+F+K[i]
607 x32=p_add32mod_return:y32=M_g:exec add32mod:.p_add32mod_return=A+F+K[i]+M[g]
608 p_lrot_x=p_add32mod_return
609 p_lrot_c=s(i):exec lrot
610 .?"lrot(A=";hex$(Ah);hex$(Al);"+F=";hex$(Fh);hex$(Fl);
611 .?"+K=";hex$(Kh);hex$(Kl);"+M[g]=";M_g;",s[i]=";s(i);")":gete
612 .?"lrot(";hex$(Ah);hex$(Al);"+";hex$(Fh);hex$(Fl);
613 .?"+";hex$(Kh);hex$(Kl);"+";M_g;",";s(i);")":gete
614 .B=(B+p_lrot_return) mod Ox100000000:g.620
615 x32=B:y32=p_lrot_return:exec add32mod:B=p_add32mod_return
620 A=temp
630 next i
640 .Addiere den Hash-Wert des Blocks zur Summe der vorherigen Hashes:
650 .a0=(a0+A) mod Ox100000000
651 x32=a0:y32=A:exec add32mod:a0=p_add32mod_return:.?"a0=";a0
660 .b0=(b0+B) mod Ox100000000
661 x32=b0:y32=B:exec add32mod:b0=p_add32mod_return:.?"b0=";b0
670 .c0=(c0+C) mod Ox100000000
671 x32=c0:y32=C:exec add32mod:c0=p_add32mod_return:.?"c0=";c0
680 .d0=(d0+D) mod Ox100000000
681 x32=d0:y32=D:exec add32mod:d0=p_add32mod_return:.?"d0=";d0
690 next block
699 .    
700 .var uint digest := a0 anfügen b0 anfügen c0 anfügen d0 // Darstellung als little-endian
710 .?hex$(a0);hex$(b0);hex$(c0);hex$(d0)
715 .32-Bit-Werte in 8 Bit aufteilen, um auch gleich fuehrende Nullen zu zeigen
720 a0xooo=int(a0/Ox1000000)
721 a0oxoo=int(a0/Ox10000)-a0xooo*Ox100
722 a0ooxo=int(a0/Ox100)-a0xooo*Ox10000-a0oxoo*Ox100
723 a0ooox=a0-a0xooo*Ox1000000-a0oxoo*Ox10000-a0ooxo*Ox100
730 b0xooo=int(b0/Ox1000000)
731 b0oxoo=int(b0/Ox10000)-b0xooo*Ox100
732 b0ooxo=int(b0/Ox100)-b0xooo*Ox10000-b0oxoo*Ox100
733 b0ooox=b0-b0xooo*Ox1000000-b0oxoo*Ox10000-b0ooxo*Ox100
740 c0xooo=int(c0/Ox1000000)
741 c0oxoo=int(c0/Ox10000)-c0xooo*Ox100
742 c0ooxo=int(c0/Ox100)-c0xooo*Ox10000-c0oxoo*Ox100
743 c0ooox=c0-c0xooo*Ox1000000-c0oxoo*Ox10000-c0ooxo*Ox100
750 d0xooo=int(d0/Ox1000000)
751 d0oxoo=int(d0/Ox10000)-d0xooo*Ox100
752 d0ooxo=int(d0/Ox100)-d0xooo*Ox10000-d0oxoo*Ox100
753 d0ooox=d0-d0xooo*Ox1000000-d0oxoo*Ox10000-d0ooxo*Ox100
760 ?hex$(a0ooox);hex$(a0ooxo);hex$(a0oxoo);hex$(a0xooo);
761 ?hex$(b0ooox);hex$(b0ooxo);hex$(b0oxoo);hex$(b0xooo);
762 ?hex$(c0ooox);hex$(c0ooxo);hex$(c0oxoo);hex$(c0xooo);
763 ?hex$(d0ooox);hex$(d0ooxo);hex$(d0oxoo);hex$(d0xooo);
799 end
5000 .addiere zwei 32 Werte modulo (schneide alles mehr als 32 ab)
5001 proc add32mod:.x32 + y32 = p_add32mod_return
5010   if x32>=Ox100000000 then ?"Error: x32 too big!":end
5011   if y32>=Ox100000000 then ?"Error: y32 too big!":end
5015   .zwei 32-bit-Zahlen in 16 bit unterteilen und mit Uebertrag addieren
5020   x32h=int(x32/Ox10000):x32l=x32-x32h*Ox10000
5021   y32h=int(y32/Ox10000):y32l=y32-y32h*Ox10000
5030   z32h=0:z32l=x32l+y32l
5031   if z32l>=Ox10000 then z32h=1:z32l=z32l mod Ox10000
5032   z32h=(z32h+x32h+y32h) mod Ox10000
5040   p_add32mod_return=z32h*Ox10000 + z32l
5090   .?x32;"+";y32;"=";p_add32mod_return
5091   .z32h=int(p_add32mod_return/Ox10000):z32l=p_add32mod_return-z32h*Ox10000
5092   .?hex$(x32h);hex$(x32l);"+";hex$(y32h);hex$(y32l);"=";hex$(z32h);hex$(z32l)
5099 endproc
5200 .Definition der lrot Funktion, c ist der übergebene Wert von s[i] - siehe Hauptschleife
5201 proc lrot:.(p_lrot_x, p_lrot_c) => p_lrot_return
5210   if p_lrot_x>=Ox100000000 then ?"Error: p_lrot_x too big!":end
5211   if p_lrot_c>=Ox100000000 then ?"Error: p_lrot_c too big!":end
5220   xrl=p_lrot_x
5230   for p_lrot_p=1 to p_lrot_c
5240     if xrl>=Ox80000000 then xrl=xrl-Ox80000000:xrl=xrl+xrl+%1:g.5260
5250     xrl=xrl+xrl
5260   next p_lrot_p
5290   p_lrot_return=xrl
5299 endproc

Als Bonus enthält das Listing die Prozedur add32mod, welche zwei 32-Bit-Zahlen ("modulo") addiert. Dazu wird sie in zwei 16-Bit-Zahlen aufgeteilt, die mit Übertrag addiert und wieder zu einem 32-Bit-Wert zusammengefügt werden. Das 33. Bit wird abgeschnitten (modulo 2 hoch 32). Hintergrund ist, dass der Atari zwar sicher mit 32-Bit-Werten umgehen kann, jedoch irgendwo im Wertebereich von 32 bis 33 Bit an seine Grenzen stößt und somit keine genaue Addition mit Bordmitteln garantiert werden kann, selbst wenn wie hier das 33. Bit im Ergebnis abgeschnitten werden soll. Diese Prozedur stellt sicher, dass der Atari im Wertebereich von maximal 17 Bit arbeitet. Sie ist getestet, jedoch nicht auf Herz und Nieren!

Kleine Anmerkung: auch für "http://www.atarixle.de" wird die richtige Summe berechnet. :-)