Crittografia a chiave pubblica, RSA
Salve, parto dal presupposto che tutti sappiate di cosa sto parlando, quindi parto subito con il mio dubbio
Ho notato degli errori negli appunti del mio prof, quindi ho pensato di fare l'esercizio da lui proposto per conto mio. Il fatto è che non mi riesce -.- mi date una mano?
1. Scegliere due numeri primi di valore elevato: $p$, $q$
2. Calcolare $n = pq$, $z = (p-1)(q-1)$, dove $z$ è la funzione di Eulero di $n$
3. Scegliere $e$ (con $e < n$) tale che non abbia fattori in comune con $z$ (e, z sono “relativamente primi”)
4. Scegliere $d$ tale che $ed-1$ sia esattamente divisibile per $z$ (ovvero: $ed mod z = 1$)
5. $K+ = (e, n)$; $K- = (d, n)$
Cifratura
Testo in chiaro: $m < n$
$K+ = (e, n)$
$c = m^e mod n$
Decifratura
Testo cifrato: $c$
$K- = (d, n)$
$m = c^d mod n$
ESERCIZIO DI ESEMPIO:
$p=5$, $q=7$
per cui $n=35$, $z=24$
Scelgo $e=5$
Scelgo $d=29$
$K+ = (5, 35) $;
$K- = (29, 35)$
E fin qui ci siamo, è quello che ha fatto il mio prof. Veniamo ora a una cifratura di esempio:
Cifratura: lettera "l" --> $m=12$
Da qui penso che il mio prof abbia commesso un errore perché scrive
$m^e=1524832$
e se non erro, correggetemi se sbaglio, $m^e=12^5=248832$ ...
Poi lui fa, e non dovrebbe uscirgli così,
$c = m^e mod n = 17$
che in effetti è il risultato giusto che riscontro anch'io, dunque sarà un semplice errore di battitura il suo... andiamo avanti.
Questa è la decifratura del mio prof. Mi pare che i calcoli siano sbagliati, anche se "magicamente" i risultati escono giusti.
Decifratura:
$c = 17$
$c^d = 481968572106750915091411825223071697$
$m = c^d mod n = 12$
La lettera è "l"
Ok. Forse faccio io degli errori... da qui lo faccio io:
Decifratura:
$c = 17$
$c^d = 17^29$
$m = c^d mod n = 17^29 mod 35$
Per calcolarmi $m$ dunque faccio così (e qui incappo nell'errore che mi blocca)
Metto a sistema (sarà qui il mio errore?):
$17^29 ≡ x mod 5$
$17^29 ≡ y mod 7$
Li risolvo e mi escono:
$x=2$
$y=5$
Dovrei moltiplicarli (?) tra loro per conoscere il risultato in mod 35, o no? E quindi $10$. E non $12$.
Dove sbaglio?
Ho notato degli errori negli appunti del mio prof, quindi ho pensato di fare l'esercizio da lui proposto per conto mio. Il fatto è che non mi riesce -.- mi date una mano?
1. Scegliere due numeri primi di valore elevato: $p$, $q$
2. Calcolare $n = pq$, $z = (p-1)(q-1)$, dove $z$ è la funzione di Eulero di $n$
3. Scegliere $e$ (con $e < n$) tale che non abbia fattori in comune con $z$ (e, z sono “relativamente primi”)
4. Scegliere $d$ tale che $ed-1$ sia esattamente divisibile per $z$ (ovvero: $ed mod z = 1$)
5. $K+ = (e, n)$; $K- = (d, n)$
Cifratura
Testo in chiaro: $m < n$
$K+ = (e, n)$
$c = m^e mod n$
Decifratura
Testo cifrato: $c$
$K- = (d, n)$
$m = c^d mod n$
ESERCIZIO DI ESEMPIO:
$p=5$, $q=7$
per cui $n=35$, $z=24$
Scelgo $e=5$
Scelgo $d=29$
$K+ = (5, 35) $;
$K- = (29, 35)$
E fin qui ci siamo, è quello che ha fatto il mio prof. Veniamo ora a una cifratura di esempio:
Cifratura: lettera "l" --> $m=12$
Da qui penso che il mio prof abbia commesso un errore perché scrive
$m^e=1524832$
e se non erro, correggetemi se sbaglio, $m^e=12^5=248832$ ...
Poi lui fa, e non dovrebbe uscirgli così,
$c = m^e mod n = 17$
che in effetti è il risultato giusto che riscontro anch'io, dunque sarà un semplice errore di battitura il suo... andiamo avanti.
Questa è la decifratura del mio prof. Mi pare che i calcoli siano sbagliati, anche se "magicamente" i risultati escono giusti.
Decifratura:
$c = 17$
$c^d = 481968572106750915091411825223071697$
$m = c^d mod n = 12$
La lettera è "l"
Ok. Forse faccio io degli errori... da qui lo faccio io:
Decifratura:
$c = 17$
$c^d = 17^29$
$m = c^d mod n = 17^29 mod 35$
Per calcolarmi $m$ dunque faccio così (e qui incappo nell'errore che mi blocca)
Metto a sistema (sarà qui il mio errore?):
$17^29 ≡ x mod 5$
$17^29 ≡ y mod 7$
Li risolvo e mi escono:
$x=2$
$y=5$
Dovrei moltiplicarli (?) tra loro per conoscere il risultato in mod 35, o no? E quindi $10$. E non $12$.
Dove sbaglio?
Risposte
nessuno?
Per quello che so moltiplicando due moduli diversi per ottenerne un terzo di deve tener conto di altre variabili (quante volte i moduli sono contenuti nei numeri di partenza) per ottenere l'effettivo resto. Inoltre dovresti dividere $(17^29)/35$ invece dividi $(17^29)/5$ e $(17^29)/5$, poi li moltiplichi.
Io ti consiglierei di fare così: Poiché per calcolare il resto di un qualsiasi $(a^e)/n$ basta calcolare il resto di $a/n$, elevare questo resto alla e e poi riportarlo in $mod n$ ti conviene scomporre la divisione in varie divisioni successive.
Mi spiego meglio:
Calcoli il resto di $(17^2)/35$ che vale $9$.
A questo punto fai $(9^14)/35$ il cui resto vale $11$.
Ora moltiplichi $11*17$ (per ora avevamo sviluppato 28 delle 29 potenze) e lo riporti in $mod 35$.
Il risultato è appunto $12$
Io ti consiglierei di fare così: Poiché per calcolare il resto di un qualsiasi $(a^e)/n$ basta calcolare il resto di $a/n$, elevare questo resto alla e e poi riportarlo in $mod n$ ti conviene scomporre la divisione in varie divisioni successive.
Mi spiego meglio:
Calcoli il resto di $(17^2)/35$ che vale $9$.
A questo punto fai $(9^14)/35$ il cui resto vale $11$.
Ora moltiplichi $11*17$ (per ora avevamo sviluppato 28 delle 29 potenze) e lo riporti in $mod 35$.
Il risultato è appunto $12$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo