Вычислить ключ OTP, если известно множество простых текстов и его набор зашифрованных текстов.

Дан набор простых текстов $P \subseteq \{0, 1\}^n$. Предположим, что мы знаем соответствующий набор шифротекстов $C \subseteq\{0, 1\}^n$ производится путем применения одноразового блокнота с неизвестным ключом $k \in \{0, 1\}^n$.

Вопрос: Как рассчитать $к$, на основе $P$ и $С$?

Мой подход: Для каждой пары $(p, c) \in P \times C$, вычислить ключ $k' = p \oplus c$. Вывести ключ наиболее часто встречающийся ключ $к'$.

Мой вопрос: какова вероятность успеха предложенного алгоритма?

Проблема с этим подходом заключается в том, что наиболее частый ключ $к'$ в некоторых случаях уникален. В некоторых других случаях $к'$ не уникален. Например, когда $P = C = \{0, 1\}^n$.

Учитывая, что у нас есть наборы $P$ и $С$, найти $к$, нам нужно только найти (одну из) пар $(p,c)\in P \times C$ с.т. $p \oplus k = c$, как и в случае с этой парой, $к$ вычислить тривиально.

Во-первых, можно отметить свойство, состоящее в том, что для заданных двух соответствующих пар $(p_1, c_1)$ и $(p_2, c_2) \in P \times C$, $c_1 \oplus c_2 = p_1 \oplus p_2$ - другими словами, разница между двумя шифротекстами такая же, как и разница между соответствующими им шифротекстами.

Мы можем использовать это, чтобы определить, какие из наших открытых текстов соответствуют шифротекстам, предполагая, что $c_i \ne c_j$, множество разностей, $d_i^c$, для данного $c_i$ со всеми другими словами в $С$ будет уникальным. То же самое верно для заданного $p_i$, с $d_i^p \ne d_j^p$ для любого другого набора различий для другого открытого текста в $P$, однако для соответствующих пар зашифрованных текстов открытого текста эти различия будут одинаковыми.

Например, если $p_1$ шифрует в $c_1$, тогда $d_1^p = d_1^c$, и мы можем соединить эти два, поскольку мы знаем, что эти различия уникальны для данного открытого текста/зашифрованного текста.

Тогда это позволяет вычислить $k = p_1 \oplus c_1$.