Bitturmixolás: véletlenszámok, titkosítás és hash függvények

Tudjuk, hogy a számítógép a programokban adott műveleteket determinisztikusan végzi el. Azaz ugyanazoknál a bemenő adatoknál ugyanaz a program ugyanazt a kimenő adatot állítja elő. Kérdés az, hogy akkor hogyan tudunk véletlenszámokat gyártani? Mert ilyesmire rendszeresen szükségünk van. Például ha kártyajátékot írunk, a programnak tudnia kell véletlenszerű leosztásokat kitalálni.

Erre két lehetőségünk van. Az egyik út az, hogy valamilyen fizikai folyamat alapján állítjuk elő ezeket. Mondjuk az elektronok véletlenszerű, ide-oda mozgása okozta zajt érzékeljük. (Ilyen zajt hallhatunk, ha a rádiót két csatorna közé állítjuk, ahol nincs semmilyen adó.) Ehhez azonban célhardver szükséges. (A mai számítógépek tartalmaznak hasonlót.) Azt is csinálhatjuk, hogy megkérjük a felhasználót, hogy gépeljen be egy mondatot – és közben nem a beírt betűket figyeljük, hanem a billentyűlenyomások között eltelt időt. Az is elég véletlenszerű, csak hát nem állíthatjuk meg mindig a programot, ha épp véletlenszámokra van szükségünk.

A másik út, hogy imitáljuk a véletlenszámokat. Fogunk egy kiindulási számértéket, osztjuk, szorozzuk, hozzáadunk valamennyit, megcseréljük néhány bitjét, invertáljuk másikakat – az így kapott számot pedig kikiáltjuk véletlenszerűnek. Bár biztosan nem az, ha ügyesek vagyunk, mégis úgy tűnhet, hogy az. Ezek az álvéletlenszámok, vagy más néven pszeudo-véletlenszámok. Ha elindulunk ezen a gondolatmeneten, kiderül, hogy az ilyen bitmágiából érdekes és hasznos dolgokat lehet kihozni.

1 Egy egyszerű véletlenszám-generátor

A Microsoft C függvénykönyvtára is tartalmazza a szabványos rand() függvényt, amely ehhez hasonlóan működik:

#include <stdio.h>

int main() {
	unsigned long allapot, szam;
	int x;
    
	allapot=1;               /* kiindulás */
	for (x=0; x<10; x+=1) {  /* 10 véletlenszám generálása */
		allapot = allapot * 214013 + 2531011;
		szam = (allapot >> 16) & 32767;
		printf("%d\n", szam);
	}
	
	return 0;
}

Mit csinál ez? Fog egy allapot nevű változót, amelyet az 1-es kezdeti értékről indít. Megszorozza egy számmal, hozzáad egy másikat – ez lesz az allapot következő értéke. Ezután kivágja ennek a változónak a 31-16. bitjeit, és az így kapott számot nevezi véletlenszámnak. A számítás részletei nem is lényegesek annyira, de egy biztos: ez minden, csak nem véletlenszám. Ha elindítjuk a programot, a kiírt számok mégis eléggé annak tűnnek. Többször indítva viszont azt látjuk, hogy mindig ugyanazt a számsort kapjuk. Ezen is segíthetünk, úgy, hogy az allapot változó tartalmát, az ún. magot (seed) más értékről indítjuk.

A reprodukálhatóság hasznos tulajdonság tud lenni! Kisorsolhatjuk ugyanazt a kártyaleosztást vagy ugyanazokat a kockadobásokat. Ha egy számítógépes hálózat forgalmát szimuláljuk programunkban, akkor elő tudjuk állítani ugyanazt a forgalomeloszlást. Ha a játékunkban véletlenszerű események történnek, akkor is tudunk könnyedén visszajátszást mutatni a játékosnak arról, hogyan teljesítette a pályát: ehhez elég rögzíteni a lépéseit, a véletlenszerű időpontokban bekövetkezett eseményeket pedig újra kisorsoljuk ugyanattól a számtól indítva a generátort.

Az ilyen, szorzunk-hozzáadunk elven működő véletlenszám-generátorokat lineáris kongruencia generátornak nevezzük a maradékos osztás miatt, ami itt túlcsordulásba van elrejtve. A kódban szereplő konstansok megválasztásának számelméleti alapjai vannak: a hozzáadott szám és a moduló osztója legyen relatív prím stb.

2 Titkosítás az XOR függvénnyel

A BA^B
0 00
0 11
1 01
1 10

Ha van egy csomó véletlenszerű bitünk, akkor könnyű egy adattitkosító algoritmust csinálni. Az XOR (kizáró VAGY) függvény egy érdekes tulajdonsággal rendelkezik, amit ehhez felhasználhatunk: ugyanis ez a függvény önmaga inverze. Ha egy tetszőleges A számot bármilyen B számmal kizáró VAGY kapcsolatba hozunk kétszer egymás után, akkor visszakapjuk A-t. Ez azért van, mert az XOR függvény az adott biteket invertálja, és a kétszeri invertálás visszaadja az eredetit. Ezt könnyű bizonyítani is:

A^B^B=A^(B^B)=A^0=A

A titkosítás egyszerű: a titkosítandó szövegben véletlenszerűen invertáljuk a biteket. Fogjuk az üzenetünket, és elkezdünk mellé véletlenszámokat generálni. Az üzenet n-edik bitjét XOR kapcsolatba hozzuk a véletlen bitsorozat n-edik bitjével: így kapjuk a titkosított adatfolyamot. A visszaalakítás ugyanígy történik. A titkosított üzenet n-edik bitjét XOR-oljuk ugyanazon véletlen bitsorozat n-edik bitjével, visszaforgatva az invertált biteket eredeti állapotukba.

A titkosításnak – nagy örömünkre – kulcsa is van, a véletlenszám generátor kiindulási értéke. Ha nem ismerjük a kulcsot, akkor nem leszünk képesek ugyanazt a bitsorozatot előállítani, és ezért a titkosított üzenetet visszafejteni sem, mert nem tudjuk, melyik biteket kell invertálni. Mivel a véletlen bitsorozatban elvileg 50% a valószínűsége mind a 0-k, mind az 1-ek megjelenésének, a titkosított bitsorozatra ugyanez lesz igaz, és egyáltalán nem fog rajta látszani az eredeti bemenetből semmi.

Ezt az algoritmust az alábbi programmal lehet megvalósítani C-ben, az egyszerűség kedvéért a beépített rand() függvényt használva:

#include <stdio.h>
#include <stdlib.h>

int main() {
    char uzenet[]="Hello, vilag!";
    int hossz, i;

    /* szöveg: 0-val lezárt karaktertömb */
    hossz = 0;
    while (uzenet[hossz]!='\0')
		hossz += 1;

    /* eredeti üzenet */
    for (i=0; i<hossz; i++)
        printf("%c", uzenet[i]);
    printf("\n");

    /* titkosított üzenet */
    srand(12345);                           /* ez a kulcs */
    for (i=0; i<hossz; i++)
        uzenet[i] ^= rand() & 0xff;         /* 8 random bit */
    for (i=0; i<hossz; i++)
        printf("%c", uzenet[i]);
    printf("\n");

    /* újra az eredeti */
    srand(12345);                           /* ugyanaz a kiindulás megint */
    for (i=0; i<hossz; i++)
        uzenet[i] ^= rand() & 0xff;         /* 8 random bit */
    for (i=0; i<hossz; i++)
        printf("%c", uzenet[i]);
    printf("\n");

    return 0;
}

Fontos megjegyezni, hogy az egyes C implementációk között a rand() függvény működése eltérő lehet. A szabvány nem írja elő a beépített álvéletlenszám-generátor konkrét működését. Az egyes fordítók által használt rand() függvények legtöbbje egy lineáris kongruencia generátor, de más konstansokat használnak. Ezért ha egy konkrét géptípuson, bizonyos fordító által készített programmal kódolunk egy szöveget, másik gépen vagy másik fordítóval esetleg nem tudjuk dekódolni azt, mert az ottani rand() eltérő számokat generál. Ha szükségünk van pontosan ugyanarra a véletlen számsorra, jobban tesszük, ha beépítünk a programba egy saját generátort.

3 Egy profi véletlenszám-generátor: a Mersenne Twister

Egy profibb véletlenszám-generátor beépítésének további indítékai is lehetnek. Ugyanis az egyszerű generátorok bár gyorsak, rendelkeznek néhány nem kívánatos tulajdonsággal. Például ha szabályosság van a kimenetében, akkor a fenti módszerrel titkosított üzenetünkben is lesz szabályosság.

Az írás elején bemutatott algoritmus például a 30546-odik véletlenszámnak ugyanúgy a 41-et hozza ki, mint az elsőnek, és onnantól kezdve a sorozat ismétlődik. Ez nem csak azt jelenti, hogy a periódusa túl rövid: a szemfülesek észrevehetik, hogy a 30546 kevesebb, mint a 32767 (a legnagyobb szám, amit kisorsol). Szóval kell lennie olyan számnak a 0 és a 32767 között, amelyet ez a generátor soha nem állít elő! Sőt azt sem mondhatjuk, hogy egyenletes a generátor kimene. Ha az előállított számok legalsó bitjét használjuk „fej vagy írás” pénzfeldobásnak…

#include <stdio.h>
 
int main() {
    unsigned allapot, szam;
    int x, fej, iras;
    
    allapot=1;
    fej=0; iras=0;
    for (x=0; x<30545; x+=1) {
        allapot = allapot * 214013 + 2531011;
        szam = (allapot >> 16) & 32767;
        if ((szam & 1) == 0)    /* a legalsó bit */
            fej+=1;
        else
            iras+=1;
    }
    
    printf("%d fej, %d iras.\n", fej, iras); 
    
    return 0;
}

Az eredmény: 15188 fej, 15357 írás. Ez nem pénzfeldobás, hanem inkább egy vajaskenyér, ami szeret a vajas oldalára esni.

A lineáris kongruencia generátoroknál sokkal jobb eredményt érhetünk el pl. a Mersenne Twister nevű algoritmussal. Ez igen meggyőző tulajdonságokkal rendelkezik. A periódusa (vagyis ahány hívás után a függvény elkezdi ugyanazt a számsort adni) 219937-1. Ez egy 6000 számjegyből álló szám! Ha másodpercenként egymilliárd számot generálunk, akkor is 5985 évig tart, mire elölről kezdődik a számsor. Talán a világ összes számítógépén futó összes Mersenne Twister függvényét összesen nem hívták még meg ennyiszer 1997 óta, amikor kitalálták ezt az algoritmust.

A lenti C nyelvű kód ennek megvalósítása. A programban egy 624 elemű, 32 bites számokból álló tömb van, ez tárolja a generátor állapotát. Minden 624-edik véletlenszám kérés után megkeveri ezt a tömböt, egymással invertálva, léptetve, összeadva a benne lévő értékeket. Az előállított számok ebből a tömbből származnak, további léptetésekkel és invertálásokkal „utókezelve”.

#include <stdio.h>

int main() {
    unsigned long mt[624], y;
    unsigned index, i, j;

    mt[0]=0;              /* itt lehet állítani a kiindulási értéket */
    for (i=1; i<624; i+=1)
        mt[i]=0x6c078965 * (mt[i-1] ^ (mt[i-1] >> 30)) + i;

    index=0;
    for (j=0; j<10; j+=1) {
        /* 624 kérésenként egy új tömböt keverünk ki*/
        if (index == 0) {
            for (i=0; i<624; i+=1) {
                y=(mt[i] & (1 << 31)) | (mt[(i+1) % 624] & ~(1 << 31));
                mt[i]=mt[(i + 397) % 624] ^ (y >> 1);
                if ((y % 2) != 0)
                    mt[i]=mt[i] ^ 0x9908b0df;
            }
        }

        /* a tömbből kivett számokat még tovább kavarjuk */
        y=mt[index];
        y ^= (y >> 11);
        y ^= (y << 7) & 0x9d2c5680;
        y ^= (y << 15) & 0xefc60000;
        y ^= (y >> 18);
        index=(index + 1) % 624;

        /* az előállt véletlenszám, 0..(1<<32)-1 */
        printf("%x\n", y);
    }

    return 0;
}

Látható, hogy ez is egy álvéletlenszámokat generál csak. Nem csinál mást, csak turmixolja ide-oda a biteket: a cél csak annyi, hogy a kimenet minél véletlenszerűbbnek tűnjön. A műveletek persze úgy vannak megkonstruálva, hogy a szabályosság minél kisebb legyen. Az algoritmus több dimenzióban biztosítja a számok egyenletes eloszlását. Vagyis nem csak az egyes számok eloszlása egyenletes nagyjából, hanem ha az egymás melletti számokat (x;y) koordinátáknak használjuk a síkon, akkor az így kapott pontok is közel egyenletesen fedik le a négyzetet, ahova esnek. Sőt ha az egymás melletti számhármasokat (x;y;z) koordinátáknak használjuk, akkor a pontok a kocka alakú teret egyenletesen töltik ki, és így tovább, bizonyíthatóan legalább 624 dimenzióig.

4 A hash függvények

Ha egy, a fenti véletlenszám-generátorhoz hasonló algoritmust úgy módosítunk, hogy az egyes számok előállítása közben folyton újabb számokkal „zavarjuk fel benne a vizet”, akkor egy ún. hash függvényt kapunk.

A Wikipedia a következőket írja a hash függvényekről. A kriptográfiában (titkosításban) használt hash függvények bemenetét általában üzenetnek (message), a kimenetét pedig kivonatnak (digest) nevezzük. Az üzenet tetszőleges hosszúságú adat lehet, a kivonat viszont egy fix hosszúságú bitsorozat. És itt jön a lényeg: a függvény biztosítja azt, hogy az üzenet megváltoztatása nagyon nagy valószínűséggel megváltoztatja a kivonatot is.

Egy ideális hash függvény az alábbi tulajdonságokkal rendelkezik:

A „nagyon nehéz” azt jelenti, hogy beláthatatlanul sok időbe, például évtizedekbe vagy évszázadokba telik elvégezni a feladatot még akkor is, ha száz vagy ezer számítógépet ráállítunk a feladatra.

5 Egy konkrét hash függvény: az SHA-1

Egy ismert hash függvény, az SHA-1 sémája látható a lenti ábrán. Itt a <<< körbeforduló bitenkénti eltolást jelent (vagyis azt, hogy az egyik oldalon kitolt bitek a másik oldalon bejönnek), Wt az üzenet bitjeit, Kt a konstansokat, a piros + a 32 biten túlcsorduló összeadást, az F függvény pedig egy olyan bitművelet-sorozatot, amely minden huszadik lépés után változik. Az algoritmus egy körben a bemenetből 512 bitet dolgoz fel, ezért a bemenet bitjeinek száma 512-vel osztható kell legyen. Ha ennél rövidebb, akkor nullákkal töltik fel a művelet előtt, és a végére az üzenet hosszát is hozzáveszik (hogy a csupa nullákból álló, de különböző hosszúságú üzenetek kellően különbözzenek egymástól). Egy kör legbelső ciklusa valahogy így néz ki:

for (i=0; i<80; i+=1) {
    if (0<=i && i<=19) {
        F=(B & C) ^ (~B & D);
        K=0x5A827999;
    } else if (20<=i && i<=39) {
        F=B ^ C ^ D;
        K=0x6ED9EBA1;
    } else if (40<=i && i<=59) {
        F=(B & C) ^ (B & D) ^ (C & D);
        K=0x8F1BBCDC;
    } else if (60<=i && i<=79) {
        F=B ^ C ^ D;
        K=0xCA62C1D6;
    }

    temp=E + F + forgat(A, 5) + W[i] + K;
    E=D;
    D=C;
    C=forgat(B, 30);
    B=A;
    A=temp;
}

Ez hasonló az előző algoritmushoz: a felismerhetetlenségig kavarja a bemeneti biteket és a beépített konstansokat. A hash függvényeknél ezeket a konstansokat egészen máshogy határozzák meg, mint a véletlenszám-generátoroknál. Mivel ezekkel digitális aláírásokat gyártanak, és jelszavakat tárolnak segítségükkel, fontos az, hogy biztosan ne legyen a konstansokban semmi elrejtve. Az algoritmusok megtervezői ezt úgy szokták biztosítani, hogy ún. „nothing up my sleeve”, azaz „semmi sincs az ingujjamban” számokat választanak. Például a π 2-es számrendszerbeli ábrázolásának első 128 bitjét, hiszen az tőlük biztosan független, nem ők találták ki. Az SHA-1 fent látható négy konstansa a 2, 3, 5 és 10 számok négyzetgyökeiből keletkezett.

A körforgó léptetésre a processzoroknak szokott lenni beépített utasítása, de a C-nek nincs beépített operátora erre a feladatra. Meg lehet írni viszont egy ilyet két szokásos léptetés segítségével is, amelyeknél nullák jönnek be. 32 bites számok esetén:

szám 01001011001010101011111010101011
szám<<501100101010101111101010101100000
szám>>2700000000000000000000000000001001
szám<<<5 = szám<<5|szám>>2701100101010101111101010101101001

Vagyis a körforgó balra léptetésre az alábbi C függvényt írhatjuk, feltételezve, hogy a gépünk unsigned long-ja 32 bites:

unsigned long forgat(unsigned long mit, int hanyszor) {
    return (mit << hanyszor) | (mit >> (32-hanyszor));
}

Az ilyesmit a legtöbb fordító felismeri, és a megfelelő gépi utasítást építi be helyette a lefordított kódba.

6 A kivonatok használata

Az alábbi táblázat néhány rövid szöveget, és azoknak SHA-1 kivonatát tartalmazza. A kivonat az SHA-1-nél 160 bites, amely itt 16-os számrendszerben látható. Ez éppen 160/4=40 hexadecimális számjegyet jelent. Látszik, hogy mind a négy üzenetnek nagyon különbözik a kivonata. Azoké is, amelyek maguk is nagyon különböznek, hosszban és tartalomban is, mint a „hello, vilag!” a „jelszo001”-től. De azoké is, amelyek csak egyetlen bitben, h→H és 0→1. (A h és a H betű karakterkódja csak az 5. biten, a 0 és az 1 karakterkódja pedig csak a 0. biten tér el egymástól.)

jelszóSHA1(jelszó)
hello, vilag!edbc24d3b390abf5f20906eee6470d83dc418358
Hello, vilag!1f65e8de587614d1ef97c09d0f0115aa15ee4292
jelszo0000b8e9981cd6b5c0ae7b080a7eda84020914ca624
jelszo001565610aeb0a3eef8481ac8d718cfd5637a642b70

Amikor jelszavakat tárolunk, az „üzenet” a jelszó maga, a felhasználók adatait tároló adatbázisban nem ez, hanem csak ezek kivonata szerepel. A hash függvények fentebb említett tulajdonságai adják a lehetőséget a biztonságos tárolásra:

Ezért van az, hogy „rendes helyeken” nem tudják megmondani a jelszót, ha a felhasználó elfelejtette azt. Legfeljebb egy másikat tudnak beállítani. Az InfoC admin portál például egy ilyen rendes hely, a jelszavakat mi is hashelve tároljuk.

Egy jó hash függvény használható ellenőrzőösszegek előállítására is. Ha egy hosszú üzenetet (pl. fél megabájtot) etetünk meg a függvénnyel, kidob egy viszonylag rövid számsort, amelyet küldésnél az üzenet mellé tehetünk. Ez olyan, mint egy ujjlenyomat: bár vannak olyan üzenetek (fájlok), amelyek kivonata egyforma, nagyon nehéz ilyeneket találni. Ha a címzett előállítja a fogadott üzenet kivonatát, ellenőrizheti az üzenet integritását. Ha a két kivonat egyezik, az üzenet szinte biztosan ép.

A digitális aláírásként történő használat egyszerűsített gondolatmenete a következő. Van egy üzenet, amit a megalkotója alá szeretne írni. Kitalál ehhez egy jeligét, hozzácsapja az üzenethez, és a kettőt együtt adja a hash függvénynek. Ezáltal keletkezik egy kivonat, amely a bizonyíték. Ha bárki azt kéri tőle, hogy igazolja, tényleg ő írta az üzenetet, nincs más dolga, mint elárulni a jeligét. Az ellenőrzéshez fogni kell az üzenetet, hozzátenni a jeligét, és újra meghatározni a kivonatot. Ha az üzenet tartalma nem változott, és a jelige is helyes, ugyanazt a kivonatot kell kapni. Így nem csak az aláíró személye ellenőrizhető, hanem az üzenet tartalma is: hogy tényleg pontosan az volt-e az üzenet, amit ő aláírt.

7 Jelszavak feltörése és a hash függvények bukása

Bár egy ismert kivonathoz „nagyon nehéz” üzenetet találni, ez nem jelenti azt, hogy lehetetlen, csak azt, hogy belátható időn belül nem lehetséges. A mai számítógépek elég gyorsak már ahhoz, hogy a néhány karakterből álló jelszavakat kitalálják. Egyszerűen próbálgatással: indulunk a rövid szavaktól a hosszabbak felé, és kipróbáljuk az összes betűkombinációt. Ha csak az angol ábécé kisbetűit használjuk, és pontosan hat betűs jelszavakat feltételezünk, nincs is olyan sok lehetőség: 266 = 308 millió jelszót kell végigpróbálni. Pár perc.

Ezért szörnyen nagy hülyeség az, hogy „komoly helyek” azt várják a felhasználóktól, hogy tegyen írásjeleket is a jelszavába. 6 karakter, kisbetű, nagybetű és számjegyek: ez 62-féle írásjel, vagyis 626 = 56 milliárd kombináció. Ha az előbbi egy percig tartott, akkor ez 180 percig fog tartani. Három óra. Kivárható. Viszont ha mondjuk négy darab ötbetűs szót választunk, csak kisbetűket használva, az

2620 = 19928148895209409152340197376 = 1,9×1028

lehetőség. Erről meg is emlékezett az xkcd, de hiába, valószínűleg még éveket kell várnunk, mire nem megjegyezhetetlen, hanem erős jelszót fog várni tőlünk a netbankunk.

A legtöbb hash függvénynek egyébként idővel az a sorsa, hogy találnak a kimenetében valami szabályosságot. Ilyenkor annak használata már nem ad elfogadható biztonságot, mert ez azt jelenti, hogy a lehetőségek végigpróbálása nélkül, vagy inkább: jóval kevesebb lehetőség végigpróbálásával válik lehetségessé egy adott kivonathoz tartozó üzenetet kitalálni.

Így jártak a manapság már nem nagyon használt MD4 és MD5 függvények is. Ezek kimenetében lévő szabályosságok miatt már olyan algoritmust is találtak, amely néhány másodperc alatt képes ütközéseket (azaz két különböző üzenetet ugyanazzal a kivonattal) találni. Az SHA-1-nél is találtak már hasonlókat, de itt jobb a helyzet – még ha ismerjük is a kivonatot, egyelőre nagyon sok időbe telik egy hozzá tartozó üzenetet találni.