🔑 Generiranje ključev 1. korak
Vpiši dve praštevili p in q
Kaj je RSA šifriranje?
RSA (Rivest–Shamir–Adleman) je asimetričen kriptografski algoritem, ki ga leta 1977 razvili Ron Rivest, Adi Shamir in Leonard Adleman. Temelji na matematičnem problemu faktorizacije velikih celih števil.
Asimetričen pomeni, da imamo dva ključa: javni ključ za šifriranje in zasebni ključ za dešifriranje. Javni ključ delimo z vsemi, zasebni pa hranimo skrivno.
Korak za korakom
- Izberi dve praštevili p in q. Izbereta se dve veliki praštevili. V praksi gre za stotine znamenk.
- Izračunaj modul n = p · q. To je modul, ki je del obeh ključev.
- Izračunaj Eulerjev fi: φ(n) = (p−1)·(q−1). Euler-ova totientna funkcija pove, koliko celih števil je tujih z n.
- Izberi javni eksponent e. e mora biti tuj s φ(n), torej gcd(e, φ(n)) = 1. Pogosta vrednost je 65537.
- Izračunaj zasebni ključ d = e⁻¹ mod φ(n). d je multiplikativni inverz e po modulu φ(n). Najdemo ga z razširjenim Evklidovim algoritmom.
- Javni ključ: (e, n). Zasebni ključ: (d, n). p, q in φ(n) se po generiranju uničijo.
Formule
Generiranje ključev
n = p · q
Modul n — produkt dveh praštevil p in q.
Eulerjev fi (totientna funkcija)
φ(n) = (p − 1) · (q − 1)
Ker sta p in q praštevili, je φ(n) = (p−1)(q−1). Za splošno n bi morali upoštevati celotno razcepitveno formo.
Pogoj za e
1 < e < φ(n) in gcd(e, φ(n)) = 1
e mora biti tuj z φ(n) (največji skupni delitelj mora biti 1). Poleg tega e ne sme biti 1.
Zasebni ključ d
d · e ≡ 1 (mod φ(n))
d je multiplikativni inverz e po modulu φ(n). Dobimo ga z razširjenim Evklidovim algoritmom (Extended Euclidean Algorithm).
Šifriranje
c = me mod n
c je šifrirano sporočilo. m je originalno sporočilo (mora biti < n). Šifriramo z javnim ključem (e, n).
Dešifriranje
m = cd mod n
m dobimo nazaj z zasebnim ključem (d, n). Deluje zahvaljujoč Eulerjevemu izreku: c^d ≡ m (mod n).
Razširjeni Evklidov algoritem
Za izračun zasebnega ključa d potrebujemo multiplikativni inverz. Algoritem poiščemo iterativno:
Razširjeni Evklidov algoritem — primer: e=7, φ(n)=40
40 = 5·7 + 5
7 = 1·5 + 2
5 = 2·2 + 1 ← gcd = 1
Obratno sledenje:
1 = 5 − 2·2 = 5 − 2·(7−5) = 3·5 − 2·7 = 3·(40−5·7) − 2·7 = 3·40 − 17·7
d ≡ −17 ≡ 23 (mod 40)
7 = 1·5 + 2
5 = 2·2 + 1 ← gcd = 1
Obratno sledenje:
1 = 5 − 2·2 = 5 − 2·(7−5) = 3·5 − 2·7 = 3·(40−5·7) − 2·7 = 3·40 − 17·7
d ≡ −17 ≡ 23 (mod 40)
Preveritev: 7·23 = 161 = 4·40 + 1 ≡ 1 (mod 40) ✓
Simboli in pojmi
| Simbol | Pomen |
|---|---|
| p, q | Dve praštevili, ki ju skrivno izberemo |
| n | Modul: n = p·q, del javnega in zasebnega ključa |
| φ(n) | Eulerjev fi (totient): φ(n) = (p−1)·(q−1) |
| e | Javni eksponent: gcd(e, φ(n)) = 1 |
| d | Zasebni eksponent: d·e ≡ 1 (mod φ(n)) |
| m | Originalno sporočilo (plaintext), m < n |
| c | Šifrirano sporočilo (ciphertext) |
| mod | Ostanek pri deljenju (modulo operacija) |
| gcd(a,b) | Največji skupni delitelj a in b |
| a ≡ b (mod n) | a in b sta kongruentna po modulu n: n | (a−b) |
💡 Nasvet za ročno računanje: Za vajo na papirju izberite majhna praštevila (npr. p=5, q=11 ali p=7, q=13). V praksi so RSA ključi dolgi 2048 ali 4096 bitov — ta števila so neprimerno prevelika za ročno računanje!
Vaje
Uspešnost:
0 / 0