Aufgabe 1. Ich habe eine Wahrscheinlichkeitstabelle für das Auftreten der Buchstaben aus der Wikipedia geladen und vergleiche die auftretenden Verteilungen mittels Kreuzkorrelation um die Verschiebung zu finden.
Aufgabe 2:
Ich Löse das Gleichungssystem y1 = (a * x1 + b) (mod m) und y2 = (a * x2 + b) (mod m) um Werte für a und b zu errechnen
Python:
# -*- encoding: utf8 -*-
import sys
# Relative Häufigkeiten der Buchstaben a bis z im deutschen Alphabet.
frequency = (
0.0651, 0.0189, 0.0306, 0.0508, 0.1740,
0.0166, 0.0301, 0.0476, 0.0755, 0.0027,
0.0121, 0.0344, 0.0253, 0.0978, 0.0251,
0.0079, 0.0002, 0.0700, 0.0727, 0.0615,
0.0435, 0.0067, 0.0189, 0.0003, 0.0004,
0.0131 )
def main():
input = sys.stdin.read().lower()
# Häufigkeiten der Buchstaben 'a' - 'z' zählen
occurences = [0] * 26
for c in [ord(c) - ord('a') for c in input]:
if c in range(26):
occurences[ c] += 1
# Relative Häufigkeiten berechnen
total = sum(occurences)
freq = [float(h) / total for h in occurences]
# Mittels Kreuzkorrelation die Verschiebung berechnen
cross = cross_correlation( frequency, freq )
distance = max_index( cross )
# Alphabet des Eingabetext um -distance rotieren
print encrypt( input, -distance )
#
# Verschiebt alle Buchstaben zwischen 'a' und 'z' um distance
# Buchstaben im Alphabet
#
def encrypt( input, distance ):
base = ord( 'a' )
def rotate( char ):
if not char.isalpha():
return char
return chr( (ord( char ) - base + distance) % 26 + base )
return "".join( rotate(c) for c in input )
#
# Gibt den Index des größten Wertes in einer Liste zurück
#
def max_index( list ):
return list.index( max(list) )
#
# Gibt das Ergebnis der Kreuzkorrelation zwischen zwei Listen zurück
#
def cross_correlation( f, g ):
r = len( f )
def fg( n ):
return sum( [ f[m] * g[ (n + m) % len(g) ] for m in range( r ) ] )
return [ fg(i) for i in range( r ) ]
if __name__ == "__main__":
main()
Aufgabe 2:
Ich Löse das Gleichungssystem y1 = (a * x1 + b) (mod m) und y2 = (a * x2 + b) (mod m) um Werte für a und b zu errechnen
Python:
# -*- encoding: utf8 -*-
import sys, struct, zlib
def main():
# Datei einlesen
fp = open( sys.argv[1], "rb" )
data = fp.read()
fp.close()
# die ersten 8 bytes jeder PNG sind gleich
x1, x2 = struct.unpack( "LL", "\x89\x50\x4E\x47\x0D\x0A\x1A\x0A" )
# die ersten 8 verschlüsselten Bytes
y1, y2 = struct.unpack( "LL", data[:8] )
# Keys errechnen und Datei in 32 bit Wörter aufteilen
keys = solve( x1, y1, x2, y2 )
input = struct.unpack( "%dL" % (len(data) / 4), data )
# Prüfen welches Ergebnis am besten ausschaut
png_ok = None
for key in keys:
# Versuchen diese Datei zu entschlüsseln
result = decrypt( input, *key )
png = struct.pack( "%dL" % len(result), *result )
# Gucken ob es sich hier um eine PNG handelt
if png[8:16] == "\x00\x00\x00\x0dIHDR":
png_ok = png
break
# Wir haben keine gültige PNG gefunden!
if not png_ok:
print "Fehler beim entschlüsseln"
# png ausgeben.
sys.stdout.write( png_ok )
#
# Errechnet mögliche Schlüssel aus zwei Werten und deren
# verschlüsselten Werten
#
def solve( x1, y1, x2, y2, m = 2 ** 32 ):
a = (x1 - x2) % m
b = (y1 - y2) % m
d, r, ignore = euclid( a, m )
# Alle gültigen Keys sammeln
keys = []
for idx in range( d ):
key_a = (r * b / d) % (m / d) + idx * (m / d)
key_b = (y1 - key_a * x1) % m
keys.append( (key_a, key_b) )
return keys
#
# Entschlüsselt ein Zahlenarray
#
def decrypt( input, a, b, m = 2 ** 32 ):
inv = mul_inverse( a, m )
return [ (inv * (y - b)) % m for y in input ]
#
# Euklid zum Berechnen des ggT und multiplikativen Inversen
#
def euclid( a, b ):
if not b:
return (a, 1, 0)
d, s, t = euclid( b, a % b )
return (d, t, s - a / b * t)
def mul_inverse( a, b ):
return euclid( a, b )[1] % b
if __name__ == '__main__':
main()
Zuletzt bearbeitet: