Suppose the ciphertext obtained by encrypting a plaintext by affine transformation is: edsgi ckxhu klzve qzvkx wkzuk vcuh It is also known that the first two characters of the plaintext are if, Decrypt the ciphertext (known plaintext attack)
Suppose we are studying a known-plaintext attack on an affine cipher. Affine ciphers are simple substitution ciphers based on modulo operations and can be described by two main operations: multiplication and addition.
Specifically, for each plaintext character
p
p
p, we can calculate the corresponding ciphertext characters
c
c
c Use the following formula:
c
≡
a
×
p
+
b
m
o
d
m
c \equiv a \times p + b \mod m
c≡a×p + bmodm
in:
-
a
a
a and
b
b
b are the keys, they must be in modulo
m
m
Select within the range of m.
-
m
m
m is the size of the alphabet. For English text, usually
m
=
26
m=26
m=26 (26 letters).
Knowing that plaintext if corresponds to ciphertext ed, we can establish the following equation:
e
≡
a
×
i
+
b
m
o
d
26
e \equiv a \times i + b \mod 26
e≡a×i + bmod26
d
≡
a
×
f
+
b
m
o
d
26
d \equiv a \times f + b \mod 26
d≡a×f + bmod26
Here, we need to convert letters into numbers, let’s start from 0, that is
a
=
0
,
b
=
1
,
.
.
.
z
=
25
a=0, b=1, … z=25
a=0,b=1,…z=25.
Therefore, in the above equation
i
=
8
,
f
=
5
i=8, f=5
i=8,f=5.
Substituting these into the equation we get:
e
≡
8
a
+
b
m
o
d
26
e \equiv 8a + b \mod 26
e≡8a + bmod26
d
≡
5
a
+
b
m
o
d
26
d \equiv 5a + b \mod 26
d≡5a + bmod26
Using the equation above, we can try to calculate the possible
a
a
a and
b
b
b value. However, it should be noted that
a
a
a must be a number between 26 and relatively prime with 26, that is
g
c
d
(
a
,
26
)
=
1
gcd(a, 26) = 1
gcd(a,26)=1. So, it’s possible
a
a
The values of a are 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25.
by trying all possible
a
a
a value, we can find the value that satisfies the above equation
a
a
a and
b
b
b.
turn up
a
a
a and
b
b
b Afterwards, we can use the decryption formula of the affine cipher to decrypt the complete ciphertext. The decryption formula is:
p
≡
a
?
1
×
(
c
?
b
)
m
o
d
m
p \equiv a^{-1} \times (c – b) \mod m
p≡a?1×(c?b)modm
in
a
?
1
a^{-1}
a?1 is
a
a
a in mold
m
m
Multiplicative inverse under m.
This is a simple way to perform a known plaintext attack. In fact, you need to try all
a
a
a value until a suitable one is found. This attack is mainly based on the linear properties of affine cryptography and known plaintext-ciphertext pairs.
Python code examples
def gcd(a, b):
while b:
a, b = b, a % b
return a
def mod_inverse(a, m):
for i in range(1, m):
if (a * i) % m == 1:
return i
return None
def find_key(plain, cipher):
i, f = ord('i') - ord('a'), ord('f') - ord('a')
e, d = ord('e') - ord('a'), ord('d') - ord('a')
for a in range(26):
b = (e - a * i) % 26
if (d - a * f) % 26 == b and gcd(a, 26) == 1:
return a, b
return None, None
def affine_decrypt(ciphertext, a, b):
a_inv = mod_inverse(a, 26)
plaintext = ''
for char in ciphertext:
if char.isalpha():
x = ord(char) - ord('a')
p = (a_inv * (x - b)) % 26
plaintext + = chr(p + ord('a'))
else:
plaintext + = char
return plaintext
# Known plaintext and ciphertext pairs
known_plain = "if"
known_cipher = "ed"
a, b = find_key(known_plain, known_cipher)
if a and b:
ciphertext = "edsgickxhuklzveqzvkxwkzukvcuh"
decrypted_text = affine_decrypt(ciphertext, a, b)
print("Decrypted text:", decrypted_text)
else:
print("Unable to find keys a and b")