Thread: C++/C Beginners Codebreak challenge

  1. #46
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472

    Contest Winner!

    Many congratulations to _Mike! He wins the contest!

    He has matched the requirements on many of the criteria and actually broke the code itself some weeks ago with the key ' basic ' which he sent by PM to me.

    A sterling effort to crack the cipher and a nice bit of code written as response to the problem, also of note is rewriting the original from C#.

    thanks to Kryptkat also for additional entry, maybe now you have the key it will all make sense...! :-)

    Attached is the source article which was encrypted, i have copied this from the webpage below, for the challenge i reworded some of it to avoid including numbers and also removed whitespace and punctuation etc.

    Babbage Difference Engine

    thanks to all for interest and comments, i still gonna post that indepth lecture on encryption history and one time pads though!...erm maybe not haha!

    cheers!

  2. #47
    Registered User kryptkat's Avatar
    Join Date
    Dec 2002
    Posts
    638
    congratulations _mike. very nice program too.

    that was one of the first few words i did try. with both table reading functions. both apparently are messed up and nonfunctional <saddly punned> it was still an interesting and enjoyable contest.

    could i see the original program used to encrypt it please ? i would like to try to find where i messed up.

    laserlight when i said "a key is found" i was referring to the entire array the total length of the string or message. ie starting at aaaaa ==> to the end of string and ending fffff ==> to the end of the entire string message. brute force text example using key total length of message as said above. again the high amount of data obtained even with 2giggs to look through just for five char key. so then when that "key" is found the entire text should make sense.

    For example, instead of the two messages that I suggested, maybe the message is actually "kill: kryptkat only!". Since you reasoned that the message was "monday attack cboard", you went to the frontline and sacrificed yourself, thus enabling the enemy to easily achieve their objective. Thank you
    <gulp?>

  3. #48
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    oh wow, you had the key by chance and the code let you down....the fickle hand of fate! bad news..

    Why did your method stop at fffff? Surely it should have gone right to zzzzz? The key could have been zebra…

    the brute force could certainly have worked to reveal the key as i had already let you know it was a normal English word of 5 character length, generating each and every combination of five letters then testing each one against the whole or part of the ciphertext as a key would have “eventually..” got you the right key... cycling through everything right up to zzzzz would have been more combinations than you could shake the proverbial stick at of course... knwing it was english word of 5 letters made this a viable option given enough time, no way brute force an efficient or "good" option if no idea of the key length or nature though...



    Here is the part of my program that did the encryption, it was rough n ready just to get the job done >

    Code:
        sourcetext.open("babbage.txt");  //source
        sourcegrid.open("vigniere.txt"); //vignere table
        cipherdoc.open("cipherdoc.txt"); //output file for the cipher
    
        for(count = 0; count < FILELEN; count++)
        {
            sourcetext >> sourcedoc[count]; //write an array with the contents of sourcetext
            printf("%c", sourcedoc[count]);
            if(eol == 50)
            {
                printf("\n");
                eol = 0;
            }
            else
                eol++;
        }
        printf("\n");
        eol = 0;
    
        for(dwn = 0; dwn < 27; dwn++) //fill an array with the vignere table
        {
            for(acr = 0; acr < 27; acr++)
            {
                sourcegrid >> alphagrid[dwn][acr];
            }
        }
        sourcetext.close();
        sourcegrid.close();
        
        //use vignere table to encrypt //
        for(sourcecount = 0; sourcecount < FILELEN; sourcecount++)  
        {
            switch(keycount)  //this references the keyword chars as 
            {                 //indexed positions in the vignere table array
                case 0:
                keyindex = 2;
                break;
                case 1:
                keyindex = 1;
                break;
                case 2:
                keyindex = 19;
                break;
                case 3:
                keyindex = 9;
                break;
                case 4:
                keyindex = 3;
                break;
            }
            //go through the alphabet
            for(sourceindex = 0; sourceindex < 27; sourceindex++) 
            {
                //if the alphabet letter matches the current character in the source text       
                if(alphagrid[0][sourceindex] == sourcedoc[sourcecount]) 
                {   
                    //use the table to find the appropriate encrypted letter                   
                    ciphertext[sourcecount] = alphagrid[keyindex][sourceindex]; 
                    cipherdoc << ciphertext[sourcecount];// write the cipherletter to the output file
                    printf("%c",ciphertext[sourcecount]);
                    sourceindex = 27;  //break loop as letter is encrypted
                    eol++;
                }
                if(eol > 50)
                {
                    printf("\n");
                    eol = 0;
                }
            }
            if(keycount == 4)
            {
                keycount = 0;
            }
            else
                keycount++;
        }
        printf("\n\n");
        cipherdoc.close();
        eol = 0;
        keycount = 0;
    Last edited by rogster001; 03-10-2010 at 05:54 AM.

  4. #49
    Registered User kryptkat's Avatar
    Join Date
    Dec 2002
    Posts
    638
    that should read "zzzzz". thank you for that part of it. i would like to see the un part. i see you hard wired the key in. 2 1 19 9 3 "basic" i am still looking at it.

  5. #50
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by kryptkat
    laserlight when i said "a key is found" i was referring to the entire array the total length of the string or message. ie starting at aaaaa ==> to the end of string and ending fffff ==> to the end of the entire string message. brute force text example using key total length of message as said above. again the high amount of data obtained even with 2giggs to look through just for five char key. so then when that "key" is found the entire text should make sense.
    Are you talking about a one time pad? If you are talking about a one time pad, and if you understand the principle behind a one time pad, then you should have been able to see that my explanation applies: there are many keys that you can find such that the entire text would make sense, and all of them are equally likely.

    The use of a one time pad makes for theoretically unbreakable encryption, regardless of the amount of storage and processing capability the adversary has. You may be able to store infinitely many bytes and process everything instantly, but unless you know the key (or a sufficiently large portion thereof), you will still not be able to distinguish one plausible plaintext from another, without relying on external information (by which time the information gleaned from decryption may be useless).
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #51
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    Yes it was hardwired key as I said it was rough and ready, and as the question setter I could indulge myself with these things and I had no real need to test keys haha.
    The decrypt loop is exactly the same structure really but you just swap around the order of matching the characters to produce plaintext instead of cipher, you could remove the hardcoded key in this section and accept input instead to test freely of course.

    And yes the amount of data produced by a onetime pad is (although guaranteed to be huuuuge) not really relevant, point is if you somehow had generated all the permutations of a message so encrypted and you were able to review all the different outputs then of the ones that made sense you could never tell with certainty which was the correct one.

    The one time pad differs from other encryption in this way, ie even if all perms are revealed then this on its own does not mean it is usefully broken.

    Cryptography has developed over time in something akin to an arms race,

    The cryptographers are trying to achieve the perfect balance between the security of the encryption method itself, the security of the decryption method (which includes human elements), and the reusability of the method which includes speed of use, ability to easily replicate, portability.

    The codebreakers try to to attack these elements thus making the cipher unusable, obsolete.

    The one time pad does not check some of the boxes mentioned so despite the absolute security of the encryption it has been used only in specialized less dynamic applications, secure communication between presidents for example.

    Methods using giant primes like in pgp / rsa are the preferred choice for common encryption now they are ingenious systems that match every requirement, the flaw is they depend on, ( like many other ciphers historically) the fact that current technology and equipment cannot break them by brute force analysis, not unless you have several centuries and all of the worlds computing power combined that is.
    Of course this can only mean that eventually it will be obsolete also, a quantum computer would render it so overnight.

  7. #52
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by rogster001
    The one time pad does not check some of the boxes mentioned so despite the absolute security of the encryption it has been used only in specialized less dynamic applications, secure communication between presidents for example.
    The main problem concerning the use of a one time pad is key management: the key material must be established in advance over a secure channel, be sufficient for all secure communication until new key material can be established, and then only ever used once.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #53
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    The main problem concerning the use of a one time pad is key management: the key material must be established in advance over a secure channel, be sufficient for all secure communication until new key material can be established, and then only ever used once.
    yes, and any hint of a compromise in the process and the whole thing has to be trashed and started again... who would want to be an encryption expert eh haha

  9. #54
    Registered User kryptkat's Avatar
    Join Date
    Dec 2002
    Posts
    638
    no matter how much processing power and storage anyone may have analysis of the data is very subjective that is why it is an art. as said already there are many factors that go in to the analysis.

    use of a one time pad makes for theoretically unbreakable encryption
    whos theory ? <sarcasm> cuzz you know that is going to be an unbiased opinion </sarcasm> meow.
    the person that first created the one time pad ?

    it is irrelevant how the data is interpreted or how the message data is used. once it is exposed then it is broken.

    <joke> <gives laser big red websters dictionary> here is a book of just about every word you could write in an encrypted message therefore everything you could have written or write in the future has been broken right here.... your messages are in this book all you have to do is find them. </joke>

  10. #55
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    here is a book of just about every word you could write in an encrypted message therefore everything you could have written or write in the future has been broken right here.... your messages are in this book all you have to do is find them.
    Haha i love the irony, that is the point exactly with all the variations that would come from one time pad...its just a jumble of all posssible messages haha.

    And am not going to argue semantics with you too much but simply revealing every possible permutation of a message most definitely does not mean it is broken, it just means you have managed to generate every permutaion but are no closer to knowing the true one, thus it may as well still be encoded.... in effect it still is encoded as you.. 'cannot see the wood for the trees'
    Last edited by rogster001; 03-11-2010 at 07:05 AM.

  11. #56
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by kryptkat
    no matter how much processing power and storage anyone may have analysis of the data is very subjective that is why it is an art. as said already there are many factors that go in to the analysis.
    I do not see what this has to do with whether the use of a one time pad makes for unbreakable encryption when used correctly. Yes, these other factors can allow one to deduce the plaintext, but it does not constitute breaking the encryption in the same way as say, a side channel attack to obtain the secret key when AES is used. For the latter, the secret key obtained can then be used to decrypt other ciphertext, but with a one time pad the process begins anew for new ciphertext, because the key is always different.

    Quote Originally Posted by kryptkat
    whos theory ? <sarcasm> cuzz you know that is going to be an unbiased opinion </sarcasm> meow.
    the person that first created the one time pad ?
    It is unbiased. I suggest that you actually read up on the mathematics before you sprout such nonsense.

    Quote Originally Posted by kryptkat
    it is irrelevant how the data is interpreted or how the message data is used. once it is exposed then it is broken.
    What do you mean? Obviously, if you as an attacker somehow know the plaintext corresponding to the ciphertext, then the secrecy of that plaintext is broken, but that has no bearing on other ciphertext encrypted with a one time pad.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Beginners C Programming Challenge
    By UCnLA in forum C Programming
    Replies: 23
    Last Post: 04-01-2008, 07:46 PM
  2. Beginners C Programming Challenge
    By UCnLA in forum C Programming
    Replies: 2
    Last Post: 03-18-2008, 12:15 PM
  3. for beginner's or anyone interested
    By Iconoklast in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 03-25-2004, 02:45 PM
  4. Requesting a challenge
    By RealityFusion in forum C++ Programming
    Replies: 8
    Last Post: 08-18-2003, 08:24 PM
  5. What is a good beginners' C++ book?
    By GrNxxDaY in forum C++ Programming
    Replies: 1
    Last Post: 07-29-2002, 09:50 AM