Tính khóa OTP nếu biết tập văn bản thuần túy và tập văn bản mật mã của nó

Đưa ra một tập hợp các văn bản đơn giản $P \subseteq \{0, 1\}^n$. Giả sử chúng ta biết bộ văn bản mật mã tương ứng $C \subseteq \{0, 1\}^n$ được tạo bằng cách áp dụng bàn phím một lần với khóa không xác định $k \in \{0, 1\}^n$.

Hỏi: Cách tính $k$, dựa trên $P$ và $C$?

Cách tiếp cận của tôi: Đối với mỗi cặp $(p, c) \in P \times C$, tính khóa $k' = p \oplus c$. Xuất khóa thường xuyên nhất $k'$.

Câu hỏi của tôi: Xác suất thành công của thuật toán đề xuất là gì?

Vấn đề với cách tiếp cận này là khóa thường xuyên nhất $k'$ là duy nhất trong một số trường hợp. Trong một số trường hợp khác, $k'$ không phải là duy nhất. Ví dụ, khi $P = C = \{0, 1\}^n$.

Cho rằng chúng ta có các bộ $P$ và $C$, để tìm $k$, chúng ta chỉ cần tìm (một trong) các cặp $(p,c)\in P \times C$ s.t. $p \oplus k = c$, như với cặp này, $k$ là tầm thường để tính toán.

Đầu tiên, chúng ta có thể lưu ý tính chất đã cho hai cặp tương ứng $(p_1, c_1)$ và $(p_2, c_2) \in P \times C$, $c_1 \oplus c_2 = p_1 \oplus p_2$ - nói cách khác, sự khác biệt giữa hai bản mã giống như sự khác biệt giữa các bản mã tương ứng của chúng.

Chúng ta có thể sử dụng điều này để bản rõ của chúng ta tương ứng với bản mã, như giả sử $c_i \ne c_j$, tập hợp các khác biệt, $d_i^c$, để cho $c_i$ với tất cả các từ khác trong $C$ sẽ là duy nhất. Điều tương tự cũng xảy ra đối với một số đã cho $p_i$, với $d_i^p \ne d_j^p$ đối với bất kỳ tập hợp khác biệt nào khác đối với một bản rõ khác trong $P$, tuy nhiên đối với các cặp bản mã bản rõ tương ứng, những khác biệt này sẽ giống nhau.

Ví dụ, nếu $p_1$ mã hóa thành $c_1$, sau đó $d_1^p = d_1^c$, và chúng tôi có thể ghép hai cái này vì chúng tôi biết những khác biệt này là duy nhất đối với bản rõ/bản mã đã cho.

Điều này sau đó cho phép chúng tôi tính toán $k = p_1 \oplus c_1$.