What are Spurious Keys and Unicity Distance?

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 R_L 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, s_n, satisfies the following relation:

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:

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

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_L = 0.75; we get 

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!!‍💻