- transfromujú vstup x na hash F(x)
- pre rôzné vstupy budu rôzné hashe: x' ≠ x => F(x)' ≠ F(x)
- JEDNOSMERNA FUNKCIA: je takmer nemožné k hashovacej hodnote vytvoriť pôvodný vstup;
- použitie napríklad v elektronickom podpise (sha1 + RSA)
- PODPISOVACIA POLITIKA: definuje aký hashovací algoritmus a šifrovací systém sa ma použiť
- Z podpisovaného dokumentu bude vypočitany hash (napríklad algoritmom sha1)
- Hash bude zašifrovaný privátnym kľúčom odosielateľa
- Výsledný dokumet je možné odoslať
- Vypočítame hash správy
- Rozšifrujeme prijatý hash verejným kľúčom odosielateľa
- Porovnáme hashe
Algoritmus RSA bol publikovaný v roku 1977 ako prvý algoritmus použiteľný na šifrovanie dát a zároveň aj na digitálny
podpis. Jeho názov sa skladá zo začiatočných písmen priezvisk jeho tvorcov – Rona Rivesta, Adiho Shamira a Leonarda Adlemana. Algoritmus je pri
použití dostatočne dlhých kľúčov považovaný za bezpečný aj v dnešnej dobe a nachádza využitie hlavne pri zaisťovaní bezpečnej komunikácie.
Aplikácia RSA algoritmu spočíva v troch krokoch:
- tvorba kľúča
- šifrovanie / podpis
- dešifrovanie / autentifikácia podpisu
RSA využíva dvojicu vzájomne previazaných kľúčov – verejný a privátny kľúč, ktoré sú z matematického hľadiska
zameniteľné. Pri mechanizme digitálneho podpisu sú zvolené dáta („hash“, „token“ a pod.) zašifrované pomocou utajeného privátneho kľúča prístupného
iba jeho majiteľovi. Ak sa dáta podarí správne rozšifrovať verejným kľúčom, je potvrdená identita majiteľa privátneho kľúča.
Dvojicu kľúčov je možné vytvoriť v piatich krokoch popísaných nasledovne:
- Generovanie dvoch dostatočne veľkých prvočísel p a q a čísla n = p.q
- Výber čísla e, ktoré nemá spoločných deliteľov s číslom (p-1).(q-1)
- Výber čísla d tak, že e.d = 1 mod [(p-1).(q-1)]
- Privátny kľúč tvorí dvojica čísiel (e, n) a verejný kľúč dvojica (d, n), kde e znamená „encryption“ (šifrovanie) a d „decryption“ (dešifrovanie). Takéto označenie kľúčov je platné pri použití algoritmu RSA na digitálny podpis. V prípade šifrovania za účelom utajenia informácií by bolo použité opačné označenie kľúčov.
- Zničenie čísiel p a q
Správnosť vytvoreného kľúča je možné overiť Euler-Fermatovou vetou, podľa ktorej:
„Ak x a n nemajú spoločných deliteľov, tak , kde φ(n) je počet čísiel menších ako n, ktoré nemajú s n spoločného deliteľa iného, než 1.
“V prípade RSA platí, že φ(n) = φ (p.q) = (p-1).(q-1). Výsledkom použitia Euler-Fermatovej vety na správne zvolené kľúče je výraz P e.d= P mod p = P mod q = P mod n dokazujúci funkčnosť kľúčov pri šifrovacom procese.
Šifrovanie pomocou RSA algoritmu je možné zapísať ako C = P e mod n.
P označuje nezašifrované údaje, resp. takzvaný „otvorený“ text. C sú výsledné zašifrované údaje, dvojica (e, n) tvorí použitý kľúč, v tomto prípade označovaný ako privátny.
Jedná sa o rovnakú matematickú operáciu ako pri šifrovaní, teda P = C d mod n.
C označuje zašifrované údaje, resp. takzvaný šifrovaný text. P sú výsledné dešifrované údaje, dvojica (d, n) tvorí použitý kľúč, v tomto prípade označovaný ako verejný.
Použitie RSA je pomalšie ako použitie symetrických šifier. Z tohto dôvodu sú pri aplikácii RSA na utajenie informácií šifrované dáta utajené pomocou niektorého menej náročného symetrického šifrovacieho algoritmu (DES a pod.). Iba použitý symetrický kľúč je zašifrovaný pomocou RSA a následne pripojený k správe.Pri systéme digitálneho podpisu však takéto riešenie stráca opodstatnenie, keďže vo väčšine implementácií je systémom RSA šifrovaná iba malá množina dát (napr. MD5 „hash“). Komunikácia zabezpečená RSA šifrou môže byť náchylná na útok typu „man in the middle“. Hrozí totižto podvrh zo strany útočníka vydávajúceho sa za legitímneho účastníka komunikácie, ktorý môže jednej strane podsunúť vlastný verejný kľúč. Otvára sa tak možnosť odchytiť komunikáciu, rozšifrovať ju privátnym kľúčom útočníka, zašifrovať verejným kľúčom pôvodného adresáta a preposlať ďalej. Takýto útok nemusí byť ani jednou stranou odhalený.
Algoritmus DSA (Digital Signature Algorithm) je štandardom
vlády Spojených štátov amerických pre digitálny podpis. Bol navrhnutý v roku 1991 a do aktuálnej podoby upravený v roku 2000 ako štandard FIPS
186-2.
Jednotlivé fázy použitia sú pri DSA nazývané:
- tvorba kľúča
- podpis
- verifikácia
Privátne a verejné šifrovacie kľúče sú pri DSA generované v dvoch stupňoch. Prvý stupeň slúži na výber tzv. „parametrov algoritmu“. Medzi tieto patrí kryptografická hashovacia funkcia H, dĺžka kľúča L, prvočísla p a q, premenná g.
Prvý stupeň pozostáva z týchto krokov:
- Výber kryptografickej hashovacej funkcie H. Tradične je používaná funkcia z rodiny SHA-1, ale je možné použiť aj silnejšie funkcie. V pripravovanej zmene DSA označovanej ako FIPS 186-3 sú používaní funkcie rodiny SHA-2.
- Voľba dĺžky kľúča L. Podľa FIPS 186-2 by algoritmus mal vždy používať kľúč s dĺžkou 1024 bitov. Neskôr bolo vydané odporúčanie používať kľúč s dĺžkou 2048 alebo 3072 bitov pre kľúče, ktoré majú zostať bezpečné aj po roku 2010. S dlhšími kľúčami počíta aj FIPS 186-3.
- Voľba prvočísla q, ktorého bitová dĺžka je rovná dĺžke výstupu funkcie H.
- Voľba prvočísla p s bitovou dĺžkou rovnou dĺžke kľúča L.
- Voľba g podľa predpisu g = h (p-1) / q mod p, kde h ∈ (1, p-1) je ľubovoľné číslo z daného intervalu, pričom g ≠ 1.
Trojica parametrov (p, q, g) nemusí byť pri každom vytvorenom kľúči počítaná nanovo, ale môže byť zdieľaná medzi viacerými jedinečnými kľúčmi.Nasleduje druhý stupeň, ktorý slúži na samotné generovanie dvojice previazaných kľúčov.
Pozostáva z týchto troch krokov:
- Výber náhodného alebo pseudonáhodného čísla x ∈ (0, q).
- Výpočet y = gx mod p.
- Vytvorenie dvojice kľúčov, pričom verejný kľúč tvorí štvorica (p, q, g, y) a privátny kľúč náhodné číslo x.
Pri podpisovaní správy m a použití hashovacej funkcie H je digitálny podpis algoritmom DSA vytvorený nasledovne:
- Výber náhodného čísla k ∈ (0, q).
- Výpočet r = (g k mod p) mod q.
- Výpočet s = (k -1 (H(m) + x * r)) mod q.
- Opätovný výpočet s novou hodnotu k v prípade, že r alebo s majú hodnotu 0.
- Zostavenie podpisu z dvojice (r, s).
Prijatý podpis je možné overiť v šiestich krokoch.
- Podpis nie je platný, ak r ∉ (0, q) alebo s ∉ (0, q) .
- Výpočet w = s -1 mod q.
- Výpočet u1 = (H(m) * w) mod q.
- Výpočet u2 = (r * w) mod q.
- Výpočet v = ((g u1 * y u2) mod p) mod q.
- Podpis je platný, ak v = r.