Asymetrická kryptografie, vlastnosti, způsoby použití, poskytované bezpečnostní funkce, elektronický podpis a jeho vlastnosti, hybridní kryptografie, algoritmus RSA, generování klíčů, šifrování, dešifrování.

RSA je asymetrický kryptografický algoritmus, takže pracuje se dvěma klíči: * veřejný klíč se může komukoli ukázat a používá se k šifrování nebo ověřování podpisu * soukromý klíč musí zůstat tajný a používá se k dešifrování nebo vytváření podpisu 1. Základní myšlenka RSA * RSA stojí na tom, že je snadné vynásobit dvě velká prvočísla, ale je extrémně těžké z výsledného součinu zjistit, která prvočísla to byla * například: * p = 61 * q = 53 * n = p * q = 3233 * když známe p a q, snadno spočítáme n * kdyby ale n bylo obrovské číslo s tisíci bity, rozložit ho zpět na p a q by bylo výpočetně velmi těžké 2. Generace klíčů * nejprve si zvolíme dvě velká náhodná prvočísla: * p a q * potom spočítáme jejich součin: * n = p * q * číslo n se používá v obou klíčích * říká se mu modulus * dále spočítáme Eulerovu funkci: * φ(n) = (p - 1)(q - 1) * tato hodnota je důležitá pro konstrukci veřejného a soukromého exponentu * poté vybereme číslo e, kterému se říká veřejný exponent * musí platit, že e je nesoudělné s φ(n), tedy: * gcd(e, φ(n)) = 1 * v praxi se často používá: * e = 65537 * nakonec se vypočítá soukromý exponent d, který je inverzí čísla e modulo φ(n): * d * e ≡ 1 mod φ(n) * to znamená, že když vynásobíme d a e, výsledek dá po dělení φ(n) zbytek 1 * výsledkem jsou dva klíče: * veřejný klíč: (n, e) * soukromý klíč: (n, d) * hodnoty p, q a φ(n) se musí uchovat v tajnosti nebo bezpečně smazat 3. Šifrování * zprávu si nejprve převedeme na číslo m * musí platit: * 0 < m < n * šifrování se provede pomocí veřejného klíče (n, e): * c = m^e mod n * kde: * m = původní zpráva jako číslo * e = veřejný exponent * n = modulus * c = zašifrovaný text * výsledek c je šifrovaná zpráva 4. Dešifrování * příjemce použije soukromý klíč (n, d) a vypočítá: * m = c^d mod n * tím získá původní zprávu m * funguje to proto, že čísla e a d jsou matematicky propojená tak, aby se operace umocnění na e dala vrátit pomocí umocnění na d v modulu n 5. Malý číselný příklad * zvolíme malá prvočísla: * p = 61 * q = 53 * spočítáme: * n = 61 * 53 = 3233 * Eulerova funkce: * φ(n) = 60 * 52 = 3120 * zvolíme veřejný exponent: * e = 17 * najdeme soukromý exponent d, aby platilo: * 17 * d ≡ 1 mod 3120 * vyjde: * d = 2753 * takže: * veřejný klíč: (3233, 17) * soukromý klíč: (3233, 2753) * teď chceme zašifrovat zprávu: * m = 65 * šifrování: * c = 65^17 mod 3233 * c = 2790 * dešifrování: * m = 2790^2753 mod 3233 * m = 65 * dostali jsme zpět původní zprávu 6. Proč útočník neumí snadno dešifrovat zprávu * útočník zná veřejný klíč: * (n, e) * tedy například ví: * n = 3233 * e = 17 * a zná šifrovaný text c * aby mohl dešifrovat, potřeboval by znát d * jenže d se počítá pomocí φ(n), a k výpočtu φ(n) potřebuje znát p a q * u malého čísla 3233 je snadné zjistit, že: * 3233 = 61 * 53 * ale u skutečného RSA má n běžně 2048 nebo více bitů, takže rozklad na prvočísla je extrémně obtížný 7. Důležitá poznámka: RSA se v praxi nepoužívá takto na holá data * popsaný postup je tzv. učebnicové RSA * to je dobré pro pochopení principu, ale samo o sobě není bezpečné * v praxi se před šifrováním používá speciální doplnění zprávy, tzv. padding, například: * RSA-OAEP * bez paddingu by RSA mělo vážné bezpečnostní problémy, například by stejné zprávy dávaly stejné šifrované výstupy 8. RSA a digitální podpis * RSA se nepoužívá jen k šifrování, ale také k digitálním podpisům * princip je opačný * při šifrování: * šifrování: veřejný klíč * dešifrování: soukromý klíč * při podpisu: * podpis: soukromý klíč * ověření: veřejný klíč * majitel soukromého klíče vytvoří podpis a kdokoli s veřejným klíčem může ověřit, že podpis opravdu vytvořil držitel soukromého klíče * v praxi se ale nepodepisuje celá zpráva přímo * nejprve se spočítá hash zprávy a ten se potom podepíše, obvykle se schématem jako RSA-PSS 9. Shrnutí * RSA funguje tak, že se vytvoří veřejný a soukromý klíč z dvojice velkých prvočísel * veřejný klíč umožní zprávu zašifrovat, ale dešifrovat ji lze jen pomocí soukromého klíče * bezpečnost RSA stojí na obtížnosti rozkladu velmi velkého čísla n na dvě původní prvočísla p a q

Hybridní kryptografie kombinuje asymetrické a symetrické šifrování. Asymetrické šifrování se použije k bezpečné výměně klíče a symetrické šifrování pak rychle zašifruje samotná data. Používá se například u HTTPS.