Calculați cheia OTP dacă se cunoaște setul de texte simple și setul său de texte cifrate

Dat un set de texte simple $P \subseteq \{0, 1\}^n$. Să presupunem că cunoaștem setul corespunzător de texte cifrate $C \subseteq \{0, 1\}^n$ produs prin aplicarea unui tampon unic cu o cheie necunoscută $k \in \{0, 1\}^n$.

Întrebare: Cum se calculează $k$, bazat pe $P$ și $C$?

Abordarea mea: Pentru fiecare pereche $(p, c) \in P \times C$, calculează cheia $k' = p \oplus c$. Ieșiți cheia cea mai frecventă cheie $k'$.

Întrebarea mea: Care este probabilitatea de succes a algoritmului propus?

Problema cu această abordare este că cea mai frecventă cheie $k'$ este unică în unele cazuri. În alte cazuri, $k'$ nu este unic. De exemplu, când $P = C = \{0, 1\}^n$.

Având în vedere că avem seturile $P$ și $C$, a găsi $k$, trebuie doar să găsim (una dintre) perechi $(p,c)\în P \times C$ Sf. $p \oplus k = c$, ca și în cazul acestei perechi, $k$ este banal de calculat.

În primul rând, putem observa proprietatea care a dat două perechi corespunzătoare $(p_1, c_1)$ și $(p_2, c_2) \in P \times C$, $c_1 \oplus c_2 = p_1 \oplus p_2$ - cu alte cuvinte, diferența dintre două texte cifrate este aceeași cu diferența dintre textele lor cifrate corespondente.

Putem folosi acest lucru pentru care dintre textele noastre clare corespund textelor cifrate, ca presupunere $c_i \ne c_j$, setul de diferențe, $d_i^c$, pentru un dat $c_i$ cu toate celelalte cuvinte în $C$ va fi unic. Același lucru este valabil și pentru un dat $p_i$, cu $d_i^p \ne d_j^p$ pentru orice alt set de diferențe pentru un text simplu diferit în $P$, cu toate acestea, pentru perechile de text cifrat corespunzătoare, aceste diferențe vor fi aceleași.

De exemplu, dacă $p_1$ criptează la $c_1$, atunci $d_1^p = d_1^c$, și putem împerechea aceste două deoarece știm că aceste diferențe sunt unice pentru textul simplu/textul cifrat dat.

Acest lucru ne permite apoi să calculăm $k = p_1 \oplus c_1$.