Cape Cracker

CombinationHelper.cs

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

namespace CapeCracker
{
    public static class CombinationHelper
    {
        private static T[] CloneArray<T>(T[] source)
        {
            var clone = new T[source.Length];
            Array.Copy(source, clone, source.Length);
            return clone;
        }

        public static IEnumerable<IEnumerable<int>> GenerateIndices(int limit, int length)
        {
            if (length == 0)
                yield break;

            var indices = new int[length];

            yield return CloneArray(indices);

            while (true)
                for (int i = 0; i < indices.Length; ++i)
                {
                    ++indices[i];
                    if (indices[i] < limit)
                    {
                        yield return CloneArray(indices);
                        break;
                    }

                    indices[i] = 0;
                    if (i >= indices.Length - 1)
                        yield break;
                }
        }

        public static IEnumerable<IEnumerable<T>> GenerateCombinations<T>(T[] source, int length)
        {
            if (length == 0)
                yield break;

            var indices = new int[length];
            var values = new T[length];
            for (int i = 0; i < indices.Length; ++i)
                values[i] = source[indices[i]];

            yield return CloneArray(values);

            while (true)
                for (int i = 0; i < indices.Length; ++i)
                {
                    ++indices[i];
                    if (indices[i] < source.Length)
                    {
                        values[i] = source[indices[i]];
                        yield return CloneArray(values);
                        break;
                    }

                    indices[i] = 0;
                    values[i] = source[indices[i]];
                    if (i >= indices.Length - 1)
                        yield break;
                }
        }
    }
}

Key.cs

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

namespace CapeCracker
{
    public class Key
    {
        public readonly byte[] key;
        public readonly byte reducedKey;

        public Key(byte[] key)
        {
            this.key = key;
            this.reducedKey = ComputeReducedKey(key);
        }

        public void ComputeHash(byte[] source, byte[] destination)
        {
            for (int i = 0; i < source.Length; ++i)
            {
                var rki = this.reducedKey ^ i;
                var x = rki ^ this.key[rki % this.key.Length];
                destination[i] = (byte)(x ^ source[i]);
            }
        }

        public static byte ComputeReducedKey(byte[] key)
        {
            int result = 0;
            for (int i = 0; i < key.Length; ++i)
                result ^= key[i] << (i % 8);
            return (byte)result;
        }
    }
}

Program.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace CapeCracker
{
    // This program is a bit of a mess
    class Program
    {
        static char[] source = "abcd".ToCharArray();
        static byte[] sourceBytes = Encoding.UTF8.GetBytes(source);

        static List<Key> keys = new List<Key>((int)Math.Pow(4, 10)); // preallocate space for the keys

        static string[] passwords =
        {
            "Hello World", // ~0.36 seconds
            "Dopefish lives", // ~0.39 seconds
            "The quick brown fox jumped over the lazy dog." // ~0.68 seconds
        };

        // A fast set of characters to assume aren't valid password characters
        // which allows the outputs to be narrowed down a bit
        static HashSet<char> invalidCharacters = new HashSet<char>();
        
        static void Main(string[] args)
        {
            // Assume the password doesn't contain:
            // control characters, surrogate pairs, tabs or new lines
            // This doesn't speed things up much, but it eliminates a few possibilities
            for (int i = 0; i <= byte.MaxValue; ++i)
            {
                char c = (char)i;
                if (char.IsControl(c) ||
                    char.IsLowSurrogate(c) ||
                    char.IsHighSurrogate(c))
                    invalidCharacters.Add(c);
            }
            invalidCharacters.Add('\t');
            invalidCharacters.Add('\n');

            // Select a password
            var password = passwords[0];
            var passbytes = Encoding.UTF8.GetBytes(password);

            // Inialise keyword
            var keyword = new string('d', 10); // worst case scenario, 10 ds
            var keybytes = Encoding.UTF8.GetBytes(keyword);

            // Initialise private key
            var privateKey = new Key(keybytes);
            var hashedPassword = new byte[passbytes.Length];

            // Hash the password
            privateKey.ComputeHash(passbytes, hashedPassword);


            StringBuilder builder = new StringBuilder();
            byte[] output = new byte[hashedPassword.Length];
            char[] chars = new char[hashedPassword.Length];
            bool valid = true;

            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Reset();
            stopwatch.Start();
            foreach(var key in GenerateKeys(10))
            {
                // Hash computation is symmetric
                key.ComputeHash(hashedPassword, output);

                valid = true;
                for(int i = 0; i < output.Length; ++i)
                {
                    char c = (char)output[i];

                    if (invalidCharacters.Contains(c))
                    {
                        valid = false;
                        break;
                    }
                    chars[i] = c;
                }

                if (valid)
                {
                    foreach (char c in chars)
                        builder.Append(c);
                    builder.AppendLine();
                }
            }
            stopwatch.Stop();

            Console.WriteLine(builder);
            Console.WriteLine(stopwatch.Elapsed);
            Console.ReadKey();
        }

        static IEnumerable<Key> GenerateKeys(int length)
        {
            return CombinationHelper.GenerateCombinations(sourceBytes, length).Select(arr => new Key(arr as byte[]));
        }


    }
}