Cryptography Reference
In-Depth Information
1. Describe the relationship of the subkeys in the encryption and decryption algo-
rithm that is required so that Eq. (3.1) is fulfilled.
2. There are four weak DES keys. What are they?
3. What is the likelihood that a randomly selected key is weak?
3.8.
DES has a somewhat surprising property related to bitwise complements of its
inputs and outputs. We investigate the property in this problem.
We denote the bitwise complement of a number
A
(that is, all bits are flipped) by
A
.Let
⊕
denote bitwise XOR. We want to show that if
y
= DES
k
(
x
)
then
y
= DES
k
(
x
)
.
(3.2)
This states that if we complement the plaintext and the key, then the ciphertext
output will also be the complement of the original ciphertext. Your task is to
prove
this property.
Try to prove this property using the following steps:
1. Show that for any bit strings
A
,
B
of equal length,
A
⊕
B
=
A
⊕
B
and
A
⊕
B
)
.
B
=(
A
⊕
(These two operations are needed for some of the following steps.)
2. Show that
PC
1(
k
))
.
3. Show that
LS
i
(
C
i
−
1
)=(
LS
i
(
C
i
−
1
))
.
4. Using the two results from above, show that if
k
i
are the keys generated from
k
,
then
k
i
are the keys generated from
k
, where
i
= 1
,
2
,...,
16.
5. Show that
IP
(
x
)=(
IP
(
x
))
.
6. Show that
E
(
R
i
)=(
E
(
R
i
))
.
7. Using all previous results, show that if
R
i
−
1
,
L
i
−
1
,
k
i
generate
R
i
, then
R
i
−
1
,
L
i
−
1
,
k
i
generate
R
i
.
8. Show that Eq. (3.2) is true.
1(
k
)=(
PC
−
−
3.9.
Assume we perform a known-plaintext attack against DES with one pair of
plaintext and ciphertext. How many keys do we have to test in a worst-case sce-
nario if we apply an exhaustive key search in a straightforward way? How many on
average?
3.10.
In this problem we want to study the clock frequency requirements for a hard-
ware implementation of DES in real-world applications. The speed of a DES im-
plementation is mainly determined by the time required to do one core iteration.
This hardware kernel is then used 16 consecutive times in order to generate the en-
crypted output. (An alternative approach would be to build a hardware pipeline with
16 stages, resulting in 16-fold increased hardware costs.)
