Cryptography Reference
In-Depth Information
1.12.
Now, we want to extend the affine cipher from Sect. 1.4.4 such that we can
encrypt and decrypt messages written with the full German alphabet. The German
alphabet consists of the English one together with the three umlauts, A, O, U, and the
(even stranger) “double s” character ß. We use the following mapping from letters
to integers:
A
↔
0
B
↔
1
C
↔
2
D
↔
3
E
↔
4
F
↔
5
G
↔
6
H
↔
7
I
↔
8
J
↔
9
K
↔
10
L
↔
11
M
↔
12
N
↔
13
O
↔
14
P
↔
15
Q
↔
16
R
↔
17
S
↔
18
T
↔
19
U
↔
20
V
↔
21
W
↔
22
X
↔
23
A
O
U
Y
↔
24
Z
↔
25
↔
26
↔
27
↔
28
ß
↔
29
1. What are the encryption and decryption equations for the cipher?
2. How large is the key space of the affine cipher for this alphabet?
3. The following ciphertext was encrypted using the key (
a
= 17
,
b
= 1). What is
the corresponding plaintext?
¨außwß
4. From which village does the plaintext come?
1.13.
In an attack scenario, we assume that the attacker Oscar manages somehow
to provide Alice with a few pieces of plaintext that she encrypts. Show how Oscar
can break the affine cipher by using two pairs of plaintext-ciphertext, (
x
1
,
y
1
) and
(
x
2
,
y
2
). What is the condition for choosing
x
1
and
x
2
?
Remark
: In practice, such an assumption turns out to be valid for certain settings,
e.g., encryption by Web servers, etc. This attack scenario is, thus, very important and
is denoted as a
chosen plaintext attack
.
1.14.
An obvious approach to increase the security of a symmetric algorithm is to
apply the same cipher twice, i.e.:
y
=
e
k
2
(
e
k
1
(
x
))
As is often the case in cryptography, things are very tricky and results are often dif-
ferent from the expected and/ or desired ones. In this problem we show that a double
encryption with the affine cipher is only as secure as single encryption! Assume two
affine ciphers
e
k
1
=
a
1
x
+
b
1
and
e
k
2
=
a
2
x
+
b
2
.
1. Show that there is a single affine cipher
e
k
3
=
a
3
x
+
b
3
which performs exactly
the same encryption (and decryption) as the combination
e
k
2
(
e
k
1
(
x
)).
2. Find the values for
a
3
,
b
3
when
a
1
= 3
,
b
1
= 5 and
a
2
= 11
,
b
2
= 7.
3. For verification: (1) encrypt the letter
K
first with
e
k
1
and the result with
e
k
2
, and
(2) encrypt the letter
K
with
e
k
3
.
4. Briefly describe what happens if an exhaustive key-search attack is applied to a
double-encrypted affine ciphertext. Is the effective key space increased?
Remark:
The issue of multiple encryption is of great practical importance in the
case of the Data Encryption Standard (DES), for which multiple encryption (in par-
ticular, triple encryption) does increase security considerably.
