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: