Home
Skip to main content eIDAS szerinti minősített bizalmi szolgáltató
Az RSA algoritmus
Az RSA egy nyilvános kulcsú kriptográfiai algoritmus, amelyet Ronald Rivest, Adi Shamir és Len Adleman fejlesztett ki. Ma az RSA messze a legelterjedtebb nyilvános kulcsú kriptográfiai algoritmus.

  A kriptográfiai alapfogalmakról szeretne olvasni?

Az RSA kódolás - akár titkosítást, akár dekódolást, akár aláírás készítését vagy annak ellenőrzését értjük kódolás alatt - moduláris hatványozással történik. Ez azt jelenti, kódoláskor hatványozást végzünk, a kódoló bemenetét (pl. a titkosítandó vagy aláírandó üzenetet) felemeljük a kulcs által meghatározott hatványra, majd a kapott eredményt elosztjuk egy ún. modulussal és a kapott maradékkal számolunk tovább.

Amikor az Alajos nevű felhasználó RSA kulcspárt generál, a következő műveleteket végzi el:

  1. Kiválaszt két nagy véletlen prímszámot. E két prímszám legyen p és q.
  2. Összeszorozza őket, a kapott szorzat lesz a modulus, m = p * q.
  3. Kiszámítja a Φ(m) = (p-1) * (q-1) értéket.
  4. Kiválaszt egy olyan e egész számot, amely relatív prím Φ(m)-hez (azaz a legnagyobb közös osztójuk 1).
  5. Kiszámít egy olyan dértéket, amelyre
    d * e = 1       (modulo Φ(m)) 

    azaz, ha e és d szorzatát elosztjuk Φ(m)-mel, akkor 1-et kapunk maradékul.

Az így kiszámított értékek közül:

Ekkor bármilyen x < m egész számra igaz, hogy ( xe ) d = x (modulo m). Erre az egyenlőségre épül az RSA kódolás és dekódolás.

Tegyük fel, hogy Bendegúz az x üzenetet szeretné titkosítva elküldeni Alajosnak. Ehhez megszerzi Alajos nyilvános kulcsát, azaz az m és e számokat. Bendegúz a következő módon határozza meg az y titkosított üzenetet:

y = xe       (modulo m)

Alajos a következő módon állítja vissza az x nyílt üzenetet:

x = yd       (modulo m)

Tegyük fel, hogy Alajos alá szeretné írni az x dokumentumot. Ekkor a következő módon számítja ki az s aláírást:

s = xd       (modulo m)

Bendegúz megkapja az x dokumentumot és az s aláírást, és Alajos (m, e) nyilvános kulcsát. A következő egyenlőség ellenőrzésével döntheti el, hogy ezek összetartoznak-e:

se = x       (modulo m)

Az RSA algoritmus biztonsága a következőkre épül:

Megjegyzés: