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$
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.