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