Differences

This shows you the differences between two versions of the page.

--- tanszek:oktatas:infrendalapjai_architekturak:informacio_titkositas_es_hitelesites:nyilvanos_kulcsu_rendszerek [2024/11/13 17:45] – knehez
+++ tanszek:oktatas:infrendalapjai_architekturak:informacio_titkositas_es_hitelesites:nyilvanos_kulcsu_rendszerek [2024/12/06 16:38] (current) – [Példa a kulcsgenerálásra] knehez
@@ Line 53: / Line 53: @@
 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<d<f(N) \) feltétel figyelembe vételével az \( e \cdot d \mod{f(N)} =1 \) egyenlet megoldásával nyerjük.
+  - nyilvános kulcs **(e,N)**, titkos kulcs **d**
+==== Példa a kulcsgenerálásra ====
+Anna választ 2 prímszámot, például legyenek: \(p=67\) és \(q=11\) a két választott prím.
+.) \(N = p \cdot q = 67 \cdot 11 = 737.\)
+.) A relatív prímek száma: \( φ(N) = (p-1) \cdot (q-1) = 66 \cdot 10 = 660 \)
+.) Válasszunk egy \( e \) számot amelyre igaz: \( 1<e< φ(N) \) és \( \text{lnko}(e, φ(N))=1 \) \( φ(N) = 660 \)-hoz a legkisebb ilyen kitevő \( e = 7 \)
+.) Anna nyilvános kulcsa tehát ezek alapján: \( (N,e) = (737,7) \)
+A következő 5. lépés többféleképpen is megoldható:
+a.) \( K \cdot φ(N) + 1 \) felbontható két szám szorzatára (miből a \( e=7 \) az egyik): tehát keressük azt a legkisebb \( K \)-t amelyre igaz: \( K \cdot 660 + 1 \mod{7} = 0 \). A legkisebb ilyen a \(K=3\). Ebből következik, hogy \( (3*660+1) / 7 = 283 \).
+b.) \( e \cdot d \mod {f(N)} = 1 \), egyenletből \(d\) kifejezhető. \( d = 283 \)
+.) A titkos kulcs \( (N,d) = (737,283) \) lesz.
+.) Az ABC 26 karaktert tartalmaz tehát \(I = log_{26} N = log_{26} 737 = 2\). Tehát a blokkhossz most 2-byte lesz.
+.) A kódolandó üzenetet 2 bájtonként tördeljük, és 26-os számrendszerbe átalakítjuk. Pl. Ha a kódolandó üzenet ‘A’ és ‘B’, akkor \( 1*26^1+2*26^0=26+2=28 \).
+.) \( 28^7 \mod{737} = 316 \). ez felírva 26-os számrendszerbe: \( 12*26^1+4*26^0 \) --> A kódolt szöveg: \(LD\) lett.
+.) Visszafejtés: \(LD\) átalakítva számmá: 316
+.) \( 316^{283} \mod{737} = 28 \) -> Betűkre átalakítva: \(AB\)
+==== Online RSA generátor ====
+https://www.devglan.com/online-tools/rsa-encryption-decryption