1
$\begingroup$

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

Generalising;

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

Questions:

  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.

$\endgroup$

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.