Cryptography Reference
In-Depth Information
As you can guess from the discussion of the substitution cipher earlier in this
topic, the shift cipher is not secure at all. There are two ways of attacking it:
1. Since there are only 26 different keys (shift positions), one can easily launch a
brute-force attack by trying to decrypt a given ciphertext with all possible 26
keys. If the resulting plaintext is readable text, you have found the key.
2. As for the substitution cipher, one can also use letter frequency analysis.
1.4.4 Affine Cipher
Now, we try to improve the shift cipher by generalizing the encryption function.
Recall that the actual encryption of the shift cipher was the addition of the key
y
i
=
x
i
+
k
mod 26. The
affine cipher
encrypts by multiplying the plaintext by one
part of the key followed by addition of another part of the key.
Definition 1.4.4
Affine Cipher
Let x
,
y
,
a
,
b
∈
Z
26
Encryption
:e
k
(
x
)=
y
≡
a
·
x
+
b
mod 26
.
a
−
1
Decryption
:d
k
(
y
)=
x
b
) mod 26
.
with the key: k
=(
a
,
b
)
, which has the restriction:
gcd(
a
,
26)=1
.
≡
·
(
y
−
The decryption is easily derived from the encryption function:
·
≡
a
x
+
b
y
mod 26
a
·
x
≡
(
y
−
b
) mod 26
a
−
1
x
≡
·
(
y
−
b
) mod 26
The restriction gcd(
a
,
26)=1 stems from the fact that the key parameter
a
needs
to be inverted for decryption. We recall from Sect. 1.4.2 that an element
a
and the
modulus must be relatively prime for the inverse of
a
to exist. Thus,
a
must be in
the set:
(1.2)
But how do we find
a
−
1
? For now, we can simply compute it by trial and error:
For a given
a
we simply try all possible values
a
−
1
a
∈{
1
,
3
,
5
,
7
,
9
,
11
,
15
,
17
,
19
,
21
,
23
,
25
}
until we obtain:
a
−
1
a
·
≡
1 mod 26
For instance, if
a
= 3, then
a
−
1
= 9 since 3
1 mod 26. Note that
a
−
1
also
always fulfills the condition gcd(
a
−
1
,
26)=1 since the inverse of
a
−
1
always exists.
In fact, the inverse of
a
−
1
·
9 = 27
≡
is
a
itself. Hence, for the trial-and-error determination of
a
−
1
one only has to check the values given in Eq. (1.2).
