Wie funktioniert der SHA256 Algorithmus…im Detail? (Teil 1/2)

SHA-256 (Secure Hash Algorithm) ist der Name einer “kryptologischen Hashfunktion”. SHA-256 ist Teil einer ganzen Gruppe von Algorithmen, mit dem gleichen Ziel: Die Erzeugung eines Hashes, der resistent gegen Kollisionen ist, dessen Berechnung nur in eine Richtung funktioniert und eine feste Länge hat. Im folgenden Artikel beschreibe ich die einzelnen Schritte die der Algorithmus vornimmt, um einen Hash zu erzeugen.

Im ersten Teil kümmern wir uns um die Vorbereitungen, im zweiten Teil geht es an den eigentlichen Algorithmus. Der Sourcecode liegt auf Github.

Was wirst du lernen?

Neben dem Erzeugen eines SHA-256 wirst du hier vor allem den Umgang mit binären Zahlen und binäre Rechenoperationen wie XOR, AND usw kennenleren. Ich gehe allerdings davon aus, dass ein Grundverständnis für binäre Zahlen vorhanden ist, der Fokus liegt auf dem Algorithmus. 10 sollte in deinem Kopf also entweder für die zehn oder eine zwei stehen. (Oder auch zwölf, wenn du das Duodezimalsystem magst.)

Vorwort

Bricht man das auf eine maximal laienhafte Beschreibung herunter, passiert bei einer krytpologischen Hash-Funktion das folgende: Ein Ausgangs-Text beliebiger Länge wird so verarbeitet, dass daraus einen Ergebnis-Text (der Hash) mit der immer gleichen Länge entsteht. Es ist nahezu unmöglich, aus dem Hash den Ausgangs-Text zu berechnen. Außerdem kann man fast sicher davon ausgehen, dass jeder Ausgangs-Text einen anderen Hash erzeugt. Ändere ich nur ein Zeichen, wirkt sich das drastisch auf den Ausgangs-Text aus. Ein derartiger Algorithmus ist daher zB prädestiniert, Texte, sprich Nachrichten, zu verfizieren. Man spricht deswegen auch von einer Prüfsumme.

Und das ist die Grundlage einer Technologie, die in jüngster Vergangenheit immer mehr von sich Reden macht: Die Blockchain, Basis für Kryptowährungen wie zB den Bitcoin. Bei der Blockchain sind, und auch das nur laienhaft heruntergebrochen, die Einträge des “Kassenbuches” sicher vor Manipulation, weil eben die Änderung eines historischen Wertes (zB Buchungsvorganges) unweigerlich eine drastische Änderung der daraus erzeugten Prüfsummen nach sich ziehen würde. Um den Blockchain-Apologeten gleich den Wind aus den Segeln zu nehmen zitiere ich mal Fefe, sinngemäß: Es geht auch einfacher. Ich gebrauche Bitcoin hier auch nur als Buzzword, aus Marketing-Gründen. :]

Um dich nun aber auch zum Weiterlesen zu motivieren, ein wichtiger Hinweis:

Der Algorithmus wird dazu verwendet, die nächsten Einträge der Blockchain zu berechnen. Genau genommen wird hier ein bestimmter Hash vorgegeben, der errechnet werden soll (das berüchtigte Mining). Die Belohnung für die korrekte Berechnung sind Bitcoins. Das Problem: Diese Berechnung ist sehr, sehr aufwendig, denn wie schon oben geschrieben: Sie funktioniert nur in eine Richtung. Die Miner müssen also unsagbar viele Berechnungen durchführen, um einen Ziel-Wert zu errechnen. Und der Miner, der die Berechnung am schnellsten ausführt, wird dafür auch belohnt. Gelingt es dir also, wider erwarten, den Algorithmus zu optimieren, kannst du im Mining-Business ganz groß rauskommen. Das klingt doch nach einer Herausforderung, oder? ;)

Quelle: https://peakd.com/deutsch/@marcus0alameda/dagobert-gold-bitcoin-perfektion

Disclaimer: Ich habe den ganzen Algorithmus in Python nachgebaut. Python ist aus Performance-Sicht sicher nicht die beste Option, um SHA-256 zu berechnen und der Umgang mit binären oder hexadezimalen Werten ist etwas unbequem. Python eignet sich dank Jupyter aber am ehesten dazu, einen komplexen Algorithmus Schritt-für-Schritt zu beschreiben.

Einführung

Bevor wir uns an die Schleifen machen, müssen wir uns um ein paar Funktionen kümmern, die wir später dazu nutzen, um binäre Zahlen ein wenig durchzumischen.

Hinweis 1: Ich verzichte im folgenden auf die Präfixe der Zahlensystem, wie zB 0b für binär, um den Text übersichtlich zu halten. Ich gehe davon aus, dass folgendes bekannt ist: 0 => Falsch und 1 => Wahr

Hinweis 2: Im Kontext von SHA-256 entspricht ein Wort (bzw word) genau 32 Bit. In der Regel entspricht 1 Word = 2 Byte = 16 Bit.

Das explizite Oder (XOR)

Das explizite Oder (Entweder-Oder) ist ein elementarer logischer, bitweise Operator. Der Ausgang der Operation ist nur dann wahr, wenn exakt ein Zustand wahr ist (im Vergleich dazu ist das Ergebnis bei dem “einfachen“ OR übrigens dann wahr, wenn mindestens ein Operand wahr ist oder beide).

Es werden also zwei Werte folgendermaßen verarbeitet:

XOR: nur wenn genau ein Wert wahr (1) ist, ist die entsprechende Stelle im Ergebnis wahr (1)

Die Implementierung in Python erfolgt mit dem Zirkumflex:

# 110 ^ 100
# 010

Das logische Und (AND)

Der AND-Operator ist ebenfalls recht geläufig und vergleichsweise simpel. Analog zu XOR ist das Ergebnis wahr, wenn exakt beide (bzw. alle) Operanden wahr sind.

AND: Nur wenn beide Werte einer Stelle wahr sind, ist die Stelle im Ergebnis wahr

Die Implementierung in Python erfolgt mit dem kaufmännischen Und:

# 110 & 100
# 100

Die Negierung (Nope?)

Jetzt wirds seltsam: Auch dafür gibt es einen Operator: Der bitweise Operator Negierung dreht Werte um. Aus 0 wird 1, aus 1 wird 0.

Die Negierung kehrt Werte bitweise um. Nicht mehr aber auch nich weniger.

Die Implementierung in Python erfolgt mit der Tilde — meinem Lieblingszeichen!

# ~110
# 001

Die Shift-Operation

Die Shift-Funktion ist eine elementare binäre Rechenoperation, bei der die einzelnen Stellen eines binären Werts nach links oder rechts geschoben werden. Die freien Stellen auf der jeweils anderen Seite werden mit 0 aufgefüllt.

Shift nach links um eine Stelle, aus 6 wird 12

Und jetzt gibt es hoffentlich einen positiven Knick in der Lernkurve: Wenn du genau hinschaust, fällt dir etwas auf und lass mich dir versichern, es handelt sich nicht um einen Zufall: 12 ist das Produkt aus 6 und 2. Das deutet auf ein interessanten Nebeneffekt: Ein Shift kommt einer Multiplikation bzw. Division mit 2 gleich. Ein Shift um mehrere Stellen entspricht demnach einer Multiplikation mit einer Potenz zur Basis 2 besteht. Klingt kompliziert, deswegen ein Beispiel:

Anstatt 139 * 2 ^17 kannst du die binäre Darstellung von 139, also 10001011, um 17 Stellen nach links shiften. Das Ergebnis: 1000101100000000000000000. Zähl gerne nach, rechts der 1 eins gibt es jetzt 17 Nullen.

In Python ist der binäre Shift mit dem Doppelpfeil implementiert:

# 110 » 1
# 011

# 110 « 2
# 000

Die Rotate-Funktion

Rotate bedeutet, dass ein die Werte einer (binären) Zahl in eine Richtung verschoben werden. Und das erklärt man am besten an einem Beispiel. Die folgende Zahlenreihe soll um einen Zähler nach links rotiert werden. Die Zahl auf der linken Seite fällt also heraus und wir rechts wieder angehangen. Die anderen Zahlen rücken eine Position nach links.

Rotate eines binären Wertes um eine Stelle nach links, aus 6wird 5

Das funktioniert in beide Richtungen und mit beliebig vielen Stellen. Die entsprechende Funktion (Kudos an so) sieht so aus:

def rotate(value, rotations, width = 32):
if int(rotations) != abs(int(rotations)):
rotations = width + int(rotations)
return (int(value) « (width - (rotations%width)) | (int(value) » (rotations % width))) & ((1 « width) - 1)

Die Sigma-Funktionen

Insgesamt werden vier sogenannte Sigma-Funktionen verwendet. σ0 und σ1 (das kleine Sigma) bzw. Σ0 und Σ1 (das große Sigma, vielen bekannt als das Summen-Zeichen). Alle funktionen werden mit einem binären Wert aufgerufen und geben diesen binären Wert in veränderter Form zurück.

σ0 (sigma0) läuft folgendermaßen ab:

der Ausgangs-Wert wird um 7 Stellen nach rechts rotiert
der Ausgangs-Wert wird um 18 Stellen nach rechts rotiert
der Ausgangs-Wert wird um 3 Stellen nach rechts geshifted

Daraus entstehen drei unterschiedliche Werte, die miteinander XOR-Verknüpft werden. Die Funktion dazu in Python:

def sigma0(word):
part1 = bin(rotate(int(word, 2), 7, 32))
part2 = bin(rotate(int(word, 2), 18, 32))
part3 = bin(int(word, 2) » 3)
return bin(int(part1, 2) ^ int(part2, 2) ^ int(part3, 2))[2:].zfill(32)

Wichtiger Hinweis: Ich arbeite mit bin() und in(s, 2), um die Ausgaben und Eingaben leserlich und vor allem nachvollziehbar zu machen. Außerdem sorge ich mit [2:] dafür, dass die binäre Darstellung ohne 0b auskommt. Das kommt dem Lernzweck zugute, da die binären Operationen an dezimalen Werten schwerer nachvollziehbar sind. Mit zfill(32) (zero fill) wird der binäre Wert nach links um so viele Nullen erweitert, um immer 32 Stellen zu umfassen. Teilweise erleichtert das die Übersicht, andererseits erfüllt das später auch eine Längen-Vorgabe. Die obere Funktion kann also auch folgendermaßen vereinfacht werden:

def sigma0(word):
part1 = rotate(word, 7, 32)
part2 = rotate(word, 18, 32)
part3 = word » 3
return part1 ^ part2 ^ part3

Bei σ1 (sigma1) sieht es ganz ähnlich aus:

der Ausgangs-Wert wird um 17 Stellen nach rechts rotiert
der Ausgangs-Wert wird um 19 Stellen nach rechts rotiert
der Ausgangs-Wert wird um 10 Stellen nach rechts geshifted

Daraus entstehen drei unterschiedliche Werte, die miteinander XOR-Verknüpft werden. Die Funktion dazu in Python:

Nun zu Σ0 (Sigma0). Auch hier keine großen Überaschungen, hier nun ohne Shift:

der Ausgangs-Wert wird um 2 Stellen nach rechts rotiert
der Ausgangs-Wert wird um 13 Stellen nach rechts rotiert
der Ausgangs-Wert wird um 22 Stellen nach rechts rotiert

Auch hier werden die jeweiligen Ergebnisse final XOR-Verknüpftg. In Python also:

def upper_sigma0(word):
part1 = bin(rotate(int(word, 2), 2, 32))
part2 = bin(rotate(int(word, 2), 13, 32))
part3 = bin(rotate(int(word, 2), 22, 32))
return bin(int(part1, 2) ^ int(part2, 2) ^ int(part3, 2))[2:].zfill(32)

Kommen wir zum letzten Teilnehmer unserer illustren griechischen Runde: Σ1 (Sigma1):

der Ausgangs-Wert wird um 6 Stellen nach rechts rotiert
der Ausgangs-Wert wird um 11Stellen nach rechts rotiert
der Ausgangs-Wert wird um 25 Stellen nach rechts rotiert

Und am Ende wieder die XOR-Verknüpfung. Python:

def upper_sigma1(word):
part1 = bin(rotate(int(word, 2), 6, 32))
part2 = bin(rotate(int(word, 2), 11, 32))
part3 = bin(rotate(int(word, 2), 25, 32))
return bin(int(part1, 2) ^ int(part2, 2) ^ int(part3, 2))[2:].zfill(32)

Wahl und Mehrheit

Bleiben wir noch etwas bei den Griechen und wechseln in die Politik: Die Wahl und die Mehrheit, englisch: choose und majority.

Choose ist eine etwas komplexere Funktion, die drei binäre Werte verarbeitet und zwar wieder bitweise. Die Funktion geht durch die jeweiligen Stellen (x) des ersten Eingangswerts und prüft:

Wenn x = 1 dann nimm y
Wenn x = 0 dann nimm z

Y und z stehen für die jeweiligen Stellen des zweiten und dritten Eingangswertes. Wie kann man das programmatisch lösen? So:

def choose(word1, word2, word3):
bin_word1 = (int(word1, 2))
bin_word2 = (int(word2, 2))
bin_word3 = (int(word3, 2))
return bin((bin_word1 & bin_word2) ^ (~bin_word1 & bin_word3))[2:].zfill(32)

Zunächst werden also Wert 1 und Wert 2 logisch UND-verknüpft. Dann wird die Negierung von Wert 1 mit Wert 3 UND-verknüpft. Die beiden Zwischensummen werden abschließend durch XOR gejagt.

Majority prüft ganz einfach für jede Stelle der drei Eingangs-Werte, welcher Wert, 1 oder 0, häufiger vorkommt. Das sieht in Python so aus — hier erklär ich die logischen Operationen jetzt nicht noch mal, es werden einfach XOR und AND verknüpft:

def majority(word1, word2, word3):
bin_word1 = (int(word1, 2))
bin_word2 = (int(word2, 2))
bin_word3 = (int(word3, 2))
return bin((bin_word1 & bin_word2) ^ (bin_word1 & bin_word3) ^ (bin_word2 & bin_word3))[2:].zfill(32)

Primzahlen?

Um noch ein anderes beliebtes Feld der Arithmetik abzudecken, lasst uns noch kurz über Primzahlen reden. Primzahlen sind mystisch. Und damit genau richtig für unser irdisches Vorhaben, das Mining zu optimieren.

SHA-256 nutzt Primzahlen als Grundlage für den Algorithmus. Was nicht bedeutet, dass das Ergebnis durchschaubar wäre.

Wir fangen mal mit den ersten 64 Primzahlen an und bauen daraus einen Satz Konstanten. Selbstverständlich in Bitform.

first_64_prime_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311]

Diese werden nun aber auch noch ordentlich durch die Mangel genommen. Warum das erforderlich ist, kann ich nicht nachvollziehen. Aus meiner Sicht ist es ziemlich egal, welche Konstanten man verwendet werden, da sie immer gleich sind (deswegen ja konstant, diesmal übrigens aus dem lateinischen). Dahinter steckt also kein großes Geheimins.

Aus den 64 Primzahlen wird zuerst jeweils die dritte Wurzel gezogen. Dann wird der natürliche Teil entfernt (sprich alles vor dem Komma) und das Ergebnis mit 2³² (aka 4.294.967.296, was übrigens auch der Anzahl verfügbarer IPv4-Adressen entspricht — der 2. positive Knick in der heutigen Lernkurve?) multipliziert. Wie du oben ja gelernt und hoffentlich noch nicht vergessen hast, ist die Mulitplikation mit 2^32 ja eigentlich gar nicht so aufwendig im Bituniversum.

Das Ergebnis wird jedenfalls auf eine natürlich Zahl abgerundet — sprich alle Nachkommastellen entfernt. Wiederholt man das für die restlichen 63 Primzahlen, erhält man eine wohlgeformte Liste mit 64 Einträgen, die in etwa so aussehen, am Beispiel der notorischen Primzahl 2:

01000010100010100010111110011000

Oder als Hex-Wert:

0x428a2f98

Und im Dezimal-Zahlensystem:

1.116.352.408

Die Funktion dafür sieht folgendermaßen aus:

result_constants = []
for prime_number in first_64_prime_numbers:
cube_root = prime_number ** (1./3.)
frac_part = cube_root - floor(cube_root)
product = frac_part * (2**32)
floored_product = floor(product)
result_constants.append(bin(floored_product)[2:].zfill(32))

Das ganze nennen wir Ergebnis-Konstante, denn diese Liste ist der Anfang unsere finalen Ausgabe. Diese Liste heben wir gut auf und weil die Arbeit mit Primzahlen so befreiend ist, veranstalten wir für die ersten 8 Primzahlen einen ähnlichen Zirkus. Mit einem Unterschied: Als Grundlage dient diesmal die Quadrat-Wurzel:

compression_constants = []
for prime_number in first_8_prime_numbers:
square_root = prime_number ** (1./2.)
frac_part = square_root - floor(square_root)
product = frac_part * (2**32)
floored_product = floor(product)
compression_constants.append(bin(floored_product)[2:].zfill(32))

Die Namen haben übrigens eine Bedeutung, auf die ich später noch eingehe.

Epilog

Die Vorbereitungen sind damit abgeschlossen und wir können uns im zweiten Teil dem eigentlichen Algorithmus widmen.

Wie funktioniert der SHA256 Algorithmus…im Detail? (Teil&nbsp;1/2)