Shannons Idea of
Confusion and Diffusion
The DES, AES and many block ciphers are designed
using Shannons idea of confusion and diffusion. The
objectives of this document is to introduce
linear and nonlinear functions; and
Shannons confusion and diffusion.
1
Linear Functions
Notation: Let F
2
denote the set {0, 1} and let
F
n
2
= {(x
1
, x
2
, , x
n
)|x
i
F
2
}.
Here F
n
2
is associated with the bitwise exclusive-or
operation, denoted +.
Linear functions: Let f be a function fromF
n
2
to F
m
2
,
where n and m are integers. f is called linear if
f(x +y) = f(x) +f(y)
for all x, y F
n
2
.
Example: Let f(x) = x
1
+x
2
+ +x
n
, where
x = (x
1
, , x
n
) F
n
2
.
Then f is a linear function from F
n
2
to F
2
. Note that
+ denotes the modulo-2 addition.
2
Examples of Linear Functions
Linear permutations: Let P be a permutation of the
set {1, , n}. Dene a function L
P
from F
n
2
to itself
by
L
P
((x
1
, x
2
, , x
n
)) = (x
P(1)
, x
P(2)
, , x
P(n)
)
for any x = (x
1
, x
2
, , x
n
) F
n
.
Lemma: L
P
is linear with respect to the bitwise exclusive-
or.
Conclusion: Such a linear function is used in both
DES and AES.
3
Examples of Linear Functions
Linear function by circular shift: Let i be any posi-
tive integer. Dene a function LS
i
from F
n
2
to F
n
2
by
LS
i
((x
0
, x
1
, , x
n1
))
= (x
(0i) mod n
, x
(1i) mod n
, , x
(n1i) mod n
)
for any x = (x
0
, x
1
, , x
n1
) F
n
.
Conclusion: LS
i
is linear with respect to the bitwise
exclusive-or.
4
Nonlinear Functions
Denition Let f be a function from F
n
2
to F
m
2
, where
n and m are positive integers. f is called nonlinear if
f(x +y) = f(x) +f(y)
for at least one pair of x, y F
n
2
.
Example: Let f(x) = x
1
x
2
+x
2
+ +x
n
, where
x = (x
1
, , x
n
) F
n
2
.
Note that + denotes the modulo-2 addition.
5
Nonlinearity of S-Boxes
The S-box in AES: A function from GF(2
8
) to GF(2
8
)
dened by
S(x) = x
2
8
2
The nonlinearity is measured by
P
S
= max
0=aGF(2
8
),
bGF(2
8
)
|{x GF(2
8
) : S(x+a)S(x) = b}|
Comment: The smaller the P
S
, the higher the nonlin-
earity of S.
Remark: S is highly nonlinear.
6
Diffusion Requirement
Diffusion: Each plaintext block bit or key bit affects
many bits of the ciphertext block.
x plaintext
k
key
y
ciphertext
E (x)
k
Remark: Linear functions are responsible for confu-
sion.
7
Diffusion Requirement
Diffusion: Each plaintext block bit or key bit affects
many bits of the ciphertext block.
Example: Suppose that x, y and k all have 8 bits. If
y
1
= x
1
+x
2
+x
3
+x
4
+k
1
+k
2
+k
3
+k
4
y
2
= x
2
+x
3
+x
4
+x
5
+k
2
+k
3
+k
4
+k
5
y
3
= x
3
+x
4
+x
5
+x
6
+k
3
+k
4
+k
5
+k
6
y
4
= x
4
+x
5
+x
6
+x
7
+k
4
+k
5
+k
6
+k
7
y
5
= x
5
+x
6
+x
7
+x
8
+k
5
+k
6
+k
7
+k
8
y
6
= x
6
+x
7
+x
8
+x
1
+k
6
+k
7
+k
8
+k
1
y
7
= x
7
+x
8
+x
1
+x
2
+k
7
+k
8
+k
1
+k
2
y
8
= x
8
+x
1
+x
2
+x
3
+k
8
+k
1
+k
2
+k
3
then it has very good diffusion, because each plain-
text bit or key bit affects half of the bits in the output
block y.
8
Confusion Requirement
Confusion: Each bit of the ciphertext block has highly
nonlinear relations with the plaintext block bits and the
key bits.
x plaintext
k
key
y
ciphertext
E (x)
k
Remark: Nonlinear functions are responsible for con-
fusion.
9
Confusion Requirement
Confusion: Each bit of the ciphertext block has highly
nonlinear relations with the plaintext block bits and the
key bits.
Example: Suppose that x, y and k all have 8 bits. If
y
1
= x
1
+x
2
+x
3
+x
4
+k
1
+k
2
+k
3
+k
4
y
2
= x
2
+x
3
+x
4
+x
5
+k
2
+k
3
+k
4
+k
5
y
3
= x
3
+x
4
+x
5
+x
6
+k
3
+k
4
+k
5
+k
6
y
4
= x
4
+x
5
+x
6
+x
7
+k
4
+k
5
+k
6
+k
7
y
5
= x
5
+x
6
+x
7
+x
8
+k
5
+k
6
+k
7
+k
8
y
6
= x
6
+x
7
+x
8
+x
1
+k
6
+k
7
+k
8
+k
1
y
7
= x
7
+x
8
+x
1
+x
2
+k
7
+k
8
+k
1
+k
2
y
8
= x
8
+x
1
+x
2
+x
3
+k
8
+k
1
+k
2
+k
3
then it has bad confusion, as they are linear relations.
10
Shannons Suggestion
The encryption and decryption functions of a cipher
should have both good confusion and diffusion of the
message block bits and secret key bits.
11
