In 2014 — after receiving dozens of unsolicited emails from the International Journal of Advanced Computer Technology¹ (IJACT) — scientists David Mazières and Eddie Kohler submitted a paper titled "Get me off Your Fucking Mailing List²".

They pretty much fell off their chair³ when the news came in the manuscript had been accepted for publication. However, that acceptance bolstered the authors' contention that IJACT is a predatory journal, an indiscriminate but superficially scholarly publication that subsists on editorial fees. Mazières said:

They told us to add some more recent references and do a bit of reformatting. But otherwise they said its suitability for the journal was excellent.

The authors didn't pursue it and so far also haven't received any confirmation yet that the journal took them off their mailing list.

Assignment

An essential step in the bitflip cipher involves converting messages consisting of a sequence of symbols (letters, numbers, punctuation marks and spaces) into bitstrings consisting only of a sequence of bits: zero (0) or one (1). To do so, the cipher uses a key that indicates what bitstring corresponds to each symbol. The key is given as a text file whose lines consists of a symbol followed by a tab and the corresponding bitstring. For example, with this key (key.01.txt⁴)

R	010
C	1100
A	10
B	00
D	1101

the message ABRACADABRA can be converted into the bitstring

A B R  A C   A D   A B R  A
1000010101100101101100001010

To convert this long bitstring back into the original message, we seem to run into the problem that the bitstrings for the symbols have different lengths. As a result, it is unclear how to divide the longer bitstring into shorter bitstrings that correspond to symbols. However, the key is composed in such a way that no bitstring for a symbol is a prefix of a bitstring for any of the other symbols.

As a consequence, the long bitstring has exactly one prefix that is a bitstring for a symbol. In the example, it is the prefix 10 that corresponds to symbol A. If the prefix is then removed from the long string, the process can be repeated with the remaining bitstring until it has been fully processed. This is how we can convert the long bitstring step by step to the symbols of the message ABRACADABRA:

The bitflip cipher itself was named after an operation on bitstrings: a bitflip converts a bitstring into a new bitstring by replacing all zeros (0) with ones (1), and all ones (1) with zeros (0). For example, a bitflip converts the bitstring 010110 into the bitstring 101001.

The bitflip cipher only works with symmetric keys: keys where for each bitstring corresponding to a symbol, its bitflip also corresponds to a symbol. However, the key we used as an example above is asymmetric: bitstring 10 corresponds to symbol A, but the bitflip of that bitstring 01 does not correspond to any symbol. We will therefore use this symmetric key (key.02.txt⁵)

a	011011111
T	0110111101
s	100100000
g	10011
n	01100
e	110
 	010
f	001
o	1000
m	111
y	0110110
k	10010001
c	01101110
r	1001001
l	011010
.	1001000010
G	100101
t	000
i	101
u	0111

to explain how the message

Get me off your fucking mailing list.

is encoded with the bitflip cipher. First, we use the key to convert the message into its corresponding bitstring:

1001011100000101111100101000001001010011011010000111100100101000101110110111010010001101011001001101011101101111110101101010101100100110100110101011001000000001001000010

We then perform a bitflip on the obtained bitstring:

0110100011111010000011010111110110101100100101111000011011010111010001001000101101110010100110110010100010010000001010010101010011011001011001010100110111111110110111101

Finally, we use the key to convert the bitstring back into a message of symbols:

lfmitfiueeiruoyieokc gnits G gniG amT

This is the step that will not necessarily succeed with asymmetric keys, but will always succeed with symmetric keys. The message obtained in this way is the ciphertext for the original message. Decoding a ciphertext back into the original message is very simple: decoding works exactly the same as encoding.

Your task:

• Write a function read_key that takes the location (str) of a text file describing a key $$\mathcal{S}$$. The function must return the dictionary representation of key $$\mathcal{S}$$: a dictionary (dict) that maps each symbol (str) of the key onto its corresponding bitstring (str).

• Write a function symbols2bits that takes two arguments: i) a message $$s$$ (str) that consist of a sequence of symbols and ii) the dictionary representation (dict) of a key $$\mathcal{S}$$. The function may assume that all symbols of message $$s$$ occur in key $$\mathcal{S}$$, without having to check this explicitly. The function must return the bitstring $$b$$ (str) that corresponds to message $$s$$ according to key $$\mathcal{S}$$.

• Write a function bits2symbols that takes two arguments: i) a bitstring $$b$$ (str) and ii) the dictionary representation (dict) of a key $$\mathcal{S}$$. The function may assume that bitstring $$b$$ corresponds to a message $$s$$ according to key $$\mathcal{S}$$, without having to check this explicitly. The function must return message $$s$$ (str).

• Write a function flip that takes a bitstring $$b$$ (str). The function must return the bitstring (str) obtained by performing a bitflip on bitstring $$b$$.

• Write a function issymmetric that takes the dictionary representation (dict) of a key $$\mathcal{S}$$. The function must return a Boolean value (bool) that indicates whether $$\mathcal{S}$$ is a symmetric key.

• Write a function encode that takes two arguments: i) a message $$s$$ (str) that consists of a sequence of symbols and ii) the dictionary representation (dict) of a key $$\mathcal{S}$$. The function may assume that all symbols of message $$s$$ occur in key $$\mathcal{S}$$, without having to check this explicitly. If $$\mathcal{S}$$ is not a symmetric key, an AssertionError must be raised with the message asymmetric key. Otherwise, the function must return the message (str) obtained by encoding message $$s$$ according to the bitflip cipher with key $$\mathcal{S}$$.

• Write a function decode that takes two arguments: i) a message $$s$$ (str) that consists of a sequence of symbols and ii) the dictionary representation (dict) of a key $$\mathcal{S}$$. The function may assume that all symbols of message $$s$$ occur in key $$\mathcal{S}$$, without having to check this explicitly. If $$\mathcal{S}$$ is not a symmetric key, an AssertionError must be raised with the message asymmetric key. Otherwise, the function must return the message (str) obtained by decoding message $$s$$ according to the bitflip cipher with key $$\mathcal{S}$$.

Example

In this interactive session we assume the text files key.01.txt⁶ and key.02.txt⁷ are located in the current directory. These are the two keys we also used as examples in the description of this assignment.

>>> key = read_key('key.01.txt8')
>>> key['A']
'10'
>>> key['R']
'010'
>>> key['C']
'1100'
>>> symbols2bits('ABRACADABRA', key)
'1000010101100101101100001010'
>>> bits2symbols('1000010101100101101100001010', key)
'ABRACADABRA'
>>> flip('1000010101100101101100001010')
'0111101010011010010011110101'
>>> issymmetric(key)
False
>>> encode('ABRACADABRA', key)
Traceback (most recent call last):
AssertionError: asymmetric key

>>> key = read_key('key.02.txt9')
>>> key['G']
'100101'
>>> key['e']
'110'
>>> key[' ']
'010'
>>> key['.']
'1001000010'
>>> symbols2bits('Get me off your fucking mailing list.', key)
'1001011100000101111100101000001001010011011010000111100100101000101110110111010010001101011001001101011101101111110101101010101100100110100110101011001000000001001000010'
>>> bits2symbols('1001011100000101111100101000001001010011011010000111100100101000101110110111010010001101011001001101011101101111110101101010101100100110100110101011001000000001001000010', key)
'Get me off your fucking mailing list.'
>>> flip('1001011100000101111100101000001001010011011010000111100100101000101110110111010010001101011001001101011101101111110101101010101100100110100110101011001000000001001000010')
'0110100011111010000011010111110110101100100101111000011011010111010001001000101101110010100110110010100010010000001010010101010011011001011001010100110111111110110111101'
>>> issymmetric(key)
True
>>> encode('Get me off your fucking mailing list.', key)
'lfmitfiueeiruoyieokc gnits G gniG amT'
>>> decode('lfmitfiueeiruoyieokc gnits G gniG amT', key)
'Get me off your fucking mailing list.'