Sunday, November 2, 2014

Beginning Cryptography - Decrypting XOR Encryption

In the first post in this series we looked at definitions. In the previous post we looked at the Caesar Cipher. In this post we will look at the Decrypting XOR Encryption


 "Exclusive-OR (XOR) encryption is an encryption method that is hard to break through with so called “brute force” methods (brute force = using random encryption keys in the hope you find the correct one.), but the encryption method is susceptible to pattern recognition. Patterns can be easily avoided by first compressing the file (compression already makes it unreadable, it removes patterns for you) before it is encrypted."


"The XOR encryption method doesn’t make use of a public-key, such as RSA. Instead both the people that encrypt the file as well as the people that want to decrypt the file need to have the encryption key. The exclusive-OR encryption (as the name already tells you) makes use of the Boolean algebra function XOR."

"The XOR function is a binary operator, which means that it takes two arguments when you use it.
If one of the two arguments is true and the other argument is false, then the XOR function will return true."



In our example XOR Encryption: XOR encryption has been used to encrypt a word made up of seven characters. The cipher text of the word is as follows:

00010000

00011011

00010110

00000111

00001100

00000101

00000001

The key is: 01010101

Answer:
Cipher Text + XOR Key:  
0001 0000       0001 1011       0001 0110       0000 0111       0000 1100       0000 0101
0101 0101       0101 0101       0101 0101       0101 0101       0101 0101       0101 0101
0100 0101       0100 1110       0100 0011       0101 0010       0101 1001       0101 0000

0000 0001
0101 0101
0101 0100

Binary Value after XORing
After XORing the Binary Value is:
0100 0101       0100 1110       0100 0011       0101 0010       0101 1001        0101 0000  0101 0100

Binary =  Hex Value = Ascii Character
0100 0101 = 45 = E   
0100 1110 = 4E = N
0100 0011 = 43 = C   
0101 0010 = 52 = R   
0101 1001 = 59 = Y   
0101 0000 = 50 = P
0101 0100 = 54 = T

The decrypted text is “ENCRYPT”

Reference:
http://www.codingunit.com/exclusive-or-xor-encryption

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