nicht angemeldet
"1" Bit, "0" Bit...
Mojen.
Ich zerbreche mir nun schon seit einiger Zeit den Kopf an einer Kleinigkeit:
In der Beschreibung des MD5-Algorithmus wird u.a. erklärt, wie die zu verschlüsselnde Nachricht auf eine bestimmte Länge erweitert werden muß:
a single "1" bit is appended to the message, and then "0" bits are appended so that the length in bits of the padded message becomes congruent to 448, modulo 512
Ok, alles klar... Dachte ich. Denn in allen Umsetzungen des Algorithmus, die ich mir bisher angeschaut habe, wird das erste Bit des Anhängsels nicht auf "1", sondern auf "0x80" gesetzt.
Das entspricht doch einem Dezimalwert von "128" - was weder "1" ist noch in ein einzelnes Bit "paßt", das nur die Zustände "1" oder "0" annehmen kann.
Ist mir da irgendwas wesentliches entgangen? Wer kann etwas Licht ins Dunkel bringen?
-
also, ja, wie bitte?
grade habe deinposting entdeckt undwill was dazu sagen.
Ist mir da irgendwas wesentliches entgangen?
jawoll.
Wer kann etwas Licht ins Dunkel bringen?
Na, ichnatürlich, wersonst? Du mußt direinfach über den Unterschied von bits und Byte klarwerden, das eineist kleiner alsdas andre. Also, bits sind die mit "1" und "0", und bytes sind schon viele bits, aberich sag dir jetzt nicht, wieviele, ätsch. Steht nämlich injedem ordentlichen Lehrbuch drin.
So.
grüße dichund alle anderenganz lieb
alsowiebitte
-
Du mußt direinfach über den Unterschied von bits und Byte klarwerden, das eineist kleiner alsdas andre.
Ich kenne mich schon gut genug mit den Zusammenhängen aus...
Aber im Text war nicht die Rede von Bytes. Sonst hätte ich gar nicht gefragt
Andere Ideen?
-
-
Hallo Alex.
Ohne mich mit dem MD5-Algorithmus auszukennen, werfe ich jetzt einfach mal mit Vermutungen um mich.
a single "1" bit is appended to the message, and then "0" bits are appended so that the length in bits of the padded message becomes congruent to 448, modulo 512
Ok, alles klar... Dachte ich. Denn in allen Umsetzungen des Algorithmus, die ich mir bisher angeschaut habe, wird das erste Bit des Anhängsels nicht auf "1", sondern auf "0x80" gesetzt.In diesen Beispielen dürfte das erste _Byte_ auf 0x80 gesetzt werden, nicht jedoch das erste _Bit_.
Das entspricht doch einem Dezimalwert von "128" - was weder "1" ist noch in ein einzelnes Bit "paßt", das nur die Zustände "1" oder "0" annehmen kann.
0x80 entspricht tatsächlich einem Dezimalwert von 128, nur ist der an dieser Stelle uninteressant.
Ist mir da irgendwas wesentliches entgangen? Wer kann etwas Licht ins Dunkel bringen?
Wenn in den Beispielen, von denen du gesprochen hast 0x80 angehängt wird, dürfte das nicht daran liegen, dass 0x80 dezimal 128 ist, sondern eher daran, dass der Wert von 0x80 im Binärsystem 10000000 ist.
0x80 benötigt exakt ein Byte an Speicherplatz und in einem Byte stecken ja bekanntlich 8 Bit.
Der Binärwert von 0x80 hat insgesamt 8 Stellen, das sind die 8 Bit (10000000) in dem einen Byte (0x80).
Das Anhängen von einem Byte mit dem Wert 0x80 ist also equivalent zum Anhängen von 8 Bits mit den Werten 1, 0, 0, 0, 0, 0, 0 und 0.
Und bei diesen 8 Bits haben wir dann ein single "1" bit, welches an die Nachricht angehängt wird, sowie die "0" bits, die dafür sorgen, dass das Ganze wieder zu 448%512 kongruent ist.Gruß
Norbert-
Das Anhängen von einem Byte mit dem Wert 0x80 ist also equivalent zum Anhängen von 8 Bits mit den Werten 1, 0, 0, 0, 0, 0, 0 und 0.
Und bei diesen 8 Bits haben wir dann ein single "1" bit, welches an die Nachricht angehängt wird, sowie die "0" bits, die dafür sorgen, dass das Ganze wieder zu 448%512 kongruent ist.Genau diesen Gedanken hatte ich auch schon einmal. Allerdings brachte mich u.a. folgende Bemerkung in der Beschreibung wieder davon ab:
In all, at least one bit and at most 512 bits are appended.
Außerdem will mir nicht so recht einleuchten, warum *überall* explizit vom Anhängen eines "1" Bits gesprochen wird...
Soweit ich da sehe, wäre es ja eigentlich auch kein Problem, ganz einfach 0x1 zu benutzen.Trotzdem danke.
-
Hallo nochmal.
Genau diesen Gedanken hatte ich auch schon einmal. Allerdings brachte mich u.a. folgende Bemerkung in der Beschreibung wieder davon ab:
In all, at least one bit and at most 512 bits are appended.
Na ja, wie schon gesagt, mit dem MD5-Algorithmus kenne ich mich nicht aus, was genau aus welchem Grund wo dran gehängt werden muss, weiß ich also nicht.
Außerdem will mir nicht so recht einleuchten, warum *überall* explizit vom Anhängen eines "1" Bits gesprochen wird...
Soweit ich da sehe, wäre es ja eigentlich auch kein Problem, ganz einfach 0x1 zu benutzen.0x1 hätte aber einen Binärwert von 00000001 und somit ist kein "1"-Bit mehr am Anfang. Es müssen demnach Werte größer-gleich 0x80 benutzt werden, da bei ihnen jeweils ein "1"-Bit am Anfang steht. Da aber 0x80 der einzige Wert ist, bei dem dem ersten Bit nur "0"-Bits und keine weiteren "1"-Bits folgen, wird vermutlich immer dieser Wert benutzt.
Gruß
Norbert-
Na ja, wie schon gesagt, mit dem MD5-Algorithmus kenne ich mich nicht aus, was genau aus welchem Grund wo dran gehängt werden muss, weiß ich also nicht.
Da die Länge der zu verschlüsselnden Nachricht nicht festgelegt ist (wäre ja auch etwas unpraktisch), wird sie "aufgefüllt" bis eine Länge von von 448 mod 512 hat. Das ist dann für die weitere Verarbeitung wichtig.
Das "1" Bit am Anfang soll eigentlich nur dazu beitragen, daß der später ermittelte Hash sich schon bei kleinen Änderungen in der Ausgangsnachricht stark verändert.
Soweit ich da sehe, wäre es ja eigentlich auch kein Problem, ganz einfach 0x1 zu benutzen.
0x1 hätte aber einen Binärwert von 00000001 und somit ist kein "1"-Bit mehr am Anfang.
Uh, war schon spät. %-)
Ich meinte natürlich eine simple "1" im ersten Bit (und nicht 0x1). Und da sich Bits auch einzeln manipulieren lassen, dürfte es eigentlich kein Problem sein, daß auch ohne ein komplettes 0x80 Byte zu bewerkstelligen...-
Hallo Alex,
ich habe gerade diesen Thread angelesen und versucht, die Zusammenhänge zu verstehen, was mir mangels Kenntnis des MD5-Algorithmus (wie Norbert) nur zum Teil gelungen ist.
Ich meinte natürlich eine simple "1" im ersten Bit (und nicht 0x1). Und da sich Bits auch einzeln manipulieren lassen, dürfte es eigentlich kein Problem sein, daß auch ohne ein komplettes 0x80 Byte zu bewerkstelligen...
Hmm, ja und nein. Bei den meisten heutigen CPUs (und auch in vielen Programmiersprachen) ist das _BYTE_ die kleinste Informationsmenge, die sich direkt ansprechen und verarbeiten lässt. Um einzelne Bits zu manipulieren, _muss_ man also mit solchen Tricks arbeiten. Da kommen dann halt Byte-Werte vor, die man eigentlich nicht als solche interpretieren sollte.
So, jetzt habe ich die Verwirrung wahrscheinlich vollendet. ;))
Schönes WE noch,
Martin
-
-
-
-
-
Hallo Alex,
ich habe zufällig vor nicht allzu langer Zeit als Übung einen C++-Wrapper für den MD5-Algorithmus geschrieben und kenne daher das RFC noch.
In der Spezifikation wird der Algorithmus so allgemein beschrieben, dass keine Annahmen über die ursprüngliche Nachricht gemacht werden. Die Beschreibung geht daher nicht einmal davon aus, dass die Länge der Ursprungsnachricht in Bits durch 8 teilbar ist, d.h. die Nachricht restlos in Bytes aufgeteilt werden kann. Daher muss es beispielsweise auch möglich sein, eine standardkonforme MD5-Checksumme aus einer 123 Bits langen Nachricht zu bilden. Eine solche Nachricht ließe sich aber nicht in Bytes aufteilen, weil das letzte Byte dann "nicht voll" wird (es "fehlen" dann noch 5 Bits). Wenn die Spezifikation also solchen Unfug erlauben will, darf sie nicht von dem Anhängen von Bytes reden, weil gar nicht sicher gestellt ist, dass sich die Nachricht überhaupt restlos in Bytes aufteilen lässt. Die Spezifikation beschreibt daher das Anhängen von Bits: Zuerst ein 1er-Bit und dann so viele 0er-Bits, dass das Ergebnis in ein vorgegebenes Raster passt.
Die C-Implementierung des Algorithmus, die noch Teil des RFC ist, kann allerdings auf Grund der Einschränkungen von C nicht so allgemein gehalten werden. Die kleinste Einheit eines standardkonformen C-Compilers ist immer mindestens 8 Bit groß, da kleinere Einheiten auf den meisten Rechnerarchitekturen ohnehin keinen Sinn machen. In der Implementierung wird also eine stillschweigende Annahme über die Ursprungsnachricht gemacht: Es wird angenommen, dass die Bitlänge der Nachricht ein Vielfaches von 8 ist, die Nachricht also restlos in Bytes aufgeteilt werden kann. Und wenn man das einmal als gegeben hinnimmt, kann man statt Bits anzuhängen auch gleich Bytes anhängen. Allerdings werden die Bytes so angehängt, dass man keinen Unterschied zwischen dieser normativen Implementierung und einer Implementierung, die auf irgend eine Weise mit Bits rechnet, feststellen kann. Allerdings kann diese normative Implementierung nur Checksummen aus Nachrichten bilden, deren Länge in Bits durch 8 teilbar ist.
Das "at least one bit" bezieht sich also nur auf Nachrichten, die gerade ein Bit kürzer sind, als dass sie genau in das vorgeschriebene Raster passen würden. Solche Nachrichten hätten aber sozusagen "nur 7 Bits im letzten Byte" und werden daher von der C-Implementierung nicht berücksichtigt.
Ich hoffe, ich habe dich jetzt nicht noch mehr verwirrt,
Robert-
In der Implementierung wird also eine stillschweigende Annahme über die Ursprungsnachricht gemacht: Es wird angenommen, dass die Bitlänge der Nachricht ein Vielfaches von 8 ist, die Nachricht also restlos in Bytes aufgeteilt werden kann.
Hm... Ok, das macht Sinn. Falls wir uns hier im Standard-ASCII bewegen, ist ja zwangsweise jede Zeichenkette ein ganzzahliges Vielfaches von 8 Bit.
Ich hoffe, ich habe dich jetzt nicht noch mehr verwirrt
Nein, im Gegenteil. Du hast mein Problem geklärt. :)
Vielen Dank.
-