Lab2b

Matriser

Denna laboration ger ännu mer träning på grundläggande programmering som repetitionssatser och alternativsatser, men även på matriser och texthantering.

Introduktion:
i denna laboration kommer du att använda Playfairchiffret, från 1854, för dölja innehållet i en text. Tekniken användes så sent som i andra världskriget, men inte för topphemliga meddelanden. För mer historia, läs Wikipedia-artikeln.

Hur metoden fungerar:
Först lite terminologi: klartext (eng. plaintext) är den text vars innehåll skall döljas. Detta åstadkommes med kryptering (eller chiffrering). Den resulterande texten kallas kryptotext eller chiffer (eng. ciphertext). Dekryptering är den inversa proceduren, att gå från kryptotext till klartext. Kryptering utförs med en krypteringsalgoritm (krypto), denna metod kan vara känd av alla. Dessutom krävs en nyckel som är känd endast av behöriga användare. En metod som använder (väsentligen) samma algoritm och nyckel för kryptering och dekryptering kallas symmetrisk.

I Playfairchiffret krypteras bara texter som består av de 25 bokstäverna "ABCDEFGHIJKLMNOPRSTUVWXYZ". Så alla eventuella Q i texten avlägsnas innan den krypteras.

Jag har använt samma exempel som i Wikipedia-artikeln ovan.

För att kryptera (och även dekryptera) används en nyckel. I exemplet har man använt nyckeln "PLAYFAIR EXAMPLE". Man gör iordning nyckeln genom att ta bort alla mellanslag och upprepningar av bokstäver. Den iordninggjorda nyckeln blir alltså

PLAYFIREXM

Man placerar sedan in de 25 tillåtna bokstäverna radvis i en 5 x 5-matris, och börjar med bokstäverna i nyckeln. Man fyller därefter på med resten av de tillåtna bokstäverna (i alfabetisk ordning). Matrisen blir alltså

P	L	A	Y	F
I	R	E	X	M
B	C	D	G	H
J	K	N	O	S
T	U	V	W	Z

Den skapade 5 x 5-matrisen används sedan för att kryptera en klartext skriven på engelska med enbart versaler (stora bokstäver) och med alla Q avlägsnade, så att bara de 25 tillåtna bokstäverna används.

I exemplet har man använt klartexten "HIDE THE GOLD IN THE TREE STUMP", som man avlägsnat alla skiljetecken från. Kvar blir texten

HIDETHEGOLDINTHETREESTUMP

När man krypterar klartexten börjar man med att dela upp den i bokstavspar; "HIDETHEGOLDINTHETREESTUMP" blir "HI DE TH EG OL DI NT HE TR EE ST UM P". Par med två likadana bokstäver, EE i exemplet, slås isär genom att ett X adderas. EE blir EXE. Observera att detta påverkar uppdelningen av efterföljande par. Är det samma bokstav i rad, t.ex."RE ES", men i olika par så sätter man inte in något X. Så att texten lyder:

HI DE TH EG OL DI NT HE TR EX ES TU MP

Består texten (efter adderande av eventuella X) av ett udda antal bokstäver adderas ett X på slutet. Metoden klarar inte av fallet när man får ett XX-par (men risken är ju inte så stor att det kommer att inträffa). Så, meningen "Felix Xavier is the spy" går inte bra.
Bokstavsparen i klartexten krypteras nu med hjälp av följande tre regler:

Om båda bokstäverna i ett par återfinns i samma matris-rad ersätts de med de grannarna till höger (om en bokstav är i femte kolonnen tas ersättaren från den första kolonnen).
Om båda bokstäverna i ett par återfinns i samma kolonn ersätts de med de grannarna nedanför (om en bokstav är i femte raden tas ersättaren från den första raden).
I övriga fall bildar bokstäverna hörnen i en "rektangel" i matrisen. Bokstäverna ersätts med de bokstäver som ligger i de andra hörnen av rektangeln. Ersättningsbokstäverna skall ligga i samma rad som ursprungsbokstäverna.

Nu till exemplet. Talet inom parentes anger vilken regel som använts.

HI -> BM (3)
DE -> ND (2)
TH -> ZB (3)
EG -> XD (3)
OL -> KY (3)
DI -> BE (3)
NT -> JV (3)
HE -> DM (3)
TR -> UI (3)
EX -> XM (1)
ES -> MN (3)
TU -> UV (1)
MP -> IF (3)

Så kryptotexten lyder slutligen: "BM ND ZB XD KY BE JV DM UI XM MN UV IF".

Dekrypteringen sker väsentligen på samma sätt (du får tänka efter lite själv). Samma matris används men i regel 1. så tar vi grannarna till vänster etc. Stryk slutligen onödiga X i den dekrypterade texten (vilket man får göra för hand när man läser texten, så det behöver inte ditt program klara av).

Nu till uppgifterna:

Skriv ett Matlabfunktion, playfair(text, key, crypt), som givet en nyckel (key) och klartext (text) krypterar eller dekrypterar texten i text enligt metoden ovan. Om den tredje parametern (crypt) har värdet true ska funktionen kryptera texten, om den har värdet false ska texten dekrypteras. Du kan utgå från att alla skiljetecken har avlägsnats från både nyckel och klartext.

(Om du vill skriva en mer generell funktion, där du tillåter skiljetecken och en blandning av versaler och gemena i klartexten, kan du enkelt avlägsna allt som inte är en bokstav (använd isletter) och konvertera till versaler (upper) eller gemena (lower) ).

Så här skall funktionen kunna användas:

ciphertext = playfair(plaintext, key, true)
plaintext = playfair(ciphertext, key, false)

Testa din kod (kryptering och dekryptering) på exemplet ovan. Testa även på följande två exempel som kontrollerar om det är något problem med strängar av udda eller jämn längd.

str = playfair('PROGRAM', 'HEMLIGT', true)
playfair(str, 'HEMLIGT', false)

str = playfair('PROGRAMPROGRAM', 'HEMLIGT', true)
playfair(str, 'HEMLIGT', false)

Dekryptera slutligen följande krypotext (klipp och klistra):

chiffer = 'FLAPJBCZFAEMAUHJNREPGPDVUNLINGNWSRMCABAHTNOREPFESGFSEMBSAHGOHJNREPGPDVUNCRAJLAEMHJNGSRPAAMNEXUULHDLEDZ';

Nyckeln är: NOPRESSURENODIAMONDS

Observera: när jag skriver playfair(text, key, crypt), så är det en del av en specifikation. Det innebär att rutinen måste heta playfair och parametrarna måste fungera som föreskrivet. Varför? Jo, det är besvärligt för mig om alla grupper har olika namn på funktionen och olika ordning eller betydelse av parametrarna. Dessutom är detta en träning i verklig programmering. Om/när du kommer att programmera ute på ett företag, skall normalt din funktion användas i ett större sammanhang. Då är det viktigt att funktion följer specifikationen annars kommer inte andra att kunna använda den.

Ledning: denna uppgift är rätt knepig så det är extra viktigt att planera inför kodningen i Matlab. Om du inte har tänkt igenom hur du skall lösa de olika deluppgifterna kommer koden att ta extra mycket tid att skriva och bli lång och komplicerad.

Man kan med fördel vektorisera vissa delar av koden. När man t.ex. skall bygga upp teckenmatrisen kan man arbeta med en vektor som innehåller originaltexten till vilken man lagt till bokstäverna A till Z (utom Q). Det är enkelt att kontrollera om man har kopior ev en bokstav, här ett inspirationsexempel:

>> text = 'ABRAKADABRA';
>> find(text == text(1))
ans = 1 4 6 8 11

När man har sorterat bort kopiorna gör man enkelt om vektorn till en matris med funktionen reshape.

Man använder också find (fast med två utparametrar) för att hit rad- och kolonnindex för en bokstav i matrisen.

Eftersom metoden är symmetrisk så kan du kombinera kryptering och dekryptering i samma kod genom att använda en logisk variabel, crypt = true eller false - men det är tillåtet att ignorera symmetrin.