Problem D
Enigma

Enigma var namnet på en krypteringsmaskin som användes av den tyska krigsmakten under andra världskriget. Enigma-maskinen översatte meddelanden i klartext till krypterade meddelanden bokstav för bokstav, på ett sådant sätt att olika förekomster av en klartext-bokstav (t.ex. ”t”) kunde översättas till olika bokstäver i kryptotexten. Till exempel kunde ”Wetter” översättas till ”fdzxrh”. Kryptot knäcktes av de allierade, mycket på grund av en kryptografisk svaghet i Enigmas konstruktion.

Svagheten i Enigma-kryptot bestod i att en given bokstav i klartexten aldrig kunde översättas till sig själv. Detta utnyttjades av kodknäckarna på följande sätt: Om man antog att ett visst ord (t.ex. ”Wetterbericht”) ingick i klartexten, och kryptotexten såg ut så här: ”astfxahbkljytrbtjkhlhuihlkj” så kunde man dra vissa slutsatser:

Meddelandet kan inte inledas med ”Wetterbericht” eftersom då blir tredje bokstaven i både klartext och kryptotext ett ”t”:

a s t f x a h b k l j y t r b t j k h l h u i h l k j
w e t t e r b e r i c h t

Inte heller kan ”Wetterbericht” starta på position 2, för då skulle ett ”b” översättas till sig självt:

a s t f x a h b k l j y t r b t j k h l h u i h l k j
  w e t t e r b e r i c h t

Däremot skulle ”Wetterbericht” kunna starta på position 3:

a s t f x a h b k l j y t r b t j k h l h u i h l k j
    w e t t e r b e r i c h t

Fortsätter man på samma sätt ser man att positionerna 3, 5, 7, 12 och 15 är möjliga startpositioner för ordet ”Wetterbericht”. Position 15 är den sista möjliga startpositionen, eftersom sedan tar kryptotexten slut:

a s t f x a h b k l j y t r b t j k h l h u i h l k j
                            w e t t e r b e r i c h t

Uppgiften består i att givet en kryptotext, och givet ett ord som man vet förekommer i motsvarande klartext, skriva ut alla positioner i kryptotexten där ordet skulle kunna börja. Positionerna räknas från 1 och uppåt.

Figure 1: En tysk, militär, tre-rotors Enigma

Indata

Indata inleds med en kryptotext som är mellan 20 och 10000 tecken lång, och därefter följer ett ord som är mellan 1 och 50 tecken långt. Du kan förutsätta att både klartext och kryptotext enbart innehåller de gemena (”små”) bokstäverna a-z.

Utdata

Utdata ska bestå av alla positioner i kryptotexten där klartextordet skulle kunna börja, separerade med mellanslag. Om det inte finns några sådana positioner ska ”-1” skrivas ut.

astfxahbkljytrbtjkhlhuihlkj
wetterbericht

3 5 7 12 15

astfxahbkljytrbtjkhlhuihlkj
ilovejustinbieber

2 3 7 10 

aaaaaaaaaaaaaaaaaaaaaaaaaaa
armadillo

-1

bbbbbbbb
armadillo

-1