Prev: Need help decoding cipher
Next: DRM2WMV
From: Rohan on 10 Mar 2005 05:11
Greetings,

I have done quite a bit of searching but without much success, but forgive
me if this is the wrong place to ask.

I have a the ciphertext of an incomplete columnar transposition cipher that
I am trying to break. I know the row length is within a given range and I
have known word of plaintext that starts with a letter which only occurs
once in the ciphertext.

I have already constructed hat diagrams for each of the row lengths and here
is my strategy for the next part:

Take the column of the hat diagram containing the first letter of the known
plaintext and then select a column with the 2nd letter of the known
plaintext and line them up so the two letters are adjacent. Then for each
of the digraphs so created check its frequency of occurrence in English.
Then pick the column with the most number of high frequency digraphs and add
a 3rd column in the same way - wash, rinse and repeat for the 4th, 5th 6th
letter etc.

Now here's are my questions: Is this a sensible way of going about it? I
know there are shortcuts if the known
plaintext is at the very start of the message, and if the known plaintext is
longer than the row (key) length but neither is true in this case. Is there
a program out there somewhere to do the above process, if that is indeed the
right way about it? There seem to be many for complete columnar
transposition but I have not been able to find any for incomplete.

Yes this is for a school assignment, but it is for beer (yes, really!) not
marks and the challenge says that any help can be obtained from anybody!

Here's the odd thing: the task was not set in a programming class (they are
after the ability to think these things through, rather than the ability to
program them, hence me trying to find a program already out there), so I
still have at the back of my mind that I have missed a trick and it can be
broken manually without many many hours of work.

any pointers would be fantastic

Rohan


From: Jim Gillogly on 11 Mar 2005 04:50
On Thu, 10 Mar 2005 10:11:11 +0000, Rohan wrote:
> I have a the ciphertext of an incomplete columnar transposition cipher that
> I am trying to break. I know the row length is within a given range and I
> have known word of plaintext that starts with a letter which only occurs
> once in the ciphertext.
>
> I have already constructed hat diagrams for each of the row lengths and here
> is my strategy for the next part:
>
> Take the column of the hat diagram containing the first letter of the known
> plaintext and then select a column with the 2nd letter of the known
> plaintext and line them up so the two letters are adjacent. Then for each
> of the digraphs so created check its frequency of occurrence in English.
> Then pick the column with the most number of high frequency digraphs and add
> a 3rd column in the same way - wash, rinse and repeat for the 4th, 5th 6th
> letter etc.
>
> Now here's are my questions: Is this a sensible way of going about it? I

Sounds like a good start. You can snip up your hat diagram
with physical scissors so you can shift the letter columns
around easily to play with them. Don't count on the correct
adjacent column to be the one with the highest value for the
digraphs if you don't have a good long collection of rows --
with small samples you get statistical fluctuations. It's
also useful to tentatively rule out column adjacencies that
produce too many impossible digraphs.

Once you get to the third column it should look cleaner -- pay
attention to the whole trigraph, not just the digraphs with the
adjacent column[s].

> know there are shortcuts if the known
> plaintext is at the very start of the message, and if the known plaintext is
> longer than the row (key) length but neither is true in this case. Is there
> a program out there somewhere to do the above process, if that is indeed the
> right way about it? There seem to be many for complete columnar
> transposition but I have not been able to find any for incomplete.

My program (which I don't share out) uses shotgun hillclimbing,
mutating the keys until the score stops increasing, then starting
over. I've described the algorithm at length a few times, so
Googling the news or web should turn it up. Interestingly, it
even works with double incomplete columnar transposition without
cribs... but doesn't translate well to manual solution.

I imagine there are programs available that do it, but I haven't
gone looking for them since I'm happy with my own... I'm currently
doing just this task with a large set of incomplete columnars
written by IRA members in the 1920's.
--
Jim Gillogly

 | 
Pages: 1
Prev: Need help decoding cipher
Next: DRM2WMV