Following the question I posted on: Chosen-plaintext-attack on "Affine Cipher" - Numerous questions, I then attempted question 1.41 (d).

You assume now that $p$ is not public knowledge, and are asked how many ciphertext / plaintext pairs $(c_1,m_1), (c_2,m_2), ... (c_n, m_n)$ are needed to make system vulnerable / & or is it secure against this attack.

My attempts:

[I chose upto 8 different random positive numbers (from 1 to 500) in the pairs.(4 numbers for 2 pairs, 6 for 3 pairs etc).]

  1. With 2 pairs, there are 2 congruences, and found that an infinite amount of solutions is possible.

  2. With 3 pairs, there are 3 congruences, and I found the number of possible solutions is much less than that for 2 pairs, and there are finitely many (multiple solutions for 2 independent congruences). So without the use of a computer would take a few hours to solve by hand & find all possible solutions $\mod p$.

  3. With 4 pairs, there are 4 congruences, and I found this could be simplified to 2 congruences in terms of multiples of $k_1$ $\mod p$. For example;

$$4k_1+ap=57$$ $$4k_1+bp=-4258,$$

and that I could derive a formula for what $p$ could be from this;

$$p=\frac{4315}{a-b}=5\frac{863}{a-b}$$ with $a\neq b$, $a, b \in \mathbb{Z}$


$$4k_1+ap=n_1$$ $$4k_1+bp=n_2$$

$p=\frac{n_1-n_2}{a-b}$, where $q$ may divide $(n_1-n_2)$, $q\in \mathbb{Z}$ .

I notice that when $a-b=q$, and $q$ divides $n_1 - n_2$, that $p$ is prime when $\frac{n_1-n_2}{q}$ is prime.


  1. From 3rd attempt - the conjectured formulae for $p$ may sometimes give values for $p$ that are not prime. Is this correct? If true I presume this is from which numbers are being chosen in the ciphertext / plaintext pairs.

  2. (Only applicable if conjecture in question 1 is correct); When using 4 ciphertext / plaintext pairs, can one derive / show how many possible pairs you can chose for $p$ to be prime? How about $n$ pairs?

  3. Is the cipher used with $p$ prime vulnerable to chosen-plaintext-attack when you have 4 correct pairs? - I think it is since you can derive $p$, then obtain $k_1$ and $k_2$ easily from these.


Your Answer

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

Browse other questions tagged or ask your own question.