Thread: Help : Brute Force String KeyGen

  1. #1
    Registered User
    Join Date
    Mar 2002
    Posts
    2

    Question 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

  2. #2
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    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;
    }
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  3. #3
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,138
    void logCombination(std::string cur)

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

  4. #4
    Unregistered
    Guest
    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?
    	}
    }

  5. #5
    Registered User
    Join Date
    Mar 2002
    Posts
    2

    Thumbs up

    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

  6. #6
    Registered User
    Join Date
    Dec 2001
    Posts
    421
    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
    U.
    Quidquid latine dictum sit, altum sonatur.
    Whatever is said in Latin sounds profound.

  7. #7
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    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).
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  8. #8
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,138
    Why did you use std::string as a parameter to a function when you already declared using namespace std?

  9. #9
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    Overkill .

    I put the std:: there first, and the added the using namespace later.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  10. #10
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,138
    OK. Sorry about that, it was just confusing me.

  11. #11
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    > 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;
    							}
    						}
    					}
    				}
    									
    			}
    		}
    		
    		
    	}
    }

  12. #12
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    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.
    Last edited by SilentStrike; 03-11-2002 at 09:05 PM.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. char Handling, probably typical newbie stuff
    By Neolyth in forum C Programming
    Replies: 16
    Last Post: 06-21-2009, 04:05 AM
  2. We Got _DEBUG Errors
    By Tonto in forum Windows Programming
    Replies: 5
    Last Post: 12-22-2006, 05:45 PM
  3. Classes inheretance problem...
    By NANO in forum C++ Programming
    Replies: 12
    Last Post: 12-09-2002, 03:23 PM
  4. creating class, and linking files
    By JCK in forum C++ Programming
    Replies: 12
    Last Post: 12-08-2002, 02:45 PM
  5. Warnings, warnings, warnings?
    By spentdome in forum C Programming
    Replies: 25
    Last Post: 05-27-2002, 06:49 PM