by Michael Shapiro and Tadeusz Wellenger

**The Problem.**
Alice has a plaintext **p**, a random bitstring **b**,
and a key **k**. She wishes to send the message **p** to Bob.
In order to do this, she uses the bitstring to encode the plaintext into
ciphertext **c**. She also wishes to send Bob the bitstring, but
wishes to encode it first. She uses the key to encode the bitstring
into a second bitstring **b'. **Alice sends Bob **c** and **b'**.
Trudy captures these as a passive wiretapper. What should Trudy do
to decode the message?

**The Solution.**
Here is a more complete description of the strings involved.
The message **p** and the and the bitstring **b** both have length
*N***, **which we assume is large. We can write these out
as bitstrings
** b =
**(

The key

where

The encoding is done by using exclusive or on each of the bits. We denote this by + so that

Here is the one minute answer to this: Both encryptions are using XOR. XORing with a given string is 1-1 and therefore invertible. The way of inverting this is to XOR with the same string again.

Here are the details. Exclusive or is the same thing
as addition mod 2. This is associative and commutative and has the property
that anything added to itself is 0. If Trudy adds **b'** and **c**
together, she gets

**b + c =**
( **b + k **) + ( **p + b **)

= **p + k + b + b**
**
= p + k**

But this is just the plaintext **p** encoded using
the key **k**. Since **k** is short, this is just a polyalphabetic
cipher and we can break this using techniques we've seen in class.

You cannot hope to use a statistical attack to decode
**b** from **b'**. The reason for this is that there **b** has
no statistical regularities, so you cannot use digrams and trigrams in
hopes of discovering the key length. If the key length is short, you might
try ennumerating all possible keys. If you do this, you will not know when
you have succeeded in finding **b** from **b'**. You will only know
this when your proposed key produces a proposed **b** which actually
succeeds in decoding **c**. However, since there are 2* ^{L}*
keys of length