Sunday, November 2, 2014

Introduction to Cryptography - Decrypting Caesar's Cipher

In the previous post, we looked at some definitions around cryptography. In this post we will look at the Caesar cipher. This is one of the oldest ciphers.

"A Caesar cipher is one of the simplest (and easiest cracked) encryption methods. It is a Substitution Cipher that involves replacing each letter of the secret message with a different letter of the alphabet which is a fixed number of positions further in the alphabet".


"Because each letter in the message has a direct translation to another letter, frequency analysis can be used to decipher the message. For example, the letter E is the most commonly used letter in the English language. Thus, if the most common letter in a secret message is K, it is likely that K represents E. Additionally, common word endings such as ING, LY, and ES also give clues.

A brute-force approach of trying all 25 possible combinations would also work to decipher the message."


What does the cipher text below say?

LZAK AK S LWKL GX LZW USWKSJ KZAXL UAHZWJ HDWSKW LWDD EW OZSL LZAK EWKKSYW KSQK

Let's see if we can find a way to decrypt this message. Using information from "www3.nd.edu/~busiforc/handouts/cryptography/cryptography hints.html".
Let's first start with 1 letter words. The first and only one we see in the ciphertext is "S"
Looking at the 2 letter words we have "AK, GX, EW"
Looking at the 3 letter words we have "LZW"
Four letter words "LZAK, LWKL, LWDD, OZSL, LZAK KSQK"

We can continue building out the words as similar as above. If we start with the one letter words, we know in English language these are "A" and "I". This means that "S" in the ciphertext is either equal to "A" or "I"


For the two letter words, we know that these are "of, to, in, it, is, be, as, at, so, we, he, by, or, on, do, if, me, my, up, an, go, no, us, am". This means that the words "AK, GX, EW" in the ciphertext equals to one of these words

Let's look at the 3 letter words.
"the, and, for, are, but, not, you, all, any, can, had, her, was, one, our, out, day, get, has, him, his, how, man, new, now, old, see, two, way, who, boy, did, its, let, put, say, she, too, use"
So "LZW" will equal to one of the following 

Last but not least 4 letter words:
"that, with, have, this, will, your, from, they, know, want, been, good, much, some, time"
So the  Four letter words "LZAK, LWKL, LWDD, OZSL, LZAK KSQK" in the ciphertext should equal to one of the words above.

Ok now that we've done all of the above. Let's try to put together our letters

Since the one letter word "S" is not in any of the 2 or 3 letter words, let's work with the assumption that it is "A" when deciphered. If after testing we find this is wrong, we can always change it to "I" since there are only two options.

If we look at the 2 letter word "AK", we can see that it is in the 4 letter word "LZAK". Interestingly also, LZ in the 3 letter ciphertext "LZW" also starts the 4 letter word "LZAK". Let's try to see which 4 letter word ends with the letters in a 2 letter word and which starts a 3 letter word :-).

If we go through the words above we see "AZ" can be deciphered to "IS"
"LZAK" can be deciphered to "THIS". This mean that "LZ" is "TH" thus "W" in the ciphertext is "E" when deciphered. If we continue this methodology, we will decipher the entire text and end up with the following


ciphertext = plaintext
A = I
W = E
K = S
L = T
S = A
Z = H
G = O
J = R
H = P
D = L
E = M
O = W
Y = G
Q = Y

Thus the deciphered text is "THIS IS A TEST OF THE CAESAR SHIFT CIPHER TELL ME WHAT THIS MESSAGE SAYS" 

The Caesar shift in this pattern is a shift by 8


Let's try this one more time.

Decipher the text below, using the methodology above.



UIJT JT B TFDSFU NFTTBHF

If you got this correct, then you should have the following representation for each letter.

Answer:
ciphertext = plaintext
B = A
J = I
T = S
I = H
U = T
F = E
D = C
S = R
N = M
H = G

Then you should have this as your deciphered text.
 
THIS IS A SECRET MESSAGE

... and you would have detected that the pattern is a shift by -1


Ok! I know I said one more. Let's do it one more time. I promise this is the last one.

Decrypt the ciphertext below.



N  INLZKI  RNI  FPGMZMT  ZLF  OKKCF,  NIS  TMTI  LVT  NHJZLZKPF.  JPL   ZL  RNIIKL  FPGMZMT  LGTNFKI  OGKH  QZLVZI.  NI  TITHX  NL  LVT  WNLTF  ZF  CTFF  OKGHZSNJCT, OKG  VT  ZF  BIKQI  NIS  RNGGZTF VZF  JNIITG  KDTICX.  JPL  LVT  LGNZLKG  HKMTF  NHKIWFL  LVKFT  QZLVZI  LVT  WNLT  OGTTCX,  VZF  QVZFDTGF  GPFLCZIW  LVGKPWV  NCC  LVT  NCCTXF,  VTNGS  ZI  LVT  MTGX  VNCCF  KO  WKMTGIHTIL  ZLFTCO.  OKG  LVT  LGNZLKG  NDDTNGF  IKL  N  LGNZLKG;  VT  FDTNBF  ZI  NRRTILF  ONHZCZNG  LK  VZF  MZRLZHF,  NIS  VT  QTNGF  LVTZG  ONRT  NIS  LVTZG  NGWPHTILF, VT  NDDTNCF  LK  LVT  JNFTITFF  LVNL  CZTF  STTD  ZI  LVT VTNGLF  KO  NCC  HTI.   VT  GKLF  LVT  FKPC  KO  N  INLZKI,   VT  QKGBF  FTRGTLCX  NIS  PIBIKQI  ZI  LVT  IZWVL  LK  PISTGHZIT  LVT  DZCCNGF  KO  LVT  RZLX,  VT  ZIOTRLF  LVT  JKSX  DKCZLZR  FK  LVNL  ZL  RNI  IK  CKIWTG  GTFZFL.  N  HPGSTGTG  ZF  CTFF  LK  OTNG. 



-HNGRPF  LPCCZPF  RZRTGK


 If you use the method used at the beginning then this should not take too much effort.

The basic idea is to first identify one letter words within the ciphertext. There is currently only 1 which is “N”. Once this is found, the next step is to identify the 1 letter words from the English language and their frequency of usages. A is known to be used more than I.

Next, identify the two letters words. Some of these are ZL, NI, NL, ZF, VT, KO, LK, FK, IK.

The third step is to identify the 3 letter words. Some of which were RNI, ZLF, NIS, LVT, JPL, OKG, VZF, ILK HTI.   Once these words are identified, the fourth step is to try to create 2 letter words or build 3 letter words based on the 2 letter words.

When you are finished the following mappings should be identified.
cyphertext = plaintext.
P=U; J=B; N=A; C=L; I=N; R=C; S=D; K=O; L=T; V=H; T=E; Z=I; F=S; G=R; O=F; H=M; X=Y; W=G; B=K; Q=W; M=V; D=P

If you have the above correctly, then your ciphertext once decrypted should read as follows.

A nation can survive its fools and even the ambitious. But it cannot survive treason from within. An enemy at the gates is less formidable for he is known and carries his bainer openly. Bu the traitor moves amongst those within the gate freely, his whispers rustlings through all the alleys, heard in the very halls of government itself. For the traitio appears not a traitor, he speaks in accents familiar to his victims and he wear their face and their arguments, he appeals to the baseness that lies in the learts of all men. He rots the soul of a nation, he works secretly in the night to undermine the pillars of the city, he infects the body politic so that it can no longer resist. A murder is less to fear.



-          Marcus Tullius Cicero
Hope you enjoyed the working with Caesar's cipher and see you in the next section where we Decrypt XOR Encryption



Reference:
http://www.braingle.com/brainteasers/codes/caesar.php
www3.nd.edu/~busiforc/handouts/cryptography/cryptography hints.html


No comments:

Post a Comment