Cryptography Reference
In-Depth Information
26 with gcd ( a, 26) = 1. As such, the
the key space
K
consists of all pairs ( a, b )
Z
key space has φ (26)
26 = 312 elements and is far too small for practical use. It
can, however, be used for demonstrational purposes. In fact, the encryption function
of an affine cipher is defined as follows:
·
E ( a,b )
:
M−→C
m
−→
am + b (mod 26) = c
Similarly, the decryption function is defined as follows:
D ( a,b )
:
C−→M
c
a 1 ( c
−→
b ) (mod 26) = m
Z 26 is needed to
decrypt c . Remember from Chapter 3 that the extended Euclid algorithm (i.e.,
Algorithm 3.2) can be used to efficiently compute this element.
An affine cipher can be broken with two known plaintext-ciphertext pairs. If,
for example, the adversary knows ( F, Q )=(5 , 16) and ( T,G )=(19 , 6), 3
Obviously, the multiplicative inverse of a (i.e., a 1 ) in
then he
or she can set up the following system of two equivalences:
a 5+ b
16 (mod 26)
a 19 + b
6 (mod 26)
The first equivalence can be rewritten as b
5 a (mod 26) andusedin
16
the second equivalence: 19 a + b
19 a +16
5 a
14 a +16
6 (mod 26).
Consequently, 14 a
8 (mod 13), respectively.
By multiplying either side with the multiplicative inverse element of 7 modulo 26
(which is 2), one gets a
≡−
10
16 (mod 26),or7 a
3 (mod 13), and hence a =3and b =1.The
adversary can now efficiently compute D ( a,b )
16
similar to the legitimate recipient of
the encrypted message.
Σ=
} = Z 26 is a good choice for human beings. If, however,
computer systems are used for encryption and decryption, then it is advantageous
and more appropriate to use Σ=
{
A,...,Z
} = F 2 and to set the plaintext message,
Z 2 =
{
0 , 1
3
This means that the letter “F” is mapped to the letter “Q” and the letter “T” is mapped to the letter
“G.”
Search WWH ::




Custom Search