Vấn đề chung / Giới thiệu: mã hóa mối quan hệ (có thể tính toán) giữa hai số ngẫu nhiên là thành viên của một tập hợp nhỏ nhất có thể trong khi bất kỳ thứ gì ngoại trừ thứ tự thực hiện đều được kẻ thù biết.
Câu hỏi này là về việc giải quyết vấn đề đó bằng cách ghép khối mật mã.
đơn giản hóa:
- chúng tôi chỉ xem xét mật mã khối tương tự như AES
- thay vì $N$ mật mã khối khác nhau, chúng tôi sử dụng một mật mã khối với $N$ các phím khác nhau (hoặc thậm chí nhiều hơn)
- mật mã khối chỉ chuyển một đầu vào sang đầu vào khác (để chúng chạy ở chế độ ECB)
Những gì được biết:
Nếu chúng ta áp dụng mật mã khối $BC$ đến một đầu vào nhất định $m$ lặp đi lặp lại chúng ta sẽ lại đạt được đầu vào vào một thời điểm nào đó.
$$BC^l(m,k) = m$$
Đối với một đầu vào ngẫu nhiên nhất định $m$ và chìa khóa $k$ chiều dài chu kỳ $l$ có thể là mọi chiều dài từ $1$ với kích thước miền của $m$ với (trong trường hợp tối ưu) cùng một xác suất.
(khá chắc chắn đó cũng là trường hợp :)
Nếu chúng ta sử dụng $N$ các khóa khác nhau và nối mật mã khối với các khóa đó với nhau (luôn có cùng thứ tự & luôn là bội số của $N$ bước), chúng tôi dẫn đến độ dài chu kỳ $N$ lần $[1,..,D]$ với $D$ kích thước miền của m.
$$BC(....BC(...BC(..BC(BC(BC(m,k_0),k_1),k_2)..,k_{N-1})...,k_{i \mod{N}})....,k_{l \equiv N-1 \mod{N}}) = m$$
Chúng ta có thể xem phép nối này như áp dụng các vòng bên trong một BC.
Áp dụng nó cho vấn đề chung từ trên:
Đối với điều này, thứ tự thực hiện (do đó, thứ tự của các khóa được sử dụng) không được biết đối với kẻ thù (nhưng bản thân các khóa được biết).
Ví dụ một giá trị $V$ có thể được tính ra khỏi giá trị $W$ với:
$$BC(BC(BC(BC(BC(W,k_5),k_2),k_3,k_5,k_1,k_1) =V$$
Đối phương biết $V,W$ và bao giờ cũng có khóa riêng nhưng anh ấy muốn biết thứ tự thực hiện khóa $5,2,3,5,1,1$ hoặc bất kỳ thứ tự nào khác cũng thực hiện công việc.
Nếu chúng tôi không sử dụng thứ tự khóa cố định nữa, các thuộc tính kích thước chu kỳ không còn hiệu lực nữa.
Thử nghiệm giải pháp 1 (thất bại):
Nếu đối thủ muốn tìm một lệnh thực hiện chuyển $W \rightarrow V$
anh ấy có thể tính toán $N$ các giá trị tiếp theo có thể có của $W$ và $N$ các giá trị trước đó có thể có của $V$ ngược với BC. Anh ta có thể lặp lại điều này cho đến khi tìm thấy một mach.
Với điều này, anh ta sẽ tìm thấy một lệnh thực hiện có nghĩa là khoảng $\sqrt{D}$ các bước không đủ an toàn.
Thử nghiệm giải pháp 2 (thất bại):
Để bảo mật cao hơn, chúng tôi giới hạn kết quả $V$ đến các giá trị đã được tính toán bằng cách sử dụng $i$-th chìa khóa tại tính toán BC cuối cùng của họ.
Đối thủ chỉ có thể sử dụng BC nghịch đảo lúc này $V$ với mục tiêu $i$-th và làm tương tự như trong giải pháp dùng thử 1.
Thử nghiệm giải pháp 3 (câu hỏi/chỉnh sửa: không thành công...):
Để đạt được bảo mật, chúng tôi có thể giới hạn số lần thực hiện thành bội số của $E$ các bước và điều này cũng làm thay đổi các phím của từng độ sâu.
Bên cạnh việc sử dụng $i$-th BC chìa khóa để tính toán của $V$ bây giờ nó cũng cần phải là bội số của $E$ bước trước $W$
trong ví dụ của chúng tôi từ trên với $E=3$ đó sẽ là:
$$BC(BC(BC(BC(BC(W,k_5^0),k_2^1),k_3^2,k_5^0,k_1^1,k_1^2) =V$$
Vì vậy, cho một nhất định $V$ với $i$-phím cuối cùng ở độ sâu $d$ đối thủ có thể tính toán mối quan hệ với một nhất định $W$ với chiều sâu $d$:
Tính nghịch đảo của $V$:
$$BC^{-1}(V,k_i^{d-1 \mod E}) = V'$$
Và tính toán các giá trị từng bước như anh ấy đã làm trong thử nghiệm giải pháp 1.
Điều này sẽ mất khoảng $N^{\lfloor{\frac{E-1}{2}}\rfloor}$ thử nghiệm nếu anh ta đang làm điều đó vũ phu.
nếu ví dụ $D=2^{128}, N=2^{16}, E=2^{5}$ điều này sẽ $2^{16 \cdot 15} = 2^{240}$ thử nghiệm.
.... sau khi viết hết bài này tôi nhận thấy anh ấy không cần phải tính toán mọi phần của mọi chiều sâu và chỉ cần $\sqrt{D}$ lại bước...
=====>
Câu hỏi: Có ai có bất kỳ ý tưởng nào khác về cách kết hợp mật mã khối có thể an toàn hơn không (gần $D$)?
lịch sử
- $D$ kích thước của bộ đầu vào và đầu ra
- $V,W$ các giá trị ngẫu nhiên có thể có tới $D$ các giá trị khác nhau
- $E$ tổng số lần thực thi mật mã khối cần phải là bội số của $E$
- $N$ số khóa mật mã khối khác nhau cho mỗi độ sâu
- $k_a^b$ biến khóa được sử dụng cho mật mã khối có chỉ số $a,b$ với $a\in\{0,N-1\}, b\in\{0,E-1\}$