Programmering av dekrypteringsmaskin för simpelt monoalfabetiskt substitutionschiffer

Hej igen!

Kul att du kommit vidare i kodandet.

Som frågan är ställd har jag svårt att svara på den. 

Jag har gjort första delen som bara kollar på enstaka bokstäver och utifrån det tar fram en första gissning på vilka bokstäver som motsvarar vilka.

Hur går gissandet till? Jämför du ord med en ordlista och/eller räknar du IoC?

Men jag har helt fastnat nu när jag försöker komma på något bra sätt att kombinera resultatet från analysen av enstaka bokstäver med resultatet från analys av exempelvis bi- och trigram.

Vad är det du fastnat på? Alltså: Vad är det du försöker göra som inte fungerar? Alternativt: Vart vill du komma?

För att kunna hjälpa till skulle jag nog behöva lite mer detaljerad info. Alltså, vad du gjort, vad som fungerar och vad du vill optimera eller lösa. Lite kod, pseudokod, eller bara beskrivande text fungerar för mig.

Jag kan inget om denna tillämpning, men en viktig grej när man gör forskning är att kolla på existerande litteratur. Så, har du tittat vad som redan finns på ämnet?

Baserat på det du skriver så låter det som att du försöker hitta på en egen metod? Om så är fallet skulle jag börjat med att implementera en existerande metod. Dels gör det att du kommer in i tänket och lär dig mer om problemet och nuvarande lösningar, och det skapar också en bra grund för jämförelse med din framtida nya metod. Då kan du svara på frågan ”gör [vad din nya metod gör annorlunda] att man kan knäcka enkelt monoalfabetiskt substitutionsschiffer snabbare/för längre meddelanden/…/[annan egenskap som kan vara av intresse]?”

En annan anledning till att börja med existerande metod är att du då har något att falla tillbaka på om du inte kommer vidare med din egna metod: då kan du istället skifta fokus och svara på frågor i stil med ”[hur snabbt knäcker/hur långa ord klarar/annat] [metoden du testat]?”

sedan när du ska utveckla din egen metod skulle jag likt tidigare svar ge rådet att börja med att skriva ned en problemformulering (vilket är problemet du vill lösa i detalj), samt hur du tänkt metoden funkar (text, pseduokod, annat) så att det blir tydligare för både dig och andra vad det är du tänkt dig. Kör hårt!

sictransit skrev:

Hej igen!

Kul att du kommit vidare i kodandet.

Som frågan är ställd har jag svårt att svara på den. 

Jag har gjort första delen som bara kollar på enstaka bokstäver och utifrån det tar fram en första gissning på vilka bokstäver som motsvarar vilka.

Hur går gissandet till? Jämför du ord med en ordlista och/eller räknar du IoC?

Men jag har helt fastnat nu när jag försöker komma på något bra sätt att kombinera resultatet från analysen av enstaka bokstäver med resultatet från analys av exempelvis bi- och trigram.

Vad är det du fastnat på? Alltså: Vad är det du försöker göra som inte fungerar? Alternativt: Vart vill du komma?

För att kunna hjälpa till skulle jag nog behöva lite mer detaljerad info. Alltså, vad du gjort, vad som fungerar och vad du vill optimera eller lösa. Lite kod, pseudokod, eller bara beskrivande text fungerar för mig.

Absolut!

Än så länge har jag skrivit ett program som tar fram alla boksavsfrekvenser i en text och jämför dessa med kända tabellvärden. Programmet tar helt enkelt fram den bästa matchningen/gissningen genom att hitta den minsta differansen mellan den uträknade frekvensen och de kända. Sedan gör programmet detta för alla bokstäver och lägger de gissade krypterad/klartext-paren i ett dictionary. Eftersom jag vet hur texten är krypterad (i mitt fall ett ceasarchiffer med förskjutning 1) kan jag också enkelt reverse-engineera algoritmen och kolla hur många rätt jag fick. Detta program fungerar ganska bra och jag har kunnat få ut extremt grova resultat för hur längden på meddelandet påverkar hur många bokstäver som jag får rätt.

Men som det ser ut nu så krävs det en väldigt lång text (tiotusentals ord minst) för att ens kunna gissa rätt på mer än hälften av de tio vanligaste bokstäverna (och de mer ovanliga bokstäverna behöver vi inte ens prata om). Så därför tänker jag att man borde kunna få ett bättre resultat om man också kollar på ex. bi- och trigram för att sedan "slå ihop" gissningarna/datan från de olika metoderna till någon form av kombinerad gissning som förhoppningsvis är mer exakt och bättre. Men jag kan inte komma på något bra och/eller enkelt sätt att kombinera resultaten. Det enda jag kunnat komma fram till än så länge är väl att på något sätt för varje bokstav i kryptotexten och för varje metod (uni-, bi- och trigram) ge någon typ av sannolikhet för vad den kan motsvara och sedan kombinera de sannolikheterna. Men jag har inte kunnat komma på något konkret sätt.

Är det verkligen bara Caesar-chiffer du vill lösa? Alltså substitutionschiffer medelst förskjutning?  Då finns det bara 28 tänkbara "nycklar" lika med antalet steg förskjutning vilket du bör kunna använda att för varje nyckel beräkna ett index på hur bra frekvenserna för samtliga bokstäver är.  T.ex.  skillnaden mellan procentuella frekvensen i den dekrypterade texten (för den nyckeln) och frekvensen i språket, ta absolutvärdet och summera.

OM det är generella  substitioner finns det alldeles fär många nycklar för en liknande ansats

Jag misstänker dock att om du har fått en lösning med bi- eller trigram lär inte unigramen tillföra nånting nämnvärt så jag skulle inte fundera så mycket på hur man kombinerar dem.

farfarMats skrev:

Är det verkligen bara Caesar-chiffer du vill lösa? Alltså substitutionschiffer medelst förskjutning?  Då finns det bara 28 tänkbara "nycklar" lika med antalet steg förskjutning vilket du bör kunna använda att för varje nyckel beräkna ett index på hur bra frekvenserna för samtliga bokstäver är.  T.ex.  skillnaden mellan procentuella frekvensen i den dekrypterade texten (för den nyckeln) och frekvensen i språket, ta absolutvärdet och summera.

OM det är generella  substitioner finns det alldeles fär många nycklar för en liknande ansats

Nej, jag tänkte försöka lösa mer generella substitutionschiffer eftersom det, som du säger, bara finns 28 (eller 25 i mitt fall eftersom jag utgår ifrån att språket är engelska) nycklar med ceasarchiffer. Så då fungerar ju inte den ansatsen som du påpekar. Att jag använder Caesar för krypteringen är bara för enkelhetens skull, programmet vet ju ändå inte om det och jag behandlar dekrypteringen som om det är en generell substitution.

Jag misstänker dock att om du har fått en lösning med bi- eller trigram lär inte unigramen tillföra nånting nämnvärt så jag skulle inte fundera så mycket på hur man kombinerar dem.

Tror du inte? Som sagt så krävs det just nu en väldigt lång text för att ens få ett någolunda bra resultat. Jag tänker att jag kommer kunna få mer exakt resultat med kortare texter om jag på något sätt kombinerar flera olika frekvensanalyser?

Självklart blir det bättre men förmodligen bara lite...

Min tanke är  bi/trigramens frekvenser begränsar de möjliga bokstavsfrekvenserna och att därmed de senare inte bidrar med så mycket ny information.

Du behöver en ordlista! Antingen nu, eller senare. För korta meddelanden är det i princip nödvändigt. Dock är det inte nyckeln till att lösa allt.

För det första har du kanske bara grundformen i ordlistan medan texten innehåll böjningar. Sedan finns det säkert flera lösningar som alla ger träffar i ordlistan, men där kanske bara en ger texten en rimlig mening. Vad värre är att texten du försöker dekryptera kanske inte innehåller enbart ord som finns i ordlistan, utan även stavfel (som kan vara avsiktliga).

Korta texter är svåra att forcera, men det är ju också en lärdom, ett resultat. 

Här är tre texter, i ökande svårighetsgrad krypterade med denna nyckel: xeigonqvazkshyjmpldbuwfcrt

Jag har provkört dem i detta verktyg: https://www.boxentriq.com/code-breaking/substitution-cipher

clear: this simple message should be easy to decode
cipher: bvad dahmso hoddxqo dvjusg eo oxdr bj goijgo
decoded: this simple message should be easy to decode

clear: the quick brown fox jumps over thirteen lazy dogs
cipher: bvo puaik eljfy njc zuhmd jwol bvalbooy sxtr gjqd
decoded: the maily frown god backs over thirteen puzj qoxs

clear: vex jumpy wizard pack cold quirk jars fast
cipher: woc zuhmr fatxlg mxik ijsg pualk zxld nxdb
decoded: ply brick womand cast shed front bang uagj

Den första texten innehåller enbart ordboksord och dessutom vanliga sådana, så en analys av bi- eller trigram borde ge resulat.

I den andra är det lite besvärligare ord. Algoritmen kan inte bestämma om exempelvis "god" är bättre än "fox". 

Till sist har jag avsiktligt valt ord vars bigram kommer långt ned på listan. Allt finns i ordlistan, men hur vet vi vad vi skall välja?

Nu har jag ändå varit snäll. Skiffertexten har fått behålla sina mellanslag på rätt ställen. Utan dem är det ännu svårare. Det är kanske också en sak att ta i beaktande?

Som du redan varit inne på blir det genast lättare med en längre text:

hxbboioybluhadxdfogadvyjymljnabjlqxyatxbajybvxbmljwagodnloohxbvbubjlayqjulhaddajyadbjmljhjboopuxsxiioddbjsoxlyayqoyvxyiodbugoybdhxbvohxbaixskyjfsogqoxygnjdbolxqloxbolaybolodbayhxbvohxbaidhxbboioybluhjmolxbodejbvjysayoxygjnnsayojnnolayqxssjnabddolwaiodijhmsobosrnloojnivxlqobjmxlbaiamxybdhxbboioybluhadnuygogbvljuqvxijheayxbajyjnmuesaiqlxybdijlmjlxbodmjydjldvamdnjuygxbajydummjlbxygaygawaguxsgjyxbajyd

Svårt? Absolut. Men det är ju ett gymnasiearbete, så lägg lite tid på att läsa på och fundera. Det finns väldigt mycket på nätet om att knäcka substitutionschiffer.

sictransit skrev:

Du behöver en ordlista! Antingen nu, eller senare. För korta meddelanden är det i princip nödvändigt. Dock är det inte nyckeln till att lösa allt.

För det första har du kanske bara grundformen i ordlistan medan texten innehåll böjningar. Sedan finns det säkert flera lösningar som alla ger träffar i ordlistan, men där kanske bara en ger texten en rimlig mening. Vad värre är att texten du försöker dekryptera kanske inte innehåller enbart ord som finns i ordlistan, utan även stavfel (som kan vara avsiktliga).

Korta texter är svåra att forcera, men det är ju också en lärdom, ett resultat. 

---

Här är tre texter, i ökande svårighetsgrad krypterade med denna nyckel: xeigonqvazkshyjmpldbuwfcrt

Jag har provkört dem i detta verktyg: https://www.boxentriq.com/code-breaking/substitution-cipher

clear: this simple message should be easy to decode
cipher: bvad dahmso hoddxqo dvjusg eo oxdr bj goijgo
decoded: this simple message should be easy to decode

clear: the quick brown fox jumps over thirteen lazy dogs
cipher: bvo puaik eljfy njc zuhmd jwol bvalbooy sxtr gjqd
decoded: the maily frown god backs over thirteen puzj qoxs

clear: vex jumpy wizard pack cold quirk jars fast
cipher: woc zuhmr fatxlg mxik ijsg pualk zxld nxdb
decoded: ply brick womand cast shed front bang uagj

Den första texten innehåller enbart ordboksord och dessutom vanliga sådana, så en analys av bi- eller trigram borde ge resulat.

I den andra är det lite besvärligare ord. Algoritmen kan inte bestämma om exempelvis "god" är bättre än "fox". 

Till sist har jag avsiktligt valt ord vars bigram kommer långt ned på listan. Allt finns i ordlistan, men hur vet vi vad vi skall välja?

Nu har jag ändå varit snäll. Skiffertexten har fått behålla sina mellanslag på rätt ställen. Utan dem är det ännu svårare. Det är kanske också en sak att ta i beaktande?

Som du redan varit inne på blir det genast lättare med en längre text:

hxbboioybluhadxdfogadvyjymljnabjlqxyatxbajybvxbmljwagodnloohxbvbubjlayqjulhaddajyadbjmljhjboopuxsxiioddbjsoxlyayqoyvxyiodbugoybdhxbvohxbaixskyjfsogqoxygnjdbolxqloxbolaybolodbayhxbvohxbaidhxbboioybluhjmolxbodejbvjysayoxygjnnsayojnnolayqxssjnabddolwaiodijhmsobosrnloojnivxlqobjmxlbaiamxybdhxbboioybluhadnuygogbvljuqvxijheayxbajyjnmuesaiqlxybdijlmjlxbodmjydjldvamdnjuygxbajydummjlbxygaygawaguxsgjyxbajyd

Visa spoiler

mat te cent rum is a swedish non profit organization that provides free mathtu to ring our mission is to promote equal access to learning enhance students mathematical knowledge and foster a greater interest in mathematics mat te cent rum operate s both on line and off line offering all of its services completely free of charge to participants mat te cent rum is fund ed through a combination of public grants corpora te sponsorship s foundation support and individual donations

 

---

Svårt? Absolut. Men det är ju ett gymnasiearbete, så lägg lite tid på att läsa på och fundera. Det finns väldigt mycket på nätet om att knäcka substitutionschiffer.

Först och främst; förlåt för lång tid sedan senaste respons här, har haft mycket annat och inte hunnit lägga så mycket tid på arbetet senaste veckan.

Efter lite research hittade jag denna sida och implementerade ett program med denna metod. Denna metod är väldigt mycket mer precis än den med frekvensanalys och jag kan (beroende på text) få en i princip helt dekrypterad text på bara ett par hundra ord. Detta till skillnad från de tusen och åter tusentals ord långa texter som krävdes för min förra metod. Värt och nämna är ju dock att denna metod bara fungerar om jag har en rättstavad text där mellanslag är bevarade.

Så min fundering nu blir ju hur jag ska använda detta. Med denna nya metod känns ju frekvensanalysen närmst värdelös så frågan är om man ska byta fokus på arbetet? Eller om man ska skifta frågeställningen till att jämföra de två metoderna? Letar inte efter ett tydligt svar men tänker om ni får några specifika tankar eller idéer :).

Själv har jag väl börjat tänka i banorna om man ska försöka göra någon jämförelse istället mellan olika dekrypteringsmetoder (Typ komplexitet, tid, krävd längd på text, förutsättningar för det krypterade meddelandet osv.). Skulle det kanske kunna vara något?