===== Nyilvános kulcsú rendszerek ===== {{:tanszek:oktatas:infrendalapjai_architekturak:informacio_titkositas_es_hitelesites:pasted:20241113-173624.png}} A kommunikáció alapmodellje: - Anna készít egy **e,d** kulcspárt. - **d**-t titokban tartja, **e**-t nyilvánosságra hozza. - Ha Berci üzenni akar Annának, akkor Anna (**e**) nyilvános kulcsát használja. - **c=E(e , m)** alapján **c**-t csak Anna tudja visszafejteni, **m = D(d,c)** alkalmazásával. - Ha más is üzenni kíván Annának, akkor használhatja az ő nyilvános (**e**) kulcsát. A rendszer biztonságos a visszafejtés szempontjából, de Anna soha sem lehet biztos, hogy Berci küldte az üzenetet, hiszen a nyilvános (e) kulcsot bárki használhatja. ===== RSA algoritmus ===== Rivest, Shanir, Adleman (1977), az algoritmus a hatványozáson és a moduló (maradékos osztás) műveleten alapul. Ha következő egyenlet teljesül: $$ T ^ {ed} \mod{N} = T $$ Akkor az egyenletet szét lehet választani két részre, ahol az első egyenlet kódol, a második dekódol: $$ T ^{e} \mod{N} = C $$ $$ C ^{d} \mod{N} = T $$ Sajnos ez az összefüggés, nem fog működni tetszőleges e, d, N számhármasokra. Próbáljuk meghatározni milyen feltételek szükségesek? ==== Alaptétel ==== Akármennyire hihetetlen, de a következő összefüggést még az ókori görögök is ismerték: \( T^{N-1} \mod {N} = 1 \) egyenlet egész számokra abban az esetben teljesül, ha \( N > T \) és \( N \) prímszám. megjegyzés: prímek azok a pozitív egész számok, amelyeknek nincsen (1-nél különböző) egész osztójuk, pl. 1, 2, 3, 5, 7, 11, 13, 19, stb... Az alapötlet szerint az egyenlet ekvivalens átalakításokkal a fenti alakra hozható a következőképpen: Az \(f(N)\) jelölje azt, hogy \(N\)-nek hány relatív prímje van. pl: \( f(9) = 6 \) mivel 9 relatív prímjei sorban a (1,2,4,5,7,8), a 6 nem az, mert a 3 többszöröse. Érdekes megfigyelni, hogy prímszámok esetén nem kell számolnunk, pl: \( f(11) = 10 \), mivel (1,2,3,4,5,6,7,8,9,10) nem lesz olyan nála kisebb szám ami osztója, mivel 11 prím szám! Ezért felírható az általános: \( f(N) + 1 = N \) összefüggés. Tehát: $$ T ^{f(N)} \mod{N} = 1, $$ mivel \( N - 1 = f(N) \) összefüggés behelyettesíthető. Ha a hatványozás kitevőjét beszorozzuk egy konstanssal, akkor a moduló művelet nem változik, a maradék akkor is ugyanannyi lesz: $$ T ^{K\cdot f(N)} \mod{N} = 1. $$ Ez a lépés biztosítja, hogy végtelen kulcs lehet, mivel "bármilyen" K-t alkalmazhatunk (K tetszőleges egész szám). Most pedig szorozzuk be T-vel mindkét oldalt: $$ T ^{K\cdot f(N) + 1} \mod{N} = T. $$ ha K-t úgy választjuk meg, hogy a \(K \cdot f(N) + 1\) felbontható legyen két egész szám szorzatára, akkor megkapjuk e, d kulcsokat. Hogy ne kelljen próbálgatni, ezért egy egzakt módszer is létezik, amit majd később részletezünk. ==== RSA kulcsgenerálás ==== A kulcsgenerálás a következőképpen történik: - keresünk két nagy prímszámot: X és Y - ezek szorzata lesz: \( N = X \cdot Y. \) - mindkét számnak ismerjük, hogy hány relatív prímje van: \( f(X) = X - 1,\,\, f(Y) = Y - 1 \) és ez alapján \( f(N) \) könnyen számolható: \( f(N) = (X-1) \cdot (Y-1) \) - felbontjuk \( K \cdot f(N) + 1 \) összefüggést két egész szám szorzatára. \( K \cdot f(N) + 1 = e \cdot d \) felbontást a gyakorlatban a következő képlettel számoljuk: $$ \text{lnko} (e, f(N)) = 1 $$ egyenletből az e-t, majd a d-t a \( 1 A kódolt szöveg: \(LD\) lett. 10.) Visszafejtés: \(LD\) átalakítva számmá: 316 11.) \( 316^{283} \mod{737} = 28 \) -> Betűkre átalakítva: \(AB\) ==== Online RSA generátor ==== https://www.devglan.com/online-tools/rsa-encryption-decryption