Automatický dešifrátor pro šifrovací hry
| Název práce v češtině: | Automatický dešifrátor pro šifrovací hry |
|---|---|
| Název v anglickém jazyce: | Deciphering tool for puzzlehunt games |
| Klíčová slova: | dešifrátor, substituční šifra, jazykový model |
| Klíčová slova anglicky: | deciphering, substitution cipher, language model |
| Akademický rok vypsání: | 2013/2014 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | čeština |
| Ústav: | Ústav formální a aplikované lingvistiky (32-UFAL) |
| Vedoucí / školitel: | RNDr. David Mareček, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 06.11.2013 |
| Datum zadání: | 06.11.2013 |
| Datum potvrzení stud. oddělením: | 26.02.2014 |
| Datum a čas obhajoby: | 04.09.2014 00:00 |
| Datum odevzdání elektronické podoby: | 29.07.2014 |
| Datum odevzdání tištěné podoby: | 28.07.2014 |
| Datum proběhlé obhajoby: | 04.09.2014 |
| Oponenti: | Mgr. Rudolf Rosa, Ph.D. |
| Zásady pro vypracování |
| Šifrovací hra (též šifrovačka) je hra či soutěž, jejíž základní částí je luštění šifer. Na každém stanovišti získá tým zadání jedné šifry, jejímž vyluštěním zpravidla získá informace o poloze dalšího stanoviště. V současnosti je v České republice několik tisíc pravidelných účastníků šifrovacích her. Nejznámější šifrovací hry jsou například TMOU (http://tmou.cz), Bedna (http://bedna.org), Matrix (http://velkyvuz.cz/matrix) nebo Svíčky (http://svicky.sifrovacka.org).
Cílem projektu je vytvořit nástroj pro řešení takzvaných substitučních šifer, ve kterých je použitá abeceda bijektivně zobrazena do nějaké jiné množiny znaků (symbolů, obrázků) nebo často do premutace té samé abecedy. Příkladem takových šifer je například Morseova abeceda, Ceasarova šifra, Brailovo písmo nebo Polský kříž, zde je ale převodní tabulka již známá. Úkolem programu bude navrhnout řešení obecné substituční šifry bez znalosti převodní tabulky. Takové zadání šifry může vypadat například takto: QBAPLOKZAPQPOFCMKAWK Program by zde měl ideálně najít takové mapování písmen, které dá co nejsmysluplnější řešení, v tomto případě mapování A->K, B->M, E->P, H->L, I->C, N->F, R->0, S->A, T->W, V->Q, Y->B dá řešení VYSEHRADSEVERNIBASTA, tedy "severní bašta na Vyšehradě". Jiná typická řešení šifer jsou například: KOVAROVAKOSTEL VROHBUDKALIBOCKYRYBNICEK VYHLIDKAUULICEPODHAVRANKOU Je zřejmé, že možností mapování je exponenciálně mnoho a při prohledávání prostoru bude třeba značně prořezávat málo pravděpodobná řešení. Bude třeba využít jazykového modelu, který bude zahazovat nepravděpodobné sekvence písmen či slov. Další možností je zadat s šifrou i aktuální polohu a použít nějakou databázi míst (ulic, náměstí, kostelů, čtvrtí) obsahující jejich GPS souřadnice, která umožní zahazovat řešení vedoucí místa příliš vzdálená od aktuální polohy. Uživatel zadá na vstupu šifru v podobě sekvence znaků (případně i aktuální polohu). Výstupem programu bude seznam možných řešení šifry seřazený od nejpravděpodobnějšího k nejméně pravděpodobnému. |
| Seznam odborné literatury |
| Chris Manning and Hinrich Schütze: Foundations of Statistical Natural Language Processing. MIT Press, Cambridge, MA, May 1999
TMOU Manuál: http://www.tmou.cz/_media/archiv/tmou_manual.pdf Malte Nuhn and Hermann Ney: Decipherment Complexity in 1:1 Substitution Ciphers. Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pp 615-621, Sofia, Bulgaria, Association for Computational Linguistics, August 2013 |