Nyilvános kulcsú titkosírás: így működik az RSA
A kulcspár ötlete, a mögötte álló matematika egy kiszámolható játékpéldán, a digitális aláírás és a javasolt kulcshossz – közérthetően.
Minden alkalommal, amikor egy webáruházban lakat ikon jelenik meg a böngésző sarkában, a háttérben nyilvános kulcsú titkosítás dolgozik. A legismertebb ilyen eljárás az RSA, amelyet Ron Rivest, Adi Shamir és Leonard Adleman publikált 1977-ben. Az alábbiakban megnézzük, mi a lényege – a matematika meglepően barátságos.
A kulcspár ötlete
A hagyományos titkosításnál ugyanaz a kulcs zár és nyit, ezért a kulcsot valahogy biztonságosan el kell juttatni a címzetthez. Az RSA két kulcsot használ: a nyilvános kulcsot bárki megkaphatja, és vele titkosíthat, a titkos kulcs viszont csak a tulajdonosnál van, és csak ezzel lehet visszafejteni. Olyan ez, mint egy postaláda: bedobni bárki tud, kivenni csak az, akinél a kulcs van.
A matematika röviden
- Választunk két nagy prímszámot, p-t és q-t, és összeszorozzuk őket: n = p · q.
- Kiszámoljuk a φ = (p − 1)(q − 1) értéket.
- Választunk egy e számot, amelynek φ-vel nincs közös osztója – ez lesz a nyilvános kitevő.
- Megkeressük azt a d számot, amelyre e · d osztva φ-vel 1 maradékot ad – ez a titkos kitevő.
A nyilvános kulcs az (n, e), a titkos kulcs a (n, d) pár. Egy m üzenetből a titkosított c = mᵉ mod n, a visszafejtés pedig m = cᵈ mod n. A módszer biztonsága azon múlik, hogy n-ből p és q visszakeresése, vagyis a prímtényezőkre bontás nagy számoknál gyakorlatilag kivitelezhetetlen.
Egy játékpélda
Legyen p = 61 és q = 53. Ekkor n = 3233, φ = 3120. Válasszuk e = 17-et; a hozzá tartozó d = 2753, mert 17 · 2753 = 46 801, ami 3120-szal osztva éppen 1 maradékot ad. Az m = 65 üzenet titkosítva 65¹⁷ mod 3233 = 2790, és 2790²⁷⁵³ mod 3233 valóban visszaadja a 65-öt. A valóságban persze több száz jegyű prímekkel dolgozunk.
Digitális aláírás
A kulcspár fordítva is használható. Ha valaki a titkos kulcsával „titkosít” egy üzenetből képzett ujjlenyomatot (hash-t), azt bárki ellenőrizheti a nyilvános kulccsal. Így bizonyítható, hogy az üzenet valóban tőle származik, és útközben senki nem módosította – ezen alapul az elektronikus aláírás és az SSL-tanúsítványok rendszere.
Mekkora kulcs kell?
A 512 bites RSA-kulcsokat már feltörték, ezért ma legalább 1024 bitet használjunk, hosszú távon megőrzendő adatokhoz pedig 2048 bitet javasolnak a szakértők. A kulcshossz növelésével a titkosítás lassul, ezért a gyakorlatban az RSA-val csak egy rövid, véletlen munkamenetkulcsot cserélnek ki, a tényleges adatforgalmat pedig gyors szimmetrikus eljárás titkosítja.