In che modo il messaggio viene decrittografato in un attacco con testo cifrato scelto da RSA quando è un modulo?

Question

Durante l'ultima fase di decrittazione di un attacco con testo cifrato scelto, ci lascia questa equazione

$$c = m \cdot t \pmod n$$

Rimuovendo tutti gli esponenti like $d$ e $e$ dove $c$ è il messaggio decifrato che (non significa nulla), $t$ è il messaggio con cui abbiamo moltiplicato il testo cifrato originale, $m$ è il messaggio che vogliamo.

Se sostituiamo con un valore come questi dopo la decrittazione $c=2$, $t=2$, $n=5$ ad esempio, otteniamo:

$$2 = (m \cdot 2) \pmod 5$$

Ma qui $m$possono essere molti valori diversi. Può essere 6 o 11:$(6*2) \bmod 5 = 2$. Voglio dire, è un orologio per tante opzioni$m$ darebbe lo stesso output di testo cifrato decrittografato.

Answer 1

In un attacco con testo cifrato prescelto , si ipotizza che l'avversario possa ottenere la decrittazione di crittogrammi scelti dall'avversario diverso da quello / i mirato / i, e inoltre ottenere la crittografia di qualsiasi messaggio scelto dall'avversario (che è gratuito per asimmetrico crittografia).

L'esperimento CCA più generale va:

• Generazione della chiave: lo sfidante disegna segretamente una chiave e rivela l'eventuale chiave pubblica (ovvero per la crittografia asimmetrica)
• Scelta e crittografia dei messaggi:
  • l'avversario sceglie i messaggi $m_0$ e $m_1$ e le sottopone allo sfidante
  • lo sfidante pesca a caso $b\in\{0,1\}$
  • lo sfidante verifica che entrambi $m_0$ e $m_1$ sono validi (potrebbero essere crittografati) e se questo contiene crittografa $m_b$ cedevole $c_b$, imposta $c=c_b$e rivela $c$ (non correlato alla domanda $c\,$).
• Interazione: lo sfidante accetta e risponde alle domande di crittografia e decrittografia, ad eccezione delle domande di decrittografia che corrisponde al testo cifrato $c$.
• Esame: l'avversario indovina $b$. Il sistema crittografico viene danneggiato sotto l'attacco di testo cifrato scelto quando l'ipotesi è corretta per probabilità non evanescente migliore di$1/2$.

Per la crittografia asimmetrica, lo sfidante non ha bisogno di rispondere alle domande di crittografia, poiché queste possono essere banalmente gestite dall'avversario utilizzando la chiave pubblica.

Nessuna crittografia deterministica può essere protetta da CCA secondo questa definizione (argomento: l'avversario può ottenere $c_0$ e $c_1$ e determinare quali corrispondenze $c$). Per una nozione più debole di sicurezza CCA applicabile alla crittografia deterministica, un'altra modifica è imperativa. Quello può essere:

• Lo sfidante non risponde alle domande di decrittografia in cui il testo cifrato inviato corrisponde a uno di $c_0$ o $c_1$ (lo sfidante deve calcolarli entrambi).
• In alternativa, solo lo sfidante è coinvolto nella scelta del messaggio, che diventa selezione $m$ in modo tale da crittografarlo in $c$riesce. E in esame l'avversario fa un'ipotesi$m$, no $b$. E deve indovinare correttamente con probabilità non evanescente.

---

La domanda è per la RSA da manuale, che è asimmetrica e deterministica. Con la seconda delle opzioni precedenti e una singola query di decrittografia, l'esperimento procede:

• Generazione chiave: lo sfidante
  • disegna una coppia di chiavi
  • rivela la chiave pubblica $(n,e)$
  • mantiene segreto l'esponente privato $d$
    Nota: $(n,e,d)$ è tale che i messaggi $m$ che possono essere crittografati sono quegli interi con $0\le m<n$; la loro crittografia corrispondente è per$c\gets m^e\bmod n$e decrittografia di $c$ con $0\le c<n$ è per $m\gets c^d\bmod n$ o equivalente.
• Scelta dei messaggi e crittografia: lo sfidante
  • disegna in modo casuale un numero intero $m\in[0,n)$
  • calcola $c\gets m^e\bmod n$
  • rivela $c$ (non correlato alla domanda $c\,$).
• Interazione: lo sfidante accetta una query di testo cifrato scelto dove si trova
  • riceve $\tilde c$ (il testo cifrato scelto) presentato dall'avversario
  • controlli $0\le \tilde c<n$ e $\tilde c\ne c$
  • controlli e decifratori $\tilde c$, cioè assegni $0\le \tilde c<n$ poi in caso affermativo calcola e rivela $\tilde m={\tilde c}^d\bmod n$ (Questo $\tilde m$ è la domanda $c\,$).
• Esame: l'avversario indovina $m$. Il sistema crittografico viene interrotto sotto l'attacco di testo cifrato scelto quando l'ipotesi è corretta per probabilità non evanescente.

Un modo standard per portare questo attacco nel libro di testo RSA è che l'avversario

• ne sceglie alcuni $t$ in $[2,n)$ con $\gcd(t,n)=1$, per esempio $t=2$ o $t=n-1$
• calcola $s=t^e\bmod n$
• calcola e invia $\tilde c=c\cdot s\bmod n$
• ottiene $\tilde m$dallo sfidante
  Nota: da$\tilde c=c\cdot s\bmod n$ segue ${\tilde c}^d\equiv(c\cdot s)^d\pmod n$ (ottenuto elevando all'esponente $d$), quindi ${\tilde c}^d\equiv c^d\cdot s^d\pmod n$, così $\tilde m\equiv m\cdot(t^e)^d\pmod n$ (poiché la decrittazione funziona per $m$ e $\tilde m$), quindi $\tilde m\equiv m\cdot t\pmod n$ (poiché la decrittazione funziona per $t$).
• risolve per $m$ con $0\le m<n$ l'equazione $\tilde m\equiv m\cdot t\pmod n$ (che nella domanda è l'equazione $c = m \cdot t \pmod n\,$) e presenta il risultato come recuperato $m$.

In quella fase successiva, l'avversario calcola un inverso moltiplicativo di$t$ modulo $n$, questo è un numero intero $t'$ tale che $t\cdot t'\equiv1\pmod n$. Questo è possibile da allora$\gcd(t,n)=1$. Un metodo utilizza l' algoritmo euclideo esteso . quando$t=2$ (risp. $t=n-1\,$), possiamo usare $t'=(n+1)/2$ (risp. $t'=n-1\,$).

Poi $\tilde m\equiv m\cdot t\pmod n$ diventa $\tilde m\cdot t'\equiv(m\cdot t)\cdot t'\pmod n$, così $\tilde m\cdot t'\equiv m\cdot(t\cdot t')\pmod n$, così $\tilde m\cdot t'\equiv m\cdot1\pmod n$, così $\tilde m\cdot t'\equiv m\pmod n$.

Pertanto, l'avversario trova sempre $m$ calcolando il definito in modo univoco $m=\tilde m\cdot t'\bmod n$ (vedi notazione alla fine).

---

Criticamente rispetto alla domanda, non ci sono esitazioni tra i diversi $m$ perché

• è noto che lo sfidante ha scelto un messaggio valido $m$, così quello $0\le m<n$
• una soluzione $m$ per $\tilde m\equiv m\cdot t\pmod n$esiste e tutti sono congruenti modulo $n$, perché una soluzione $t'$ per $t\cdot t'\equiv1\pmod n$ esiste e tutti sono congruenti modulo $n$, perché l'avversario ha scelto $t$ con $\gcd(t,n)=1$, così $t\bmod n$appartiene al gruppo moltiplicativo di interi modulo $n$
• quando $y$ è congruente a $x$ modulo $n$, ecco quando $y\equiv x\pmod n$, la condizione aggiuntiva $0\le y<n$ fa $y$ definito in modo univoco da $(n,x)$.

---

Notazione: per intero $n>0$ e intero $x$

• $y\equiv x\pmod n$ significa che $n$ divide $x-y$. È meglio leggere come:$y$ è congruente a $x$ (breve pausa) modulo $n$. Può essere scritto y = x (mod n).
• $y=x\bmod n$ significa che $n$ divide $x-y$, e $0\le y<n$. Questo può essere letto come:$y$ è $x$ modulo $n$. Tale numero intero$y$ è definito in modo univoco per un dato $(n,x)$. Quello$y$è il resto della divisione euclidea di$x$ di $n$ quando $x\ge0$.