Kriptoanaliza homofone substitucijske šifre ; Cryptanalysis of homophonic substitution cipher

Substitucijsko šifro so znali s pomočjo frekvenčne analize razbiti že v 9. stoletju. Z razširitvijo abecede šifriranega sporočila šifro izboljšamo, saj s tem zabrišemo jezikovne vzorce in tako otežimo razbijanje. Izboljšani šifri rečemo homofona substitucijska šifra. Njeno razbijanje le z uporabo papirja in svinčnika tako ni mogoče. V diplomskem delu problem razbijanja homofone substitucijske šifre predstavimo kot optimizacijski problem, ki ga nato uspešno rešimo s kombinacijo dveh hevrističnih algoritmov. Med seboj primerjamo uporabo simuliranega ohlajanja in iskalnega algoritma Tabu ter vpliv uporabe bigramov in trigramov na možnost uspešnega razbitja šifre. Na uspešnost razbijanja je vplivala predvsem dolžina kriptograma in kompleksnost ključa šifre. Razvit algoritem je razbil kar 57% najtežjih testnih primerov in 98% najlažjih. ; Substitution cipher was broken using frequency analysis already in the 9th century. By using more ciphertext symbols the frequency distribution is flattened which makes cracking more difficult. This cipher is named homophonic substitution cipher. It is not possible to break it using only pencil and paper. In this thesis, the problem of breaking the homophonic substitution cipher is presented as an optimization problem, which is then successfully solved by a combination of two heuristic algorithms. We compare simulated annealing and Tabu search with each other and inspect the impact of the use of bigrams and trigrams on cracking. Performance is mainly influenced by the length of the ciphertext and the complexity of the cipher key. Our implementation broke as many as 57% of the most difficult test cases and 98% of the easiest ones.