1
$\begingroup$

Update 2

Being new to the world of Stack Exchange I did not realize that there exists a site solely devoted to cryptography. In light of this, I hope someone could help me migrate this question to the appropriate site. Unless, of course, someone could answer the question here instead. I am not getting anywhere with this question.

Background

Last year, a question concerning plaintext attacks was posted on on this website. I have no problem to see how to solve it when we are given two ciphertexts and $(c_1,c_2)$ and their corresponding plaintexts $(m_1,m_2)$. But, when I am to deal with the situation where $p$ is unknown it gets complicated. In this instance, I have three pairs of ciphertexts and plaintexts - $c_i \not =c_j$ for $i,j \in \{1,2,3\}$ and $m_i \not = m_j$ for $i,j \in \{1,2,3\}$. This differs then from the previous question in the sense that I cannot use the method that fkraiem provided given two of the ciphertexts are equal.

To find $p$:

You have $k_1m_1+k_2 \equiv k_1m_2+k_2 \equiv c_2 \pmod p$ so $k_1(m_1-m_2) \equiv 0 \pmod p$. This means that either $k_1$ or $m_1-m_2$ is a multiple of $p$ (this is where the fact that $p$ is prime comes in). $k_1$ can't be a multiple of $p$, because otherwise the encryption function is constant, which is absurd, so $m_1-m_2$ is a multiple of $p$.

You can now try to find $k_1,k_2$ using each prime divisor of $m_1-m_2$ as modulus until you find one which works for the two pairs $((m_1,c_2),(m_3,c_3))$ and $((m_2,c_2),(m_3,c_3))$.

Thus my question is this: How would one go about determine $p$ if the ciphertexts are all different?

Update

For example, suppose $(c_1,c_2,c_3)=(13,19,3)$ and $(m_1,m_2,m_3)=(5,10,23)$. How do I go about to determine $p$?

$\endgroup$
0
$\begingroup$

You know from the affine equations that there are $t_i$ such that $5k_1 + k_2 = 13 + t_1p, 10k_1 +k_2 = 19+t_2p$ and $23k_1+k_2=3+t_3p$. The first 2 subtracted tells us that $5k_1 -6$ is a multiple of $p$, and the third minus the first tells us $18k_1+10$ is a multiple of $p$ as well.

Multiply $5k_1 -6$ by $18$ and $18k_1+10$ by $5$ and we still have multiples of $p$. Subtract and we know $158$ is a multiple of $p$.

Now you can fill in the rest I think.

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