Re: How easy it is to solve "classical" crypto?

From: Jim Gillogly (jim_at_acm.org)
Date: 08/26/04 

Date: Thu, 26 Aug 2004 02:22:33 GMT

On Thu, 26 Aug 2004 04:32:00 +0300, Markus Jansson wrote:
> Lets take an example. How easy or hard would you say it is to solve (get
> the plaintext message) a message written in english (lets say about
> 10000 letters long), encrypted first with Vigenere (lets say you dont
> know the key lenght), then with Hill cipher (lets say you dont know the
> table size or content), and again with Vigenere (lets say you dont know
> the key lenght). And after this, unknown amount of random letters is
> added to the beginning and the end of the message. And yes, the Vigenere
> keys would not be more than, lets say, couple hundred letters maximum.
>
> Any suggestions or guesses?

For this exposition, ignore the random letters at fore and aft -- you
can throw a bunch away and try again without loss of generality. If the
first Vig key is (say) 100 letters long and we have (say) 8000 letters
total, we have 80 periods, so we're likely to have good long repeats in
this. These repeats (except perhaps for beginning and end) will still
be repeats after running them through the Hill cipher if they're lined
up at the beginning of the Hill's block size. A 2x2 Hill is a manual
cipher only under the most liberal of definitions, and a 3x3 is slightly
ridiculous by hand, so I think we don't need to consider anything higher --
if you're encrypting it with a computer you might as well *really* stump
him with a hard cipher, like the Solitaire cipher my friend Mark left
for me in my guest book after using my condo. Still haven't cracked it.

Anyway, there should be a good number of repeats in the Hill output.
This suggests a potential evaluation function for the Vig 2 step:
hill-climb to the key that gives the best set of repeats for the
intermediate Hill output. Since we don't know the length, we could
(for example) just start with the lowest and keep increasing it until
we start getting good repeats. Note that this is independent of the
random garbage on front and back... we're only interested in the
repeating bits.

Use the same kind of evaluation function to solve the Hill: when we get
it right we'll see not only the repeats that bled through the first two
stages, but also the ones for which the Hill block size led to offsets
in the repeats -- that is, we may see "-t he" and "th e-" as parts of
different repeats in the Hill output, but they'll be combined in the
Vig 1 output when the correct Hill matrix is discovered.

The final Vig 1 step would go the usual way.

> Id like to think it would be hard but I doubt. You can somehow still
> calculate the Vigenere key lenght and do all the voodoo magic to get the
> frequences etc. in place and finally solve the cipher I guess. But
> doesnt the two independent Vigenere keys (with possibly carefully
> chosen, different lenghts) mess it up? Or the Hill cipher in between
> those two?
>
> Im just curious, I've encrypted such message and wondering will my
> friend be able to crack it open easily or will it take some time
> atleast. ;) Or, do you have any suggestions on how to make it more
> secure still using only "classical ciphers"?

It'd be hard enough that I'd need to have a really good reason to attack
it. It's probably harder than it looks above, because there are
always false steps as you get one of the keys a little wrong, or
something accidentally extends one of the evaluation function strings
due to sheer chance.

Other kinds of combined ciphers would be harder -- think about combining
substitution, fractionation and transposition in one cipher, preferably
without clear fault lines between them. But once you get that elaborate,
you might just as well be using a *good* cipher on your Palm. 

-- 
	Jim Gillogly

Relevant Pages