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.

För att underlätta läsandet av Wikipedia-artikeln har jag använt samma exempel.
Vi har en klartext på engelska, skriven med enbart versaler eller gemena. Bokstaven Q avlägsnas, så att de 25 tillåtna bokstäverna är "ABCDEFGHIJKLMNOPRSTUVWXYZ". Alla skiljetecken avlägsnas. Så Wikipedias klartext "Hide the gold in the tree stump" skrivs först om till "HIDETHEGOLDINTHETREESTUMP". Vi har en nyckel, i exemplet "playfair example", egentligen "PLAYFAIREXAMPLE". Vi placerar nu in de 25 tillåtna bokstäverna radvis i en 5 x 5-matris, och börjar med nyckeln. Om en bokstav redan har blivit utplacerad struntar vi i eventuella upprepningar. Så nyckeln kommer att bli utplacerad som PLAYFaIREXaMple, där jag har skrivit dubbletter med gemena. Vi fyller därefter på med resten av bokstäverna och stryker dubbletter. 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

Vi delar upp klartexten 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. 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 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 kodnyckel och teckenvektor (klartext) producerar kryptotexten enligt metoden ovan. Programmet skall också klara att dekryptera en text (givet nyckeln).
Du kan utgå från att alla skiljetecken har avlägsnats från både kodnyckel och klartext. Om du vill skriva en mer generell rutin, där du tillåter skiljetecken och en blandning av versaler och gemena i klartexten, kan du enkelt (en rad) 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 program genom att använda en logisk variabel, crypt = true eller false. Somliga ignorerar symmetrin (tillåtet) och får en onödigt lång kod.