Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I'm trying to solve a problem:

I have 11 ciphers encoded with the same key. My aim is to decode target cipher.

If I do xor C1, C2 (ciphers encoded with the same key) I do get M1 xor M2 (where M1, M2 are plain text messages).

Please say what to do next. I don't understand how to get plain texts from M1 xor M2

UPD: it's a two time pad (i.e. the same key has been use more than one time)

share|improve this question
2  
What cipher? I'm guessing a one-time-pad that's been reused for several messages, is that right? See Taking advantage of one-time pad key reuse? –  Gilles Nov 18 '12 at 13:21
    
Is it correct: here are two methods, named statistical analysis or Frequency analysis and pattern matching. So I have to implement one of them and apply to xor results. –  Sergey Nov 18 '12 at 14:02
2  
You have more information since you have a depth of 11 rather than 2. So your task is much easier, though you probably still have to apply the same kind of analysis. –  Yuval Filmus Nov 18 '12 at 19:00

1 Answer 1

So I've passed coursera Scala course and deciced to apply my fresh knowledge. Here is my algo:

  1. Xor ciphers with each other and collect xor result for each position. As a result I got a Map[Int, List[String]] where Int is a position of char in chiper and List[String] are all xor results for current position.

  2. I have an assumption that if xor in List[String] equals to UPPER ASCII alpha, it means that source of this computation was: *space xor lower_alpha = UPPER_alpha*.

  3. I can try to guess key value: c1 (char from 1st cipher), c2(char from 2nd cipher), xorRes (c1 xor c2 = xorRes) => c2 xor(c1 xor xorRes) or c1 xor(c2 xor xorRes) = *lower_alpha*.

Here is a part of code:

  /**
   * hex1 is a hex from 1st cipher
   * hex2 is a hex from second cipher
   * xor is ahex1 xor hex2
   * @return List with pos of possible key and possible key value else return empty list
   * */
  def getPossibleKey(hex1: String, hex2: String, xor: String, pos: Int): List[(Int, String)] = {
      if(isUpperAphpa(xor)){
          if( isLowerAphpa(xorHexStrings(xorWithSpace(hex1), hex2)) ){
            List( (pos, xorWithSpace(hex1)) )
          }else if( isLowerAphpa(xorHexStrings(xorWithSpace(hex2), hex1)) ){
            List( (pos, xorWithSpace(hex2)) )
      }else{
        List.empty
      }
  }else{
    List.empty
  }

}

As a result i got: List[Int, String] where String is the most popular lower_alpha got from getPossibleKey function.

Then i just applied collected key to each cipher and started to fix the key. I know that c1 xor m1 = k1 where c1 is a cipher fragment, k1 is a key fragment and m1 is a plain text.

share|improve this answer
    
This is not going to work. If $X$ is an XOR of two uppercase letters, then there are lots of ways to represent it as an XOR of two letters, for example by flipping the LSB of both, or by switching the letters (unless they're equal). As an extreme example, if $X = 0$ then there are $26$ different ways. When considering $11$ different messages together you get more information, but I'm not sure whether that's enough. In general, you need to look at more than one letter at the same time, say using dynamic programming to make it computationally feasible. –  Yuval Filmus Dec 23 '12 at 21:02
    
Sorry, I did solve the problem and got 100% score on this task. As I mentioned before, I did have to spend some time picking right values for the key. I can agree that for just two encrupted messages I would have to apply much more coplicated algorithm. –  Sergey Dec 23 '12 at 21:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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