Affine Cipher

March 20, 2019

A linear cipher like the Hill Cipher is vulnerable to a known plaintext attack: just resolve a set of linear equations and get the secret key.

An affine cipher is a little harder to break, however it could be vulnerable to a differential attack.

Formerly, an affine encryption looks like this

$$ A p_i + B = c_i\quad(\textrm{mod } m)$$

and the decryption like this:

$$ p_i = [A]^{-1} (c_i - B)\quad(\textrm{mod } m)$$

where $A$ and $B$ are secret and unknown to the attacker but we can assume that have known shapes of $n\textrm{x}n$ and $n\textrm{x}1$ respectively.

Differential cryptanalysis

Consider the following ciphertext and the partial known plaintext:

>>> from cryptonita import B as asbytes
>>> import numpy as np

>>> m = 251
>>> ciphertext = asbytes(b'"\x93&\xd3)\x97\xb0\xa8\xa6\xf17@,f\xb2\x17LsNs\xe0\xd7').toarray()
>>> kplaintext = asbytes(b'..fi....ra..fo..at....').toarray()

From there we can take two plaintexts $p_i$ and $p_j$ with their associated ciphertexts $c_i$ and $c_j$.

$$ A p_i + B = c_i\quad(\textrm{mod } m)$$ $$ A p_j + B = c_j\quad(\textrm{mod } m)$$

If we substract both equations we obtain a linear system like the Hill Cipher:

$$ A (p_i - p_j) = (c_i - c_j)\quad(\textrm{mod } m) $$

⊕ Keep in mind the affine transformation is a block cipher with blocks of $n$ bytes. So the plaintext/ciphertext pairs must be $n$-bytes aligned (they must come from positions multiple of $n$).

In order to break an affine cipher we need $2n$ independent plaintext-ciphertext pairs (for a linear cipher we need just $n$)

Here is the first two pairs and the first difference:

>>> p11, c11 = kplaintext[2:4].reshape(2,1), ciphertext[2:4].reshape(2,1)
>>> p12, c12 = kplaintext[12:14].reshape(2,1), ciphertext[12:14].reshape(2,1)

>>> dp1 = (p11 - p12) % m
>>> dc1 = (c11 - c12) % m

Here we build the second difference:

>>> p21, c21 = kplaintext[8:10].reshape(2,1), ciphertext[8:10].reshape(2,1)
>>> p22, c22 = kplaintext[16:18].reshape(2,1), ciphertext[16:18].reshape(2,1)

>>> dp2 = (p21 - p22) % m
>>> dc2 = (c21 - c22) % m

Stacking all this together we build the difference matrices for the plaintexts and ciphertexts of shapes $n\textrm{x}n$.

>>> dP = np.hstack((dp1, dp2))
>>> dC = np.hstack((dc1, dc2))

Remembering that the linear cipher is:

$$ A\ dP = dC \quad(\textrm{mod } m)$$

From here we can obtain $A$:

$$ A = dC\ [dP]^{-1} \quad(\textrm{mod } m)$$

>>> from cryptonita.mod import inv_matrix
>>> idP = inv_matrix(dP, m)

>>> A = np.dot(dC, idP) % m
>>> A
array([[ 95,   1],
       [ 88, 191]])

>>> iA = inv_matrix(A, m)
>>> iA
array([[  4,  67],
       [123, 161]])

Using one of the plaintext-ciphertext pairs we can obtain the remaining unknown value: the $B$ vector.

$$ B = c - A p \quad(\textrm{mod } m)$$

>>> B = (c11 - np.dot(A, p11)) % m

Finally, let’s decrypt the message!

>>> cblocks = asbytes(ciphertext).nblocks(2)
>>> pblocks = []

>>> for cb in cblocks:
...     cb = cb.toarray().reshape(2,1)
...     pb = np.dot(iA, cb - B) % m
...     pb = asbytes(pb.reshape(-1))
...     pblocks.append(pb)

>>> plaintext = b''.join(pblocks)
>>> plaintext
'Affine transformation!'