TILDA, ÖVNING 6 10 okt 2008 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 010101011000110011001111 ? o / \ / \ / \ / \ o \ / \ o / \ / \ o o o T / \ / \ / \ D V H N Ä A ______________________________________________________________________ ********************************************************************** 2. "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. Lempel-Ziv I denna uppgift ska du avkoda ett meddelande som komprimerats med Lempel-Zivs metod. Komprimeringen går till så att komprimeraren lagrar en lista med strängar som från början enbart innehåller tomma strängen. Komprimeraren läser tecken för tecken från intexten den längsta sträng som ligger i strängtabellen. Sedan skrivs index för denna sträng i tabellen ut, följt av nästa tecken i intexten. Strängtabellen utökas med strängen plus nästa tecken. Därefter läses åter tecken för tecken från intexten. Så fort en sträng inte finns i strängtabellen läggs den alltså till. Metoden kan i (icke-optimerad) kod beskrivas så här: def lzw(text): table = Table() q=Queue() for c in text: # spara texten tecken för tecken i en kö q.put(c) s="" table.add(s) kodtext="" # här sparas den kodade texten while not q.isempty(): c=q.get() if table.exists(s+c): s=s+c else: kodtext+=str(table.code(s))+c table.add(s+c) s="" if not s=="": kodtext+=str(table.code(s)) return kodtext Klassen Table stöder inläggning av strängar, kontroll av om en sträng finns i tabellen och möjlighet att ta reda på index hos en speciell sträng. Index bestäms av ordningen strängarna lades in i, där den första strängen har index 1. Uppgiften är att avkoda följande text, där alfabetet består av versaler och mellanslag kodat som "_". 1S1T1O1R2T4C1K1H4L1M2_6O1L3A1_9O14M1A5 Det vill säga: vad är t om print lzw(t) ger ovanstående som utskrift? Ge också en tabell med strängar och index som motsvarar tabellen i koden! ______________________________________________________________________ ********************************************************************** 4. 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! ______________________________________________________________________ ********************************************************************** 5. RSA-kryptering (ur kursboken, uppg 2 s. 125) Du vill hålla ditt turnummer (18) hemligt, och har därför bestämt dig för att kryptera det med RSA. Välj två primtal större än 500 och använd dom för att kryptera turnumret. ______________________________________________________________________ ********************************************************************** 6. Enkel kryptering Kryptera lösenordet SIMSALABIM med a) rot13 b) Transpositionschiffer LÖSNINGAR ______________________________________________________________________ ====================================================================== 1. Smittskydd TVÄTTA HÄNDERNA ______________________________________________________________________ ====================================================================== 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 ______________________________________________________________________ ====================================================================== 5. 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 ______________________________________________________________________ ====================================================================== 6. Enkel kryptering a) FVZFNYNOVZ b) SSAMIABMLI (andra varianter är också möjliga)