Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What are Spurious Keys?
3.
Theorem On Spurious Keys
4.
What is Unicity Distance in Cryptography?
5.
Unicity Distance Formula
6.
Ciphertexts and Unicity Distance
6.1.
Unicity Distance Of Substitution Cipher
7.
Frequently Asked Questions
7.1.
What is the unicity distance in cryptography?
7.2.
How do you calculate Unicity distance?
7.3.
What is meant by substitution cipher?
8.
Conclusion
Last Updated: Mar 27, 2024

What are Spurious Keys and Unicity Distance?

Author Yukti Kumari
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

A cryptosystem consists of a set of plain texts, cipher texts, secret keys, encryption, and decryption algorithms. 

Now, given a bunch of ciphertexts, can you find the corresponding plaintexts? One can do this by finding the secret key. 

But while designing the cryptosystem, we want to ensure that it's not possible to break into the system easily. To determine the security of the cryptosystem, we need some standard parameters like spurious keys and unicity distance. 

What are Spurious Keys and Unicity Distance?

In this article, we will learn about spurious keys and unicity distance in cryptography. 

Let's get started 🔰

What are Spurious Keys?

In cryptography, we use a secret key to encrypt plaintexts and generate corresponding cipher text. Suppose we want to do the reverse operation! 

That is, given a ciphertext, find out the secret key. 🔑

Seems impossible, right? 

But the process of finding the key is a brute force approach, i.e., trying out all possibilities. 

Spurious keys are a set of possible but incorrect keys for a given encryption. 

Let's understand with the help of an example. 
 

Say, for some cryptosystem, you have a ciphertext, C = WNAJW, which we obtain by encryption using shift cipher.

If we decrypt C with keys E and W, we get back the following plaintexts:

  • Decryption with F(= 5) - RIVER
  • Decryption with W(= 22) - ARENA
     

Both the obtained plaintexts seem valid. Out of E and W, one of them is the correct key, while the remaining possible key (incorrect one) is a spurious key
 

How many such spurious keys can be there? The more spurious keys, the more are the chances of incorrect decryption. We are interested in finding the bound on the expected number of spurious keys for a given cryptosystem. 

In the next section, we will see a theorem to determine the number of spurious keys, sn

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Theorem On Spurious Keys

Suppose (P, C, K, E, D)  is a cryptosystem where ;

  • P is a finite set of possible plaintexts
  • C is a finite set of possible ciphertexts
  • K, id the set of possible keys
  • E is the set of encryption rules for all the keys
  • D is the set of decryption rules for all the keys 
     

Here, |C| = |P|, and we chose the keys with equal probability. 
 

Let RL denote the redundancy of the underlying language. 

Then for a string of ciphertext of length n, where n is sufficiently large, the expected number of spurious keys, sn, satisfies the following relation:

Formula

What is Unicity Distance in Cryptography?

Cryptanalysis is breaking the code and accessing meaningful information from the encoded data. To decode the entire system, a cryptanalyst aims to discover the secret key from the available cipher texts.
 

So, if you perform a brute-force attack on a cryptosystem, how many cipher texts will you need to crack the system or ensure that your solution is correct? 🧐 

Here comes the role of the unicity distance. 

Unicity distance is defined as the length of ciphertext, n0, for which the expected number of spurious keys is reduced to zero. In other words, unicity distance is the average amount of ciphertext for which you can uniquely compute the key given enough computing time. 

Claude Shannon defined the unicity distance in 1949.
 

In the next section, let's see how to calculate the unicity distance for a given cryptosystem.

Unicity Distance Formula

In the theorem on spurious keys, given by:

Formula

Putting sn=0, we get an estimate of the value of n, which is nothing but the unicity distance as:

 Formula

Ciphertexts and Unicity Distance

Till now, we have seen the formal definition of the unicity distance. Now, let's understand how the length of ciphertexts affects the probability of breaking the system.

Here are some interesting points:

  • The ciphertexts having a length greater than the unicity distance are assumed to have only one meaningful decryption. 
     
  • The ciphertexts shorter than the unicity distance may have multiple decryptions since the number of spurious keys will be greater than 0.

Unicity Distance Of Substitution Cipher

We can compute the unicity distance of the substitution cipher using the above formula.

In the substitution cipher cryptosystem, we have:

  • |P| = 26
  • |K| = 26! 

Let's say we take R= 0.75; we get 

Formula

What does it mean to have a unicity distance of 25?

It means that if you have a ciphertext of length greater than or equal to 25, you can find its unique decryption.

Frequently Asked Questions

What is the unicity distance in cryptography?

In cryptography, unicity distance is the length of an original ciphertext needed to break the cipher by reducing the number of possible spurious keys to zero in a brute-force attack.

How do you calculate Unicity distance?

It can be calculated using the U=H(k)/D formula, where D=R−r and R=8 is the number of bits in a byte (ASCII is 7, but we are rounding up), r≈1.5 bits is the average entropy of a single letter in written English.

What is meant by substitution cipher?

The data encryption scheme in which units of the plaintext (generally single letters or pairs of letters of ordinary text) are replaced with other symbols or groups of symbols is referred to as substitution cipher.

Conclusion

In this article, we learned about spurious keys and unicity distance and their importance in cryptography. We also saw the theorem and formulas for computing the number of spurious keys and unicity distance for a given cryptosystem.

We hope this blog has helped you enhance your knowledge of spurious Keys and Unicity distance.

Check out these useful blogs on Cryptanalysis - 

🎯 What is Linear Cryptanalysis?

🎯 Substitution-Permutation Networks (SPN) in Cryptography

🎯 Difference Between Differential and Linear Cryptanalysis

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available, interview puzzles, take a look at the interview experiences, and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow ✨

Happy Reading!!‍💻

Live masterclass