Ricavare totiente se si sanno due inversi mod(phi(n))
Ho il seguente problema da risolvere:
Alice e Bob hanno implementato un sistema basato su RSA che rende possibile alle persone di mandare messaggi crittati a uno di loro due.
Un amico fidato Tom sceglie segretamente due grandi numeri primi p e q di circa la stessa grandezza e li moltiplica per ottenere n = pq. Sceglie a caso degli esponenti segreti per decrittare (tali che $gcd(d_a, phi(n))$, $gcd(d_b, phi(n))$ = 1) e calcola i loro inversi modulo $phi(n)$ dove $phi(n) = (p-1)(q-1)$
Tom da ad Alice n, il suo esponente per decrittare $d_a$ e il suo esponente pubblico per crittare $e_a$ e da a Bob n, il suo esponente per decrittare $d_b$ e il suo esponente pubblico per crittare $e_B$.
E' successo per caso che $gcd(e_a, e_b) = 1$
- Puo' Alice decifrare la posta crittata di bob in qualche modo?
- Puo' Eva decifrare un messaggio m se lo stesso messaggio e' stato mandato crittato in due modi diversi ad Alice e Bob?
In pratica per rispondere alla prima domanda vorrei sapere se vi viene in mente un modo per ottenere $phi(n)$ se si conoscono due inversi $e_a$ e $d_a$ tali che $e_a d_a = 1 mod phi(n)$
Per la seconda domanda Eva dovrebbe usare una sottrazione e calcolare un qualche gcd ma non mi viene in mente dove/come.
Grazie per l'aiuto se potete!
Alice e Bob hanno implementato un sistema basato su RSA che rende possibile alle persone di mandare messaggi crittati a uno di loro due.
Un amico fidato Tom sceglie segretamente due grandi numeri primi p e q di circa la stessa grandezza e li moltiplica per ottenere n = pq. Sceglie a caso degli esponenti segreti per decrittare (tali che $gcd(d_a, phi(n))$, $gcd(d_b, phi(n))$ = 1) e calcola i loro inversi modulo $phi(n)$ dove $phi(n) = (p-1)(q-1)$
Tom da ad Alice n, il suo esponente per decrittare $d_a$ e il suo esponente pubblico per crittare $e_a$ e da a Bob n, il suo esponente per decrittare $d_b$ e il suo esponente pubblico per crittare $e_B$.
E' successo per caso che $gcd(e_a, e_b) = 1$
- Puo' Alice decifrare la posta crittata di bob in qualche modo?
- Puo' Eva decifrare un messaggio m se lo stesso messaggio e' stato mandato crittato in due modi diversi ad Alice e Bob?
In pratica per rispondere alla prima domanda vorrei sapere se vi viene in mente un modo per ottenere $phi(n)$ se si conoscono due inversi $e_a$ e $d_a$ tali che $e_a d_a = 1 mod phi(n)$
Per la seconda domanda Eva dovrebbe usare una sottrazione e calcolare un qualche gcd ma non mi viene in mente dove/come.
Grazie per l'aiuto se potete!
Risposte
Il messaggio criptato con la chiave $e_a$ e' dato da $c_a=m^{e_a}~mod ~n$, il messaggio criptato con la chiave $e_b$ e' dato dato da $c_b=m^{e_b}~ mod~ n$.
Se $e_a$ ed $e_b$ sono coprimi, allora esistono due interi $r,s$ per cui vale $r\cdot e_a+s\cdot e_b=1$. Gli interi $r$ ed $s$ si possono determinare in modo efficiente con l'algoritmo di Euclide. Una volta trovati $r$ ed $s$, calcolando
$ (c_a)^r\cdot (c_b)^s=m^{r \cdot e_a}\cdot m^{s\cdot e_b} =m^{r\cdot e_a+s\cdot e_b}=m ~ mod~ n$
possiamo ricostruire $m$ senza fattorizzare $n$.
Se $e_a$ ed $e_b$ sono coprimi, allora esistono due interi $r,s$ per cui vale $r\cdot e_a+s\cdot e_b=1$. Gli interi $r$ ed $s$ si possono determinare in modo efficiente con l'algoritmo di Euclide. Una volta trovati $r$ ed $s$, calcolando
$ (c_a)^r\cdot (c_b)^s=m^{r \cdot e_a}\cdot m^{s\cdot e_b} =m^{r\cdot e_a+s\cdot e_b}=m ~ mod~ n$
possiamo ricostruire $m$ senza fattorizzare $n$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo