IDA - Institutionen för datavetenskap

Del B

Nu när ni har er ADT så kan ni börja implementera algoritmen solitaire_keystream, som krävs för att generera den nyckelfras som senare används för att kryptera och avkryptera meddelanden. 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.

Algoritmen kommer att använda en kortlek för att generera nyckelfrasen, och detta använder ni er ADT för. All hantering av kortleken ska gå genom de funktioner ni implementerat för er ADT. När ni implementerar algoritmen (skriver Pythonkod) för att generera en nyckelfras 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.

Vi har nu tre steg (eller tre funktioner för vår problemlösar-programmerare att implementera) - generera en nyckelfras, kryptera en text och dekryptera en text.

Om er kortleks-ADT innehåller all funktionalitet från del A och ni känner att ni behöver lägga till fler ADT-funktioner för att implementera algoritmen så bör ni i första hand fråga en assistent om tips på hur ni kan använda den existerande funktionaliteten för att lösa problemet.

Generera nyckelfras

Första steget består av att generera en nyckelfras som kommer att användas för att kryptera eller avkryptera ett meddelande. Funktionen som genererar nyckelfrasen ska kunna generera en nyckelfras av en godtycklig längd, vilket kommer att vara längden på meddelandet som ska krypteras. Notera att ni endast får använda de funktioner ni implementerade i del A för att interagera med kortleken.

Ni kommer i flera steg, både för kryptering och dekryptering, att konvertera siffror till bokstäver (A = 1, B = 2, ... Z = 26). Skapa en bra hjälpfunktion för att konvertera ett kort till ett tal, t.ex. att hjärter ess blir 1 och spader ess blir 14, med hjälp av era ADT-funktioner. En joker kan ni ge värdet 27 för enkelhetens skull. Sedan behöver ni även kunna mappa ett tal till en bokstav på ett smidigt sätt, samt från en bokstav till en siffra.

Stegen som algoritmen följer för att generera en nyckelfras är:

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 och sammanfoga dem 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. Använd er hjälpfunktion för att konvertera kortets värde till ett tal. Ifall kortet är en joker blir det ingen nyckel i denna iteration, och ni får köra en gång till från steg 2 direkt. 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.

Säg att vi vill ha en nyckelfras som är sex tecken långt. Då kan vi, som ett exempel, få nyckelfrasen ABCDEV.

Viktigt att tänka på är att ni i detta skede endast ska använda ADT-funktionerna för att interagera med kortleken. Det är dock helt okej (och starkt uppmuntrat!) att ni skapar hjälpfunktioner som använder ADT-funktioner för att lösa delproblem.

Kryptera en text

Nu när ni kan ta fram en nyckelfras så är det dags att kryptera ett meddelande!

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.
7. Ni bör nu ha ett krypterat meddelande!

deck = create_deck()
shuffle_deck(deck)
encrypted = solitaire_encrypt("Meddelande", deck)
print(encrypted) # Skriver ut t.ex. NRPPRZJHPR

Dekryptera en text

Sista steget är nu att dekryptera ett meddelande! Detta görs med följande steg:

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.
6. Om allting är korrekt bör ni nu få ut samma meddelande som krypterades!

deck1 = create_deck()
shuffle_deck(deck1)
deck2 = copy_deck(deck1)
encrypted = solitaire_encrypt("Meddelande", deck1) # Blir t.ex. NRPPRZJHPR
decrypted = solitaire_decrypt(encrypted, deck2)
print(decrypted) # Skriver ut MEDDELANDE

Krav på inlämningen

Utöver att din kod fungerar enligt beskrivningarna 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 och behöver interagera med datan.
• Dina funktioner skall ha tydliga namn och skall lösa det delproblem som namnet indikerar
• Ni behöver förstå hur inkapslingen i ert program fungerar och varför den är viktig.
• Klasser är något som ligger utanför målen för denna kurs. Lösningen på detta problem ska inte innehålla någon klass (vet du inte vad en klass är för tillfället är det helt okej). 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.