Generazione ogni combinazione di caratteri fino ad una certa lunghezza di parola

Question

Sto facendo una presentazione di sicurezza per il mio corso di informatica e sicurezza delle informazioni in poco tempo settimane, e in questa presentazione mi sarà dimostrare i pro ei contro dei diversi attacchi (dizionario, arcobaleno e bruteforce). Sono fare la multa dizionario e arcobaleno attacchi, ma ho bisogno di generare l'attacco bruteforce al volo. Ho bisogno di trovare un algoritmo che mi lascia ciclo se ogni combinazione di lettere, simbolo e numero fino a un certo numero di caratteri.

Così, ad esempio, per una lunghezza di 12 caratteri, il primo e ultime generazioni sarà:

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

Ma sarà anche possibile utilizzare numeri e simboli, quindi è molto difficile per me spiegare ... ma penso che si ottiene l'idea. Usando solo i simboli dalla tabella ASCII va bene.

posso tipo di immagine utilizzando una funzione ASCII di fare questo con un contatore, ma non riesco proprio a lavorare fuori nella mia testa. Se qualcuno potrebbe fornire qualche codice sorgente (io probabilmente utilizzerò C #) o anche qualche pseudo codice che posso programmare una funzione da sarebbe fantastico.

Grazie in anticipo. :)

Answer 1

Una funzione ricorsiva permette di far funzionare attraverso tutte le combinazioni di 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);
            }
        }
    }

Assegna il set di caratteri validi per ValidChars, la lunghezza massima della stringa che si desidera maxlength, quindi chiamare Dive("", 0); e si va via.

Answer 2

È necessario generare tutte le combinazioni di caratteri da un insieme di caratteri validi; Chiamiamo questo insieme validChars. Fondamentalmente, ogni insieme di combinazioni di lunghezza N è un prodotto cartesiano di validChars con se stessa, N volte. Questo è abbastanza facile da fare utilizzando 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);

Ovviamente, non si vuole scrivere manualmente il codice per ogni lunghezza, soprattutto se non si conosce in anticipo la lunghezza massima ...

Eric Lippert ha un articolo sulla generazione del prodotto cartesiano di un numero arbitrario di sequenze. Utilizzando il metodo di estensione CartesianProduct fornito da questo articolo, è possibile generare tutte le combinazioni di lunghezza N come segue:

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

Dal momento che si desidera che tutte le combinazioni di lunghezza da 1 a MAX, si può fare qualcosa di simile:

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

allCombinations è un IEnumerable<IEnumerable<char>>, se si desidera ottenere i risultati come una sequenza di stringhe, basta aggiungere una proiezione:

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

Si noti che non è certamente la soluzione più efficiente, ma almeno è breve e leggibile ...

Answer 3

Si può provare questo codice, che l'uso ricorsione per stampare tutte le possibili stringhe di 0 a stringsLenght carbonizzazione lunghezza, composto da tutte le combinazioni di caratteri da firstRangeChar a 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;


}

Questo sguardo per essere più veloce rispetto alla soluzione di @ dthorpe.I've confrontato i algorthms utilizzando questo codice:

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

e, sul mio pc, ottengo questi risultati:

First method: 247
Second method: 910

Answer 4

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

Answer 5

Un'altra alternativa ho fatto, che restituiscono una stringa.

non mi importava circa le prestazioni della cosa in quanto non fosse stato per un vero e proprio scenario del mondo.

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