[Quiz#11] Alexander Schuc (C#)

[Alexander Schuc]

Hi.

Stufe 1

Die verschiedenen Verschiebungen zu "berechnen" ist jetzt nicht sonderlich schwer, darauf geh ich jetzt nicht ein.
Zur Erkennung welche Verschiebung nun die richtige ist, habe ich 2 Varianten eingebaut. Die Erste schaut sich die Häufigkeiten der Buchstaben an, die 2. nimmt sich ein paar (maximal 2) Wörter aus dem Ergebnis und fragt duden.de ob die Wörter bekannt sind.

Zum Vergleichen der Häufigkeiten sei erwähnt, dass es da sicher eine clevere Art und Weise gibt, aber.. es funktioniert.

Decoder

public class CaesarDecoder : Decoder
{
	public override string Name { get { return "Caesar"; } }

	public override DecodingResult Decode(string phrase)
	{
		DecodingResult result = new DecodingResult
		{
			Success = false,
			Ciphertext = phrase,
			Plaintext = "",
			Key = "",
			Encryption = "Caesar",
			Correctness = 0.0
		};

		for (int s = 1; s <= 26; s++)
		{
			string tempPhrase = "";
			foreach (char c in phrase)
			{
				if (c < 97 || c > 122)
					tempPhrase += c;
				else
				{
					tempPhrase += (char)((((c - 97) + s) % 26) + 97);
				}
			}

			var vresult = Verifier.Verify(tempPhrase);

			if (Verbose)
			{
				Console.Error.WriteLine("#{0:00} - {1:0.00000}\r\n{2}", s, vresult.Correctness, tempPhrase);
			}

			if (vresult.Correctness > result.Correctness)
			{
				result = new DecodingResult
				{
					Success = true,
					Ciphertext = phrase,
					Plaintext = tempPhrase,
					Key = (26-s).ToString(),
					Encryption = "Caesar",
					Correctness = vresult.Correctness
				};
			}

			if (this.ResultMode == ResultMode.FirstAboveLimit
				&& result.Correctness >= this.NeededCorrectness)
				return result;
		}

		return result;
	}
}

Verfikation über Häufigkeiten

public abstract class ProbabilityVerifier : Verifier
{
	protected virtual double Threshold { get; set; }

	protected Dictionary<char, double> CharPercentage { get; private set; }

	public ProbabilityVerifier()
	{
		CharPercentage = new Dictionary<char, double>();
		Threshold = 0.05;
	}

	protected void Add(char c, double value)
	{
		if (CharPercentage.ContainsKey(c))
			CharPercentage[ c] = value;
		else
			CharPercentage.Add(c, value);
	}

	public override VerificationResult Verify(string phrase)
	{
		if (phrase.Length == 0)
			return new VerificationResult { Correctness = 0 };

		Dictionary<char, double> data = new Dictionary<char, double>();

		foreach (char c in phrase.ToLower())
		{
			if (!CharPercentage.ContainsKey(c))
				continue;

			if (data.ContainsKey(c))
				data[ c] += 1;
			else
				data[ c] = 1;
		}

		int count = 0;

		for (int i = 0; i < data.Keys.Count; i++)
		{
			char c = data.Keys.ElementAt(i);
			double value = data[ c] / phrase.Length;
			double diff = Math.Abs(value - CharPercentage[ c]);

			if (diff > Threshold)
			{
				count++;
			}
		}

		return new VerificationResult { Correctness = 1.0 - (1.0 / data.Count) * count };
	}
}

public class GermanProbabilityVerifier : ProbabilityVerifier
{
	public GermanProbabilityVerifier()
	{
		Add('a', 0.0651); Add('b', 0.0189); Add('c', 0.0306); Add('d', 0.0508);
		Add('e', 0.1740); Add('f', 0.0166); Add('g', 0.0301); Add('h', 0.0476);
		Add('i', 0.0755); Add('j', 0.0027); Add('k', 0.0121); Add('l', 0.0344);
		Add('m', 0.0253); Add('n', 0.0978); Add('o', 0.0251); Add('p', 0.0079);
		Add('q', 0.0002); Add('r', 0.0700); Add('s', 0.0727); Add('t', 0.0615);
		Add('u', 0.0435); Add('v', 0.0067); Add('w', 0.0189); Add('x', 0.0003);
		Add('y', 0.0004); Add('z', 0.0113);	Add('ß', 0.0031);
	}
}

Verifikation über duden.de

public class DudenSpellingVerifier : Verifier
{
	private readonly int wordsToCheck = 3;

	private string dudenUrl = "http://www.duden-suche.de/suche/trefferliste.php?suchbegriff%5BAND%5D={0}";
	public override VerificationResult Verify(string phrase)
	{
		string[] parts = phrase.Split(new char[] { ' ', '\r', '\n', '\t', '.', ',', ':', '!', '?' },
			StringSplitOptions.RemoveEmptyEntries);

		int check = parts.Length > wordsToCheck ? wordsToCheck : parts.Length;

		int success = 0;

		for (int i = 0; i < check; i++)
		{
			WebClient wc = new WebClient();
			string site = wc.DownloadString(string.Format(dudenUrl, parts[i]));

			if (!site.Contains(@"<strong>0</strong> Treffer in Duden"))
			{
				success++;
			}

			Thread.Sleep(1000);
		}

		return new VerificationResult { Correctness = (double)success / (double)check };
	}
}

Gesamter Code ist angehängt.
Stufe 2 im nächsten Beitrag.

 

[Alexander Schuc]

Stufe 2

Zur Theorie: Die affine Verschlüsselung lässt sich (einfach) brechen sobald man 2 Wörter kennt (verschlüsselt und unverschlüsselt). Da die ersten beiden Bytes in einer PNG Datei sind immer gleich ist diese Voraussetzung erfüllt, und wir können die Schlüssel berechnen.

Die beiden Beispieldateien von OnlyFoo können mit meinem Code nicht entschlüsselt werden. Hat da keinen Bock mehr rumzutüfteln.

Zum Aufbau meines Codes: Ich habe die Ver/Entschlüsselung (teilweise) den Crypto-Klassen des .net Frameworks angepasst.

Cracker

using System;
using System.IO;

namespace CodingQuiz11.Affine
{
	public class AffinePngCracker
	{
		private readonly uint x1 = 1196314761; // Header Byte 1
		private readonly uint x2 = 169478669; // Header Byte 2
		private readonly uint iX2sX1 = 484324769; // vorberechnet: eeuclid(x2 - x1, m)[1];

		public AffineKey Crack(Stream pngStream)
		{
			BinaryReader reader = new BinaryReader(pngStream);
		
			uint y1 = reader.ReadUInt32();
			uint y2 = reader.ReadUInt32();
			uint a = 0, b = 0;
			
			a = (y2 - y1) * iX2sX1; 
			a >>= 2; // mmhmmmmm.. naja ;)
			b = y1 - a * x1;
			
			if (pngStream.CanSeek)
				pngStream.Seek(-8, SeekOrigin.Current);

			return new AffineKey { A = a, B = b };
		}
	}
}

Entschlüsselungs Code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Security.Cryptography;

namespace CodingQuiz11.Affine
{
	public class AffineDecrypter : ICryptoTransform
	{
		public AffineKey Key { get; set; }

		public AffineDecrypter(AffineKey key)
		{
			this.Key = key;
		}

		public bool CanReuseTransform
		{
			get { return true; }
		}

		public bool CanTransformMultipleBlocks
		{
			get { return false; }
		}

		public int InputBlockSize
		{
			get { return 4; }
		}

		public int OutputBlockSize
		{
			get { return 4; }
		}

		public int TransformBlock(byte[] inputBuffer, int inputOffset, int inputCount, byte[] outputBuffer, int outputOffset)
		{
			if (inputCount == 0)
				return 0;

			UInt32 x, y;

			y = (uint)inputBuffer[3 + inputOffset] << 24
					| (uint)inputBuffer[2 + inputOffset] << 16
					| (uint)inputBuffer[1 + inputOffset] << 8
					| (uint)inputBuffer[0 + inputOffset];

			x = Key.InverseA * (y - Key.B);

			outputBuffer[outputOffset + 0] = (byte)(x >> 0 & 0xFF);
			outputBuffer[outputOffset + 1] = (byte)(x >> 8 & 0xFF);
			outputBuffer[outputOffset + 2] = (byte)(x >> 16 & 0xFF);
			outputBuffer[outputOffset + 3] = (byte)(x >> 24 & 0xFF);

			return OutputBlockSize;
		}

		public byte[] TransformFinalBlock(byte[] inputBuffer, int inputOffset, int inputCount)
		{
			byte[] outputBuffer = new byte[inputCount];
			TransformBlock(inputBuffer, inputOffset, inputCount, outputBuffer, 0);
			return outputBuffer;
		}

		public void Dispose()
		{

		}
	}
}

Verschlüsselung
Nicht gefordert, aber zwecks Vollständigkeit.

using System;
using System.Security.Cryptography;

namespace CodingQuiz11.Affine
{
	public class AffineDecrypter : ICryptoTransform
	{
		public AffineKey Key { get; set; }

		public AffineDecrypter(AffineKey key)
		{
			this.Key = key;
		}

		public bool CanReuseTransform
		{
			get { return true; }
		}

		public bool CanTransformMultipleBlocks
		{
			get { return false; }
		}

		public int InputBlockSize
		{
			get { return 4; }
		}

		public int OutputBlockSize
		{
			get { return 4; }
		}

		public int TransformBlock(byte[] inputBuffer, int inputOffset, int inputCount, byte[] outputBuffer, int outputOffset)
		{
			if (inputCount == 0)
				return 0;

			UInt32 x, y;

			y = (uint)inputBuffer[3 + inputOffset] << 24
					| (uint)inputBuffer[2 + inputOffset] << 16
					| (uint)inputBuffer[1 + inputOffset] << 8
					| (uint)inputBuffer[0 + inputOffset];

			x = Key.InverseA * (y - Key.B);

			outputBuffer[outputOffset + 0] = (byte)(x >> 0 & 0xFF);
			outputBuffer[outputOffset + 1] = (byte)(x >> 8 & 0xFF);
			outputBuffer[outputOffset + 2] = (byte)(x >> 16 & 0xFF);
			outputBuffer[outputOffset + 3] = (byte)(x >> 24 & 0xFF);

			return OutputBlockSize;
		}

		public byte[] TransformFinalBlock(byte[] inputBuffer, int inputOffset, int inputCount)
		{
			byte[] outputBuffer = new byte[inputCount];
			TransformBlock(inputBuffer, inputOffset, inputCount, outputBuffer, 0);
			return outputBuffer;
		}

		public void Dispose()
		{

		}
	}
}

Main

using System;
using System.Security.Cryptography;
using System.IO;
using System.Diagnostics;

namespace CodingQuiz11.Affine
{
	class Program
	{
		static void Main(string[] args)
		{
			Stopwatch watch = new Stopwatch();
			watch.Start();

			if (args.Length == 0)
			{
				PrintUsage();
				return;
			}

			switch (args[0])
			{
				case "-e":
					Encrypt(args);
					break;
				case "-d":
					Decrypt(args);
					break;
				case "-c":
					Crack(args);
					break;
				default:
					PrintUsage();
					break;
			}

			watch.Stop();
			Console.WriteLine("Done in: " + watch.Elapsed);
		}

		private static void Encrypt(string[] args)
		{
			AffineKey key = new AffineKey { A = uint.Parse(args[1]), B = uint.Parse(args[2]) };

			using (Stream input = File.OpenRead(args[3]))
			using (Stream output = File.Create(args[4]))
			using (CryptoStream crypto = new CryptoStream(output,
				AffineCrypto.CreateEncrypter(key), CryptoStreamMode.Write))
			{
				byte[] buffer = new byte[4096];
				int count = 0;

				while ((count = input.Read(buffer, 0, buffer.Length)) != 0)
				{
					crypto.Write(buffer, 0, count);
				}
			}
		}

		private static void Decrypt(string[] args)
		{
			AffineKey key = new AffineKey { A = uint.Parse(args[1]), B = uint.Parse(args[2]) };

			using (Stream input = File.OpenRead(args[3]))
			using (Stream output = File.Create(args[4]))
			using (CryptoStream crypto = new CryptoStream(input,
				AffineCrypto.CreateDecrypter(key), CryptoStreamMode.Read))
			{
				byte[] buffer = new byte[4096];
				int count = 0;

				while ((count = crypto.Read(buffer, 0, buffer.Length)) != 0)
				{
					output.Write(buffer, 0, count);
				}
			}
		}
		private static void Crack(string[] args)
		{
			AffineKey k;
			using (var s = File.OpenRead(args[1]))
			{
				k = new AffinePngCracker().Crack(s);
			}

			Decrypt(new string[] { "-d", k.A.ToString(), k.B.ToString(), args[1], args[2] });
		}

		private static void PrintUsage()
		{
			Console.WriteLine("Usage:\r\n   Encryption: -e a b input output\r\n   Decryption: -d a b input output\r\n   Cracking:   -c input output");
		}
	}
}

Gesamter Code wieder angehängt.

 

[zeja]

Eine Anfrage an den Duden ist auch nett Da kann ich mit meinem kleinen Wörterbuch nicht ganz mithalten