Brute Force Attack on Caesar Cipher in Python.

The Caesar cipher is a simple encryption technique that was used by Julius Caesar to send secret messages to his allies. It works by shifting the letters in the plaintext message by a certain number of positions, known as the “shift” or “key”. The Caesar Cipher technique is one of the earliest and simplest methods of encryption techniques.

To know more about Caesar Cipher follow this link:

https://medium.com/@aanshsavla2453/caesar-cipher-a-classical-cryptography-technique-c393cadc8da2

If we have an encrypted message is it possible to decrypt message without knowing key?

It is trivial since an immediate problem with caesar cipher is that the method is fixed and there are only 26 possible keys. Thus, anyone learning how Caesar encrypted his messages would be able to decrypt effortlessly. Thus we can hack the Caesar cipher by using a cryptanalytic technique called “brute-force”.

What is brute-force attack?

Nothing can stop a cryptanalyst from guessing one key, decrypting the ciphertext with that key, looking at the output, and if it is not the correct key then moving on to the next key. The technique of trying every possible decryption key is called a brute-force attack. It isn’t a very sophisticated hack, but through sheer effort the Caesar cipher can be broken.

Ideally, the ciphertext would never fall into anyone’s hands.

But according to cryptographer Auguste Kerckhoffs:

"A cryptosystem should be secure even if everything about the system, except the key, is public knowledge." This is known as Kerckhoff's Principle.

It was restated by Claude Shannon as Shannon’s Maxim:

“The enemy knows the system.”

What is a key space?

A keyspace, is the set of all valid, possible, distinct keys of a given cryptosystem. Brute force attack is about using all the keys in the key space one by one to decrypt the encrypted message and deriving some useful information out of it.

This brings us to a trivial, yet important, principle called the “sufficient key space principle”:

"Any secure encryption scheme must have a key space that is not vulnerable to exhaustive search."

Key length vs Key Space:

Length of a key is the number of bits in the key and Key Space is the set of all the possible keys using a particular length of key.

e.g. Length of a key : 20 bits & Key Space : 1,048,576

With a key of length n bits, there are 2ⁿ possible keys.

If an exhaustive brute-force key search is the only possible attack. At a trillion attempts per second, it would take tens of thousands of years to carry out a brute-force attack against an 80-bit key. There are 1,208,925,819,614,629,174,706,176 possible keys.

But in Caesar Cipher the key space has only 26 possible keys. Now a python code will generate 26 possible decrypted messages. The probability of 2 messages being meaningful is very less. As the size of the encrypted message increases, this probability tends to 0.

Thus we can derive a meaningful message manually by checking each possible outcome. But if we want to make computer to know the meaningful message then we declare a constant variable which consists of repeated English Words. It can be as follows : {'the','a','an','am','it','he','she','or','and',....}. We can put as many words as much we want to.

Consider an encrypted text:

"Udg bhv xc Tcvaxhw iwtgt pgt iltcin hxm ztnh, xu ndj peean dct puitg pcdiwtg dc tcrgneits bhv pcs dqhtgkt imi dct du iwt igpchudgbts imi xh gtpspqat."

Decrypt following message using exhaustive key attack:

Code:

• cipher: Stores the cipher text

• word_dict: Pre-defined dictionary to check for meaningfulness of decrypted statement.

• give_point: Points are given to each decrypted text according to the pre-defined dictionary

• max_point: Gives decrypted text with max_point

• final_text : Stored final text

Output:

Though Brute-Force Attack is a powerful technique to break Caesar-Cipher due to small key space but as the length of key increases the key space grows exponentially. Hence very powerful supercomputers or thousands of PCs are needed for brute force attack. But having large key size is a necessary condition for security but not a sufficient condition.

This approach underscores the importance of using more complex encryption methods in modern cryptography. While Caesar cipher and similar algorithms serve as important historical examples, they demonstrate why today's secure communication requires stronger, more sophisticated encryption mechanisms to withstand brute force attacks and other cryptographic threats.