Help : Brute Force String KeyGen

I am currently making a general purpose tool for cracking a vigenere cipher as part of a project. At the moment, I have coded functions to find the index of coincidence, determine an estimated length of the keyword and also give suggested relative distances of letters that make up the keyword (in a nutshell -> the Kasiski Attack)

I want to be able offer a brute force attack as a last resort if a combination of all other information given fail to produce anything fruitful.

If anybody can help me to point me in the write way to code a function that would generate all combinations of 26 letters in a string of length 1 to a string of length n.

i.e.

"A"
"B"
"C"
.
.
.
"X"
"Y"
"Z"
"AA"
"AB"
"AC"
.
.
.
"ZZZZZZZZZZZ"

I hope I've managed to explain myself properly. If not, look at it in terms of counting up from 1 to, say, a million but with letters A-Z rather than the numbers 0-9.

Any help/links will be greatly appreciated.

~Tangy

Code:

---

#include <iostream>
#include <string>

using namespace std;

const int MAX_STRING_LENGTH = 3;

void logCombination(std::string cur) {
        if (cur.length() > MAX_STRING_LENGTH) return;
        cout << cur << endl;
        for (char currentChar = 'A'; currentChar <= 'Z'; currentChar++) {
                string temp=cur;
                temp+=currentChar;
                logCombination(temp);
        }
}


int main() {
        logCombination("");
        return 0;
}

---

void logCombination(std::string cur)

Do you need the std:: ? You already included the using namespace std.

could someone explain this to me line by line?

Code:

---

void logCombination(std::string cur) {
        if (cur.length() > MAX_STRING_LENGTH) return; //and what would cur.lenght() be?
        cout << cur << endl;//what is cur?
        for (char currentChar = 'A'; currentChar <= 'Z'; currentChar++) {
                string temp=cur;
                temp+=currentChar;//what is the variable temp?
                logCombination(temp);//why do you use recursion on this function?
        }
}

---

SilentStrike,

Thanks for the neat piece of code, it does just the trick with the added bonus of being recursive!

You're a star! :)

~Tangy

with the added bonus of being recursive!

recursion is good.. but for really big strings it'll be bloody slow.

loops are generally quicker.. but can make the code hard to read... recursion makes code easier to read but it generally slower.

thanks for listening :D
U.

Basically this works by starting with no string at all, outputting it, the appending the letter A-Z to it. Each time a letter is appeneded, it recursively addes another series of A-Z. You can set MAX_STRING_LENGTH to 2 and see the pattern it produces fairly easily.

It's recursive because that's the first way it came to me to solve it. If anyone wants to post an iterative solution (especially one that does more than explictly manage a stack), I'd be happy to see it... It's just that I found the recursive solution a lot easier to do.

"In order to understand recursion, one must first understand recursion "

If this were true, then one could never understand recursion, unless they had already understood it. Recursion can be learned by first assuming it works, and then proving it does (IE, proof by induction).

Why did you use std::string as a parameter to a function when you already declared using namespace std?

Overkill :).

I put the std:: there first, and the added the using namespace later.

OK. Sorry about that, it was just confusing me.

> If anyone wants to post an iterative solution (especially one that does more than explictly manage a stack), I'd be happy to see it...

An alternative would be nested for loops with a conditional statement checking how deep to go based on the MAX_STRING_LENGTH. It'd get really ugly if you had to check for long strings but it wouldn't choke as easily. I got board at four nested loops -

Code:

---

void logCombination() {
        string cur="A";
        for(int i=0;i<26;i++)
        {
       
                cur[0]='A'+i;
                cout << cur[0] << endl;
       
               
        if(MAX_STRING_LENGTH>1)
                {
                        if(cur.length()<2)
                                cur+='A';
                       
                        for(int j=0;j<26;j++)
                        {
                                cur[1]='A'+j;
                                cout << cur[0] << cur[1] << endl;               
                                if(MAX_STRING_LENGTH>2)
                                {
                                        if(cur.length()<3)
                                                cur+='A';

                                        for(int k=0;k<26;k++)
                                        {
                                                cur[2]='A'+k;
                                                cout << cur[0]<<cur[1]<<cur[2]<<endl;
                                                if(MAX_STRING_LENGTH>3)
                                                {
                                                        if(cur.length()<4)
                                                                cur+='A';
                                                        for(int l=0;l<26;l++)
                                                        {
                                                                cur[3]='A'+l;
                                                                cout << cur[0]<<cur[1]<<cur[2]<<cur[3]<<endl;
                                                        }
                                                }
                                        }
                                }
                                                                       
                        }
                }
               
               
        }
}

---

Heh, nice. How about a readable non-recursive (for arbitrary N) (at least.. not running time recursive) solution?

Got that covered :).

Code:

---

#include <string>
#include <iostream>
#include <ctime>

using namespace std;

template <int N> struct logCombination {
        static void log(string cur) {
                for (int i = 0; i < 26; i++) {
                        string temp = cur;
                        temp+='A' + i;
                        cout << temp << endl;
                        logCombination<N-1>::log(temp);
                }
        }
};

template <> struct logCombination<0> {
        static void log(string cur) { }
};

int main() {
        size_t start = time(NULL);
        logCombination<4>::log("");
        cout << time(NULL) - start << endl;
        return 0;
}

---

It took 12 seconds this way, (12 seconds for Sorensen's as well) as opposed to 19 seconds with my recursive solution. This has been an interesting thread.. for me at least. Perhaps the Code Journal should have like a "Thread of the Week" where "the best" (most interesting, revealing, etc) is linked to from the journal.