Po drátě 6: Řešení úlohy č. 9

Ejhle, QR kód. Pokud zkusíte na monitor namířit mobil s dekodérem, nejspíš neuspějete. Ale pokud nějaký dekodér (třeba Zxing Online) nakrmíte přímo obrázkem, hned se dozvíte, že kód obsahuje URL http://en.wikipedia.org/w/index.php?title=QR_code. Nic moc, že je to QR kód, to už jsme věděli.

Kde tedy bude schované heslo? Nejspíš jsou v kódu ještě nějaká další data. Tak zkusíme URL zpětně zakódovat a porovnat se zadáním:

No tedy, to vypadá úplně jinak! Po chvíli ale zjistíme, že enkodér má několik zajímavých parametrů, konkrétně verzi kódu (ta udává jeho velikost, a tedy i kapacitu) a úroveň ochrany proti chybám. Chvíle experimentování odhalí, že velikost zadání odpovídá verzi 10. Když jsme si navíc mohli dovolit přes kód jen tak plácnout logo hry, bude nejspíš odolnost proti chybám nastavená dost vysoko, tak zkusme maximální možnou. Vyjde následující kód, od zadání ovšem stále dost odlišný. Tak zkusme zjistit, kde se všude liší – pravý obrázek ukazuje XOR se zadáním:

XOR vypadá zvláštně. Pravidelný vzorek a v něm dvě oblasti podoby rozsypaného čaje. Ta dolní je jasná, tam bylo nakresleno logo hry. Ale co ta horní? Zkusme doplnit pravidelný vzorek i do těchto částí a podívat se, v čem se liší:

Heslo je na světě, ale uznejte, že metodou jaksi haluznou. Speciálně hádání stupně zabezpečení a doplňování jakéhosi pravidelného vzorku, aniž bychom věděli, kde se vzal, má k elegantnímu řešení dost daleko.

Začteme se proto do specifikace a zkusíme přijít na kloub tomu, jak QR kódy fungují. Nejprve si označme různé speciální oblasti:

Žlutě jsme vyznačili hlavní zaměřovací značky (podle těch se pozná, kde kód leží a jak je natočený), oranžově vedlejší zaměřovací značky (ke korekci zkosení), růžově synchronizační značky určující velikost bitů v obou směrech. Modré části popisují verzi kódu (opravdu je to verze 10), červené jeho formát (úroveň zabezpečení maximální a masku č. 1).

Vida, masku... to v parametrech enkodéru (aspoň toho našeho) jaksi chybělo. Během kódování se totiž celý obrázek vyxoruje jedním z osmi definovaných maskovacích vzorků, přičemž se zvolí taková maska, aby výsledný kód nebyl ani moc černý, ani moc bílý a aby se v něm nacházelo co nejméně artefaktů, které by mohly komplikovat dekódování (například tím, že by vypadaly jako některá ze zaměřovacích značek).

A právě to, že náš kód používal úplně jinou masku než ten, který vypadl z obvyklého enkodéru, způsobilo, že jejich rozdíl byl téměř všude nějaký pravidelný vzorek. Mimochodem, maska, kterou jsme vybrali, dostala podle standardního hodnotícího algoritmu jen o maličko víc trestných bodů než ta nejlepší. Vypadá takto:

Zde bychom se mohli zastavit a úlohu vyřešit drobnou úpravou enkodéru a vyxorováním jeho výstupu se zadáním. Ale jsouce zvědaví, nahlédneme do tajů konstrukce QR kódů ještě trochu hlouběji. Kód odmaskujeme a prohlédneme si ho podrobněji:

Obrázek je složený z 57×57 = 3249 modulů (tak se v hantýrce okolo kódů říká jednotlivým elementárním čtverečkům). Z toho 414 zabírají zaměřovací a synchronizační značky, 67 popisuje verzi a formát a zbylých 2768 obsahuje data rozdělená do 346 bloků po 8 bitech (vyznačeny zeleně).

Bloky se hledají takto: začneme v pravém dolním rohu a chodíme po sloupečcích širokých 2 moduly střídavě nahoru a dolů (sloupce bereme zprava doleva). Na každém řádku nejdříve použijeme pravý modul a pak ten levý. Blok začína nejvyšším bitem a končí nejnižším. Moduly, které už jsme použili pro synchronizaci apod., přeskakujeme. První blok tedy obsahuje hodnotu 01000000, druhý 10110110, poslední 11101101.

Bloky se nicméně nečtou v tomto pořadí. Data jsou v kódu verze 10 rozdělena na 8 částí a každá z nich je zvlášť ochráněna proti chybám. Prvních 6 částí se skládá z 43 bloků (z toho 15 datových a 28 ochranných), zbylé 2 části z 44 bloků (16 datových, 28 ochranných). V obou případech se proti chybám chráníme Reedovým-Solomonovým samoopravným kódem s kódovou vzdáleností 28, který dokáže v každé části opravit až 14 chyb. Tak to pojďme udělat:

Modře jsou vyznačena místa, kde nastaly chyby (celkem v 87 blocích, což je dost blízko hranice možností použitého opravného kódu, proto také nefungovaly čtečky v mobilech – po přidání nepřesností vzniklých při sejmutí z obrazovky bylo chyb už příliš).

Nakonec najdeme jednotlivé části dat:

Části jsou uloženy na střídačku, vždy jeden blok z každé části. Datové bloky první části jsou označeny zeleně (obsahují byty 40 03 16 87 47 47 03 a2 f2 f6 56 e2 e7 75 96 hexadecimálně), ochranné bloky fialově. Datové bloky druhé části azurově (data: b6 97 06 56 46 96 12 e6 f6 26 72 f7 72 f6 96). Ostatních 6 částí jistě najdete sami.

Zbývá tedy části pospojovat za sebe a zjistit, co v nich je napsáno. První 4 bity určují způsob uložení znaků (čtyřka značí "8 bitů na znak", jiné možnosti by byly třeba kompaktní kódování anglické abecedy, čísel nebo japonštiny), ve verzi 10 dalších 16 bitů (0031) udává počet znaků. Pak už následují jednotlivé znaky: 68 74 74 70 3a 2f 2f 65 6e 2e 77 59 6b 69 70 65 64 69 61 2e 6f 62 67 2f 77 2f 69 atd., tedy přesně text URL z Wikipedie.

Poznámky

Úloha se nechtěně stala připomínkou toho, že Wikipedii není radno brát příliš vážně. Až při kreslení obrázků ke vzorovému řešení jsme zjistili, že některé ukázky struktury kódu v článku o QR kódech odpovídají zastaralé podobě "model 1", kterou takřka nemáte šanci potkat ve světě a tím méně v této úloze.

Setkání s normami vydávanými ISO je pro člověka zvyklého na internetové standardy značný kulturní šok. Ať už v preciznosti formulací nebo v dostupnosti. Velebena buď IETF.

Autorem úlohy je Medvěd, který konečně našel záminku k důkladnému průzkumu fungování dvojrozměrných kódů.