Algorithm for finding all possible key combinations in given range

Question

Last time I got curious about how long would it take to break my password using brute force attack. I'd like to check it.

So, how should I implement algorithm to find all possible key combinations in given range (for eg. 15 letters)? I found algorithms for permutations around but they all swap letters for given word, it's not what I'm looking for.

Answer 1

Assuming that passwords can consist of combinations of 89 possible characters (a-z, A-z, 0-9, space, and all the different symbol keys on a Windows keyboard), a there there are 82 the the 15th power different combinations of 15 characters (82 * 82 * 82 ... ). In other words, a lot.

If you want to use just letters, and you differentiate between upper and lower case, there would be 52 ** 15 possible 15-letter combinations. If you want to take in the possibility of shorter strings as well you could write something like (pseudocode):

  long combos = 0

  for i = 6 TO 20           -- legal password lengths
     combos = combos + POW(52, i)

  print "there are " + combos.ToString() 
        + " possible passwords between 6 and 20 characters"

To actually enumerate and print the permutations in C# you could do:

  void AddNextCharAndPrintIfDone(string pwd, int maxLen)
  {
     for (char c = 'a';  c < 'Z';  c++)
     {
        pwd = pwd + c;
        if (pwd.Length >= maxLen)
            System.Console.WriteLine(pwd);
        else AddNextCharAndPrintIfDone(pwd, maxLen)
     }
  }

  Main()
  {
     for (int i=6;  i < 20;  i++)
           AddNextCharAndPrintIfDone("", i);
  }

Not really written for efficiency, but if you have enough memory and time, you'll get every possible permutation.

Answer 2

You can download php pear project math combinatoric to generate those passwords.