Генерация каждой комбинации символов до определенной длины слова - PullRequest
Новая
       29

Генерация каждой комбинации символов до определенной длины слова

5 голосов
/ 04 сентября 2010

Через несколько недель я делаю презентацию по безопасности для своего курса «Компьютерная и информационная безопасность», и в этой презентации я продемонстрирую плюсы и минусы различных атак (словарь, радуга и грубая сила).Я хорошо справляюсь со словарем и радужными атаками, но мне нужно генерировать грубую атаку на лету.Мне нужно найти алгоритм, который позволит мне циклически повторять каждую комбинацию буквы, символа и числа до определенной длины символа.

Так, например, для длины символа 12, первые и последние несколькопоколений будет: 

a
ab
abc
abcd
...
...
zzzzzzzzzzzx
zzzzzzzzzzzy
zzzzzzzzzzzz

Но он также будет использовать цифры и символы, поэтому мне довольно сложно объяснить ... но я думаю, вы поняли идею.Хорошо использовать только символы из таблицы ASCII.

Я могу сделать вид изображения, используя функцию ASCII, чтобы сделать это со счетчиком, но я просто не могу решить это в своей голове.Если бы кто-нибудь мог предоставить какой-нибудь исходный код (я, вероятно, буду использовать C #) или даже какой-нибудь псевдокод, из которого я мог бы запрограммировать функцию, это было бы здорово.

Заранее спасибо.:)

Ответы [ 5 ]

8 голосов
/ 04 сентября 2010

Рекурсивная функция позволит вам пройти через все комбинации ValidChars: 

    int maxlength = 12;
    string ValidChars;
    private void Dive(string prefix, int level)
    {
        level += 1;
        foreach (char c in ValidChars)
        {
            Console.WriteLine(prefix + c);
            if (level < maxlength)
            {
                Dive(prefix + c, level);
            }
        }
    }

Присвойте ValidChars набор допустимых символов, максимальную длину строки, которую вы хотите задать maxlength, затем вызовите Dive("", 0); и все готово.

5 голосов
/ 04 сентября 2010

Вам необходимо сгенерировать все комбинации символов из набора допустимых символов; давайте назовем этот набор validChars. По существу, каждый набор комбинаций длины N является декартовым произведением validChars с самим собой, N раз. Это довольно легко сделать с помощью Linq: 

char[] validChars = ...;

var combinationsOfLength1 =
    from c1 in validChars
    select new[] { c1 };

var combinationsOfLength2 =
    from c1 in validChars
    from c2 in validChars
    select new[] { c1, c2 };

...

var combinationsOfLength12 =
    from c1 in validChars
    from c2 in validChars
    ...
    from c12 in validChars
    select new[] { c1, c2 ... c12 };

var allCombinations =
    combinationsOfLength1
    .Concat(combinationsOfLength2)
    ...
    .Concat(combinationsOfLength12);

Очевидно, что вы не хотите вручную писать код для каждой длины, особенно если вы не знаете заранее максимальную длину ...

У Эрика Липперта есть статья о генерации декартового произведения из произвольного числа последовательностей. Используя метод расширения CartesianProduct, предоставленный в статье, вы можете сгенерировать все комбинации длины N следующим образом: 

var combinationsOfLengthN = Enumerable.Repeat(validChars, N).CartesianProduct();

Поскольку вы хотите, чтобы все комбинации имели длину от 1 до МАКС, вы можете сделать что-то подобное: 

var allCombinations = 
    Enumerable
        .Range(1, MAX)
        .SelectMany(N => Enumerable.Repeat(validChars, N).CartesianProduct());

allCombinations - это IEnumerable<IEnumerable<char>>, если вы хотите получить результаты в виде последовательности строк, вам просто нужно добавить проекцию: 

var allCombinations = 
    Enumerable
        .Range(1, MAX)
        .SelectMany(N => Enumerable.Repeat(validChars, N).CartesianProduct())
        .Select(combination => new string(combination.ToArray()));

Обратите внимание, что это, конечно, не самое эффективное решение, но, по крайней мере, оно короткое и удобочитаемое ...

1 голос
/ 04 сентября 2010

Вы можете попробовать этот код, который использует рекурсию для печати всех возможных строк от 0 до длины строки stringsLenght, составленной из всей комбинации символов от firstRangeChar до lastRangeChar. 

class BruteWriter
{
    static void Main(string[] args)
    {
        var bw = new BruteWriter();
        bw.WriteBruteStrings("");
    }

    private void WriteBruteStrings(string prefix)
    {
        Console.WriteLine(prefix);
        if (prefix.Length == stringsLenght)
            return;

        for (char c = firstRangeChar; c <= lastRangeChar; c++)
            WriteBruteStrings(prefix + c);

    }

    char firstRangeChar='A';
    char lastRangeChar='z';
    int stringsLenght=10;


}

Это выглядит быстрее, чем решение @ dthorpe. Я сравнил алгоритмы, используя этот код: 

class BruteWriter
    {
        static void Main(string[] args)
        {
            var st = new Stopwatch();
            var bw = new BruteWriter();
            st.Start();
            bw.WriteBruteStrings("");
            Console.WriteLine("First method: " + st.ElapsedMilliseconds);

            for (char c = bw.firstRangeChar; c <= bw.lastRangeChar; c++)
                bw.ValidChars += c;

            st.Start();
            bw.Dive("", 0);
            Console.WriteLine("Second method: " + st.ElapsedMilliseconds);

            Console.ReadLine();


        }

        private void WriteBruteStrings(string prefix)
        {
            if (prefix.Length == stringsLenght)
                return;

            for (char c = firstRangeChar; c <= lastRangeChar; c++)
                WriteBruteStrings(prefix + c);

        }

        char firstRangeChar='A';
        char lastRangeChar='R';
        int stringsLenght=5;



        int maxlength = 5;
        string ValidChars;
        private void Dive(string prefix, int level)
        {
            level += 1;
            foreach (char c in ValidChars)
            {
                if (level <= maxlength)
                {
                    Dive(prefix + c, level);
                }
            }
        }
    }

и на моем компьютере я получаю следующие результаты: 

First method: 247
Second method: 910
0 голосов
/ 13 декабря 2012

Еще одна альтернатива, которую я сделал, это возвращение строки.

Мне было все равно, что делать, потому что это было не для сценария реального мира. 

private void BruteForcePass(int maxLength)
    {
        var tempPass = "";
        while (tempPass.Length <= maxLength)
        {
            tempPass = GetNextString(tempPass);//Use char from 32 to 256
            //Do what you want
        }
    }

    private string GetNextString(string initialString, int minChar= 32, int maxChar = 256)
    {
        char nextChar;
        if (initialString.Length == 0)
        {
            nextChar = (char)minChar;//the initialString Length will increase
        }
        else if (initialString.Last() == (char)maxChar)
        {
            nextChar = (char)minChar;
            var tempString = initialString.Substring(0, initialString.Length -1);//we need to increment the char just before the last one
            initialString = GetNextString(tempString, minChar, maxChar); 
        }
        else
        {
            nextChar = (char)(initialString.Last() + 1);//Get the lash Char and increment it;
            initialString= initialString.Remove(initialString.Length - 1);//Remove the last char.
        }
        return initialString + nextChar;
    }
0 голосов
/ 04 сентября 2010 
public void BruteStrings(int maxlength)
{
   for(var i=1;i<i<=maxlength;i++)
      BruteStrings(Enumerable.Repeat((byte)0,i));

}

public void BruteStrings(byte[] bytes)
{
   Console.WriteLine(bytes
                       .Cast<char>()
                       .Aggregate(new StringBuilder(), 
                          (sb,c) => sb.Append(c))
                       .ToString());

   if(bytes.All(b=>b.MaxValue)) return;

   bytes.Increment();

   BruteStrings(bytes);
}

public static void Increment(this byte[] bytes)
{
   bytes.Last() += 1;

   if(bytes.Last == byte.MinValue)
   {
      var lastByte = bytes.Last()
      bytes = bytes.Take(bytes.Count() - 1).ToArray().Increment();
      bytes = bytes.Concat(new[]{lastByte});
   }
}
...