Nadat ze tientallen ongevraagde emails hadden ontvangen om hun onderzoeksresultaten te publiceren in het tijdschrift International Journal of Advanced Computer Technology¹ (IJACT), dienden wetenschappers David Mazières en Eddie Kohler in 2014 uiteindelijk een manuscript in met de titel "Get me off Your Fucking Mailing List²".

Ze vielen letterlijk van hun stoel³ toen ze het bericht ontvingen dat het manuscript aanvaard was voor publicatie. Dit bevestigde immers hun stelling dat IJACT een roofzuchtig tijdschrift is, dat enkel uit is op het aanrekenen van publicatiekosten ten koste van strenge kwaliteitscontrole op hun wetenschappelijke publicaties. Mazières zei hierover:

Ze vroegen ons enkel om nog wat recentere referenties toe te voegen en de opmaak van de tekst hier en daar een beetje te herschikken. Maar verder zeiden ze dat het manuscript uitstekend geschikt was voor publicatie in het tijdschrift.

De auteurs weigerden om verder te gaan met het publicatieproces. Tot op heden kregen ze ook nog altijd geen bevestiging dat ze van de mailinglijst van het tijdschrift gehaald zijn.

Opgave

Een essentiële stap in het bitflip-geheimschrift bestaat uit het omzetten van berichten die bestaan uit een reeks symbolen (letters, cijfers, leestekens en spaties) naar bitstrings die enkel bestaan uit een reeks bits: nul (0) of één (1). Hiervoor wordt gebruikgemaakt van een sleutel die aangeeft welke bitstring correspondeert met elk symbool. De sleutel wordt gegeven als een tekstbestand waarvan elke regel bestaat uit een symbool, gevolgd door een tab en de corresponderende bitstring. Met deze sleutel (sleutel.01.txt⁴)

R	010
C	1100
A	10
B	00
D	1101

kan bijvoorbeeld het bericht ABRACADABRA omgezet worden naar de bitstring

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

Om deze lange bitstring terug om te zetten naar het corresponderende bericht, lijken we aan te lopen tegen het probleem dat de bitstrings voor de symbolen niet allemaal even lang zijn. Daardoor weten we niet hoe de langere bitstring moet opgedeeld worden in kortere bitstrings die met symbolen corresponderen. De sleutel is echter zo samengesteld dat geen enkele bitstring voor een symbool een prefix is van een bitstring voor één van de andere symbolen.

Een gevolg daarvan is dat de lange bitstring juist één prefix heeft die een bitstring is voor een symbool. In het voorbeeld is dat de prefix 10 die correspondeert met symbool A. Als we nu die prefix van de lange string weghalen, dan kunnen we het proces herhalen met de overblijvende bitstring, totdat die bitstring volledig verwerkt is. Dit is hoe we de lange bitstring stap voor stap kunnen omzetten naar de symbolen van het bericht ABRACADABRA:

Het bitflip-geheimschrift zelf werd vernoemd naar een bewerking op bitstrings: een bitflip zet een bitstring om naar een nieuwe bitstring door alle nullen (0) te vervangen door enen (1), en alle enen (1) door nullen (0). Zo wordt de bitstring 010110 door een bitflip omgezet in de bitstring 101001.

Het bitflip-geheimschrift werkt enkel met symmetrische sleutels: sleutels waarbij voor elke bitstring die correspondeert met een symbool ook de bitflip van die bitstring correspondeert met een symbool. De sleutel die we hierboven als voorbeeld gebruikt hebben, is echter asymmetrisch: bitstring 10 correspondeert met symbool A, maar de bitflip-bitstring 01 correspondeert niet met een symbool. We gebruiken daarom deze symmetrische sleutel (sleutel.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

om uit te leggen hoe het bericht

Get me off your fucking mailing list.

gecodeerd wordt met het bitflip-geheimschrift. Eerst gebruiken we de sleutel om dit bericht om te zetten naar de corresponderende bitstring:

1001011100000101111100101000001001010011011010000111100100101000101110110111010010001101011001001101011101101111110101101010101100100110100110101011001000000001001000010

Daarna voeren we een bitflip uit op deze bitstring:

0110100011111010000011010111110110101100100101111000011011010111010001001000101101110010100110110010100010010000001010010101010011011001011001010100110111111110110111101

Ten slotte gebruiken we de sleutel om de bitstring terug om te zetten naar een bericht van symbolen:

lfmitfiueeiruoyieokc gnits G gniG amT

Dit is een stap die niet noodzakelijk zal lukken met een asymmetrische sleutel, maar wel met een symmetrische sleutel. Het bericht dat we op die manier bekomen is de gecodeerde versie van het originele bericht. Het gecodeerde bericht terug decoderen tot het originele bericht is heel eenvoudig: decoderen werkt op exact dezelfde manier als coderen.

Gevraagd wordt:

• Schrijf een functie lees_sleutel waaraan de locatie (str) moet doorgegeven worden van een tekstbestand met de beschrijving van een sleutel $$\mathcal{S}$$. De functie moet de dictionaryvoorstelling van sleutel $$\mathcal{S}$$ teruggeven: een dictionary (dict) die elk symbool (str) van de sleutel afbeeldt op de correspondende bitstring (str).

• Schrijf een functie symbolen2bits waaraan twee argumenten moeten doorgegeven worden: i) een bericht $$s$$ (str) dat bestaat uit een reeks symbolen en ii) de dictionaryvoorstelling (dict) van een sleutel $$\mathcal{S}$$. De functie mag ervan uitgaan dat alle symbolen van bericht $$s$$ voorkomen in sleutel $$\mathcal{S}$$, zonder dat dit expliciet moet gecontroleerd worden. De functie moet de bitstring $$b$$ (str) teruggeven die volgens sleutel $$\mathcal{S}$$ correspondeert met bericht $$s$$.

• Schrijf een functie bits2symbolen waaraan twee argumenten moeten doorgegeven worden: i) een bitstring $$b$$ (str) en ii) de dictionaryvoorstelling (dict) van een sleutel $$\mathcal{S}$$. De functie mag ervan uitgaan dat bitstring $$b$$ volgens sleutel $$\mathcal{S}$$ correspondeert met een bericht $$s$$, zonder dat dit expliciet moet gecontroleerd worden. De functie moet bericht $$s$$ (str) teruggeven.

• Schrijf een functie flip waaraan een bitstring $$b$$ (str) moet doorgegeven worden. De functie moet de bitstring (str) teruggeven die verkregen wordt door een bitflip uit te voeren op bitstring $$b$$.

• Schrijf een functie issymmetrisch waaraan de dictionaryvoorstelling (dict) van een sleutel $$\mathcal{S}$$ moet doorgegeven worden. De functie moet een Booleaanse waarde (bool) teruggeven die aangeeft of $$\mathcal{S}$$ een symmetrische sleutel is.

• Schrijf een functie codeer waaraan twee argumenten moeten doorgegeven worden: i) een bericht $$s$$ (str) dat bestaat uit een reeks symbolen en ii) de dictionaryvoorstelling (dict) van een sleutel $$\mathcal{S}$$. De functie mag ervan uitgaan dat alle symbolen van bericht $$s$$ voorkomen in sleutel $$\mathcal{S}$$, zonder dat dit expliciet moet gecontroleerd worden. Als $$\mathcal{S}$$ geen symmetrische sleutel is, dan moet een AssertionError opgeworpen worden met de boodschap asymmetrische sleutel. Anders moet de functie het bericht (str) teruggeven dat men bekomt door bericht $$s$$ te coderen volgens het bitflip-geheimschrift met sleutel $$\mathcal{S}$$.

• Schrijf een functie decodeer waaraan twee argumenten moeten doorgegeven worden: i) een bericht $$s$$ (str) dat bestaat uit een reeks symbolen en ii) de dictionaryvoorstelling (dict) van een sleutel $$\mathcal{S}$$. De functie mag ervan uitgaan dat alle symbolen van bericht $$s$$ voorkomen in sleutel $$\mathcal{S}$$, zonder dat dit expliciet moet gecontroleerd worden. Als $$\mathcal{S}$$ geen symmetrische sleutel is, dan moet een AssertionError opgeworpen worden met de boodschap asymmetrische sleutel. Anders moet de functie het bericht (str) teruggeven dat men bekomt door bericht $$s$$ te decoderen volgens het bitflip-geheimschrift met sleutel $$\mathcal{S}$$.

Voorbeeld

In deze interactieve sessie gaan we ervan uit dat de tekstbestanden sleutel.01.txt⁶ en sleutel.02.txt⁷ zich in de huidige directory bevinden. Het zijn de twee sleutels die we ook in de beschrijving van deze opgave gebruikt hebben.

>>> sleutel = lees_sleutel('sleutel.01.txt8')
>>> sleutel['A']
'10'
>>> sleutel['R']
'010'
>>> sleutel['C']
'1100'
>>> symbolen2bits('ABRACADABRA', sleutel)
'1000010101100101101100001010'
>>> bits2symbolen('1000010101100101101100001010', sleutel)
'ABRACADABRA'
>>> flip('1000010101100101101100001010')
'0111101010011010010011110101'
>>> issymmetrisch(sleutel)
False
>>> codeer('ABRACADABRA', sleutel)
Traceback (most recent call last):
AssertionError: asymmetrische sleutel

>>> sleutel = lees_sleutel('sleutel.02.txt9')
>>> sleutel['G']
'100101'
>>> sleutel['e']
'110'
>>> sleutel[' ']
'010'
>>> sleutel['.']
'1001000010'
>>> symbolen2bits('Get me off your fucking mailing list.', sleutel)
'1001011100000101111100101000001001010011011010000111100100101000101110110111010010001101011001001101011101101111110101101010101100100110100110101011001000000001001000010'
>>> bits2symbolen('1001011100000101111100101000001001010011011010000111100100101000101110110111010010001101011001001101011101101111110101101010101100100110100110101011001000000001001000010', sleutel)
'Get me off your fucking mailing list.'
>>> flip('1001011100000101111100101000001001010011011010000111100100101000101110110111010010001101011001001101011101101111110101101010101100100110100110101011001000000001001000010')
'0110100011111010000011010111110110101100100101111000011011010111010001001000101101110010100110110010100010010000001010010101010011011001011001010100110111111110110111101'
>>> issymmetrisch(sleutel)
True
>>> codeer('Get me off your fucking mailing list.', sleutel)
'lfmitfiueeiruoyieokc gnits G gniG amT'
>>> decodeer('lfmitfiueeiruoyieokc gnits G gniG amT', sleutel)
'Get me off your fucking mailing list.'