Classic Encryption Techniques
All encryption techniques are based on 2 methods, which can be used separately or together:
1- Substitution
2- Transposition
1- Substitution Encryption Techniques: Substitution is an encryption technique where elements in the plaintext are replaced or mapped with another elements. There are many types of the substitution techniques such as (monoalphabetic cipher and polyalphabetic cipher).
A - Monoalphabetic Cipher
Let's look at an example of monoalphabetic cipher called Caesar cipher.
Caesar Cipher: Is the simplest and the oldest known encryption techniques where elements in the plaintext are shifted a fixed number of spaces. For example, they're moved 3 places:
Example:
Plaintext : WELCOME TO CRYPTOGRAPHY
Ciphertext : ZHOFRPH WR FUBSWRJUDSKB
The ciphertext is produced by adding 3 positions for every letter.
As we can see here, the encryption algorithm for each plaintext P to produce a ciphertext C, where C = E(3,P) = (P+3)mod26. So, generally the encryption algorithm for Caesar cipher is C= E(K,P) = (P+K)mod26.
The decryption algorithm for Caeser cipher is: P= D(K,C) = (C-K)mod26 Note: K takes a value from 1 to 25.
Caesar cipher is too easy to break because it only uses 25 position keys. Simply preforming a brute force using the 25 possible keys, the language would help us in breaking this cipher. In modern encryption, we use a very large key, such as 1024 bits or greater that gives us 2^1024 key space. There's a very wide range of possible of keys.
Caesar cipher and many of substitution ciphers can be broken by using frequency of letters analysis.
Frequency of Letters Analysis: This method is used to break a cipher encrypted by a substitution method. It's based on the relative use of letters and can be determined by and compared to a standard frequency distribution for a language (English).
As we can see the previous figure, E is the most letter uses in English words by 12.7% , then T by 9.056%. See the figure below as well:
Here's the encrypted text:
LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVE
WHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIMWQLMGLMXQ
ERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEX
XMZITWAWSQWXSWEXTVEPMRXRSJGSTVRIEYVIEXCVMUIM
WERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEG
ARCSXRWIEVSWIIBXVIZMXFSJXLIKEGAEWHEPSWYSWIWI
EVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPS
RRFQMXLEPPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIM
YLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPPX
LMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMX
IVJSVLMRSCMWMSWVIRCIGXMWYMX
Consider the letter frequencies in the above text:
i : 58
e : 48
x : 41
w : 35
m : 34
v : 31
s : 30
r : 27
l : 22
p : 21
g : 16
h : 16
y : 13
t : 12
q : 12
c : 9
k : 9
j : 9
z : 6
f : 6
a : 5
o : 3
b : 2
u : 1
n : 1
d : 0
With these numbers and some good guessing at words, we can solve it. Let's try I=E and L=H. And, let's guess X=T and E=A. We get the following:
heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtate
PFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGa
ReMWQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPR
GaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaP
MRtRSJGSTVReaYVeatCVMUeMWaRGMeWtMJMGCS
MWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWe
aVSWeeBtVeZMtFSJtheKaGAaWHaPSWYSWeWeaV
theStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaW
HYPSRRFQMthaPPtheaCCeaVaWGeSJKTVWMRheH
YSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAa
KPeaWHtaAMWYaPP
We can substitute V=R in "heVe" to be "here" and R=S in "Rtate" to be "state" M=I, Z=M from "atthattMZe" to be "atthattime"
We apply this change and get:
hereTCSWPeYraWHarSseQithaYraOeaWHstate
PFairaWHKrSTYhtmetheKeetPeJrSmaYPassGa
seiWQhiGhitQaseWGPSseHitQasaKeaTtiJTPs
GaraKaeTsaWHatthattimeTWAWSQWtSWatTraP
istsSJGSTrseaYreatCriUeiWasGieWtiJiGCS
iWtSJOieQthereQeretQSrSTWHKPaGAsCStsWe
arSWeeBtremitFSJtheKaGAaWHaPSWYSWeWear
theStherthesGaPesQereeBGeeHiWYPFharHaW
HYPSssFQithaPPtheaCCearaWGeSJKTrWisheH
YSPHtheQeiYhtSJtheiWseGtQasOerFremarAa
KPeaWHtaAiWYaPPthiWYsiWtSGSWsiHeratiSW
iGSTPHharHPFKPameNTCiterJSrhisSCiWiSWr
esCeGtiWYit
We deduce the substitution, until we get a right message:
hereuponlegrandarosewithagraveandstate
lyairandbroughtmethebeetlefromaglasscase
inwhichitwasencloseditwasabeautiful
scarabaeusandatthattimeunknowntonatura
listsofcourseagreatprizeinascientific
pointofviewthereweretworoundblackspot
snearoneextremityofthebackandalongone
neartheotherthescaleswereexceedingly
hardandglossywithalltheappearanceof
burnishedgoldtheweightoftheinsectwas
veryremarkableandtakingallthingsinto
considerationicouldhardlyblamejupiter
forhisopinionrespectingit
After adding spaces...
Hereupon Legrand arose, with a grave
and stately air, and brought me the
beetle from a glass case in which it
was enclosed. It was a beautiful
scarabaeus, and, at that time,
unknown to naturalists of course
a great prize in a scientific point
of view. There were two round black
spots near one extremity of the back,
and along one near the other.
The scales were exceedingly hard and
glossy, with all the appearance of
burnished gold. The weight of the
insect was very remarkable, and,
taking all things into consideration,
I could hardly blame Jupiter for his
opinion respecting it.
Note: Frequency of letters analysis works well as long as the cipher text is large.
B - Polyalphabetic Cipher:
Polyalphabetic Cipher is an encryption method to improve the simple substitution cipher techniques by using a larger key space and making the frequency of letters analysis harder. Polyalphabetic Cipher is a block cipher with the following properties:
1- The key space consists of all order of K = (k1, k2, k3, ... ki) and i= block length
2- Encryption of plaintext M = (m1, m2, m3 ... mi)
Encryption algorithm:
E(m+k) = (k1(m1).k2(m2).k3(m3). ,,,, ki(mi))
Let's see an example of Polyalphabetic Cipher called Vigenere Cipher:
Vigenere Cipher is Polyalphabetic Cipher technique and it uses 26 letters shifting from 1 to 25. It's similar to Caesar cipher, but with a dynamic key, which changes every time on "i"interval.
The encryption algorithm for Vigenere Cipher to produce a ciphertext C:
Ci = (Pi+Ki)
The decryption algorithm for Vigenere Cipher to produce a plaintext P:
Pi = (Ci-Ki)
Example:
Let key: K= HAMZA and plaintext = WELCOME TO CRYPTOGRAPHY
Key = HAMZAHAMZAHAMZAHAMZAH
Plaintext = WELCOMETOCRYPTOGRAPHY
Ciphertext = ZEUBOTEFNCYYBSONRMOHF
Simply do the addition operation on each element:
Ci = (Pi⊕Ki)
Note: Look at the letter frequencies:
o : 3
n : 2
e : 2
f : 2
y : 2
b : 2
s : 1
r : 1
t : 1
z : 1
u : 1
m : 1
h : 1
c : 1
We reduced the frequency of letters analysis.
Vernam Cipher:
Vernam Cipher works on binary data rather than letters, which give us a defense against frequency letters analysis because there's no statistical relationship between the plaintext and the ciphertext.
The encryption algorithm in Vernam Cipher can be expressed as:
Ci = Pi⊕Ki
Ci = ith binary digit of ciphertext.
Pi = ith binary digit of plaintext.
⊕ = exclusive-OR (XOR) operation.
Ki = ith binary digit of key.
The decryption algorithm in Vernam Cipher is:
Pi = Ci⊕Ki
This system works by constructing a loop that takes the plaintext and the generated key, bit by bit, and preforming XOR operation on each bit. Then, generate a ciphertext and so on to the end of the plaintext.
Perfect Secrecy:
Any encryption algorithm has perfect secrecy when the ciphertext gives us nothing about the plaintext (such as One-Time pad).
One-Time Pad:
One-Time Pad is an encryption technique that's UNBREAKABLE by using a secret key - the key will not repeated to fit the plaintext. The key generator algorithm generates a key for each plaintext. The ciphertext has no statistical relationship to the plaintext. The secret key will be used to encrypt and decrypt for only one plaintext, then the secret key will be destroyed.
For example:
Suppose we use Vernam Cipher but with One-Time Pad method, we generate a secret key as long as the plaintext and only for this plaintext.
Let's try to encrypt "HELLO"
Plaintext = HELLO
Secret key = XMCKL
by adding the values of each digit
Ciphertext = EQNVZ
If we try to crack the cipher without the secret ke , and only one key can gives us the original plaintext we will get a lot of plaintexts. If we use an exhaustive search, we could translate this ciphertext into many plaintext. For example, here we used the secret key = "XMCKL" But, if we use a secret key = "TQURI" on the same ciphertext = "EQNVZ" that gives us plaintext = "LATER" but ONLY ONE KEY IS THE RIGHT KEY.
Why One-Time Pad has Perfect Secrecy?
Because:
- of the randomness on keys
- only one key is used for one message (plaintext)
- one ciphertext can be translated into many plaintext of same lengths
This makes the ciphertext that tells us us nothing about the plaintext.
Thanks and I hope this was useful to you.
