1
$\begingroup$

We have got a task with the following content:

Given is a language with 3 letters: A, B, C.

The binary expression is:

A = 000, B = 1111 and C = 0011 

Two words were encrypted in this language with the same key:

W1 = 0101001110111010101100100 
W2 = 1011001010000000000101011 

Determine the possible message pair.

How am I able to do this?

$\endgroup$
  • 3
    $\begingroup$ Hint: x-or W1 and W2 then start guessing the letters. and see this and this $\endgroup$ – kelalaka Nov 22 '18 at 22:37
  • $\begingroup$ @kelalaka Although this is a good general scheme, I don't really see how it would solve the problem. I have solved the problem on my computer (it can be done by hand as well) but having XOR'ed patterns will not directly help you here. $\endgroup$ – Maarten Bodewes Nov 23 '18 at 14:45
  • $\begingroup$ I've edited the answer so it becomes on topic. Asking us to decrypt ciphertext is explicitly off topic. Please look at the tutorial on which questions can be asked here. $\endgroup$ – Maarten Bodewes Nov 23 '18 at 15:11
1
$\begingroup$

I think guessing key bits and checking if the plaintext is valid in both words is the way to go (much like a binary puzzle).

For instance, it is clear that at least one of the words starts with an A because if you take the first 4 bits they are all different except for the last one. That rules out BB, BC, CB or CC as combinations of the first letter, because they don't differ by 3 bits where the final bit is 1. Similarly you should be able to rule out two other combinations, leaving only one combination - unfortunately you don't know yet if it is AX or XA. Similarly, you expect an AA and B combination at the final bits as the bits must be each other complements.

I would implement this using left to right guessing of key bits with backtracking in case the pattern becomes impossible for either W1 or W2. You may even start at each end, but I don't think that is needed. You should be able to do this by hand, but programming it may be fun as well.

In the end I see 13 bits set to 0 and 13 bits set to 1, and I had to backtrack 18 times to find a solution (assuming bits set to 0 before possibly back tracking, simply working from left to right), which is entirely doable for a mere human. Of course giving the key, the pattern of W1 or W2 gives away the entire result, so I won't do that.

The complement of the found key is also a solution in this particular case.


High level design:

  • create a tree for the key;
  • create code to perform a breath first search of the key bits;
  • create a method to check if a given (partial key) could be valid;
    • create a method that creates a tree of patterns;
    • check for W1 and W2 - up to the key size - if the key produces a tree up to a leaf node;
    • to do this you can search the tree using depth first search;
  • create checks to see:
    • if the key is complete;
    • if there can be a partial match at the end;

Beware to check the end conditions correctly, or you may have to do some manual restructuring at the end.

This is not an easy task to program. Basically you need to create a tree for both the key as well as the resulting plaintext to perform the pattern matching.

$\endgroup$
  • $\begingroup$ can you give me the final result? $\endgroup$ – Ahmet mohit Nov 23 '18 at 8:16
  • 1
    $\begingroup$ Nah, I went into programming it a bit, but this problem is definitely better solved by hand. We're not here to decrypt ciphertext and your question is bordering on being off topic. Generic solutions on how to solve problems are on topic, decrypting ciphertext isn't. $\endgroup$ – Maarten Bodewes Nov 23 '18 at 10:47
  • $\begingroup$ Happy to help you if you try to implement or solve. Just comment here. $\endgroup$ – Maarten Bodewes Nov 24 '18 at 1:52
1
$\begingroup$

After, Maarten comment, here an intro to solve by two-time pad;

we have;

A = 000
B = 1111
C = 0011

0101001110111010101100100 
1011001010000000000101011
-------------------------
1110000100111010101001111  x-ored ciphertext gives us x-ored plaintext
1111                       only this possible.
000
-------------------------
1110000100111010101001111  
1111                       
0001111                    only this possible.
-------------------------
1110000100111010101001111  
11111111                       
0001111                    only this possible.
-------------------------
1110000100111010101001111  
11111111                       
0001111                    Now here we have a branching 000 and 0011 
                           but one causes an immediate contradiction.

The rest is left to the OP.

$\endgroup$
  • 1
    $\begingroup$ Yeah, XOR'ing patterns works as well of course. It becomes a bit tricky with the 3 bit pattern in it, but for solving it by hand it is probably the best option. "Fortunately" the 3 bit pattern is all zeros :) $\endgroup$ – Maarten Bodewes Nov 24 '18 at 17:16
  • $\begingroup$ @MaartenBodewes It was clear that the questioner designed this question solvable by two-time pad, since only given 3 possible letters. Your solution contains how to solve it by programming. It is nice that we have it. $\endgroup$ – kelalaka Nov 24 '18 at 18:42

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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