Övning 6

Komprimering, kryptering, dokumentering & testning

1. Smittskydd (Tildatenta 030828)

   Du har fått ett mail som innehåller tips mot spridning av virus. Informationen är komprimerad med ett Huffmanträd där nollor motsvarar vänster och ettor motsvarar höger (se figur, T kodas t.ex. som 11) Vad står det i meddelandet nedan?

   010101011000110011001111
   
   
             o
            / \
           /   \
          /     \
         /       \
        o         \
       / \         o
      /   \       / \
     o     o     o   T
    / \   / \   / \
   D   V H   N Ä   A 
   

   ---

2. man är mans gamman

   "man är mans gamman" kan man läsa i Havamal. Konstruera en huffmankod för tecknen i detta uttryck (rita trädet) och skriv sedan upp det i kodad form.

   ---

3. Bäst komprimering

   Jämför Huffmanträden i uppgifterna ovan. Vilket ger bäst komprimering? Motivera ditt svar!

   ---

4. Enkel kryptering

   a) Kryptera SIMSALABIM med rot13

   b) Visa med ett exempel hur man går till väga för att dechiffrera transpositionschiffer. T ex GKNTAAKN ESEL

   c) 1 1 2 5 6 15 är krypterat med en variant av bokchiffer där man använt uppgiftsnummer istället för sidnummer. Vad står det?

   d) Meddelandet 0b1100010 är krypterat med one-time pad med nyckeln 0b0110011. Dekryptera!

   ---

5. Testning

   I labb 6 ska ni göra ett program som kontrollerar syntaxen för en molekylformel. Skriv upp en samling indata att testa programmet med!

   ---

6. Tidstentan 2015-03-20, uppgift 1 (betyg E)

   Rymdvarelser har uppmärksammat jordens existens och vill ta kontakt med en tildastudent på KTH. Rymdvarelserna är oroliga för att NSA ska avlyssna eller på annat sätt blanda sig i kommunikationen, men har läst att RSA-konceptet med publika och privata nycklar kan lösa kommunikationsproblematiken. Förklara vilka problem som kan lösas med hjälp av asymmetrisk kryptering med publika och privata nycklar, och berätta för rymdvarelserna hur det ska gå till.

7. Tidstentan 2014-10-24, uppgift 7 (betyg C)

   Följande tre uppsättningar av koder är tänkta att använda för komprimering. Vilka fungerar för komprimering? Vilken är effektivast? Motivera ditt svar! kod1 E 11 A 10 N 011 R 010 T 001 S 0001 I 0000 kod2 111 101 100 011 010 001 000 kod3 10 11 110 101 111 0100 0111

LÖSNINGAR

1. Smittskydd

   HANDTVÄTT

   ---

2. "man är mans gamman"

   Totalt är det 18 tecken. Andelen av respektive tecken:

   Tecken | antal | andel
   ----------------------
   m   | 4 | 2/9
   a   | 4 | 2/9
   n   | 3 | 3/18
   " " | 3 | 3/18
   ä   | 1 | 1/18
   r   | 1 | 1/18
   s   | 1 | 1/18
   g   | 1 | 1/18
   
   

   Detta ger efter trädskapande till exempel följande huffmankoder:

   Tecken | Huffmankod
   -------------------
   m   | 10
   a   | 11
   n   | 010
   " " | 011
   ä   | 0000
   r   | 0001
   s   | 0010
   g   | 0011
   
   Vilket ger följande kodning av texten:
   10 11 010 011 0000 0001 011 10 11 010 0010 011 0011 11 10 10 11 010
   

   ---

   ---

3. Bäst komprimering

   Det vi strävar efter är att mer frekventa tecken ska få kortare koder. Därför ger det andra huffmanträdet (som inte är balanserat) bäst komprimering.

   ---

4. Enkel kryptering

   a) FVZFNYNOVZ
   b) Låt programmet byta rad efter 2, sen efter 3, sen efter 4 ... tills meddelandet framträder.
   c) Du kan kryptera

   ---

5. Testning

   Tänk på att du ska testa både med giltiga och ogiltiga molekylformler!

   ---

6. RSA-kryptering

   p = 503  
   q = 601
   
   n = p*q = 302303
   
   f = (p-1)*(q-1) = 301200
   
   Välj e så att gcd(e, f) = 1
   301200 = 2*5*2*5*2*2*3*251
   Faktorn 7 finns inte med, välj e = 7
   
   Krypteringen:
   18 upphöjt till 7 modulo 302303