Confusion and diffusion
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.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, confusion and diffusion are two properties of the operation of a secure cipher
Cipher
In cryptography, a cipher is an algorithm for performing encryption or decryption — a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. In non-technical usage, a “cipher” is the same thing as a “code”; however, the concepts...
which were identified by Claude Shannon
Claude Elwood Shannon
Claude Elwood Shannon was an American mathematician, electronic engineer, and cryptographer known as "the father of information theory"....
in his paper Communication Theory of Secrecy Systems
Communication Theory of Secrecy Systems
Communication Theory of Secrecy Systems is a paper published in 1949 by Claude Shannon discussing cryptography from the viewpoint of information theory. It is one of the foundational treatments of modern cryptography...
, published in 1949.
In Shannon's original definitions, confusion refers to making the relationship between the key
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
and the ciphertext
Ciphertext
In cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher...
as complex and involved as possible; diffusion refers to the property that the redundancy
Redundancy (information theory)
Redundancy in information theory is the number of bits used to transmit a message minus the number of bits of actual information in the message. Informally, it is the amount of wasted "space" used to transmit certain data...
in the statistics of the plaintext
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
is "dissipated" in the statistics of the ciphertext
Ciphertext
In cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher...
. 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
Avalanche effect
In cryptography, the avalanche effect refers to a desirable property of cryptographic algorithms, typically block ciphers and cryptographic hash functions. The avalanche effect is evident if, when an input is changed slightly the output changes significantly...
. 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
Substitution-permutation network
In cryptography, an SP-network, or substitution-permutation network , is a series of linked mathematical operations used in block cipher algorithms such as AES .Other ciphers that use SPNs are 3-Way, SAFER, SHARK, and Square....
. 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.