0
$\begingroup$

In "An introduction to Mathematical Cryptography", published by Springer, on page 56 question 1.41(b), they ask why the "Affine Cipher" below is vulnerable to a chosen-plaintext-attack, assuming $p$ and $c$ are public knowledge.

They define the Cipher on page 43 as;

$$e_k(m)=k_1 . m +k_2 \mod p$$ $$d_k(c)=k_{1}^{'} . (c-k_2) \mod p $$

Where $k_{1}^{'}$ is the inverse of $k_1$ modulo $p$

I have tried using $p=17$, and $c_1=401$.

1) I can't currently see how the Cipher is weakened / vulnerable - there are still many possible values for $m_1$, $k_1$ and $k_2$.

2) Is the objective of the attack to reduce the solution space of the keys and messages?

$\endgroup$

2 Answers 2

3
$\begingroup$

Correct me if I'm wrong, but I think the chosen plaintext attack assumes that the attacker can ask for $e_k(m)$ for his choice of selected (few) values of $m$.

So if the attacker can ask for, and is given $e_k(0)=k_2$ and $e_k(1)=k_1+k_2$, they can easily solve for $k_1=e_k(1)-e_k(0)$ (all arithmetic done in $\Bbb{Z}_p$). Therefore they have broken the key.

$\endgroup$
0
$\begingroup$

In another attempt I chose two plaintext & ciphertext pairs (as per hint in question in the book);

$$(m_1,c_1)=(104,401)$$ $$(m_2,c_2)=(292,398)$$

Substituting each into the encryption function & simplifying I get 2 simultaneous congruences;

$$2k_1+k_2 = 10, \mod 17$$ $$3k_1 +k_2 = 7, \mod 17$$

One can solve for $k_1,k_2$ from this;

$$k_1 = 14, \mod 17$$ $$k_2 = 16, \mod 17$$

Thus

$$c=e_k(m)=14m +16, \mod 17$$

And

$$m=d_k(c)=14^{-1} . (c-16), \mod 17 $$

Hence why with only 2 correct plaintext / ciphertext pairs, the system can be broken, and hence the system is vulnerable to chosen-plaintext attack.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .