\font\largerbold = cmbx10 scaled \magstep1
\font\largerslant = cmsl10 scaled \magstep1
\font\largerrm = cmr10 scaled \magstep1
\font\largestbold = cmbx10 scaled \magstep2
\font\largerrm =cmr10 scaled \magstep1
\def\mycirc{\raise .2em\hbox{$\scriptstyle\bigcirc$}}
\font\seventt = cmtt10.tfm scaled 800
\nopagenumbers
\magnification=\magstep1
\parindent=0pt
\rightline{\sevenrm March 26, 2000}

\centerline{\largerbold More binary homework: \largerslant ALIENS! } 
\smallskip
\centerline{\bf Due Monday, April 3}

\smallskip
%\centerline{\sevenrm{\sevenbf Aliens invade earth!} Details at 11, after the football game. {\sevenbf Aliens invade earth!} Details at 11, after the football game. {\sevenbf Aliens invade earth!} Details at 11, after the football game. {\sevenbf Aliens invade earth!} Details at 11, after the football game. {\sevenbf Aliens invade earth!} Details at 11, after the football game. {\sevenbf Aliens invade earth!} Details at 11, after the football game. {\sevenbf Aliens invade earth!} Details at 11, after the football game. {\sevenbf Aliens invade earth!} Details at 11, after the football game. }

\smallskip

{\bf Background assumptions} We imagine an alien language which has only three
words:

\smallskip 

\quad $\bullet$ 40\% of the words are 1111111. Abbreviate this word
with {\bf A}. It is seven bits long.

%\smallskip

\quad $\bullet$ 30\% of the words are 00000. Abbreviate this word with
{\bf B}. It is five bits long.

%\smallskip

\quad $\bullet$ 30\% of the words are 10101010. Abbreviate this word
with {\bf C}. It is eight bits long.

\smallskip

%The aliens fit their words together to make binary strings whose
%length is about 100 bits. These messages are disguised by xoring them
%with pseudorandom bit strings.

\smallskip


1.~Decipher the following messages. That is, describe the sequence
of alien words which produced them. For example, if you believe the
message is
{$\overbrace{00000}\overbrace{1111111}\overbrace{10101010}\overbrace{10101010}$}
you would report that the aliens were signalling
{\bf BACC}.

\smallskip
\overfullrule=0pt

a) The aliens have xored a message with a pseudorandom bit string with
about 5\% 1's. 

\smallskip

{\tt
10111 11111 11111 01010 10111 11110 01001 01010 10000 00101 01010 11111 11101 \
01110 00000 10111 11101 01010 11101 11000 00 
}
\smallskip


%plain1 := 111111111111111010101011111110000010101010000001010101011111111010101000000111111110101010111111100000

%pr1 := 010000000000000000000000000000010000000000000000000000000000000000010000000

b) The aliens have xored a message with a pseudorandom bit string with
about 10\% 1's.
 
\smallskip

{\tt
10101 00001 10011 01111 00000 11111 11000 10110 10111 01010 10111 11111 11011 \
10000 11000 11010 10100 00001 11111 11111 010 
}


%plain2 := 1010101000000111111100000111111100000111111110101010111111111111110000000000101010100000011111111111111

%pr2 := 00000010011000010000000000000000000100010100000000000000000000100000001100010000000000000000000000001010000000


\medskip

2.~The aliens now xor two messages and send the resulting bitstream.

\smallskip

{\tt 
11111 11111 00000 10111 11101 01011 01001 01000 00101 00101 00000 01010 00010 \
10101 11100 11111 11110 10101 00000 00111 11 

}

\smallskip

Reconstruct \underbar{both} messages as well as you can from this
information.

\medskip 

3.~The aliens created a pseudorandom bitstream with 50\% 1's and
50\% 0's, {\bf but} they made a major error. They used
the \underbar{same} stream to conceal three different
messages. The concealed messages are displayed
below. Decipher as much as you can of all three messages.
 
\smallskip
{\bf First message} 

\smallskip
{\tt
00100 11011 10110 10110 10101 11110 11101 11111 11110 00000 10010 01110 10110 \
00011 01111 01011 00000 10110 11000 10010 00101 1 

}



\smallskip
{\bf Second message}

\smallskip
{\tt
00100 11001 00011 01001 11010 01110 11100 10101 01110 00011 01111 01110 11100 \
10110 00000 10100 11111 00110 11011 01111 01111 0 
}


\smallskip
{\bf Third message}

\smallskip
{\tt
01110 01110 11100 00110 11010 01110 00011 11111 11011 01010 00111 01110 00011 \
00110 00101 11110 01010 01100 01110 00101 110 
}


\smallskip
{\bf Hint}\smallskip
{
{\baselineskip=.7\baselineskip
{\sevenbf Xor of first and second messages}

\seventt
00000 00010 10101 11111 01111 10000 00001 01010 10000 00011 11101 00000 01010 \
10101 01111 11111 11111 10000 00011 11101 01010 1 
\smallskip
{\sevenbf Xor of first and third messages}

01010 10101 01010 10000 01111 10000 11110 00000 00101 01010 10101 00000 10101 \
00101 01010 10101 01010 11010 10110 10111 111 

\smallskip

{\sevenbf Xor of second and third messages}


01010 10111 11111 01111 00000 00000 11111 01010 10101 01001 01000 00000 11111 \
10000 00101 01010 10101 01010 10101 01010 101 
\vfil
%\centerline{\sevenrm{\sevenbf Aliens invade earth!} Details at 11, after the football game. {\sevenbf Aliens invade earth!} Details at 11, after the football game. {\sevenbf Aliens invade earth!} Details at 11, after the football game. {\sevenbf Aliens invade earth!} Details at 11, after the football game. {\sevenbf Aliens invade earth!} Details at 11, after the football game. {\sevenbf Aliens invade earth!} Details at 11, after the football game. {\sevenbf Aliens invade earth!} Details at 11, after the football game. {\sevenbf Aliens invade earth!} Details at 11, after the football game. }
}
%\vfil\eject

\vfil\eject\end

{\sevenrm Of course, this illustrates what might happen if one used a book to
create pseudorandom strings. All known languages have many statistical
irregularities. These irregularities usually seem to diminish the
security of encryption schemes which rely on the possible ``random''
nature of text in that language.

\end

vocab:=[`1111111`,4,`00000`,3,`10101010`,3];
v50:=[`0`,1,`1`,1];
v5:=[`0`,19,`1`,1];
v10:=[`0`, 9, `1`, 1];
v20:=[0, 4, 1, 1];
v40:=[0, 6, 1, 4];
v30:=[0,7, 1,3]


pr3 := 11011001000100101001001011000100011010101000111111011011101111100101100\
111101011000001100100100100001000011010

plain3 := 11111111111111111111100000111111110101010111111111111111010101010101\
01000000000000000011111110000010101010

plain4 := 11111111010101000000111111111111111111111111111100000101010100000000\
00011111111111111111111111111111111111

plain5 := 10101010101010101111111111111100000101010101010101010101010111111100\
00010101010101010101010101010101010

vocab:=[`1010101010`,2,`1111111`,1,`000000`,1]


