The Full Wiki

Confusion and diffusion: Wikis

  

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

From Wikipedia, the free encyclopedia

In cryptography, confusion and diffusion are two properties of the operation of a secure cipher which were identified by Claude Shannon in his paper Communication Theory of Secrecy Systems, published in 1949.

In Shannon's original definitions, confusion refers to making the relationship between the key and the ciphertext as complex and involved as possible; diffusion refers to the property that the redundancy in the statistics of the plaintext is "dissipated" in the statistics of the ciphertext. In other words, the non-uniformity in the distribution of the individual letters (and pairs of neighbouring letters) in the plaintext should be redistributed into the non-uniformity in the distribution of much larger structures of the ciphertext, which is much harder to detect.

Diffusion means that the output bits should depend on the input bits in a very complex way. In a cipher with good diffusion, if one bit of the plaintext is changed, then the ciphertext should change completely, in an unpredictable or pseudorandom manner. In particular, for a randomly chosen input, if one flips the i-th bit, then the probability that the j-th output bit will change should be one half, for any i and j — this is termed the Strict Avalanche Criterion. More generally, one may require that flipping a fixed set of bits should change each output bit with probability one half.

One aim of confusion is to make it very hard to find the key even if one has a large number of plaintext-ciphertext pairs produced with the same key. Therefore, each bit of the ciphertext should depend on the entire key, and in different ways on different bits of the key. In particular, changing one bit of the key should change the ciphertext completely.

The simplest way to achieve both diffusion and confusion is a substitution-permutation network. In these systems, the plaintext and the key often have a very similar role in producing the output, hence it is the same mechanism that ensures both diffusion and confusion.

See also

References

  • Claude E. Shannon, "Communication Theory of Secrecy Systems", Bell System Technical Journal, vol.28-4, page 656--715, 1949. [1]
  • Wade Trappe and Lawrence C. Washington, Introduction to Cryptography with Coding Theory. Second edition. Pearson Prentice Hall, 2006.
  • William Stallings, Cryptography and Network Security, 3rd Edition, Prentice Hall, 2003

Simple English

In cryptography, confusion and diffusion are two properties of the operation of a secure cipher.

Confusion and diffusion were identified by Claude Shannon in his paper, "Communication Theory of Secrecy Systems" published in 1949. In Shannon's original definitions:

  1. Confusion refers to making the relationship between the key and the ciphertext as complex and as involved as possible
  2. Diffusion refers to the property that redundancy in the statistics of the plaintext is "dissipated" in the statistics of the ciphertext.

Diffusion is associated with the dependency of the output bits on the input bits. In a cipher with good diffusion, flipping an input bit should change each output bit with a probability of one half (this is termed the Strict Avalanche Criterion).

Substitution (a rule for replacing plaintext symbols by another) has been identified as a mechanism for primarily confusion (see S-box); on the other hand transposition using P-box) (rearranging or swapping the order of symbols) is a technique for diffusion, although other mechanisms are also used in modern practice, such as linear transformations (e.g. in AES). Product ciphers use alternating substitution and transposition phases (rounds) to achieve both confusion and diffusion respectively.

Other pages

References








Got something to say? Make a comment.
Your name
Your email address
Message