[Crittografia-RSA] Aiuto su aritmetica finita
RSA il noto algoritmo di critografia asimmetrica, funziona in pochi passaggi nel seguente modo:
- Scelgo due numeri primi $p$ e $q$;
- calcolo $n=p*q$ e $\varphi(n) = (p-1)*(q-1)$;
- scelgo un intero $e$ (esponente pubblico) coprimo con $\varphi(n)$ e $e<\varphi(n)$;
- calcolo $d$ (esponente privato) $d-=e^-1 mod (\varphi(n))$
La chiave pubblica sarà = $Pu(e,n)$.
La chiave privata sarà = $Pr(d,n)$.
La cifratura è $C = M^e mod n$. M=testo in chiaro - C=testo cifrato
La decifratura è $M = C^d mod n$.
Le mie domande a questo punto sono due per chi è più pratico con l'aritmetica modulare.
1- Un hacker conoscendo $Pu$ vorrebbe ricavarsi la chiave privata e quindi scovare $d$.
Quindi prova con un attacco di tipo bruteforce tutti i possibili valori di $q$ e $p$ tali che sostituiti in
$d-=e^-1 mod ((p-1)(q-1))$, generano una $d$ che utilizzata in $M = C^d mod n$ ci fornisce un testo in chiaro
comprensibile??
2- La debolezza dell'algoritmo si basa su un'assunzione mai dimostrata che è il problema di calcolare:
$root(e)C mod n$ (l'indice della radice è $e$)
e sia computazionalmente intrattabile. Perchè sarebbe problematico calcolarlo in tembi brevi??
Grazie a tutti e buona serata
- Scelgo due numeri primi $p$ e $q$;
- calcolo $n=p*q$ e $\varphi(n) = (p-1)*(q-1)$;
- scelgo un intero $e$ (esponente pubblico) coprimo con $\varphi(n)$ e $e<\varphi(n)$;
- calcolo $d$ (esponente privato) $d-=e^-1 mod (\varphi(n))$
La chiave pubblica sarà = $Pu(e,n)$.
La chiave privata sarà = $Pr(d,n)$.
La cifratura è $C = M^e mod n$. M=testo in chiaro - C=testo cifrato
La decifratura è $M = C^d mod n$.
Le mie domande a questo punto sono due per chi è più pratico con l'aritmetica modulare.
1- Un hacker conoscendo $Pu$ vorrebbe ricavarsi la chiave privata e quindi scovare $d$.
Quindi prova con un attacco di tipo bruteforce tutti i possibili valori di $q$ e $p$ tali che sostituiti in
$d-=e^-1 mod ((p-1)(q-1))$, generano una $d$ che utilizzata in $M = C^d mod n$ ci fornisce un testo in chiaro
comprensibile??
2- La debolezza dell'algoritmo si basa su un'assunzione mai dimostrata che è il problema di calcolare:
$root(e)C mod n$ (l'indice della radice è $e$)
e sia computazionalmente intrattabile. Perchè sarebbe problematico calcolarlo in tembi brevi??
Grazie a tutti e buona serata
Risposte
La debolezza dell'RSA dovrebbe essere la fattorizzazione di $n$ in tempi brevissimi (che forse ancora nessuno ha fatto) e da li ti calcoli la chiave privata
Si sceglie $M^e>n$
Grazie altrimenti il risultato sarebbe sempre $n$ giustamente.
Un algoritmo polinomiale (precisamente cubico) per la fattorizzazione in numeri primi. L'unico particolare è che richiede un computer quantistico.
(https://it.wikipedia.org/wiki/Algoritmo ... ne_di_Shor)
C'è da preoccuparsi per l'imminente futuro nel mondo della crittografia??
Un algoritmo polinomiale (precisamente cubico) per la fattorizzazione in numeri primi. L'unico particolare è che richiede un computer quantistico.
(https://it.wikipedia.org/wiki/Algoritmo ... ne_di_Shor)
C'è da preoccuparsi per l'imminente futuro nel mondo della crittografia??
No, all'arrivo dei computer quantistici basterebbe cambiare algoritmo. Già esistono alternative e ce ne sono anche fornite dagli stessi computer quantistici.
Si io ne ho in garage uno.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo