Affine cipher

Affine cipher is a monoalphabetical symmetrical substitution cipher, which eliminates the biggest drawback of the Caesar cipher – very easy cryptanalysis stemming from the low number of possible transformations.

Encryption

The affine cipher is based on the transformation which can be expressed using the following formula:

$C_{i} = a \\cdot T_{i} + b \\pmod{m}$

C_i – i-th character of the ciphertext
T_i – i-th character of the plaintext
a – parameter a, gcd(a,m) = 1
b – parameter b
m – modulus (we usually choose a prime number, because then we can be sure, that gcd(a, m) = 1. The prime modulus also maximizes the number of potential transformations.

Example

Encrypt the plaintext using affine cipher.

Plaintext: THEINITIAL
a = 5
b = 9
m = 26

T ⇒ 19 ⇒ 5*19 + 9 mod(26) = 0  ⇒ A
H ⇒ 7  ⇒ 5*7  + 9 mod(26) = 18 ⇒ S
E ⇒ 4  ⇒ 5*4  + 9 mod(26) = 3  ⇒ D
I ⇒ 8  ⇒ 5*8  + 9 mod(26) = 23 ⇒ X
N ⇒ 13 ⇒ 5*13 + 9 mod(26) = 22 ⇒ W
I ⇒ 8  ⇒ 5*8  + 9 mod(26) = 23 ⇒ X
T ⇒ 19 ⇒ 5*19 + 9 mod(26) = 0  ⇒ A
I ⇒ 8  ⇒ 5*8  + 9 mod(26) = 23 ⇒ X
A ⇒ 0  ⇒ 5*0  + 9 mod(26) = 9  ⇒ J
L ⇒ 11 ⇒ 5*11 + 9 mod(26) = 12 ⇒ M

Decryption

Decryption has to revert changes made by encryption, hence we must use the following formula:

$T_{i} = (C_{i} \\; - \\; b) \\cdot a^{-1} \\pmod{m}$

a^-1 – multiplicative inverse of a in Z_m

Example

Decrypt the ciphertext using affice cipher.

Ciphertext: ASDXWXAXJM
a = 5
b = 9
m = 26

Using the extended Euclid algorithm we calculate:

$a^{-1} = 21$

A ⇒ 0  ⇒ (0  – 9) * 21 mod(26) = 19 ⇒ T
S ⇒ 18 ⇒ (18 – 9) * 21 mod(26) = 7  ⇒ H
D ⇒ 3  ⇒ (3  – 9) * 21 mod(26) = 4  ⇒ E
X ⇒ 23 ⇒ (23 – 9) * 21 mod(26) = 8  ⇒ I
W ⇒ 22 ⇒ (22 – 9) * 21 mod(26) = 13 ⇒ N
X ⇒ 23 ⇒ (23 – 9) * 21 mod(26) = 8  ⇒ I
A ⇒ 0  ⇒ (0  – 9) * 21 mod(26) = 19 ⇒ T
X ⇒ 23 ⇒ (23 – 9) * 21 mod(26) = 8  ⇒ I
J ⇒ 9  ⇒ (23 – 9) * 21 mod(26) = 0  ⇒ A
M ⇒ 12 ⇒ (12 – 9) * 21 mod(26) = 11 ⇒ L

Breaking the cipher

Because there are many possible combinations of input parameters of the affine cipher, the brute force attack is inefficient, but still feasible. The weak point of the cipher is the frequency analysis.

Example

We have gathered by eavesdropping the following ciphered English text and we know the used modulus (26).

ASDXWXAXJMJYKJWTDBIASDVXUASJQRZPJVVBVFTTDVVIFM
ASJASXAMDQXWADQKDWDYJWYBQYDQDYASDIBFQASGJWEDQJ
QRZABCBXWJQRZNQBFGVBFASJABASDVBFASJRJVVXKDAQJI
IXTCJRQDVFMADYPSDWASDIBFQASGJWEDQJWYASDVXUASOB
ASQDLFXQDYASDIDPQBJYVXWASDJQDJOBASJQRXDVPDQDVA
BGGDYYDJYPSXMDASDZJAADRGADYABTMDJQASDQDVFMAXWN
RDVVBIASBFVJWYVBIKDSXTMDVASDYDMJZPJVMBWNJWYXAX
VASBFNSAASJAXATBVAASDJYKJWTDJAMDJVABWDPDDHPXAS
ASDJYKJWTDWBPVMBPDYSXAMDQTSJWNDYSXVRXWYJWYQDJV
VXNWDYASDIBFQASGJWEDQJQRZOJTHABASDJAAJTHBWVAJM
XWNQJY

Now we can calculate frequencies of the characters in the ciphered text (in percent).

A (0): 11.802575107296137
B (1): 6.008583690987124
C (2): 0.4291845493562232
D (3): 12.660944206008583
E (4): 0.6437768240343348
F (5): 2.7896995708154506
G (6): 1.502145922746781
H (7): 0.6437768240343348
I (8): 2.1459227467811157
J (9): 9.656652360515022
K (10): 1.2875536480686696
L (11): 0.2145922746781116
M (12): 3.004291845493562
N (13): 1.502145922746781
O (14): 0.6437768240343348
P (15): 2.1459227467811157
Q (16): 6.008583690987124
R (17): 2.1459227467811157
S (18): 7.939914163090128
T (19): 2.575107296137339
U (20): 0.4291845493562232
V (21): 6.437768240343347
W (22): 5.579399141630901
X (23): 5.36480686695279
Y (24): 5.150214592274678
Z (25): 1.2875536480686696

We know, that in plain English text, the most common character are E (12.702%) and T (9.056%), hence we can suppose that they have been transformed into D and A. If we plug the order in alphabet of the mentioned characters into the encryption formula, we get:

0 = a*19 + b mod(26)
3 = a*4  + b mod(26)

We can subtract these equations, and calculate the multiplicative inversion of 11 using the extended Euclid algorithm and we get the value of the variable :

3 = -15*a mod(26)
3 = 11*a mod(26)
a = 3*11^-1 mod(26)
a = 3*19 mod(26)
a = 5 mod(26)

Plug into the first equation and we get the variable .

0 = 5*19 + b mod(26)
0 = 17 + b mod(26)
b = -17 mod(26)
b = 9 mod(26)

Now we can decipher the encrypted text:

THEINITIALADVANCEOFTHESIXTHARMYWASSOSUCCESSFUL
THATHITLERINTERVENEDANDORDEREDTHEFOURTHPANZERA
RMYTOJOINARMYGROUPSOUTHATOTHESOUTHAMASSIVETRAF
FICJAMRESULTEDWHENTHEFOURTHPANZERANDTHESIXTHBO
THREQUIREDTHEFEWROADSINTHEAREABOTHARMIESWEREST
OPPEDDEADWHILETHEYATTEMPTEDTOCLEARTHERESULTING
MESSOFTHOUSANDSOFVEHICLESTHEDELAYWASLONGANDITI
STHOUGHTTHATITCOSTTHEADVANCEATLEASTONEWEEKWITH
THEADVANCENOWSLOWEDHITLERCHANGEDHISMINDANDREAS
SIGNEDTHEFOURTHPANZERARMYBACKTOTHEATTACKONSTAL
INGRAD

Encryption

Example

Decryption

Example

Breaking the cipher

Example

Doporučujeme