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.
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:
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):
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 found online here. This is a known rot cipher, but we don't know what number:
ymnxhtzwxjfnrxytuwtanijdtzbnymijyfnqjipstbqjiljtknrutwyfsyyjhmstqtlnjxfsifuuqnh fyntsymfyfwjzxjinsymjnsyjwsjyizjytymjgwtfisfyzwjtkymnxknjqiymjhtzwxjhtajwxtsqdx jqjhyjiytunhxkthzxxnslknwxytsxtrjfiafshjiytunhxnsnsyjwsjyyjhmstqtlnjxjlbnwjqjxx qfsxrtgnqjnsyjwsjyrzqynhfxyfsiymjsfxjqjhyntstkhzwwjsyfsisjcyljsjwfyntsfuuqnhfyn tsxfsixjwanhjxjluunuyaatnudtzbnqqqjfwsmtbymjnsyjwsjybtwpxfsimtbxjwanhjxfsifuuqn hfyntsxfwjuwtanijiytzxjwxtkymjnsyjwsjyymnxpstbqjiljbnqqmjqudtz
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
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):
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.
'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.
(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:
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
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.
(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.
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