## 2. Kryptografia

### 2.1. RSA

Nech p a q sú veľké prvočísla, napr. 100-ciferné (získame ich tak, že budeme náhodne generovať 100-ciferné čísla dovtedy, kým neprejdu Miller-Rabinovým testom. Pravdepodobnosť, že náhodné číslo p je prvočíslom je daná približne vzťahom 1 / ln(p), takže viac ako 100 pokusov by sme potrebovať nemali, ak z testu vynecháme párne čísla). Ďalej nech N=pq a d,e sú také, že: de mod (p-1)(q-1) = 1 (d,e získame pomocou rozšíreného Euklidovho algoritmu: e zvolíme nesúdeliteľné s (p-1)(q-1) a d vypočítame z de+k(p-1)(q-1)=1 ako Bezoutov element). Potom sa dá za pomoci Malej Fermatovej vety ukázať, že
Vzťah (2.1) predstavuje šifrovanie správy x a vzťah (2.2) jej dešifrovanie. Čísla (N,e) sa nazývajú verejným kľúčom a (N,d) privátnym. Ak teda chceme zašifrovať správu systémom RSA rozdelíme si ju na rovnaké úseky nie dlhšie ako je bitová dĺžka N, tj. v prípade 100-ciferných prvočísel cca 640 bitov. Tieto 80 bajtové úseky zašifrujeme verejným kľúčom prijímateľa správy (vzorec 2.1), použijeme pri tom algoritmus na umocňovanie v module N. A rovnakým spôsobom (teraz podľa vzorca 2.2) ich môže príjemca dešifrovať svojim privátnym kľúčom.

Ak poznáme čísla N a e, môžme získať privátny kľúč d ? Bez rozkladu čísla N na prvočísla sa nám to nepodarí. Šifra RSA je preto taká silná ako je obtiažne rozložiť číslo zložené z veľkých prvočísel.

Uplatnenie RSA nieje len šifrovanie správ, ale aj tzv. elektronický podpis: ak správu zakódujeme našim privátnym kľúčom, odšifrovať ju síce môže ktokoľvek (našim verejným kľúčom), ale má istotu, že správa pochádza práve od nás, pretože nik iný nedokáže bez znalosti nášho privátneho kľúča správu zašifrovať (podpísať) tak, že po odkódovaní našim verejným kľúčom dá zmysel. Samozrejme v praxi sa kombinuje šifrovanie spolu s podpisom.

Vzhľadom na to, že umocňovanie v module je pomerne časovo náročné, obyčajne nepodpisujeme celú správu, ale len jej "odtlačok". RSA sa častokrát používa aj na bezpečné prenesenie symetrickej šifry, pomocou ktorej potom samotné kódovanie prebehne, je rýchlejšie.

Systém RSA je asymetrický, pretože na kódovanie používa iný kľúč ako na odkódovanie. Ak má n ľudí medzi sebou (každý s každým) bezpečne komunikovať v systémoch so symetrickou šifrou, potrebujú spolu n.(n-1)/2 rôznych šifier a tieto si medzi sebou "bezpečne" vymeniť. Najúžasnejšie na systéme RSA je, že tu na rozdiel od systémov so symetrickou šifrou stačí každému vygenerovať dva vyššie spomínané kľúče a jeden z nich zverejniť. Treba mať však istotu, že zverejnený kľúč naozaj pochádza od používeteľa s ktorým chceme komunikovať. To nám zabezpečí certifikačná autorita svojim podpisom tohto kľúča spolu s ďalšími identifikačnými údajmi.

### 2.2. Crc32

Chyby v prenose dát môžu v vznikať kdekoľvek (bezdrôtový prenos, zápis na disk a pod.). Preto je dobré si overiť, či takáto chyba nastala. Môžme to urobiť tak, že k dátam samotným pridáme tzv. kontrolný súčet, ktorý predstavuje matematický (prípadne výhradný) súčet všetkých bajtov popr. celých slov. A vždy, keď je predpoklad vzniku chýb, tento súčet overiť. Takáto kontrola je síce rýchla a výpočtovo nenáročná, má však výrazny nedostatok. Ak v dvoch bajtoch na rovnakej bit-ovej pozícii, vznikne chyba, tak celkový výhradný súčet zostane nezmenený a chyba neodhalená. Preto sa hľadal spôsob ako tento nedostatok odstrániť resp. minimalizovať. Jedným z riešení je tzv. CRC kód (cyclic redundancy check). Z matematického hľadiska sa jedná o delenie polynómov, pričom dáta sú delenec, konštantne zvolený polynóm deliteľ a zvyšok po delení je CRC kód, podiel samotný nás nezaujíma. Jednotlivé bity predstavujú koeficienty polynómov (počíta sa v module 2, kde namiesto matematického súčtu sa použije súčet výhradný). Pre dobrú detekciu chýb je kľúčová voľba deliteľa. Existuje mnoho polynómov v technických štandardoch, sú rôznej dľžky a určené pre rôzne aplikácie. V softvéroch sa však najčastejšie používa polynóm 32.rádu:
x32+ x26+x23+x22+x16+x12+ x11+x10+x 8+x 7+x 5+ x 4+x 2+x+1 známy ako CRC32.
Tu je implementácia tohto algoritmu v jayzku C :

    unsigned int crc32(FILE *f)
     {
       unsigned int crc = 0xffffffff;
       unsigned int POLY = 0xedb88320;  // 1110 1101 1011 1000 1000 0011 0010 0000 (1)
       char x; int k;

       while((x = fgetc(f))!=EOF)
        {
          crc ^= x;
          for(k=0; k<8; k++)
            if (crc&1) crc = POLY^(crc>>1);
                  else crc >>= 1;
        }

       return crc^0xffffffff;
     }

Tento 32-bitový CRC kód sa používa napr. v zip súboroch ako kontrola správnosti súborov po rozbalení alebo na pevných diskoch pre kontrolu správnosti načítania stopy (každá stopa je ukončená CRC kódom). Nakoľko CRC kód používa jednoduché logické operácie je možné ho i poľahky hardvérovo "nadrôtovať".

### 2.3. MD5 - "odtlačok prsta"

Na overenie bezchybnosti dát CRC kódy vcelku dobre poslúžia (je málo pravdepodobné, že chyba zmení dáta takým spôsobom, že výsledné CRC bude rovnaké ako má pôvodný nepoškodený súbor), ale z bezpečnostného hľadiska je nedostatočný. Dá sa pomerne ľahko nahradiť pôvodný súbor iným súborom s identickým CRC kódom. Preto bol zavedený 128-bitový MD5 kód, kde to v reálnom čase možné nieje. MD5 kód sa používa napr. na overenie stiahnutého súboru z internetu alebo na overovanie hesiel pri prihlásení. Tu je algoritmus MD5 v jazyku C od jeho autora Ronalda Rivesta ako aj podrobný popis tohto algoritmu.

### 2.4. Base64

Base64 nieje v pravom zmysle slova kryptovaním, ale slúži na prevod binárnych súborov (jpg, exe, zip a pod.) do textového tvaru, napr. za účelom prenosu takýchto súborov e-mailom. Nakoľko binárny súbor môže obsahovať celú množinu znakov (0-255, 8bitov) je potrebné túto zredukovať len na písmená (a-z, A-Z) a číslice (0-9). Malých písmen je rovnako ako veľkých (26) tj. spolu 52, s číslicami dohromady je to 62, táto množina je rozšírená ešte o znaky + a /, aby ich celkový počet bol celistvá mocnina čísla 2 (26 = 64). Kódovanie je v skutku jednoduché: vždy každú po sebe nasledujúcu trojicu bajtov (24 bitov) "postriháme" na štyri 6-bitové úseky, ktoré prevedieme na množinu vyššie spomenutých textových znakov.
Obrázok 2.1: presun bitov v systéme base64
Tým nám síce veľkosť súboru narastie o 33% (4/3 pôvodnej velkosti), ale môže byť zaslaný prostredníctvom e-mailu, ktorý podporuje len textové znaky. Na strane príjemcu je súbor prekódovaný z textového (base64) do pôvodného (binárneho) tvaru.
Funkcia v jazyku C na zokódovanie súboru do systému base64 môže vyzerať nasledovne:

    char znak[64] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

    void base64(FILE *out, FILE *in)
     {
       while(!feof(in))
        {
          unsigned char a = fgetc(in);
          unsigned char b = fgetc(in);
          unsigned char c = fgetc(in);

          int x1 =  (a & 0xfc) >> 2;
          int x2 = ((a & 0x03) << 4) | ((b & 0xf0) >> 4);
          int x3 = ((b & 0x0f) << 2) | ((c & 0xc0) >> 6);
          int x4 =  (c & 0x3f);

          fputc(znak[x1], out);
          fputc(znak[x2], out);
          fputc(znak[x3], out);
          fputc(znak[x4], out);
        }
     }

späť na obsah