Programming lesson
SHA-3 und Hash-Funktionen: Eine praktische Einführung mit θ, ρ und π
Lerne die Grundlagen von Hash-Funktionen und SHA-3 kennen. Von Kollisionen und Einweg-Eigenschaften bis zur Implementierung der θ-, ρ- und π-Funktionen – mit praktischen Beispielen und Bezug zur aktuellen Kryptographie.
Einführung in Hash-Funktionen und SHA-3
Hash-Funktionen sind ein fundamentaler Baustein der modernen Kryptographie. Sie werden in vielen Bereichen eingesetzt, von der Passwortspeicherung bis zur Blockchain-Technologie. In diesem Tutorial lernst du die theoretischen Grundlagen und die praktische Implementierung von SHA-3-Funktionen kennen – genau wie in deiner Hausaufgabe. Wir nutzen aktuelle Beispiele aus der Welt der Kryptowährungen und digitalen Signaturen, um die Konzepte greifbar zu machen.
Was ist eine Hash-Funktion?
Eine Hash-Funktion h nimmt eine Eingabe beliebiger Länge und erzeugt eine Ausgabe fester Länge, den sogenannten Hashwert. In deiner Aufgabe hat h eine Eingabe von 1088 Bit und einen Hash von 256 Bit. Das bedeutet, dass viele verschiedene Eingaben auf denselben Hash abgebildet werden – es gibt Kollisionen. Die durchschnittliche Anzahl von Eingaben, die auf einen Hash abgebildet werden, ist n = 2^(1088) / 2^(256) = 2^(832). Das ist eine enorm große Zahl, aber dennoch ist die Wahrscheinlichkeit, durch Raten eine passende Eingabe zu finden, extrem gering: n / 2^(1088) = 2^(-256). Das ist die Grundlage der Einweg-Eigenschaft.
Einweg-Eigenschaft und schwache Kollisionsresistenz
Eine Hash-Funktion gilt als sicher, wenn sie sowohl einweg als auch schwach kollisionsresistent ist. Die Einweg-Eigenschaft besagt: Gegeben ein y, ist es praktisch unmöglich, ein x mit h(x)=y zu finden. Die schwache Kollisionsresistenz besagt: Gegeben ein x, ist es praktisch unmöglich, ein anderes x' mit h(x')=h(x) zu finden. In deiner Aufgabe sollst du zeigen: Wenn eine Funktion nicht einweg ist, dann ist sie auch nicht schwach kollisionsresistent. Stell dir vor, ein Angreifer kann zu einem gegebenen y ein x finden. Dann kann er auch zu einem gegebenen x ein anderes x' finden, indem er y = h(x) berechnet und dann die Einweg-Eigenschaft nutzt, um ein x' mit h(x')=y zu finden. Ist x' != x, hat er eine Kollision. Das zeigt die logische Verbindung.
Praktische Implementierung von SHA-3-Funktionen
SHA-3 basiert auf der Keccak-Permutation, die auf einem 3-dimensionalen Zustandsarray a[5][5][64] operiert. Dieses Array hat insgesamt 5*5*64 = 1600 Bits, genau wie die Eingabedatei sha3in.txt. In den nächsten Schritten implementierst du die Funktionen inputSHA3, outputSHA3 und die θ-Funktion.
Schritt 1: Einlesen der Daten mit inputSHA3
Die Funktion inputSHA3 wandelt einen 1D-Array v[0..1599] in ein 3D-Array a[0..4][0..4][0..63] um. Die Formel lautet: a[i][j][k] = v[64*(5*j + i) + k]. Das bedeutet, die Bits werden zeilenweise aus dem 1D-Array gelesen und in der Reihenfolge i, j, k abgelegt. Achte auf die Indizes: i und j laufen von 0 bis 4, k von 0 bis 63. Implementiere diese Funktion in deiner bevorzugten Sprache (z.B. Python, C++).
def inputSHA3(v):
a = [[[0]*64 for _ in range(5)] for _ in range(5)]
for i in range(5):
for j in range(5):
for k in range(64):
a[i][j][k] = v[64*(5*j + i) + k]
return aSchritt 2: Ausgabe mit outputSHA3
Die Umkehrfunktion outputSHA3 wandelt das 3D-Array zurück in ein 1D-Array. Die Formel ist: v[64*(5*j + i) + k] = a[i][j][k]. Teste deine Implementierung, indem du die Eingabedatei einliest und dann mit outputSHA3 wieder ausgibst – du solltest die ursprünglichen Bits erhalten.
def outputSHA3(a):
v = [0]*1600
for i in range(5):
for j in range(5):
for k in range(64):
v[64*(5*j + i) + k] = a[i][j][k]
return vSchritt 3: Die θ-Funktion
Die θ-Funktion ist der erste Schritt der Keccak-Runde. Sie berechnet Paritätsbits und XORiert sie mit dem Zustand. Die Implementierung erfolgt in zwei Schritten: Zuerst werden die Paritätsbits C[x] = XOR über alle y von a[x][y][*] berechnet, dann D[x] = C[x-1] XOR ROT(C[x+1], 1). Schließlich wird a[x][y][z] = a[x][y][z] XOR D[x][z]. Achte auf die Indizes modulo 5. Hier ist ein Beispiel in Python:
def theta(ain):
aout = [[[0]*64 for _ in range(5)] for _ in range(5)]
C = [[0]*64 for _ in range(5)]
D = [[0]*64 for _ in range(5)]
for x in range(5):
for z in range(64):
C[x][z] = ain[x][0][z] ^ ain[x][1][z] ^ ain[x][2][z] ^ ain[x][3][z] ^ ain[x][4][z]
for x in range(5):
for z in range(64):
D[x][z] = C[(x-1)%5][z] ^ C[(x+1)%5][(z-1)%64]
for x in range(5):
for y in range(5):
for z in range(64):
aout[x][y][z] = ain[x][y][z] ^ D[x][z]
return aoutTeste deine Funktion mit der bereitgestellten Eingabedatei. Die Ausgabe an der Position aout[4][3][9..18] sollte 0011011000 sein. Notiere dann die zehn Bits aout[3][1][15..24] für deine Hausaufgabe.
Weitere Funktionen: ρ und π (Vorschau)
In der nächsten Hausaufgabe wirst du die Funktionen ρ und π implementieren. ρ führt Rotationen auf den einzelnen Spuren durch, basierend auf der rhomatrix. π permutiert die Positionen der Spuren. Hier ein kurzer Vorgeschmack auf die ρ-Implementierung:
def rho(ain):
rhomatrix = [
[0,36,3,41,18],
[1,44,10,45,2],
[62,6,43,15,61],
[28,55,25,21,56],
[27,20,39,8,14]
]
aout = [[[0]*64 for _ in range(5)] for _ in range(5)]
for x in range(5):
for y in range(5):
for z in range(64):
aout[x][y][(z + rhomatrix[x][y]) % 64] = ain[x][y][z]
return aoutDie Ausgabe nach ρ an der Stelle aout[4][3][9..18] sollte 0110011001 sein. Für π wird eine Permutation der Indizes durchgeführt: aout[x][y] = ain[(x+3*y)%5][x]. Die Überprüfung ergibt aout[4][3][9..18] = 0110110001.
Fazit und Ausblick
Hash-Funktionen sind ein spannendes und wichtiges Thema in der Informatik. Mit den Implementierungen von θ, ρ und π hast du die ersten Schritte in die Welt von SHA-3 gemacht. Diese Funktionen werden in der Kryptographie verwendet, um sichere Hashwerte zu erzeugen – zum Beispiel in der Blockchain-Technologie oder bei digitalen Signaturen. Wenn du mehr über die Sicherheit von Hash-Funktionen erfahren möchtest, lies weiter über Kollisionsangriffe und die Einweg-Eigenschaft. Viel Erfolg bei deiner Hausaufgabe!