Vítejte na stránkách konference CryptoFest
Praha, 19.3.2005 > ČVUT Praha
Fakulta elektrotechnická, Praha 2, Karlovo náměstí 13, místnost K1
Fakulta elektrotechnická, Praha 2, Karlovo náměstí 13, místnost K1
• ročník 03 05
Dne 19.3.2005 se konal CryptoFest 2005. Na akci jste si mohli kromě shlédnutí šesti skvělých přednášek vyzkoušet v soutěži i vaše dešifrovací schopnosti. Tato stránka je tu pro ty, kteří si chtějí schopnosti vyzkoušet dodatečně nebo ty, které zajímají komentovaná řešení.
Přirozeně už se nehraje o výhry, ty už jsou rozdány a šťastní výherci si je užívají.
Úlohy jsou navržené tak, aby pro jejich řešení nebyl nutný počítač. Řešení úloh je stručně popsáno v komentáři k další úloze. Na konci je podrobnější vysvětlení.
Bodování úloh bylo následující 1. - 1 bod, 2. - 2 body, 3. - 4 body. Mezi nejlepšími finální kolo.
Píše se rok 63 před naším letopočtem. Celá Evropa je ovládána Římany - tedy skoro celá. Jedna malá Galská osada stále a vytrvale vzdoruje uchvatiteli. V tomto roce - 63 před naším letopočtem - zašlo vše již tak daleko, že i sám velký Caesar se přijel podívat jaktože ti Galšťí barbaři jsou schopni vzdorovat vojskům neporazitelného Římského impéria. Po zdrcujícím zjištění odeslal do Říma zašifrovanou zprávu o stavu věcí, nechť si senátoři lámou hlavy jak situaci vyřešit.
My se přesuneme do roku 2005, kdy již víme, že zpráva padla do rukou nepřítele díky zlovolnému senátoru jménem Biggus Dickus in-the-middle. Dovolte mi abych se představil, jsem zlomyslný historik - fiktivní postava, která vás bude dnešní soutěží provázet a jíž se jen tak nezbavíte. Před nedávnem jsem zmiňovanou zprávu nalezl, rozšifroval, přeložil - tady by se vám asi líbilo aby věta končila, leč ona pokračuje - a znovu zašifroval. Ale v tom by neměl být žádný problém, jsme na CF a vaším prvním soutěžním úkolem tedy bude zprávu rozšifrovat.
Oqhrdk irdl, uhcdk irdl z mdudqhk ukzrsmhl nbhl. Jnrsjx irnt uqydmx.
Dešifrujte.
A máme tady další soutěžní vstup. Přesunuli jsme se po časové ose směrem k současnosti o celých 15 století a aby to nebylo málo, nezůstaneme ani na stejném místě. Nacházíme se v Portugalsku v roce 1492 a královna právě obdržela důležitou - leč zašifrovanou - zprávu. Vy již jistě tušíte, co bude váš další soutěžní úkol - a také jistě tušíte, že zlomyslný historik - tedy já - opět zapracoval.
Podívejme se ale na předchozí úlohu. Jak jste jistě všichni rozluštili, Cézar po obhlédnutí bojiště pronesl památný výrok "Přišel jsem, viděl jsem a neveřil vlastním očím. Kostky jsou vrženy.". Teď jsem si vzpomněl - taková veselá historka - víte, ona španělská královna velmi ráda hrála hru v kostky. Nechci tedy příliš napovídat, ale myslím si, že v tom by mohl být schovaný klíč.
Pwyl jdim ses dnt e stz roct wmecim nl daplh a pz hlofle a fxrpyi cedxe jdim nlwel ysvof gesey do Trdip.
Dešifrujte.
Liberté, egalité, fraternité.
Je 13. července roku 1789, předvečer velkých událostí. Monarchie již má na kahánku a revoluce se nezadržitelně blíží. To proto, že revoltující lid je překvapivě dobře a přitom tajně organizován.
Francouzští revolucionáři používali již velmi pokročilou šifru. Ve srovnání s touto šifrou vypadá šifra, kterou používala Španělská královna, jako hračka pro děti. Proto také dnes víme, že tenkrát v roce 1492 zpráva zněla "Plul jsem sto dní a sto nocí směrem na západ a po dlouhé a útrpné cestě jsem našel novou cestu do Indie." což je také řešením předchozí úlohy.
Vaší další úlohou bude vyluštit zprávu, která se zapsala do dějin. Nyní budu dokonce tak svolný, že vám celou šifru popíši. První kousek textu, který chceme zašifrovat, zpracujeme stejně jako to dělal Kryštof Columbus a pro zbytek zprávy použijeme jako tajné heslo celou zprávu od začátku - tedy bez malého kousku na konci. Ale aby to nebylo příliš jednoduché, použili francouzští revolucionáři víceslovné heslo.
Avmxam! Ni kafkv grbmmcct zudlp iiis rixx dbea q Cuoejdeim. Oucvl pdxpxnzfhl, kikftjte iizcqi ewk xgpr gqezx.
Dešifrujte.
Dnes jste se dozvěděli, jak je snadné hledat kolize hashovacích funkcí, a proto jsme si pro vás, kteří jste postoupili do posledního - finálního - kola, připravili hledání jedné takové kolize. Vaším úkolem bude zmařit francouzskou revoluci. V předposledním kole naší soutěže jsme vyluštili zprávu, která stála u zrodu revoluce.
"Bratři! Do zámku přivezou zítra ráno sudy vína z Champagne. Buďte připraveni, revoluce nemůže již déle čekat."
Vítězem celé soutěže se stane ten, kdo revolucionářům podvrhne zprávu jiným obsahem, nebude to mít však lehké protože zpráva je chráněna hashí. Hash byla poslána poštovním holubem. Hash spočteme následovně: od každého písmene vynásobíme jeho četnost jeho pořadovým číslem v abecedě a všechny takto získané hodnoty sečteme.
Cílem je podvrhnout zadaný text. Nalezněte smysluplný text, který má stejnou hodnotu hash funkce jako zadaný text. Smysluplnost bude hodnocena subjektivně, kolize exaktně.
Hash spočteme následovně: od každého písmene vynásobíme jeho četnost jeho pořadovým číslem v abecedě a všechny takto získané hodnoty sečteme.
Bratri! Do zamku privezou zitra rano sudy vina z Champagne. Budte pripraveni, revoluce nemuze jiz dele cekat.
Nalezněte kolizi (soutěžilo se na čas).
První kolo úspěšně vyluštilo a odevzdalo 40 řešitelů mezi přítomnými posluchači. Jedná se o šifru, které se připisuje název "Caesarova". Caesar však použil jiný posuv než my. Text je v češtině bez diakritiky a posuv byl o jedno písmeno směrem zpět proti abecedě, takže při dešifrování stačí nahradit písmeno písmenem v abecedě následujícím (a->b, b->c, q->r, z->a, atd.). Nápovědou byl historický kontext i text s opakujícími se slovy a jednopísmennou spojkou.
Druhé kolo úspěšně vyluštilo 23 řešitelů (z toho 2, kteří se neúčastnili prvního kola). Jedná se o šifru složenou z několika posunutých abeced. Posuny abeced jsou popsány heslem "alea" - tedy IACTA ALEA EST - kostky jsou vrženy. Toto heslo bylo úmyslně zvoleno, protože obsahuje dvě ačka, která abecedu neposouvají a tak zbylo v textu hodně informace pro bystrého pozorovatele. Velkou nápovědou mohly být i spojky a slovo "Indie".
Třetí kolo bylo velmi těžké. Celé ho nikdo nevyluštil během zhruba dvou hodin. Na dotaz má-li někdo částečné řešení se přihlásil však jeden posluchač, který měl několik slov ze začátku. Vzhledem k tomu, jak je šifra stavěná - bylo dešifrování celého textu jen otázkou několika minut a řešení bylo uznáno.
Mezi zbylými nejvíce ohodnocenými posluchači (t.j. měli řešení prvního a druhého kola) bylo vedeno finální soutěžní kolo o druhé a třetí místo - hledání kolize jednoduché hash funkce k zadanému textu. Hash funkce byla zadaná vzorcem pro výpočet. Z něj vyplývalo několik vlastností, které umožňují snadno hledat kolize: 1, promíchání znaků (i větších celků jako jsou slova) nemění hash. 2, část textu lze nahradit jiným textem se stejnou částečnou hashí. Přirozeně taková hash funkce z hlediska kryptografie je naprosto nevhodná - z hlediska soutěže je přiměřená. Změna smyslu textu byla hodnocená subjektivně. Hledání dvou řešení zabralo asi dvacítce řešitelů kolem 15 minut. Poměr mezi pokusy o odevzdání textu se správnou kolizí vs. nekolizních textů byl asi 1:10.
"Bratri! Do zamku privezou jiz zitra rano sudy vin z Champagne. Budte pripraveni, pitka nemuze dele jiz cekat." (2. místo)
"Drazi bratri, na zamku budu zitra cekat az privezou sudy vina z Champagne. Nebudte dele strizlivi. Noc je dlouha. F." (3. místo)
"Bratri! Revoluce muze cekat do zitra na rano. Budte zde, ne u zamku. V Champagne pripraveni jiz i s dely, privezou." (nadbytečné řešení od řešitele s již uznaným prvním místem)
Soutěž vnesla do přednášek trochu živé soutěživosti a umožnila momentálně nudícím se posluchačům, aby se zabavili, nenudili a nerušili - a tím splnila svůj účel. Výhercům blahopřejeme. A se všemi se těšíme na setkání u dalších akcí Studentské unie.
