1
$\begingroup$

I'm currently trying to prove the following:

Where p is a prime number of cryptographic size, prove that:

  • e(m) = am + b (mod p) where a and b are private is open to a known plaintext attack
  • e(m) = am + b (mod p) where a, b, and p are private is open to a known plaintext attack
  • e(m1,m2) = $ \left[ \begin{array}{ c c } m1 & m2 \end{array} \right] $ $\left[ \begin{array}{ c c } a & b \\ c & d \end{array} \right] $ + $ \left[ \begin{array}{ c c } e & f \end{array} \right] $ mod p

where a,b,c,d,e,f are private and m1 and m2 are two parts of a message is open to a chosen plaintext attack.

I think I've figured out the answer for the first one (it's an affine cipher with variable values for the modulus instead of 26, if the adversary Eve has 2 samples of plaintext-ciphertext pairs then it's not too hard to prove that she can find the decryption function which allows her to decode the entire message).

I'm having trouble with the last two however. With the 2nd one, how will having a few samples of plaintext-ciphertext pairs help Eve find out p? With the 3rd one, I'm not seeing how her ability to choose particular plaintext and finding out their corresponding ciphertext helps her find out how to decrypt the message.

Any guidance would be highly appreciated.

$\endgroup$
2
$\begingroup$

how will having a few samples of plaintext-ciphertext pairs help Eve find out p [in the second scheme]?

Well, suppose we have four plaintext/ciphertext pairs, and lets look at what is available to the attacker. We make the plaintexts $m_1$, $m_2$, $m_3$, $m_4$, and the corresponding ciphertexts:

$$e_1 = a m_1 + b + k_1 p$$ $$e_2 = a m_2 + b + k_2 p$$ $$e_3 = a m_3 + b + k_3 p$$ $$e_4 = a m_4 + b + k_4 p$$

for unknown values $a$, $b$, $p$, and $k_1, k_2, k_3, k_4$.

First step: can we combine these ciphertexts in a way to form three values that do not involve the unknown $b$ values? Hint: consider $e_1 - e_2$.

Second step: can we combine the values from step 1 in a way to form two values that are both multiplies of $p$?

Third step: given two values which are multiples of $p$, what's an efficient way to recover $p$?

With the 3rd one, I'm not seeing how her ability to choose particular plaintext and finding out their corresponding ciphertext helps her find out how to decrypt the message.

Suppose you ask for the encryptions of the values $(x,w), (y,w), (z,w)$; how could we use the previous observation to recover $p$? (Hint: you might find it a bit easier if you assume a few more chosen texts).

$\endgroup$
  • $\begingroup$ Thanks for the help! I've made progress with the second one and eliminated the b. I can't seem to get rid of the a however...I tried doing e1 - e2 , e2 - e3, and e3 - e4. I'm not sure if that's the way I should be approaching the problem. $\endgroup$ – user21547 Jan 27 '15 at 18:33
  • $\begingroup$ Also, you suggested for the 3rd one that we ask for the encryptions of (a,d), (b,d), (c,d) but aren't a, b, c, d supposed to be private? How would we give them to be encrypted if we don't know what they are? $\endgroup$ – user21547 Jan 27 '15 at 18:41
  • $\begingroup$ @user21547: oops, I meant them as arbitrary parameters -- I forgot that the cipher used them as key variables. I changed the answer to use the values $x, y, z, w$ $\endgroup$ – poncho Jan 27 '15 at 18:53
  • $\begingroup$ @user21547: if $e_1 - e_2 = a(m_1 - m_2) + (k_1-k_2)p$ and $e_2 - e_3 = a(m_2 - m_3) + (k_2-k_3)p$, what is $(e_1-e_2)(m_2-m_3) - (e_2-e_3)(m_1-m_2)$? $\endgroup$ – poncho Jan 27 '15 at 18:56

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.