[Quiz#11] OnlyFoo (python)

OnlyFoo

Erfahrenes Mitglied
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.

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:

OnlyFoo

Erfahrenes Mitglied
Ich möchte noch ein paar Worte zu meiner zweiten Lösung verlieren, und warum einige der Bilder nicht entschlüsselt wurden.

Ich zitire aus der Wikipedia:

For example, the congruence 12x ? 20 (mod 28) has 4 solutions since gcd(12, 28) = 4 divides 20. The extended Euclidean algorithm gives (-2)*12 + 1*28 = 4, i.e. r = -2 and s = 1. Therefore, one solution is x = -2*20/4 = -10, and -10 = 4 modulo 7. All other solutions will also be congruent to 4 modulo 7. Since the original equation uses modulo 28, the entire solution set in the range from 0 to 27 is x = {4,11,18,25}.

Das wichtigste hab ich hervorgehoben... So eine Gleichung kann mehrere Ergebnisse haben, ist also nicht eindeutig zu lösen. Ich vergeliche darum die nächsten acht entschlüsselten bytes mit deren (häufig vorkommenden) Plaintext Varianten.
 
Das wichtigste hab ich hervorgehoben... So eine Gleichung kann mehrere Ergebnisse haben, ist also nicht eindeutig zu lösen. Ich vergeliche darum die nächsten acht entschlüsselten bytes mit deren (häufig vorkommenden) Plaintext Varianten.
Das kann man sich auch sparen, wenn man als „known plaintext“ z.B. den ersten und dritten int32 verwendet (was man machen kann, da beim PNG-Format die ersten 16 Bytes vorgegeben sind). Die Differenz (x1 - x2) ist dann nämlich ungerade und damit invertierbar im Restklassenring modulo 2^32. Damit ist die Lösung eindeutig.

Grüße, Matthias