Tìm thấy câu trả lời.
Đầu tiên, tôi sẽ thay đổi ký hiệu một chút để các phương trình trở nên đối xứng hơn một chút.
Sử dụng ký hiệu này, từ bản rõ $PH$ trong bài báo của Matsui trở thành $x_0$, và $PL$ trở thành $x_1$. Từ bản mã $CH$ trở thành $x_{n+1}$, và $CL$ trở thành $x_n$.
Chúng ta có thể tìm thấy một xấp xỉ $n$ làm tròn thông qua tìm kiếm đồ thị. Một nút trong biểu đồ này sẽ trông như thế này:
$$
\bigoplus_{i=0}^{n+1} x_i[\delta_i] = \bigoplus_{i=1}^n k_i[\epsilon_i] \tag{1}
$$
ở đâu $\delta_i$ và $\epsilon_i$ là bitmasks.
Để xem các cạnh là gì, giả sử chúng ta có xấp xỉ 1 vòng như sau:
$$
x[\alpha] \oplus F(x, k)[\beta] = k[\gamma] \tag{2}
$$
Chúng ta có thể khởi tạo nó ở vòng, nói, $i$, để có được:
$$
x_i[\alpha] \oplus F(x_i, k_i)[\beta] = k_i[\gamma] \tag{3}
$$
và bây giờ chúng ta có thể sử dụng cấu trúc Feistel, biết rằng $x_{i+1} = x_{i-1} \oplus F(x_i, k_i)$, để viết lại $F(x_i, k_i)$ như $x_{i+1} \oplus x_{i-1}$, và vì thế:
$$
x_i[\alpha] \oplus \left(x_{i+1} \oplus x_{i-1}\right)[\beta] = k_i[\gamma] \tag{4}
$$
Đây sẽ là một cạnh trong biểu đồ của chúng tôi. Nghĩa là, đối với tất cả các xấp xỉ tuyến tính và đối với tất cả các vòng khởi tạo $i$, chúng ta có thể tạo ra một cạnh như vậy. Nếu nguồn của cạnh là phương trình $(1)$, mục tiêu của cạnh là phương trình sau, thu được bởi $\operatorname{XOR}$ing $(1)$ và $(4)$:
$$
\bigoplus_{j=0}^{i-2} x_j[\delta_j] \oplus x_{i-1}[\delta_{i-1} \oplus \beta] \oplus x_i[\delta_i \oplus \alpha] \oplus x_{i+1}[\delta_{i+1} \oplus \beta] \bigoplus_{j=i+2}^{n+1} x_j[\delta_j] = k_i[\epsilon_j \oplus \gamma ] \bigoplus_{j=1}^n k_j[\epsilon_j] \tag{5}
$$
Một $n$xấp xỉ -round là một nút như vậy $(1)$, khẩu trang ở đâu $\delta_2 \dots \delta_{n-1}$ là tất cả $0$. Nghĩa là, phương trình chỉ liên quan đến bản rõ, bản mã và khóa.
Chúng tôi bắt đầu tìm kiếm đồ thị của mình với một xấp xỉ tầm thường, trong đó $\forall i, \delta_i = 0$, và $\forall i, \gamma_i = 0$. Để xem những cạnh nào chúng ta thực sự sẽ lấy, một chút danh pháp:
- Một bang $x_i$ được gọi là "ẩn" khi $1 < i < n$. Đó là, nó không phải là một bản rõ cũng không phải là một bản mã. Một cái mặt nạ $\delta_i$ được gọi là "ẩn" trong cùng điều kiện.
Chúng tôi sẽ chỉ có một lợi thế $e$, đưa chúng ta từ một nút $v: \bigoplus_{i=0}^{n+1} x_i[\delta_i] = \bigoplus_{i=1}^n k_i[\epsilon_i]$ đến một nút $w: \bigoplus_{i=0}^k x_i[\delta'_i] = \bigoplus_{i=1}^k k_i[\epsilon'_i]$, khi có nhiều nhất 2 mặt nạ ẩn trong $w$ là khác không.
Chúng tôi đạt đến trạng thái kết thúc khi tất cả các mặt nạ ẩn bằng 0 và chúng tôi không ở nút bắt đầu.
Chúng tôi sử dụng bổ đề chồng chất để tính trọng số khi chúng tôi thực hiện, điều mà chúng tôi có thể thực hiện trong không gian log để cải thiện độ chính xác.
Dưới đây là mã nguồn C++ để sao chép bảng kết quả của Matsui trong phần phụ lục. Tôi đã sử dụng thuật toán Dijkstra để tìm kiếm đồ thị, nhưng thực sự nó quá mức cần thiết, một giải pháp lập trình động cũng sẽ làm được. Điều này là do các đường dẫn duy nhất mà chúng ta quan tâm đang tăng lên ở vị trí mà chúng áp dụng các phép tính gần đúng một vòng (tức là chúng bắt đầu với phép tính gần đúng rỗng và áp dụng nó ở các vòng, chẳng hạn như 1, 2, 3, 5, 6, 8, 9, 10 và đạt đến trạng thái cuối cùng). Tuy nhiên, Dijkstra đã chạy ngay lập tức, vì vậy không cần phải suy nghĩ quá nhiều về nó.
Điều duy nhất dành riêng cho DES ở đây là các xấp xỉ một vòng one_round_approximations. Việc sửa đổi làm cho điều này tìm thấy các chuỗi tuyến tính cho bất kỳ mạng Feistel nào, được tính gần đúng với hàm vòng.
Vì NUM_ROUNDS = 10, mã này xuất ra:
xấp xỉ tốt nhất:
round_number: 10
mặt nạ trạng thái = [1: [7, 18, 24, 29], 10: [15], 11: [7, 18, 24, 29]]
mặt nạ phím = [1: [22], 2: [44], 3: [22], 5: [22], 6: [44], 7: [22], 9: [22]]
xấp xỉ được áp dụng: [-ACD-DCA-A]
Xác suất: 0,500047
Log2(Độ lệch): -14.3904
hoàn toàn khớp với bài báo của Matsui.
#bao gồm <mảng>
#bao gồm <cstdint>
#include <iostream>
#bao gồm <bộ>
#include <bản đồ không có thứ tự>
#include <xác nhận>
#bao gồm <vectơ>
#include <cmath>
#bao gồm <tùy chọn>
constexpr size_t NUM_ROUNDS = 10;
std::ostream& show_mask(std::ostream& o, uint64_t m) {
int tôi = 0;
bool đầu tiên = đúng;
o<<"[";
trong khi (m) {
nếu (m & 1) {
nếu (!đầu tiên) {
o << ", ";
} khác {
đầu tiên = sai;
}
o<<i;
}
m >>= 1;
++i;
}
o<<"]";
trở lại o;
}
struct Xấp xỉ OneRound {
const char* tên;
uint32_t alpha;
uint32_t phiên bản thử nghiệm;
uint64_t gamma;
nhân đôi log2_bias;
xác suất kép() const {
gấp đôi x = std::pow(2.0, log2_bias) + 0.5;
trả lại std::max(x, 1.0 - x);
}
toán tử tự động kết bạn<=>(const OneRoundApproximation&,
const OneRoundApproximation&) = mặc định;
bạn std::ostream& toán tử<<(std::ostream& o,
const OneRoundApproximation& ra) {
o << ra.name;
trở lại o;
}
};
Xấp xỉ cấu trúc {
std::array<uint32_t, NUM_ROUNDS + 2> state_mask;
std::array<uint64_t, NUM_ROUNDS> round_key_mask;
std::array<std::tuỳ chọn<Xấp xỉ một vòng>, NUM_ROUNDS>
áp dụng_xấp xỉ;
int vòng_số;
toán tử tự động kết bạn<=>(const Xấp xỉ&, const Xấp xỉ&) = mặc định;
bạn std::ostream& toán tử<<(std::ostream& o, const Approximation& a) {
o << "số_vòng: " << a.số_vòng<< std::endl;
o << "bang mask = [";
int cnt = 0;
for (size_t i = 0; i < NUM_ROUNDS + 2; ++i) {
nếu (!a.state_mask[i]) tiếp tục;
if (cnt++ > 0) o << ", ";
o<<i<<":";
show_mask(o, a.state_mask[i]);
}
o << "]" << std::endl;
cnt = 0;
o << "key mask = [";
for (size_t i = 0; i < NUM_ROUNDS; ++i) {
nếu (!a.round_key_mask[i]) tiếp tục;
if (cnt++ > 0) o << ", ";
o<<i<<":";
show_mask(o, a.round_key_mask[i]);
}
o << "]" << std::endl;
o << "áp dụng xấp xỉ: [";
for (size_t i = 0; i < NUM_ROUNDS; ++i) {
auto ma = a.applied_approximations[i];
if (ma == std::nullopt) {
o<<"-";
} khác {
o << *ma;
}
}
o << "]" << std::endl;
trở lại o;
}
};
struct Xấp xỉ có trọng số {
Xấp xỉ a;
nhân đôi log2_bias;
xác suất kép() const {
gấp đôi x = std::pow(2.0, log2_bias) + 0.5;
trả lại std::max(x, 1.0 - x);
}
};
std::array<OneRoundApproximation, 5> one_round_approximations = {{
{"A", 0x8000, 0x21040080, 0x400000, std::log2(std::abs(12.0/64.0 - 0.5))},
{"B", 0xd8000000, 0x8000, 0x6c0000000000ULL, std::log2(std::abs(22.0/64.0 - 0.5))},
{"C", 0x20000000, 0x8000, 0x100000000000ULL, std::log2(std::abs(30.0/64.0 - 0.5))},
{"D", 0x8000, 0x1040080, 0x400000, std::log2(std::abs(42.0/64.0 - 0.5))},
{"E", 0x11000, 0x1040080, 0x880000, std::log2(std::abs(16.0/64.0 - 0.5))}
}};
Xấp xỉ apply_one_round_approximation(const Xấp xỉ & a,
const Xấp xỉ OneRound& o,
size_t vị trí) {
Xấp xỉ b = a;
b.vòng_số = vị trí + 1;
b.state_mask[vị trí] ^= o.beta;
b.state_mask[vị trí + 1] ^= o.alpha;
b.state_mask[vị trí + 2] ^= o.beta;
b.round_key_mask[vị trí] ^= o.gamma;
b.applied_approximations[vị trí] = o;
trả lại b;
}
size_t HiddenSize(Xấp xỉ & b) {
size_t kết quả = 0;
for (size_t i = 2; i < NUM_ROUNDS; ++i) {
kết quả += b.state_mask[i] != 0;
}
trả về kết quả;
}
std::vector<Xấp xỉ có trọng số> Chuyển tiếp(
const Xấp xỉ Trọng số& a, const Xấp xỉ Một vòng& o) {
kết quả std::vector<Xấp xỉ có trọng số>;
for (size_t i = a.a.round_number; i < NUM_ROUNDS; ++i) {
Xấp xỉ b = apply_one_round_approximation(a.a, o, i);
nếu (HiddenSize(b) > 2) tiếp tục;
kết quả.push_back(
{.a = std::move(b),
.log2_bias = 1 + a.log2_bias + o.log2_bias});
}
trả về kết quả;
}
std::ostream& toán tử<<(std::ostream& o, const WeightedApproximation& wa) {
o << wa.a << std::endl;
o << "Xác suất: " << wa.probability() << std::endl;
o << "Log2(Độ lệch): " << wa.log2_bias << std::endl;
trở lại o;
}
mẫu <lớp T>
inline void hash_combine(std::size_t& seed, const T& v) {
std::hash<T> hasher;
hạt giống ^= hasher(v) + 0x9e3779b9 + (hạt giống << 6) + (hạt giống >> 2);
}
size_t HashApproximation(const Approximation& a) {
size_t h = 0;
for (size_t i = 0; i < NUM_ROUNDS + 2; ++i) {
hash_combine(h, a.state_mask[i]);
}
hash_combine(h, a.round_number);
trả lại h;
};
int main() {
tự động so sánh_by_probability = [](const WeightedApproximation& a,
const Xấp xỉ Trọng số& b) {
nếu (a.log2_bias > b.log2_bias) trả về true;
nếu (a.a.round_key_mask < b.a.round_key_mask) trả về true;
trả về Xấp xỉ Hash(a.a) < Xấp xỉ Hash(b.a);
};
std::set<WeightedApproximation, decltype(compare_by_probability)> hàng đợi;
std::unordered_map<Xấp xỉ, decltype(queue.begin()),
decltype(&HashApproximation)>
đã thấy(1, &Xấp xỉ hàm băm);
Xấp xỉ có trọng số wa = {.a = Xấp xỉ{},
.log2_bias = std::log2(0,5)};
auto it = queue.insert(wa).first;
đã thấy.emplace(wa.a, nó);
Xấp xỉ có trọng số best_approximation = wa;
trong khi (!queue.empty()) {
WeightedApproximation v = queue.extract(queue.begin()).value();
đã thấy[v.a] = queue.end();
if (v.a.round_number == NUM_ROUNDS && HiddenSize(v.a) == 0) {
nếu (best_approximation.a.round_number == 0 ||
best_approximation.log2_bias < v.log2_bias) {
best_approximation = v;
}
tiếp tục;
}
for (const auto& o : one_round_approximations) {
for (Xấp xỉ có trọng số w : Chuyển tiếp(v, o)) {
tự động nó = đã thấy.find(w.a);
nếu (nó == đã thấy.end()) {
auto [jt, đã chèn] = queue.insert(std::move(w));
khẳng định (đã chèn);
đã thấy.emplace(jt->a, std::move(jt));
} khác {
if (it->second == queue.end()) tiếp tục;
if (it->second->log2_bias < w.log2_bias) {
queue.erase(it->second);
auto jt = queue.insert(w).first;
nó->thứ hai = jt;
}
}
}
}
}
std::cout << "Xấp xỉ tốt nhất: " << std::endl
<< best_approximation << std::endl;
}
```
