The Art of Encryption and Decryption
What is the goal here? — Secure communication
(Alice) Aㅡㅡㅡ|ㅡㅡㅡ B (Bob)
E (Adversary/attacker)
Let say A wants to send a message to B. For this both possess a key for communication say k
A wants to send m=m1m2m3m4m5…….mn and the key for each piece of message is k=k1k2k3k4k5………kn.
Then a ciphertext is created using the original plaintext message and the key as
c=m⊕k [∵ ⊕= XOR addition]
c=c1c2c3c4c5…..cn
This ciphertext reaches B and he will extract the message using c⊕k=m.
Let’s take a case here:
We will convert all the m,k,c in the decimal format first
A wants to send m=15 to B and k=19
- Convert m and k to binary [m=15=01111; k=19=10011]
- Calculate c=m⊕k=11100=28
- B will get c as 28 and then he calculates c⊕k=01111=m
Thus the communication protocols are:
- A & B share a random secret key k.
- A sends B ciphertext c=m⊕k.
- B computes c⊕k = (m⊕k)⊕k = m and hence decodes the original plaintext message.
- E (adversary or attacker) sees only c=m⊕k but doesn’t know k, so can’t understand anything.
- Indeed, given c, all m=c⊕k are equally likely depending on random k.
Now consider the perspective of adversary or attacker, how can he attack or get the secret message.
1. ONE-TIME PAD ATTACK:
m⊕k = (m+k) mod(2) is a type of XOR addition
a=(a1,a2,a3,a4,……..,an)
b=(b1,b2,b3,b4,……..,bn)
⇒a⊕b = (a1+b1 mod(2), a2+b2 mod(2),……….,an+bn mod(n))
⇒ a⊕b⊕b=a
2. MANY-TIME PAD ATTACK:
If A wants to send many messages to B, so each message needs a separate random key. What will happen if we use the same key to encrypt two messages?
c1=m1⊕k
c2=m2⊕k
here k is used as a key in both ciphertexts.
Now the attacker knows the ciphertext but not the key or keys, so he/she would calculate c1⊕c2=m1⊕k⊕m2⊕k=m1⊕m2
And it turns out that m1 & m2 are plain English & it is not possible to partially decipher both given just m1⊕m2.
If we know m1⊕m2 & the i-th character of m1 by English Redundancy method or by any chance then we can decipher the i-th character of m2 also.
Note: XOR of a letter with space is always different from XOR of any two letters
Attack Method:
- Guess a word that might appear in one of the messages
- Encode the guessed word to a hex string
- Take XOR of c1 & c2 (both ciphertexts)
- Take XOR of the hex string of guessed word and c1⊕c2 at each of its position
- When the results from the previous step are a readable text, then we would guess our English word and expand our crib search.
- If the result is not readable text, we try an XOR of the crib word at the next position of c1⊕ c2.
We will use English redundancy and frequency table to guess our possible word. You can search on the internet for the frequency table of letters, bigrams, and trigrams.
Let’s do an example:
m1=’Hello World’
m2=’the program’
key(k)=’supersecret’
Firstly, we will convert all the strings or messages to hexadecimal as
m1=48656c6c6f20576f726c64
m2=7468652070726f6772616d
k=7375706572736563726574
c1=m1⊕k=3b101c091d53320c000910
c2=m2⊕k=071d154502010a04000419
In English trigrams, ‘the’ is the most used word. So why not our first guess to be ‘the’
Converting ‘the’ to hexadecimal as 746865
Calculating c1⊕c2=3c0d094c1f523808000d09
now, we will XOR our crib word ‘746865’ at each position of c1⊕ c2 like
Taking XOR,
‘3c0d09’ 4c1f523808000d09
‘746865’
— — —
48656c ⇒converting this into ASCII from hexadecimal⇒ ‘Hel’ (seems readable)
here Hel could be ‘Hello’ as well as ‘help’
Let say its Hello and then we convert Hello into hex:48656c6c6f
Taking XOR,
‘3c0d094c1f’ 523808000d09
‘48656c6c6f’
— — — — —
7468652070 ⇒converting to ASCII ⇒ ‘the p’ (Hurray!, we got something including out guessed word ‘the’)
Similarly, we can guess and proceed and could decipher the whole message.
The algorithms for how to do all these processes are here: Click here!
In the next blog, we will know about RSA Cryptosystem!
