Dekrypteringsmaskin för substitutionsschiffer = görbart gymnasiearbete inom naturvetenskap?
Hej!
Jag (och min partner) går i trean på naturprogrammet och håller på med vårt gymnasiearbete. Vi vill gärna göra något inom programmering då vi båda är intresserade av det. Jag är också intresserad av kryptografi så jag tänkte att man kanske kan kombinera dessa ämnen. Min tanke var då att man kanske kunde skriva ett program som med hjälp av frekvensanalys och relaterade metoder (typ kolla på vilka bokstäver som ofta förekommer bredvid varann eller på frekvenser av dubbla likadana bokstäver) kan knäcka substitutionsschiffer.
Och sedan tänker jag att man kan ha någon frågeställning i stil med "hur påverkar meddelandets längd hur precist vi kan knäcka det?" eller kanske "Hur påverkar texttypen hur svårt det är att knäcka med frekvensanalys?"
Jag har börjat jobba nu och märker att det antagligen kan bli rätt svårt (men inte omöjligt) i och med att man måste göra ganska många antaganden och gissningar när man dekrypterar och att få en dator att anta saker är inte helt enkelt. Men till frågan: Tror ni fantastiska människor att det är ett rimligt arbete? Och har ni några andra intressanta frågeställningar ifall ämnet känns rimligt?
Tack på förhand för evetuella svar/tips/råd! :))
Jag tycker det låter som en intressant idé och med lite kreativitet går den säkert att realisera!
Frågeställningarna du har föreslagit verkar okej, men hur ska man kvantifiera hur "precist" man kan knäcka ett meddelande, eller hur "svårt" det är att knäcka ett meddelande? Det kanske hade varit bättre att ha en mer teknisk formulering á la "hur beror dekrypteringstiden av meddelandets längd?" eller dylikt. Då bakar man in lite algoritmteori också vilket är trevligt. Ett rimligt antagande är kanske att dekrypteringstiden avtar då meddelandets längd ökar eftersom t.ex. frekvensanalys blir säkrare med fler ord. Utöver en manuell analys av tidskomplexitet har Python många bibliotek som håller koll på hur lång tid det tar att exekvera ett program.
Ni kan ju skriva flera dekrypteringsalgoritmer för olika fall och låta datorn tugga tills den hittar en som fungerar. Jag är inte så insatt i kryptografi, men jag förstår inte hur man bara skulle kunna "delvis" avkryptera ett meddelande. Antingen så hittar man väl nyckeln och dekrypterar allt, eller så hittar man den inte och dekrypterar ingenting (om hela meddelandet är krypterat på samma sätt, såklart).
Hej och välkommen till Pluggakuten!
Intressant projekt, som definitivt är genomförbart.
Du skriver att ni båda är intresserade av programmering. Skoj! Då utgår jag ifrån att ni inte kommer att ha problem med syntax. Jag tänker att ni säkerligen vill prova olika algoritmer och kommer att skriva en hel del kod. Det är där, alltså precis runt de tankar du redan har, som arbetet skall ligga. Om ni istället lägger en stor del av tiden på att samtidigt lära er programmering så får ni justera ambitionsnivån därefter.
Jag har sysslat en hel del med kryptografi i kombination med kodande, så det finns säkert många tips jag kan komma med. För några år sedan knåpade jag ihop en komplett Enigma i C#. Kika på koden om du är nyfiken. Just nu sitter jag lite tight (på jobbet), men jag återkommer kanske senare. Helt säkert svarar jag på ytterligare konkreta frågor du ställer i forumet.
En sak som direkt blir intressant vid automatisering är ju hur en algoritm skall veta när den är klar, alltså när kryptot är knäckt och du har en klartext. Nyatte var inne på den frågeställningen också.
Ta den här kryptotexten som ett enkelt substitutionschiffer spottat ut:
Zhofrph wr Soxjjdnxwhq
Som människa kan du definitivt gissa klartexten om din algoritm spottar ur sig:
Weldome to Pluggzkuten
Det är bara 4/25 bokstäver i den gissade nyckeln som är fel, men hur vet er kod när den är klar?
Ett viktigt verktyg att titta på, som inte helt löser ovanstående fråga: Index of coincidence - Wikipedia
Den kan göra en google-sökning med de funna orden. Om den hittar massor är det förmodligen en korrekt text, om den knappt hittar någonting är det inte det.
Laguna skrev:Den kan göra en google-sökning med de funna orden. Om den hittar massor är det förmodligen en korrekt text, om den knappt hittar någonting är det inte det.
25!/2 för ett substitutionschiffer med A-Z. Många sökningar blir det. 🤣
Man ska ju använda information om bokstävernas frekvens också.
Om man tror att man vet språket kan man ha en lista över vanliga ord i närheten.
En människa som dechiffrerar provar inte heller 25! möjligheter.
Nej, det var ju just det som var den ledande frågan till TS. Hur vet en maskin när den är (tillräckligt) klar?
Du och jag har ju en inbyggd ordlista och dessutom en svårslagen förmåga till mönsterigenkänning. För oss är det inga problem.
Att lösa det i kod är en bra och viktig del av gymnasiearbetet.
sictransit skrev:Hej och välkommen till Pluggakuten!
Intressant projekt, som definitivt är genomförbart.
Du skriver att ni båda är intresserade av programmering. Skoj! Då utgår jag ifrån att ni inte kommer att ha problem med syntax. Jag tänker att ni säkerligen vill prova olika algoritmer och kommer att skriva en hel del kod. Det är där, alltså precis runt de tankar du redan har, som arbetet skall ligga. Om ni istället lägger en stor del av tiden på att samtidigt lära er programmering så får ni justera ambitionsnivån därefter.
Jag har sysslat en hel del med kryptografi i kombination med kodande, så det finns säkert många tips jag kan komma med. För några år sedan knåpade jag ihop en komplett Enigma i C#. Kika på koden om du är nyfiken. Just nu sitter jag lite tight (på jobbet), men jag återkommer kanske senare. Helt säkert svarar jag på ytterligare konkreta frågor du ställer i forumet.
En sak som direkt blir intressant vid automatisering är ju hur en algoritm skall veta när den är klar, alltså när kryptot är knäckt och du har en klartext. Nyatte var inne på den frågeställningen också.
Ta den här kryptotexten som ett enkelt substitutionschiffer spottat ut:
Zhofrph wr SoxjjdnxwhqSom människa kan du definitivt gissa klartexten om din algoritm spottar ur sig:
Weldome to Pluggzkuten
Det är bara 4/25 bokstäver i den gissade nyckeln som är fel, men hur vet er kod när den är klar?Ett viktigt verktyg att titta på, som inte helt löser ovanstående fråga: Index of coincidence - Wikipedia
Tack alla för snabba och intressanta svar! Och tack för välkomnandet!
Funderar lite på de "olika algoritmerna" du nämner, vad syftar du på där? Menar du att t.ex. frekvensanalys för de individuella bokstäverna och för dubbelbokstäver (ex. 'tt' eller 'll') är två olika algoritmer? Eller tänker du på helt andra metoder än frekvensanalys (typ brute-force) som andra algoritmer?
Nej, det jag först och främst tänkte på är att man brukar skriva kod, skriva om, några gånger … Då underlättar det om man behärskar språket så att man kan realisera de idéer man har i kod utan att fastna i onödan.
Sedan kanske ni också vill prova olika angreppssätt, där brute force kan vara ett.
sictransit skrev:Nej, det jag först och främst tänkte på är att man brukar skriva kod, skriva om, några gånger … Då underlättar det om man behärskar språket så att man kan realisera de idéer man har i kod utan att fastna i onödan.
Sedan kanske ni också vill prova olika angreppssätt, där brute force kan vara ett.
Okej, tack! Då ska jag fortsätta jobba och återkommer med eventuella frågor som uppstår längs vägen :)
