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?

Improve this question
$\endgroup$
6
  • $\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, 2015 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, 2015 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, 2015 at 13:42
  • $\begingroup$ I assumed XOR, as this is standard for a one-time pad. $\endgroup$
    – Henno Brandsma
    Oct 26, 2015 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, 2015 at 13:44

3 Answers 3

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ $C_1 \neq C_2$, or am I missing something? $\endgroup$
    – Henno Brandsma
    Oct 26, 2015 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, 2015 at 13:32
  • $\begingroup$ Yes, I get contradictions in all 3 cases. Something is amiss. $\endgroup$
    – Henno Brandsma
    Oct 26, 2015 at 13:38
  • $\begingroup$ @HennoBrandsma $c_i$ is supposed to denote $C_i$'s first bit. $\endgroup$
    – yyyyyyy
    Oct 26, 2015 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.