병렬 브 루트 포스 알고리즘 그래서

Question

내가 http://codahale.com/how-to-safely-store-a-password/#보고 다소 강력한 데스크톱 컴퓨터에 bruteforced 수 있습니다 얼마나 빨리 다른 해시 호기심이되었고,이

알고리즘의 대부분은 내가 비록 볼 수 있습니다 한 테스트 유혹 하였다 single-threaded 그리고 이것이 C# 4.0 Parallel.net/Plinq 확장과 동시 구조 (ConcurrentBag와 IProducerConsumer와 같은)를 사용할 때 정말 흥미로운 도전이 될 것이라는 것을 알게되었습니다.

내 작업은 다음과 같습니다. 병렬 처리를 사용하여 길이가 n이고 charset [x] 인 암호를 가장 효율적으로 사용하는 bruteforce 검사기를 만듭니다. 즉, 일치하는 문자열이 발견 될 때까지 가능한 모든 문자열을 생성합니다. . 적어도 두 개의 코어와 최고의 남자/여자 성능을 비교하지 않고 :

편집

첫 번째 시도에서 승리 내가 나 자신이,하자 소용돌이를 줄거야

램의 적절한 양을 가정 그러나 제한된 범위 알려진 암호 길이

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)); 

    } 

다음 시도

012,351

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); 

또한 때문에 당신이 문제 (36^6> 2 드릴 것입니다 기지 36 알파벳 만 6 자와 nrCombinations에 대한 int에 추천^31). long을 사용하십시오. 나는 큰 숫자가 필요한 경우 무차별 한 힘이 어쨌든 옵션이 아니기 때문에 BigInteger이 필요하다고 생각하지 않습니다.

나는 De Bruijn 시퀀스 스트림을 사용하여 무차별 한 속도를 높일 수 있다는 생각이 들었다. 합리적인 것 같지만 지금 당장 표시 할 코드가 없기 때문에 다시 생각해 봐야합니다.