並行蠻力算法

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序列流來加速蠻力。看起來很合理，但我必須回頭看看，因爲我現在沒有代碼可以顯示。