并行蛮力算法

Question

所以我一直在寻找http://codahale.com/how-to-safely-store-a-password/#，并成为好奇哈希有多快不同时，稍微强大的台式计算机上bruteforced和被诱惑，以测试它

大部分的算法我见过，虽然是单线程，它让我感到这对于使用c＃4.0 Parallel.net/Plinq扩展和并发结构（如ConcurrentBag和IProducerConsumer）是一个非常有趣的挑战。

所以我的任务如下，使用并行化构建一个密码长度为n和长度为charset [x]的最有效/高性能的bruteforce检查器，即生成给定字符集和长度的所有可能字符串，直到找到匹配。假设至少两个核心和RAM的合理量

我要试一试自己，让最好的男人/女人赢得:)

编辑

第一次尝试没有性能比较但和范围有限的和已知的密码长度

char[] chars = new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' }; 

    public long NrCombinations(int nrChars, int stringLength) 
    { 
     Func<long, int, long> power = null; 
     power = (i, p) => p == 1 ? i : i * power(i, p - 1); 

     return power(nrChars, stringLength); 
    } 


    public static bool StringArrayEquals(char[] a, char[] b) 
    { 
     if (a.Length != b.Length) 
      return false; 
     for (int i = 0; i < a.Length; i++) 
     { 
      if (!a[i].Equals(b[i])) 
       return false; 
     } 
     return true; 
    } 

    public char[] GenerateString(int i, int stringLength) 
    { 
     char[] current = new char[stringLength]; 
     for (int i = 0; i < stringLength; i++) 
     { 
      double remainder = i % this.chars.Length; 
      i = i/this.chars.Length;   
      current[i] = this.chars[(int) remainder]; 
     } 
     return current; 
    } 

    public bool IsMatch(int i, char[] password) 
    { 
     return StringArrayEquals(GenerateString(i, password.Length), password); 
    } 

    private int GetMatching(string passwordString) 
    { 
     char[] password = passwordString.ToArray(); 
     int nrCombinations = (int)NrCombinations(this.chars.Length, password.Length); 

     return ParallelEnumerable.Range(0, nrCombinations).WithDegreeOfParallelism(10).FirstOrDefault(i => IsMatch(i, password)); 

    } 

下一次尝试

使用ParallelEnumerable不是很聪明，因为它的大小限制为int，即使我怀疑这会持续很长一段时间，并且需要较大的密码字符集，但您很快就需要至少很长的时间。猜想你要么必须去BigInt，要么就开始以某种方式分解它。

public long NrCombinations(int nrChars, int stringLength) 
    { 
     Func<long, int, long> power = null; 
     power = (i, p) => p == 1 ? i : i * power(i, p - 1); 

     return power(nrChars, stringLength); 
    } 


    public string GenerateString(long number, int sentenceLength) 
    { 
     char[] current = new char[sentenceLength]; 
     for (int i = 0; i < sentenceLength; i++) 
     { 
      double remainder = number % this.chars.Length; 
      number = number/this.chars.Length;   
      current[i] = this.chars[(int) remainder]; 
     } 
     return new string(current); 
    } 

    public bool IsMatch(string hash, long i, int passwordLength) 
    { 
     string generated = GenerateString(i, passwordLength); 
     string hashed = GetMasterHash(generated, this.site); 
     return string.Equals(hashed, hash); 
    } 

    private string GetMatching(string hash,int passwordLength) 
    { 
     string result = string.Empty; 
     int stringlength = passwordLength; 
     long nrCombinations = NrCombinations(this.chars.Length, stringlength); 
     long x = 0; 

     Parallel.For(0, nrCombinations, (i, loopState) => 
     { 
      if (IsMatch(hash,i, passwordLength)) 
      { 
       x = i; 
       loopState.Stop(); 
       return; 
      } 
     }); 


     if (x > 0) 
     { 
      result = this.GenerateString(x, passwordLength); 
     } 

     return result; 

    } 

Answer 1

为什么NrCombinations方法，而不仅仅是

long combinations = (long)Math.Pow(base, stringLength); 

我还建议对int为nrCombinations因为只有6个与你的基地36字母字符，你会遇到麻烦（36^6> 2获得^ 31）。使用long。我不认为BigInteger是必要的，因为如果你需要这个大数字，蛮力不会是一个选项。

我有这个想法，它可能通过使用一种De Bruijn序列流来加速蛮力。看起来很合理，但我必须回头看看，因为我现在没有代码可以显示。