Cryptography Reference
In-Depth Information
Problems
3.1.
As stated in Sect. 3.5.2, one important property which makes DES secure is that
the S-boxes are nonlinear. In this problem we verify this property by computing the
output of
S
1
for several pairs of inputs.
Show that
S
1
(
x
1
)
⊕
S
1
(
x
2
)
=
S
1
(
x
1
⊕
x
2
), where “
⊕
” denotes bitwise XOR, for:
1.
x
1
= 000000,
x
2
= 000001
2.
x
1
= 111111,
x
2
= 100000
3.
x
1
= 101010,
x
2
= 010101
) and
IP
−
1
(
3.2.
We want to verify that
IP
(
) are truly inverse operations. We con-
sider a vector
x
=(
x
1
,
x
2
,...,
x
64
) of 64 bit. Show that
IP
−
1
(
IP
(
x
)) =
x
for the first
five bits of
x
, i.e. for
x
i
,
i
= 1
,
2
,
3
,
4
,
5.
·
·
3.3.
What is the output of the first round of the DES algorithm when the plaintext
and the key are both all zeros?
3.4.
What is the output of the first round of the DES algorithm when the plaintext
and the key are both all ones?
3.5.
Remember that it is desirable for good block ciphers that a change in one input
bit affects many output bits, a property that is called diffusion or the avalanche
effect. We try now to get a feeling for the avalanche property of DES. We apply an
input word that has a “1” at bit position 57 and all other bits as well as the key are
zero. (Note that the input word has to run through the initial permutation.)
1. How many S-boxes get different inputs compared to the case when an all-zero
plaintext is provided?
2. What is the minimum number of output bits of the S-boxes that will change
according to the S-box design criteria?
3. What is the output after the first round?
4. How many output bit after the first round have actually changed compared to
the case when the plaintext is all zero? (Observe that we only consider a single
round here. There will be more and more output differences after every new
round. Hence the term
avalanche effect
.)
3.6.
An avalanche effect is also desirable for the key: A one-bit change in a key
should result in a dramatically different ciphertext if the plaintext is unchanged.
1. Assume an encryption with a given key. Now assume the key bit at position 1
(prior to
PC
1) is being flipped. Which S-boxes in which rounds are affected
by the bit flip during DES encryption?
2. Which S-boxes in which DES rounds are affected by this bit flip during DES
decryption?
−
3.7.
ADESkey
K
w
is called a
weak key
if encryption and decryption are identical
operations:
DES
K
w
(
x
)=DES
−
1
K
w
(
x
)
,
for all
x
(3.1)
