Understanding Cryptography by Christof Paar and Jan Pelzl - Chapter 1 Solutions - Ex1.13

- 1 min

Exercise 1.13

In an attack scenario, we assume that the attacker Oscar manages somehow to provide Alice with a few pieces of plaintext that she encrypts. Show how Oscar can break the affine cipher by using two pairs of plaintext–ciphertext, \((x_1, y_1)\) and \((x_2, y_2)\). What is the condition for choosing \(x_1\) and \(x_2\)?

Remark: In practice, such an assumption turns out to be valid for certain settings, e.g., encryption by Web servers, etc. This attack scenario is, thus, very important and is denoted as a chosen plaintext attack.


This solution is verified as correct by the official Solutions for Odd-Numbered Questions manual.

In order to use the chosen plaintext attack, the plaintexts need to be chosen such that \(\mathrm{gcd}(x_2 - x_1, m) = 1\), where \(m\) is the size of the alphabet being encrypted. Another way to put this is that \(x_2 - x_1\) must have multiplicative inverse in \(m\).

The following equations can be derived by trying to solve the two chosen plaintext encryptions as a pair of simultaneous equations:

\[a \equiv (x_1 −x_2)^{-1}(y_1 − y_2)\,\mathrm{mod}\,m\] \[b \equiv y_1 − ax_1\,\mathrm{mod}\,m\]
Thomas Busby

Thomas Busby

I write about computing stuff

comments powered by Disqus
rss facebook twitter github youtube mail spotify instagram linkedin google google-plus pinterest medium vimeo stackoverflow reddit quora