A részeg futó
Hogyan lesz egy ujjlenyomatból ASCII rajz?
A szokásostól eltérően most egész aktuálisak leszünk, ha nem is a bejegyzés témájával, de legalább a kiváltó okával. 2026 októberében kiderült, hogy az eMudhra tanúsítvány szolgáltató olyan felettébb biztonságos privát kulcsokat használt, mint például 4.
Ennek kapcsán futottam bele az alábbi remek illusztrációba:
The key's randomart image is:
+---[RSA 2048]----+
| |
| |
| |
| |
| 4 |
| |
| |
| |
| |
+----[SHA256]-----+
Ha a viccet félretesszük, a kép nyilván távol áll a valóságtól, mivel ezek eredetileg nem a privát kulcsból számolódnak, hanem a publikus kulcs (SHA256) ujjlenyomatából/hash-éből. De ez elég volt ahhoz, hogy elgondolkodjak azon, hogy akkor vajon hogyan is működnek.
Nézzünk meg néhány igazi példát, hátha jutunk velük valamire:
+--[ED25519 256]--+ +--[ED25519 256]--+ +--[ED25519 256]--+
| | |o ..E. .o.. | |B=o+++o |
| . | |.. = . ..... | |Bo+.+ +.. |
| . o . | |. . = ..+.. | |*@ o o +.. |
|...+ + + | |. . =+o.o | |@.o . ..o. |
|.=.o+.. S o | | . ..+S.. | |= + . S. |
|* * .o . | |... + .+ o o | |== .E |
|=.o* .ooo o | |.+. =. o o = . | |B... |
|.=ooEo.+=* o | |ooo . o = + | |+o+ |
|+..o.o====* | |o=.... Oo | |o=. |
+----[SHA256]-----+ +----[SHA256]-----+ +----[SHA256]-----+
A mérete 17*9 karakter, tehát 153 karakterből áll összesen. A kép jó része üres marad, a maradék pedig ránézésre egy fix karakterkészletből dolgozik. Ami még feltűnhet ezen felül, hogy a kép közepén fixen egy S betű van és van a képen még egy E betű is. Nagyjából eddig jutottam a dologgal, aztán meguntam a gondolkodást és inkább utánanéztem, hogy ténylegesen hogyan is működik.
Az algoritmust Részeg Futóként (Drunken Bishop) emlegetik, mivel a kurzorunk középről indulva a bejövő adat alapján átlósan mozog valamilyen irányokba. Mozgás közben azt is feljegyzi, hogy melyik cellában hányszor járt.
Az egyszerűség kedvéért nézzünk meg egy példát, ami rövidebb, mint egy SHA256 hash:
Hello.
Ha vesszük a karakterek értékeit, a következő hexadecimális számokat kapjuk:
48 65 6c 6c 6f 2e
Amik kettes számrendszerben a következőképpen néznek ki:
01001000 01100101 01101100 01101100 01101111 00101110
A bináris számokat két bitenként csoportosítjuk:
01 00 10 00
01 10 01 01
01 10 11 00
01 10 11 00
01 10 11 11
00 10 11 10
Két bitnyi adat négy értéket vehet fel, amihez rendelhetünk négy irányt:
00 |
↖ |
01 |
↗ |
10 |
↙ |
11 |
↘ |
Ez a következő mozdulatsort eredményezi:
↗ ↖ ↙ ↖
↗ ↙ ↗ ↗
↗ ↙ ↘ ↖
↗ ↙ ↘ ↖
↗ ↙ ↘ ↘
↖ ↙ ↘ ↙
A bájtokat egymás után, fentről lefelé haladva dolgozzuk fel, de egy bájton belül a kis helyi érték felől haladunk a nagy helyi érték felé (tehát jobbról balra). Így a következő a végrehajtási sorrend:
↖ ↙ ↖ ↗ ↗ ↗ ↙ ↗ ↖ ↘ ↙ ↗ ↖ ↘ ↙ ↗ ↘ ↘ ↙ ↗ ↙ ↘ ↙ ↖
Középről indulva szépen eltáncolhatjuk ezt a koreográfiát. Ha falhoz érünk, akkor az átlós mozgás azon részét valósítjuk csak meg, amelyiket tudjuk, a dobozt nem hagyhatjuk el. Sarokban előfordulhat, hogy egy helyben maradunk, de a cella értékét növeljük. Végül, ha jól számoltam, az alábbi mintát kapjuk:
+-----------------+
| 22 |
| 24 |
| 12 1 |
| 1 1 2 |
| 1 12 |
| 1 1 |
| 1 |
| |
| |
+-----------------+
A számok azt jelölik, hogy hányszor jártunk az adott cellában (az üres cellákban nem jártunk), ezeket még le kell cserélnünk az algoritmus által használt .o+=*BOX@%&#/^ karakterkészletre. Ezen felül az S jelöli a kiindulási pontunkat, az E pedig az a pont, ahova érkeztünk. Az S nem változik meg, ha áthaladunk rajta, de E lesz belőle, ha ott fejezzük be a táncot.
+-----------------+
| oo |
| o= |
| .o . |
| . . o |
| . So |
| E . |
| . |
| |
| |
+-----------------+
És... tulajdonképpen ennyi. A SHA256 hash egy kicsit hosszabb (32 bájt), mint a mi kiinduló adatunk (6 bájt), így valamivel érdekesebb képeket tud eredményezni, de az alapelv ugyanez. Az SSH által használt implementáció megtekinthető itt.