Beefy Boxes and Bandwidth Generously Provided by pair Networks
Come for the quick hacks, stay for the epiphanies.
 
PerlMonks  

Re: CipherText

by Steeeeeve (Initiate)
on Jul 17, 2001 at 09:02 UTC ( [id://97253]=note: print w/replies, xml ) Need Help??


in reply to CipherText

This node falls below the community's threshold of quality. You may see it by logging in.

Replies are listed 'Best First'.
Re: Re: CipherText
by no_slogan (Deacon) on Jul 23, 2001 at 11:18 UTC
    The cipher period is diffused to N*(N-1) message elements (where N is key length.) This significantly reduces data available for frequency analysis so that a 2K textarea window can be protected with a 15 character key if it is assumed that more than 5 key periods are required for analysis.
    Frequency analysis is not the only way to attack a cipher. A message encrypted with this system can be broken easily in only 2 key periods. Simply XOR the first N*(N-1) characters with the second N*(N-1), which removes the key entirely and leaves the difference of two chunks of plaintext. Using common words like "the" and "and" as a crib quickly produces enough of the original message for the key to be discovered.

    What if you don't know the key length to start with? Some well-chosen shifts and xors expose the redundancy in the N*(N-1) period, allowing it to be attacked with frequency analysis as though it had a length of only N+(N-1). I'll post the details if anyone cares. Once you have the key length, proceed as described above.

    And who am I? Not a professional cryptographer. I'm sure they have even better techniques. I'm a green amateur, armed only with what I've come up with over the course of the past week.

        
      A message encrypted with this system can be broken easily in only 2 ke +y periods
      That's not quite true. As you said, having only two key periods of message length means that when you XOR the two encrypted segments together, you are left with the XOR of the two plaintext segments. This is not usually enough information to reconstruct the original plaintext message, unless advanced statistical techniques enter the picture. To see why, consider that:
      ("case" ^ "hook") eq ("gone" ^ "lark")
      This is not an isolated case either, it's just the first I came up with after not more than a few minutes of randomly poking around with XOR.

        
      What if you don't know the key length to start with? Some well-chosen +shifts and xors expose the redundancy in the N*(N-1) period, allowing + it to be attacked with frequency analysis as though it had a length +of only N+(N-1).
      I'm not sure what you mean by attacking as though length was N+(N-1). You can reduce a double XOR of lengths N and N-1 to solving for N+(N-1) if you have known plaintext of that length, but I'm not aware of any other attacks that reduce the problem in that way.

      To find an unknown key length, however, is trivial. The standard technique for discovering an unknown key length is to try XORing the text against itself shifted at various distances, until you see a spike in the index of coincidence. The lowest common multiple of the spiked distances is then your key length.

      I'm not a professional cryptographer either, but I like to play one on perlmonks.com ;-)

         MeowChow                                   
                     s aamecha.s a..a\u$&owag.print
        This is not usually enough information to reconstruct the original plaintext message, unless advanced statistical techniques enter the picture.
        Fortunately, you don't have to reconstruct the entire plaintext message from the two chunks of xored text. About 2N characters, not necessarily contiguous, is enough to start attacking the two original xor keys. It's pretty easy (and kind of fun) to do that much by eye. Just write a little perl script to plug in some common words, and see if what comes out looks like English text. Sometimes you'll guess wrong, but once you get three or four words that form a sensible phrase, things start looking pretty certain.
        The standard technique for discovering an unknown key length is to try XORing the text against itself shifted at various distances, until you see a spike in the index of coincidence. The lowest common multiple of the spiked distances is then your key length.
        Your method is probably better than mine. Told you I was an amateur.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://97253]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others surveying the Monastery: (4)
As of 2024-03-29 01:57 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found