2
$\begingroup$

I'm studying for a cryptography test and I came across this question:

Assume a language has three letters: A=1111, B=0011 and C=1010. Two words in this language are encrypted with a one-time pad and by using the same binary key sequence. The first four bits for both corresponding cipher texts are, respectively: $C_1= 1110$ and $C_2=1000$. Determine the first letter of both corresponding plain texts as well as the first 4 bits of the key.

Isn't this question impossible to solve without additional information? Because:

$C_1 = L_1 + K + P_1$

$C_2 = L_2 + K + P_2$

Where $C_i$ is the cipher text, $L_i$ is the encrypted letter, $P_i$ is the one time pad and $K$ is the key.

Seeing how $L_1, L_2, P_1, P_2$ and $K$ are unknown, it's not possible to solve this, right? Or am I missing something?

$\endgroup$
  • $\begingroup$ The question is incredibly ambiguous. Is the second quote from the question or your interpretation? Does it state whether $P_i$ are random binary values or from the same alphabet? $\endgroup$ – otus Oct 26 '15 at 13:29
  • $\begingroup$ The data is not quite right. As was observed below, all plain text letters have the third bit set to 1. So all third bits in the ciphertext would be the same in a double "one-time pad", which is not the case for $C_1$ and $C_2$. $\endgroup$ – Henno Brandsma Oct 26 '15 at 13:40
  • $\begingroup$ Also, do you know what operation $+$ is? Addition modulo 16 and bitwise XOR are probably the most likely ones. $\endgroup$ – otus Oct 26 '15 at 13:42
  • $\begingroup$ I assumed XOR, as this is standard for a one-time pad. $\endgroup$ – Henno Brandsma Oct 26 '15 at 13:43
  • $\begingroup$ The second quote is my interpretation. The first quote is taken directly from an old exam I'm doing. I use the $+$ operation to mean XOR . I'm beginning to suspect the question itself is wrong... $\endgroup$ – user1870238 Oct 26 '15 at 13:44
0
$\begingroup$

The question is either wrong or leaves something important unstated.

Two reasonable interpretations for the ambiguous "with a one-time pad and by using" would be the equations in your question or the ones in yyyyyyy's answer. In the former case you have to assume something about the OTPs for there to be any hope. For example, that $P_1, P_2 \in \{A, B, C\}$.

In either case $C_1 \oplus C_2 = L_1 \oplus L_2 (\oplus P_1 \oplus P_2) = 0110$ cannot be produced by any combination of $A, B, C$. (You would need an odd number of letters, at least 3, to produce it.)

Further, if you take the combination operation to be addition modulo 16, then $C_1 - C_2 = L_1 - L_2 (+ P_1 - P_2) = 0110$, which also cannot be produced by any pair or quadruple of letters.

$\endgroup$
1
$\begingroup$

First, there seems to be a misunderstanding: The one-time pad is the key. So your equations simplify to $$ C_1 = L_1 + K \text, $$ $$ C_2 = L_2 + K \text. $$

At this point, you would be right if the $L_i$ could contain arbitrary bit sequences. However, the question imposes a constraint: $L_i\in\{A=\mathtt{1111},B=\mathtt{0011},C=\mathtt{1010}\}$.

Let's look only at the first bit of all the variables (I'll denote these in lower-case). Since $c_1=c_2$ by observation, you know that $l_1=l_2$ from the equations above. Hence given the alphabet from the question, we know that either both $L_1$ and $L_2$ are $B=\mathtt{0011}$, or they are both not $B$. You can proceed similarly for the next bits, and at some point you should be able to reduce the set of possibilities to one unique solution.

$\endgroup$
  • $\begingroup$ $C_1 \neq C_2$, or am I missing something? $\endgroup$ – Henno Brandsma Oct 26 '15 at 13:27
  • $\begingroup$ Okay, that makes sense. However, the third bit of on both ciphers is equal to 1 and 0 respectively, but if you look at the third bit of all possible letters, you'll see that they're all equal to 1. So what's going on there? In mathematical terms: $c_{1,3} \neq c_{2,3}$ and $l_{A,3} = l_{B,3} = l_{C,3} = 1$ $\endgroup$ – user1870238 Oct 26 '15 at 13:32
  • $\begingroup$ Yes, I get contradictions in all 3 cases. Something is amiss. $\endgroup$ – Henno Brandsma Oct 26 '15 at 13:38
  • $\begingroup$ @HennoBrandsma $c_i$ is supposed to denote $C_i$'s first bit. $\endgroup$ – yyyyyyy Oct 26 '15 at 18:07
0
$\begingroup$

The one-time pad is the key. We know that $C_1 = 1110$, $C_2 = 1000$, $C_1 = K + L_1, C_2 = K + L_2$.

If $L_1 = 1111$, then $K$ (the one-time pad first byte, or the first key byte) must equal $0001 = C_1 + L_1$, where $+$ denotes the bitwise xor. But then $L_2 = C_2 + K = 1000 + 0001 = 1001$, which is not valid as a letter. So $L_1 = 1111$ can be ruled out this way.

Now try the other letters yourself.

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