Wenn du den ersten Teil erfolgreich verarbeitet hast, bist du bestens gewappnet, um in diesem Teil zu erfahren, wie die einzelnen Komponenten bzw. Funktionen nun zusammenspielen.

Vorbemerkung

Bevor es los geht möchte ich noch einmal die Zusammenhänge verdeutlichen: Wir werden gleich eine Nachricht (Message) erzeugen, deren Länge einem Vielfachen von 512 Bit entspricht; im Beispiel genau 512 Bit. Die Nachricht wird in Message-Blocks zerlegt, die exakt 512 Bit lang sind. Jeder Message-Block wird wiederum zu einer Message-Schedule zerlegt, mit 16 Wörtern (Words) zu je 32 Bit Länge. Die Länge der Wörter muss und wird immer 32 Bit sein! Der Message-Schedule wird dann aber erweitert, um 64 Wörter zu enthalten. Seine Länge dann: 2.048 Bit. Und grafisch:

Wichtige Zusammenhänge

Dekompressions

Wir wollen also aus einer Nachricht eine SHA-256-konforme Prüfsumme, den Hash, berechnen. Dazu muss die Nachricht, also der String, zunächst vorbereitet werden. Unsere Nachricht ist, klischeegerecht:

message = ‘hello_world’

Zunächst müssen wir für jeden Buchstabend die Position in der Zeichentabelle herausbekommen, sprich die Buchstaben (bzw genauer jedes Zeichen) in ihre numerische Repräsentation umwandeln:

dec_message = []
for char in message:
dec_message.append(ord(char))

Das Ergegnis ist eine Liste mit Integern:

[104, 101, 108, 108, 111, 95, 119, 111, 114, 108, 100]

Und da wir im ersten Teil so viel Spaß am Umgang mit binären Werten hatten, wandeln wir die Liste in binäre Werte um, die wir schlicht miteinander verknüpfen:

bin_message = ’’
for decimal in dec_message:
bin_message += ‘0’ + bin(decimal)[2:

Das Ergebnis:

0110100001100101011011000110110001101111010111110111011101101111011100100110110001100100

Hier gibt es allerdings eine Stolperfalle, und es widerstrebt mir das so stehen zu lassen, für die ich noch keine Erklärung gefunden habe: Bei der Umwandlung in die binäre Entsprechung stellen wir jedem binären Wert eine 0 voran. Aus 104 wird also nicht 1101000 sondern 01101000, uswf.

Außerdem hängen wir an dieses Datum eine 1 heran, sozusagen als Trennzeichen für das, was jetzt gleich kommt.

Als nächstes berechnen wir die Länge dieser binären Zahl:

len_bin_message = len(bin_message)

Die Längenangabe darf bzw muss exakt 64 Bit belegen. Wir wandeln sie also auch in eine binäre Zahl um hängen vorne ein paar Nullen ran um genau 64 Stellen zu erhalten:

rest_to_64 = 64 - len(bin(len_bin_message)[2:])

bin_message_len = ‘0’ * rest_to_64 + bin(len_bin_message)[2:]

Nun müssen wir diese drei binären Informationen, Nachricht, trennende Eins und Längenangabe nicht nur verbinden, sondern auch mit so vielen Nullen auffüllen, damit die Gesamtlänge ein vielfaches von 512 ist.

payload = bin_message + ‘1’ + bin_message_len

len_payload = len(payload)

pad_string = int(512 - (len_payload % 512))

full_message = bin_message + ‘1’ + (‘0’ * pad_string) + bin_message_len

In unserem Beispiel belegen die drei Informationen 153 Bit. Wir müssen also 359 Nullen dazupacken. Genau genommen kommen die zwischen Nachricht und Längenangabe. Das Ergebnis ist immer n* 512 Bits lang:

Aufbau einer vorkodierten Nachricht

Zu guter Letzt nehmen wir diese sehr, sehr, sehr, sehr….sehr, sehr große Zahl (sie ist sehr groß, du solltest sie auch nicht als Zahl sehen, sondern als Bitfolge!) und teilen sie in sogenannte Message Blocks mit einer Länge von jeweils 512 Bits auf:

message_block_length = 512
message_blocks = [full_message[i:i+message_block_length] for i in range(0, len(full_message), message_block_length)]

Schnapp dir einen Kaffee, geh noch mal frische Luft schnappen, schüttel den Stuhl aus. Jetzt geht es los.

8 Bits sind keine Bitfolge

Die Schleife!

Da es einfacher ist, den Vorgang ohne Schleife zu erklären, hier nur eine Schleife. Die programmatische Schleife findest du trotzdem auf Github.

Es folgt: Eine Schleife

Da unsere Nachricht genau 512 Bit groß ist und wir auch ohne Schleife arbeiten, können wir direkt in die Vollen gehen: Die mühsam zusammengeklebte Nachricht wird nun in den sog. Message Schedule zerlegt: Sprich in 16 Wörter mit jeweils 32 Bit Länge.

Im ersten Durchlauf nehmen wir vier Wörter und führen folgende Modifikationen aus:

• σ1 wird auf Wort 1 an Position 14 angewendet,
• Wort 2 von Position 9 bleibt unverändert,
• σ0 wird auf Wort 3 an Position 1 angewendet und
• Wort 4 an Position 0 bleibt wieder unberührt

Die Werte werden zunächst addiert und jetzt gibt es wieder einen wichtigen Punkt zu beachten: Wir müssen strikt dafür sorgen, dass die Wörter nicht länger als 32 Bit sind. Denn nur so können wir sicherstellen, dass der finale Hash immer die gleiche länge hat. Und spätestens jetzt, bei der Addition großer Werte, können wir die 32 Bit recht schnell überschreiten. Das ist auch aus technischer Sicht eine Hürde. Deswegen gilt: Hier und bei allen Additionen müssen wir abschließend Modulo 2³² anwenden. Und jetzt kommt der dritte hoffentlich positive Knick in der Lernkurve: Auch für Modulo hält das binäre Universum eine schöne Vereinfachung parat: Das logische Und mit 2³²–1 (bzw 4.294.967.295, das ist eine sehr große Zahl, nicht so groß wie die im ersten Teil, sondern genau einen Zähler kleiner) führt zum gleichen Ergebnis.

Berechnung des ersten Schritts

Damit wäre der Message-Schedule vorbereitet und enthält nun 64 wunderschöne Wörter zu je 32 Bit. Wir haben die Informationen aus dem Message Block also zunächst aufgeplustert und von 512 Bit auf 2.048 Bit erweitert- sie sind aber immer noch lesbar:

Der erweiterte Message Schedule

Aber damit ist jetzt Schluss, wir kommen zum nächsten und wichtigsten Schritt:

Die Kompression

Der erweiterte Message-Schedule wird in diesem Schritt nicht direkt modifiziert, die Wörter werden vielmehr als Grundlage für die Modifikation der anfangs erzeugten Kompressions-Konstanten verwendet.

In 64 Schleifen-Durchläufen gehen wir durch den Message-Schedule. Aus jedem Wort des Schedules (also unserer ursprünglichen Nachricht) wird zusammen mit den 64 Ergebnis-Konstanten und den 8 Kompressions-Konstanten ein neues Wort berechnet. Das neue Wort wird dann den Kompressions-Konstanten vorangestellt, gleichzeitig wird der letzte Eintrag gelöscht. So enthält die Liste immer genau 8 Einträge.

new_compression_constants = compression_constants.copy()

for i, word in enumerate(message_schedule):

term1 = (int(upper\_sigma1(new\_compression\_constants\[4\]), 2) + \\  
            int(choose(new\_compression\_constants\[4\], new\_compression\_constants\[5\], new\_compression\_constants\[6\]), 2) + \\  
            int(new\_compression\_constants\[7\], 2) + \\  
            int(result\_constants\[i\], 2) + \\  
            int(word, 2)) \\  
            & int('11111111111111111111111111111111', 2)

term2 = (int(upper\_sigma0(new\_compression\_constants\[0\]), 2) + \\  
            int(majority(new\_compression\_constants\[0\], new\_compression\_constants\[1\], new\_compression\_constants\[2\]), 2)) & int('11111111111111111111111111111111', 2)

new\_compression\_constants.insert(0, 1)  
new\_compression\_constants.pop()

new\_compression\_constants\[0\] = bin(  
            (term1 + term2) & int('11111111111111111111111111111111', 2)  
            )\[2:\].zfill(32)

new\_compression\_constants\[4\] = bin(  
            (int(new\_compression\_constants\[4\], 2) + term1) & int('11111111111111111111111111111111', 2)  
            )\[2:\].zfill(32)

Zunächst ein paar Berechnungen:

• Term 1 berechnet sich aus den Kompressions-Konstanten, einer der Ergebnis-Konstanten und dem jeweiligen Wort. Wir verwenden hier auf Bitebene und Σ1 (upper_sigma1) sowie choose.
• Term 2 ist eine Summe zweier anderer Kompressions-Konstanten, die mithilfe von Σ0 (upper_sigma0) sowie majority modifiziert werden.

Und jetzt achte mal drauf, dass die ursprüngliche Nachricht Teil des 1. Terms ist — in der Abbildung rot markiert:

Im ersten Schritt erfolgt die Berechnung zweier Terme

Die beiden Terme werden nun wiederum addiert (und wie immer mit Modulo 2³² auf 32 Bit-Kurs gebracht) und an den Anfang der Kompressions-Konstanten gestellt. Der erste Term wird außerdem mit der 4. Position dieser nun 9 Wörter langen List summiert:

Im zweiten Schritt wird die Listse der Kompression-Konstanten aktualisiert

Als nächstes wird der letzte Eintrag der Liste gelöscht, sie umfasst nun 8 komplett neue Kompressions-Konstanten (wenn du aufmerksam aufgepasst hast, wird dir nicht entgangen sein, dass sie gar nicht mal so konstant sind).

Ein Teil der ursprünglichen Nachricht befindet sich nun an als Summand von Term 1 and den Positionen 0 und 4 und. Diese werden in den nächsten Durchläufen Teil der gleichen Berechnungen und immer weiter nach unten rutschen. So verteilt sich die ursprüngliche, bisher noch halbwegs lesbare Nachricht, über die gesamte Liste.

Diese Liste ist also die Grundlage für den zweiten Durchlauf, der sie erneut “durchrotiert”, um wiederum eine komplett neue Liste für den dritten Durchlauf zu erzeugen. Und so weiter, bis alle 64 Wörter des Message-Schedules verarbeitet wurden. Das Ergebnis sollte in etwa so aussehen:

11100010000000010111101011011001
01000110110100101000001000010100
11100011111110010111100001001011
01110001100001100000010000011110
01001000000111100100000000011000
00011111110001101011001000110101
11101001110010001101110111110100
00001001011011110000111011111011

Oder in Hexadezimal:

0xe2017ad9 0x46d28214 0xe3f9784b 0x7186041e 0x481e4018 0x1fc6b235 0xe9c8ddf4 0x96f0efb

Abschließend gehen wird durch genau diese Liste der 8. Kompressions-Konstanten und addieren jede Positionen mit dem entsprechenden Wort der Ausgangs-Liste:

result = []

for i in range(0, 8):

result.append(  
    bin(int(compression\_constants\[i\], 2) +   
    int(new\_compression\_constants\[i\], 2)  &      
    int('11111111111111111111111111111111', 2))\[2:\].zfill(32))

Und im Klartext:

Letzter Schritt: Addieren der Listen

Die neue Liste ist nun die Ausgangs-Liste für den nächsten Message-Schedule. Da wir die Schleife hier aber nicht implementieren, war es das fürs erste. Im Folgenden noch mal eine beispielhafte Zusammenfassung der Schritte:

Schematische Darstellung des SHA-256 Algorithmus’

Haschee. Gesundheit. Was?

Wir haben es geschafft. Du hast es geschafft. Herzlichen Glückwunsch.

Quelle: memecreator.org

Nun können wir den Hash entweder als Hex-Wert ausgeben oder wieder in binärer Schreibweise darstellen, je nach Anwendungszweck.

for word in result:

print(hex(int(word, 2))\[2:\].zfill(8) + '', end = '')

Das Ergebnis kann sich in jedem Fall sehen lassen.

35072c1ae546350e0bfa7ab11d49dc6f129e72ccd57ec7eb671225bbd197c8f1

Oder

110101000001110010110000011010111001010100011000110101000011101011111110100111101010110001111010100100111011100011011111001010011110011100101100110011010101011111101100011111101011110011100010010001001011011101111010001100101111100100011110001

Epilog

Eine komplette Implementierung, inklusive einer Schleife, um auch große Nachrichten zu verarbeiten, findest du in diesem Gist.

Freilich ist Python nicht dazu geeignet, den SHA-256 Prozess zu optimieren, wohl aber um den Prozess zu verstehen und den Umgang mit elementaren binären Rechenoperation zu lernen.

Willst du den Prozess noch etwas interaktiver nachvollziehen, möchte ich dir dieses Video empfehlen. Dort wird der Algorithmus in Ruby nachgebaut und die einzelnen Rechenschritte auch etwas genauer erklärt.

Und warum ist SHA-256 für das Mining von Kryptowährungen jetzt so wichtig? Kurz: Der Hash validiert die Gültigkeit des Kassenbuches. Beim Mining geht es darum, aus einer gegebenen Nachricht und einem frei wählbaren Zusatz exakt einen gegebenen Ziel-Hash zu berechnen. Der Algorithmus muss also wahnsinng oft durchlaufen werden. Da das sehr aufwendig ist, kostet das Zeit und wird entsprechend belohnt.