IDA - Institutionen för datavetenskap

Laboration 4 - Algoritmer och kryptering

I denna laboration ska ni arbeta med de egna abstrakta datatyperna card och deck (som beskrivs i föregående del ) och kontrollstrukturer på ett sådant sätt att ni kan skriva program som löser riktiga problem. Laborationen är tänkt att öka er förståelse för problemlösning med hjälp av programmering. Även om inte alla algoritmer har ett officiellt namn kan de flesta lösningar på ett problem beskrivas enligt en algoritm.

Wikipedia beskriver en algoritm på följande sätt:

En algoritm är inom matematiken och datavetenskapen en begränsad uppsättning (mängd) väldefinierade instruktioner för att lösa en uppgift, som från givna utgångstillstånd (starttillstånd) med säkerhet leder till något givet sluttillstånd. Den kan också beskrivas som en systematisk procedur för hur man genom ett begränsat antal steg utför en beräkning eller löser ett problem.

Algoritm för solitaire_keystream

Nedan följer algoritmen för solitaire keystream. Det är viktigt att ni följer denna algoritm noga om er lösning på laborationen skall fungera korrekt. Algoritmen utgår ifrån ett verkligt sett kryptering utförts med hjälp av kortlekar.

1. Blanda kortleken inklusive jokrarna. Det är denna blandning som gör din krypteringsnyckel unik, det gäller att både sändaren och mottagaren av meddelandet är överens om den slutliga ordningen för att metoden ska fungera.
2. Om joker A inte är längst ned i kortleken, flytta joker A ner ett steg i kortleken. Ifall jokern redan är längst ner i kortleken flyttas den under det översta kortet.
3. Om joker B inte är längst ned eller näst längst ned i kortleken, flytta joker B ner två steg i kortleken. Ifall jokern redan är längst ner i kortleken flyttas den under det näst översta kortet. Ifall jokern är precis ovanför det nedersta kortet i kortleken flyttas den under det översta kortet
4. Dela kortleken i tre delar; del A är alla kort från toppen av leken till den första jokern, del B är alla kort mellan de båda jokrarna (inklusive jokrarna) och del C är korten under den andra jokern. Flytta om delarna så att de kommer i ordningen C, B, A.
5. Flytta lika många kort från övre delen av kortleken som värdet på det understa kortet och sätt in dessa precis ovanför det understa kortet.
6. Det översta kortets värde bestämmer vilket kort i kortleken som ska användas som del i nyckelfrasen. Räkna lika många kort uppifrån som värdet på det översta kortet, titta på kortet direkt efter dessa kort, det är värdet för nästa bokstav i nyckelfrasen, där 1 = A, 2 = B ... 26 = Z. Ifall kortet är en joker blir det ingen nyckel i denna iteration. Notera att detta steg inte förändrar kortleken.
7. Återupprepa från steg 2 tills ni har en nyckelfras med rätt längd.

Ett tips är att titta på seed i random för att se till att leken blandas på samma sätt. Ett annat sätt är att blanda kortleken först och sedan kopiera den för att få två identiskt blandade kortlekar.

Körexempel:

>>> python3 -i lab3.py
>>> solitaire_deck = create_deck()
>>> solitaire_keystream(length = 30, deck = solitaire_deck)
MUFKDPSIQMDCCIFLSKENFKSPEFSSUO

Inlämningsuppgifter

Uppgift 4a - Generera nycklar inför kryptering

I denna uppgift ska ni implementera algoritmen för solitaire_keystream som krävs för att generera den nyckelfras som senare används för att kryptera och avkryptera meddelanden. Notera att ni ska skriva funktioner för att representera en kortlek i Python som en abstrakt datatyp. All hantering av kortleken ska gå genom dessa funktioner. När ni implementerar algoritmen (skriver Pythonkod) för att generera en nyckelfras solitaire_keystream ska ni tänka att andra personer som endast känner till hur man krypterar med hjälp av en fysisk kortlek ska förstå ert program.

Funktioner för en kortlek (lägg gärna till fler om ni behöver det):

• Skapa en ny och oblandad kortlek (se övningsuppgifterna).
• Blanda och kupera kortleken.
• Flytta ett kort från en position i kortleken till en annan.
• Ta bort ett kort från en viss position ur kortleken.

En kortlek består av 52 spelkort och två jokrar. För enkelhets skull kommer ni bara att använda er av en halv kortlek (två färger) och två jokrar. Varje kort i kortleken tilldelas ett värde. Spelkorten med den första färgen tilldelas värdena 1 till och med 13, spelkorten med den andra färgen tilldelas 14 till och med 26. De båda jokrarna får värdet 27. Observera att ni ska hantera kortleken som om den bestod av kort, så ni får INTE representera ett kort med enbart ett tal. Däremot bör ni implementera en funktion för att få värdet av ett kort enligt principen ovan.

Uppgift 4b - kryptera text

I denna uppgift ska ni implementera funktionalitet för att kryptera meddelanden med hjälp av Solitaire.

I flera av stegen ska man konvertera mellan bokstäver och tal, gör detta med bokstavens position i alfabetet (A = 1, B = 2, ..., Z = 26).

Algoritm för kryptering:

1. Slopa alla tecken förutom A - Z och konvertera alla gemaner till versaler.
2. Använd solitaire_keystream för att generera en nyckelfras med samma längd som meddelandet. Anta som exempel att vi får nyckelfrasen ABCDEV.
3. Konvertera alla bokstäver i meddelandet till tal. Meddelandet Python skulle bli 16,25,20,8,15,14
4. Konvertera alla bokstäver i nyckelfrasen (steg 2) till tal. Exemplet i steg 2 skulle bli 1,2,3,4,5,22
5. Addera talen från meddelandet (steg 3) med talen i nyckelfrasen (steg 4) och dra bort 26 om summan är högre än 26. Exemplen ovan skulle ge (16+1),(25+2-26),(20+3) och så vidare.
6. Konvertera talen i steg 5 till bokstäver.

Körexempel (det ska gå att köra på detta sätt, resultatet beror dock på hur leken blandas):

>>> deck = create_deck()
>>> solitaire_encrypt("Python", deck)
SGUATB
  

Uppgift 4c - dekryptera text

I denna uppgift ska ni implementera funktionalitet för att dekryptera meddelanden med hjälp av Solitaire.

Algoritm för dekryptering:

1. Konvertera meddelandet som ska dekrypteras till tal.
2. Använd solitaire_keystream för att generera en nyckelfras med samma längd som meddelandet. Det är viktigt att denna fras blir samma som vid kryptering (dvs att kortleken blandas på samma sätt).
3. Konvertera nyckelfrasen till tal.
4. Subtrahera talen från nyckelfrasen (steg 3) från talen i meddelandet (steg 1) och addera 26 om resultatet är mindre än 1.
5. Konvertera siffrorna från steg 4 till bokstäver.

Körexempel:

>>> deck1 = create_deck()
>>> deck2 = create_deck()
>>> secret_message = solitaire_encrypt("Python", deck1)
>>> solitaire_decrypt(secret_message, deck2)
PYTHON

Tänk i detta körexempel på att kortleken behöver vara sorterad på samma sätt när den skickas med till encrypt och decrypt. Det innebär att create_deck behöver skapa identiska kortlekar. Det finns andra lösningar på problemet om man inte vill skapa en create_deck som gör identiska kortlekar, ett exempel är att göra en funktion som kan kopiera kortlekar.

Krav på inlämningen

Utöver att din kod fungerar enligt beskrivningarna och körexemplena ovan så behöver den uppfylla kraven nedan.

• Din kod skall följa principerna för god inkapsling av dina abstrakta datatyper. Detta innebär att dina abstrakta datatyper har alla funktioner som krävs för att hantera datan. Detta innebär också att dessa funktioner är det ENDA sättet som ni interagerar med datan.
• Dina funktioner skall ha tydliga namn och skall lösa det delproblem som namnet indikerar
• Trots att körexemplen ovan körs i interprativt läge så skall ni ha ett huvudprogram att köra vid redovising som visar upp funktionaliteten av programmet.
• Ni behöver förstå hur inkapslingen i ert program fungerar och varför den är viktig.
• Lösningen på problemet skall inte innehålla någon klass, dessa erbjuder vissa features och säkerhet som det är meningen att ni skall lösa uppgiften utan. Klasser kommer ni arbeta med i TDP004.