[[oktatas:programozás:algoritmusok|< Algoritmus]]

===== RSA =====

  * **Szerző:** Sallai András
  * Copyright (c) 2014, Sallai András
  * Szerkesztve: 2014, 2015
  * Licenc: [[https://creativecommons.org/licenses/by-sa/4.0/|CC BY-SA 4.0]]
  * Web: https://szit.hu

==== Az RSA-ról ====


**Ron Rivest**, **Adi Shamir** és **Len Adleman** fejlesztette ki.


===== Kulcsgenerálás =====

  - Válasszunk két nagy prím számot, p és q-t.
    - p ≠ q
  - Számítsuk ki a szorzatukat, **n**-t: n = p * q.
  - Ekkor: φ(n) = (p-1) * (q-1)
  - Válasszunk egy **e** számot, amelyre igaz:
    - 1 < e < φ(n)
    - lnko(e, φ(n))=1
  - Kiszámítjuk **d** értékét:
    - e * d ≡ 1 mod φ(n)
    - 0 ≤ d ≤ φ(n)

  * A nyilvános kulcs: {e, n}
  * A titkos kulcs: {d, n}

Megjegyzés: A <m>a ≡ b (mod m)</m> azt jelenti, hogy <m>a mod m = b</m>, vagyis
ha a-t elosztom m-el, akkor b-t kapom.


===== Használat =====

Kódolás:

<m>c = m^e mod n</m>

Visszafejtés:

<m>m = c^d mod n</m>

===== Megjegyzés =====

  * Nem bizonyított, hogy polinomiális faktorizáló algoritmus nem létezik.
  * Nem bizonyított, hogy faktorizálás nélkül nem lehet feltörni.