6
$\begingroup$

I have computed the keyword length using I.C. but I don't know how to derive the first keyword. This polyalphabetic cryptogram requires two keywords to break, but I am not sure how to get either of them. Could someone please explain or point me to a resource where I can learn this? I have not been able to find anything related to it at all.

$\endgroup$
  • 2
    $\begingroup$ Can you give more information about the cipher you're trying to break (and an example if you have one)? The title says "keyword transposition cipher", but the question says "polyalphabetic cryptogram". A cryptogram is not a transposition cipher. If the message is encrypted using both a polyalphabetic substitution cipher (like Vigenere) and a keyword transposition cipher, and you know neither keyword, your chances of decrypting are extremely slim, since the transposition messes with any kind of word pattern or keyword length detection, and the substitution messes with letter frequency. $\endgroup$ – GentlePurpleRain May 18 '17 at 15:08
9
$\begingroup$

NOTE: This is a guide to solving polyalphabetic cryptograms as it says in the question, and not transposition ciphers like it says in the title

This is called cryptanalysis. Defined as

'the art or process of deciphering coded messages without being told the key.'

There are different methods and different results. It depends what you are looking for and what's good enough for you. You could achieve a:

  • Total break — you work out the key and the plaintext.
  • Global deduction — you discover the method of encryption and manage to find the plaintext, but not the key.
  • Distinguishing algorithm — you identify the cipher from a random permutation.

There are also two types of ciphers:

  • Symmetric - one key used
  • Asymmetric - two keys used (one public, one private)

You have an asymmetric cipher, which of course is harder to break. However you don't know any of the keys, just the length.

There are a couple of different ways to solve such ciphers:

Lets take a look:


Frequency Analysis

Facts

This is one of my favourite ways of cracking ciphers, although it really only works best with substitutional or rotational ciphers, though both of those can have keys. Frequency analysis is the study of the frequency of letters or groups of letters in a ciphertext, which can then be used to help deduce what certain letters are.

Computers have calculated that in the english language, the order of the most frequent letters from high to low is etaoinshrdlcumwfgypbvkjxqz.

Here is the stats for analysis on the english language in brief below and all ordered from high to low:

  • Unigram frequency: etaoinshrdlcumwfgypbvkjxqz
  • Bigram frequency: th, he, in, en, nt, re, er, an, ti, es, on, at, se, nd, or, ar, al, te, co, de, to, ra, et, ed, it, sa, em, ro
  • Trigram frequency: the, and, tha, ent, ing, ion, tio, for, nde, has, nce, edt, tis, oft, sth, men
  • Quadrigram frequency: that, ther, with, tion, here, ould, ight, have, hich, whic, this, thin, they, atio, ever, from, ough, were, hing, ment

Note: Quadrigrams and Trigrams are less effective on shorter ciphertexts, and even bigrams and unigrams can be unreliable for really short ciphertexts to a point where there is no use

And of course you gotta include a few graphs (courtesy of wikipedia):

enter image description here enter image description here

As you can see, 'e' is by far the most frequent letter. 't' - 'r' is a lot closer.

For simple substitutions, there are some more very useful pieces of information (still higher to lower):

If spaces are included in the ciphertext:

  • Single letter words must be A or I
  • Two letter words nearly always have 1 vowel, 1 consonant. Most common: OF, TO, IN, IS and IT
  • Three letter words: THE, AND, FOR, WAS and HIS
  • Double letters in words are in order of frequency usually LL, EE, SS, OO and TT (there are others)

If punctuation is included:

  • Letters after apostrophes are most likely to be S, T, D, M, LL or RE

Application of facts

If you know that the text is a substitution, and the ciphertext is quite large, then you can use the above facts to try and break the cipher.

Using an online tool such as this, you can find the most common letters and most frequent substrings.

The most frequent letter in the ciphertext is probably 'e', and so on.

Using this you can break a cipher, or get a plaintext which you can then deduce the correct plaintext.

Example

Example found online here. This is a known rot cipher, but we don't know what number:

ymnxhtzwxjfnrxytuwtanijdtzbnymijyfnqjipstbqjiljtknrutwyfsyyjhmstqtlnjxfsifuuqnh fyntsymfyfwjzxjinsymjnsyjwsjyizjytymjgwtfisfyzwjtkymnxknjqiymjhtzwxjhtajwxtsqdx jqjhyjiytunhxkthzxxnslknwxytsxtrjfiafshjiytunhxnsnsyjwsjyyjhmstqtlnjxjlbnwjqjxx qfsxrtgnqjnsyjwsjyrzqynhfxyfsiymjsfxjqjhyntstkhzwwjsyfsisjcyljsjwfyntsfuuqnhfyn tsxfsixjwanhjxjluunuyaatnudtzbnqqqjfwsmtbymjnsyjwsjybtwpxfsimtbxjwanhjxfsifuuqn hfyntsxfwjuwtanijiytzxjwxtkymjnsyjwsjyymnxpstbqjiljbnqqmjqudtz

Frequency analysis:

a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
8  9  1  4  0  27 2  18 20 60 7  8  16 40 0  3  22 5  39 39 16 0  25 31 45 12  

most common letters:

j : 60, y : 45, n : 40, t : 39, s : 39, x : 31

so we can assume e = j. If e = j, then j is +5 from e so we can assume this is rot 5. Decoding using rot 21 (the reverse gives):

thiscourseaimstoprovideyouwithdetailedknowledgeofimportanttechnologiesandapplic ationthatareusedintheinternetduetothebroadnatureofthisfieldthecoursecoversonlys electedtopicsfocussingfirstonsomeadvancedtopicsininternettechnologiesegwireless lansmobileinternetmulticastandthenaselectionofcurrentandnextgenerationapplicati onsandservicesegppiptvvoipyouwilllearnhowtheinternetworksandhowservicesandappli cationsareprovidedtousersoftheinternetthisknowledgewillhelpyouinthedesignandman agementofcomputernetworksaswellasdevelopmentandexecutionofinternetapplications

So we have solved it using just one substitution.

This cipher really works best with quite lengthy ciphertext, and is almost useless with short ciphertexts. And with modern day encryption, this technique is likely to become a thing of the past, although it is very useful at the end of each of the two following methods, which is why I have explained it first.


Index of coincidence

Facts

This method puts two ciphertexts together and seeing which letters are the same in the same position. This works well for ciphers such as Vigenere. The index of coincidence provides a measure of how likely it is to draw two matching letters by randomly selecting two letters from a given text.

The chance of drawing a given letter in the text is (number of times that letter appears / length of the text).

The calculation itself is very complex and it is better to use an online calculator. Here is the calculation, in the most basic and understandable form (courtesy wikipedia):

enter image description here

c = the normalizing coefficient (26 for English), N? = the number of times the letter "?" appears in the text, N = the length of the text.

Application of facts

I haven't used this often, and it is hard to understand but the basis of how it can be used is that for a repeating-key polyalphabetic cipher (such as Vigenere) arranged into a matrix, the coincidence rate within each column will usually be highest when the width of the matrix is a multiple of the key length. This can be used to determine the key length and in turn crack the cipher.

From Wikipedia:

'If the key size happens to have been the same as the assumed number of columns, then all the letters within a single column will have been enciphered using the same key letter, in effect a simple Caesar cipher applied to a random selection of English plaintext characters. The corresponding set of ciphertext letters should have a roughness of frequency distribution similar to that of English, although the letter identities have been permuted (shifted by a constant amount corresponding to the key letter). Therefore, if we compute the aggregate delta I.C. for all columns ("delta bar"), it should be around 1.73. On the other hand, if we have incorrectly guessed the key size (number of columns), the aggregate delta I.C. should be around 1.00'

Basically, split the ciphertext into groups of x, and stack them. If the key length = x then the I.C. will be around 1.73 (index coincidence of english language). If it isn't the same as x it will be around 1.

The index of coincidence for the english language is roughly 1.73.

Example

(Courtesy of Wikipedia)

We have the following ciphertext:

QPWKA LVRXC QZIKG RBPFA EOMFL JMSDZ VDHXC XJYEB IMTRQ WNMEA IZRVK CVKVL XNEIC FZPZC ZZHKM LVZVZ IZRRQ WDKEC HOSNY XXLSP MYKVQ XJTDC IOMEE XDQVS RXLRL KZHOV

We can guess this vigenere with a short key, and its english. We can stack them in say groups of seven:

QPWKALV
RXCQZIK
GRBPFAE
OMFLJMS
DZVDHXC
XJYEBIM
TRQW...

So if the key length is 7, then the I.C should be around 1.73. However, calculating it gives 1, showing it is incorrect. If we do this for keylengths 1-10:

1  1.12
2   1.19
3   1.05
4   1.17
5   1.82
6   0.99
7   1.00
8   1.05
9   1.16
10  2.07

We can see that 5 and 10 are the closest to 1.73, and as 10 is a factor of 5 then the key length will be 5.

Next stack the ciphertext in groups of 5.

We can now try to determine the most likely key letter for each column considered separately,by testing Caesar decryption on the whole common with letter A-Z, and choosing the key letter that produces the highest correlation between the decrypted column letter frequencies and the relative letter frequencies for normal English text (frequency analysis).

When we try this, the best-fit key letters are reported to be "EVERY," which we recognize as an actual word, and using that for Vigenère decryption produces the plaintext:

MUSTC HANGE MEETI NGLOC ATION FROMB RIDGE TOUND ERPAS SSINC EENEM YAGEN TSARE BELIE VEDTO HAVEB EENAS SIGNE DTOWA TCHBR IDGES TOPME ETING TIMEU NCHAN GEDXX

Which we can see is

MUST CHANGE MEETING LOCATION FROM BRIDGE TO UNDERPASS SINCE ENEMY AGENTS ARE BELIEVED TO HAVE BEEN ASSIGNED TO WATCH BRIDGE STOP MEETING TIME UNCHANGED XX


Kasiski Examination

Facts and Application of Facts

The Kasiski Examination is quite simple so I have merged facts and applications together. It is another way of deducing key length, and also can be used on Vigenere. Works best with longer ciphertexts, though a computer is then usually required.

The Kasiski Examination finds the repeated strings in the ciphertext and the distance between them. The distances between are likely to be multiples of the keyword length. Finding more repeated strings means it is easier to find the key length, as it is the highest common factor or greatest common divisor of the distances.

Example

(Courtesy of wikipedia, with some added elaboration.)

Take the plaintext

crypto is short for cryptography

'crypto' appears twice in the plaintext, the distance between is 20 characters.

If the key is 'abcdef' the length is 6, which doesn't go into 20 we don't get any repeats in the ciphertext:

abcdefabcdefabcdefabcdefabcdefab
crypto is short for cryptography
csasxt it ukswt gqu gwyqvrkwaqjb

'abcdef' matches 'crypto' the first time, but for the second crypto the key is 'cdefab' and as a result the ciphertext doesn't match.

But if the key is 'abcd', the length is 4 which goes into 20. So the ciphertext repeats:

abcdabcdabcdabcdabcdabcdabcdabcd
crypto is short for cryptography
cqwmtn gp sgmot emo cqwmtneoaofv

You can see that 'abcd' lines up with 'crypto' both times. And hey presto we get a repeat in the ciphertext: 'cqwmtn'.


These are a few, and probably the most well known methods to decrypt such ciphers. I hope this helps you, and you crack your cipher eventually.

$\endgroup$
0
$\begingroup$

I think you can always do this:

First enter this site http://www.dcode.fr/
Second if you know the cipher type then search for it
on the cipher web page you will find a decoder with a lot of options like deciphering knowing the key-length or a partial key or a plaintext word.
when you decipher the text you will be able to find the keyword

Hope this helps

$\endgroup$
  • 2
    $\begingroup$ You are able to edit your own answers, you don't need to delete and repost them. $\endgroup$ – Sconibulus May 18 '17 at 12:59
  • $\begingroup$ Thank you for the reply but unfortunately no program I have tried works because it is polyalphabetic and I do not know the keyword to change it to monoalphabetic. $\endgroup$ – J. Doe May 18 '17 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.