Solved

Basic Cryptograhy Challenge

Posted on 2004-04-03
20
936 Views
Last Modified: 2007-12-19
The text file below contains a large English text and has been encrypted using atbash, transposition and vigenere in the following order

TEXT FILE: http://www10.brinkster.com/divet/januscipher.txt

Transposition
Atbash
Vigenere
Vigenere (different key)

The object of this challenge is to break the encryption and reveal the original english text.

The only hint I was given was that the transposition key has the length of a prime
-------------------------------------------------------------------------------------------------------

From working on this myself I know that even if the keylengths are known a bruteforce approach would not be
feasible in this lifetime.
There is a trick behind solving this puzzle.
I am assuming that it involves a more advanced knowledge or experience using these ciphers than I posess.
Any help or insight would be appreciated.

Please note that I understand how the ciphers work so no links or explainations are required just insight into how they work together to provide clues to the solution.

Thanks!
0
Comment
Question by:aaronCS
  • 9
  • 6
  • 5
20 Comments
 
LVL 13

Expert Comment

by:danblake
Comment Utility
I am going to give you some good news... Friedman (1973-- Britanica Encyclopedia) said that every example of 25 or more characters can be solved.
http://www.xmethods.net/  has a Vigenere decipher engine.

There is a trick behind solving this puzzle -- Normally yes.

You can alternativly attempt a letter frequency analysis to get what the most likely values are for the key-vowels/then for key-constants (do you have a letter frequency analysis table for the english language ?)

I can provide one, let me know.
0
 
LVL 13

Expert Comment

by:danblake
Comment Utility
The only hint I was given was that the transposition key has the length of a prime
-- This makes all primes < 26 viable.

So the only values for the vigenere are: (with two different keys..)
1, 3, 5, 7, 11, 13, 17, 19, 23.

Here are some hints...
http://www.cs.uwaterloo.ca/High_School_Liaison/Institute2002/resources/Resources/Tam_Aloysius/CodeandDecode.doc
0
 

Author Comment

by:aaronCS
Comment Utility
If my original link doesnt work please use this one: http://www10.brinkster.com/divet/januscipher.html
0
 

Author Comment

by:aaronCS
Comment Utility
Thanks for your response danblake.
I have read about frequency attacks and the weaknesses of Vigenere cipher.  However, since there are 4 ciphers used of which the characters are changed wouldnt that make frequency attacks useless?
I am told that there is a simple, logical method for solving this puzzle without and type of brute force attempts.
Have any more suggestions?
0
 

Author Comment

by:aaronCS
Comment Utility
After some more research I have found that the use of two vigenere ciphers is the same as using one vigenere cipher with a key length equal to the lowest common product of the two original keys.

What approach would i take to solving this puzzle?
0
 
LVL 17
Comment Utility
It's been a while since I have done one of these, but as far as I remember you need to identify the key length.
In a long section of text, there is a fairly good chance that a common word will be repeated several times, and a chance that this word will fall more than once at a distance equal to the key length (or the combined key length in this case). Whatever has been done to each character it will end up with the same offset if it falls at the same relative position (doesn't have to fall at the beginning of the key, just somewhere in it).
For instance in your text you have (if my program still works) the letters 'VLRN' appearing at position 2673 and again at 2685 (12 apart), also 'RLP' appearing at positions 3857 and 3869, again 12 apart. Several other repeats happen at differences of multiples of 12 so this could be a place to start. Take every twelvth character and count the appearances of each character in this subsection - if 12 is the right key length then the letters should appear in relative quantities to their representations in general English text. ie the most common is usually e, followed by t, i, o, n, s. The character that appears most often in the 12th character substring could represent 'e' etc. You will need to do this 12 times to find the other subsets representations.
If it was a keylength of 12 and you are not far off in your guesses for each character, placing the 'decoded' text over the original CT string ought to produce a few recogniseable words that you can fill in some gaps of and these will gradually give you keys to the entire text. You don't need to know the enciphering keys at each stage, just the effect that all of them had on the result.
      
0
 
LVL 17
Comment Utility
I found a nice looking vigenere breaker here(down the bottom of the page):
http://math.ucsd.edu/~crypto/java/EARLYCIPHERS/Vigenere.html

and the site also has a monoalphabetic substitution breaker:
http://math.ucsd.edu/~crypto/java/EARLYCIPHERS/Monoalphabetic.html

Good news is that using the vigenere program, the periodicity certainly looks like 12, with two little problems.
1) I can't make 12 from a multiple of primes.
2) Using the tool, the character frequencies look good at 12, but there seems to be an offset around the middle of the alphabet. E and I peaks line up quite nicely, but the RST triple and the NO double seem to be shifted as if they are reversed - is that the atbash? I thought that was just a reversed vigenere block.

Bad news is that it's obiously not that simple. I thought that a combination of vigenere keys would give the same result as one long one - any ideas?
0
 
LVL 13

Expert Comment

by:danblake
Comment Utility
Still watching, and thinking..
0
 

Author Comment

by:aaronCS
Comment Utility
Thanks for the replies guys.
I have made some more progress on this cipher.  After doing some preliminary tests I have found that when you apply the vigenere cipher twice to the same text you can decipher the message with just one key.  The key length of this "skeleton key" will be the lowest common product of the two individual keeps.
RobinD suggests the period of this skeleton key to be 12.  This makes sense since the two keys used could be 3 and 4 letters in length (it is just a challenge so this makes sense).
Again based on what RobinD said "..seem to be shifted as if they are reversed.".  This would be the result of an atbash cipher.  Atbash is a substitution cipher.

ABCDEFGHIJKLMNOPQRSTUVWXYZ   <--- MESSAGE
ZYXWVUTSRQPONMLKJIHGFEDCBA   <--- ATBASH

The first character in the alphabet is switched with the last character, the second character is switched with the second last letter, etc....

When I applied a frequency analysis to text my atbash decipher program produced I found a promising result.  The graphs match almost PERFECTLY with a key of "AKZWPSCLXVRT".  Which has a period of 12 as RobinD predicted.  Now that we have solved 3 of the 4 encipherings we are now left with the last transposition cipher.  For that we need a key with a length of a prime (as given as the hint).

I will be trying a few methods.  If you have any ideas please let me know.  We are so close! ;)
0
 
LVL 17
Comment Utility
I'm a little unsure of AKZWPSCLXVRT as a key. When I applied this I got a string that comes out with an 'index of coincidence' of 0.04008 which is a bit too flat for most languages. English should produce an i.c. of about 0.0661 and most European languages are 0.07 or higher.

index of coincidence is found by counting all the characters and then applying the formula (numberOfChar x numberOfChar-1)/(wholeStringLength x wholeStringLength-1) for each character and then summing all the  results. For a proper measurement you are supposed to take a string of the expected language of about the same length as the encrypted string.
This expects that only a monoalphabetic transposition has been used (one Code character replaces one plaintext) but it doesn't matter whether the replacements are a single shifted alphabet or a shuffled up one. The code doesn't even have to be alpabetic characters, could be any symbol you like as long as the replacements are one for one. It can be a fairly good guide to what language you are trying to decode.
I get a 'good' i.c. for all 12 strings built by taking every 12th character, but haven't got very much further at the moment.

*All my rambling in this post above here comes out with an i.c. of 0.06536 - it's nearly English :7)
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 13

Expert Comment

by:danblake
Comment Utility
@RobinD,

Isnt' the coincidence going to depend on the level of the text/writing ?
A college-thesis may score a lower rating than a normal piece of prose or text for example a quotation from the bible ?
0
 

Author Comment

by:aaronCS
Comment Utility
Hey you guys bring up some good points.  I am confident that the original message is in english and may contain certain slang type words which would affect the index.  It is possible that the cipher has "traps" to throw off such analysis.  

To illustrate what I was saying before check out this text.
http://www10.brinkster.com/divet/januscipher-atbash.txt

It contains the cipher text after it has been run through the atbash cipher.

Copy that text and paste it into the frequency analysis applet that robind posted:
http://math.ucsd.edu/~crypto/java/EARLYCIPHERS/Vigenere.html

Play around with it for a bit if you want.  The best match will come with a period of 12 and the letters: "AKZWPSCLXVRT".
0
 
LVL 17
Comment Utility
>Isnt' the coincidence going to depend on the level of the text/writing ?
Yes, you are supposed to use a piece of 'equivalent' text. If you are trying to decipher something that you believe to be old english then use a bit of shakespear, or use a bit of someones thesis or some Mark Twain - all depends what you are looking for. But these variations don't change the i.c. a great deal - apparantly you can almost identify an author. This is a way of measuring someones writing style. Obviously there are variations, but it can be a very good guide. My rambling above did contain aaronCS's suggested key.
Incidentally, taking every second letter from the text will produce almost exactly the same i.c. as did the full text - or every twelvth letter etc. It just measures the relative quantities of each letter.

I withdraw my complaint about AKZWPSCLXVRT, after the atbash that text gives an i.c. of 0.06559, that looks much more like English. And it certainly matches up better with the vigenere tool than the original did.

Should be easy now :7)

*i.c. of above = 0.0669 (You probably need a longer bit to identify an author)
0
 
LVL 17
Comment Utility
aaronCS,
What did you do to that ciphertext?
After using the vigenere tool the frequency analysis comes out with E being the most common letter, followed by T, A, O, N, I, S, H - (see my earlier post).

It's English now I'm sure of it, just that all the letters seem to be in the wrong order.
I wonder if that could be an effect of using the vigenere tool incorrectly -  You tend to force the decryption into a pattern that you want to see and that will change the letter frequencies depending on which offsets you pick.
0
 
LVL 17
Comment Utility
This seems quite useful (not got anywhere yet though):

http://www.richkni.co.uk/php/crypta/trans0.php
0
 
LVL 17
Comment Utility
Wa-HHEY!!!!

'I met a traveler from an antique land'

 *****my nameiso zymandi askingo fkingsl ookupon myworks yemight yanddes pair***

That should be all the clues you need !
0
 
LVL 17

Accepted Solution

by:
Thibault St john Cholmondeley-ffeatherstonehaugh the 2nd earned 500 total points
Comment Utility
aaronCS,

Just found a password buried in there, not too far from the top.
0
 
LVL 17
Comment Utility
Thanks aaronCS,

'twas fun if a little time consuming. There's a great feeling when you can finally read what was there.

you might find this interesting:
http://www.biblion.com/litweb/biogs/shelley_percy_bysshe.html

word for word except the dates and the phrase 'shelley was considered with his friend lord byron a pariah for his lifestyle'

Interesting effect the atbash has and how you can remove it either before or after the vigenere.
Had me confused when I saw the graph seeming to be reversed, I thought the character count wouldnt be affected by that , there are still the same number of characters representing the letter E even if they happen to be V's, reversed it was though.
0
 

Author Comment

by:aaronCS
Comment Utility
Youre right it is very rewarding to be able to make sense out of apparent chaos.


The effect of the atbash is quite interesting.  I wouldnt have thought it would behave so nicely like it did.  But there is a logical explaination for it.  Since atbash is just a substitution cipher the location of each character doesnt change.  The vigenere cipher then shifts each character by a fixed amount determined by the keyword.  

If a message contains characters we can label them as follows...
C1 C2 C3 C4 C5 .... Cn

now if you apply an atbash cipher it is the same as doing the following where c is the location of the letter in the alphabet (a = 1, b =2, ..., z=26)

Atbash: a( C ) = 27 - C


So our message would now look like this:
(27 - C1) (27 - C2) (27 - C3) (27 - C4) (27 - C5) ... (27 - Cn)

Now the vigenere cipher can be defined as this, where c is the location in the alphabet and i is the location in the key
Vigenere: (c + k(i) - 1) % 26  

If we apply that to our message we basically get
(26 - C1 + ki) (26 - C2 + ki) (26 - C3 + ki) (26 - C4 + ki) (26 - C5 + ki).... (26 - Cn + ki)

So it is obvious now that we can remove the atbash and be left with just the vigenere.

0
 
LVL 13

Expert Comment

by:danblake
Comment Utility
;)
0

Featured Post

Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Roulette strategy probability question 58 82
Relative Frequency Assessment 2 27
Discrete Values 2 39
Dice Roll Probabilities 3 51
Complex Numbers are funny things.  Many people have a basic understanding of them, some a more advanced.  The confusion usually arises when that pesky i (or j for Electrical Engineers) appears and understanding the meaning of a square root of a nega…
How to Win a Jar of Candy Corn: A Scientific Approach! I love mathematics. If you love mathematics also, you may enjoy this tip on how to use math to win your own jar of candy corn and to impress your friends. As I said, I love math, but I gu…
Get a first impression of how PRTG looks and learn how it works.   This video is a short introduction to PRTG, as an initial overview or as a quick start for new PRTG users.
This tutorial demonstrates a quick way of adding group price to multiple Magento products.

763 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now