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.
// Tìm chuỗi xấp xỉ tuyến tính trong mật mã Feistel.
//
// Một vòng mật mã Feistel có thể được mô tả như sau:
// x0 x1
// | k|
// | | |
// v v |
// + <- F ---
// | |
// vv
// x2
//
// Trong đó + là bitwise xor và F là hàm hoán vị có khóa. đại số,
// x2 = x0 + F(k, x1) (1)
// Dây mang x1 không đổi, đổi chỗ cho x2
// trước vòng tiếp theo trong mạng Feistel. Toàn bộ mạng sau đó nhìn
// như thế này, trong đó ===><== có nghĩa là chúng ta hoán đổi hai dây:
// x0 x1
// | k1 |
// | | |
// v v |
// + <- F ---
// | |
// vv
// x2 x1
// | |
// x1===><==x2
// | |
// | k2 |
// | | |
// v v |
// + <- F ---
// | |
// vv
// x3 x2
// | |
//...
//
//
// Xấp xỉ một vòng đối với F là ba mặt nạ bit, alpha, beta, gamma, chẳng hạn
// điều đó
// x[alpha] + F(x, k)[beta] = k[gamma]
// giữ với một số xác suất p. Ở đây ký hiệu a[m] có nghĩa là chúng ta xor
// các bit trong chuỗi bit a, được biểu thị bằng mặt nạ m. Vì vậy, một [0b101] có nghĩa là
// ((a & 100) >> 2) ^ (a & 1).
//
// Chúng tôi lưu ý rằng phương trình (1) cho chúng tôi biết rằng F(k, x1) = x2 ^ x0. Nói chung, nếu chúng ta
// xem vòng thứ i phương trình (1) cho ta biết
// F(x_{i + 1}, k_{i + 1}) = x_{i + 2} + x_i (2)
//
// Do đó, nếu chúng ta có một xấp xỉ như:
//
// x[alpha] + F(x, k)[beta] = k[gamma]
//
// Chúng ta có thể khởi tạo nó ở bất kỳ vòng nào, ví dụ:
//
// x1[alpha] + F(x1, k1)[beta] = k1[gamma]
//
// Và sau đó sử dụng phương trình (2) để viết lại thành:
//
// x1[alpha] + (x2 + x0)[beta] = k1[gamma]
//
// Theo cách này, chúng ta thu được phương trình cho các giá trị của dây trong Feistel
// mạng. Nói chung, chúng sẽ luôn có dạng:
//
// x_{i + 1}[alpha] + (x_{i + 2} + x_i)[beta] = k_{i + 1}[gamma] (3)
//
// Mục tiêu của chúng ta là bắt đầu với một phương trình rất đơn giản:
//
// x0[0] + x1[0] = 0
//
// đúng với xác suất 1, và áp dụng các phương trình này, chúng ta đạt được một
// phương trình chỉ bao gồm:
// * x0, từ cao trong bản rõ.
// * x1, từ thấp trong bản rõ.
// * x_{n+1}, từ cao nhất trong bản mã.
// * x_n, từ thấp trong bản mã.
// * Một số phím tròn k_i.
// và chúng tôi muốn biết xác suất mà chúng nắm giữ. Chúng tôi gọi loại này
// của phương trình xấp xỉ tuyến tính của mật mã đầy đủ.
//
// Chương trình này xem xét một biểu đồ trong đó mỗi nút có dạng:
// (m_0, m_1, ..., m_{N+1}, km_0, km_1, ..., km_0, p)
// trong đó N là số vòng, mỗi m_i là một mặt nạ bit 32 bit, mỗi km_i là một
// Mặt nạ bit 64 bit và p là xác suất. Ý nghĩa của nút này là:
//
// với xác suất p,
// (\sum_{i=0}^{N + 1} x_i[m_i]) + (\sum_{i=0}^{N-1} k_i[km_i]) = 0
//
// trong đó x_i là giá trị của các dây trong mạng Feistel, k_i là
// các phím tròn, m_i là mặt nạ bit cho x_i và km_i là mặt nạ cho k_i.
//
// Bắt đầu từ nút m_i = 0 cho tất cả i và km_j = 0 cho tất cả j và p =
// 1, chúng tôi muốn đạt đến trạng thái đại diện cho xấp xỉ tuyến tính của
// mật mã đầy đủ.
//
// Các cạnh của biểu đồ này sẽ sử dụng một số xấp xỉ 1 vòng,
// khởi tạo tại một số vòng trong mạng. Chẳng hạn, nếu chúng ta có nút
//
// x_0[0b101] + x_1[0b11] = k_1[0b110] (4)
//
// và chúng ta biết phương trình dạng (3):
// x_{i+1}[0b1011] + (x_{i + 2} + x_i)[0b11] = k_{i + 1}[0b101]
//
// chúng ta có thể khởi tạo cái này tại i = 1, để có được
//
// x_2[b1011] + (x_3 + x_1)[0b11] = k_2[0b101] (5)
// Nếu ta xor phương trình (5) này với (4), ta được
//
// x_0[0b101] + x_2[0b1011] + x_3[0b11] = k_1[0b110] + k_2[0b101]
//
// đó là một nút khác trong biểu đồ của chúng tôi. Bằng cách này, chúng tôi khám phá biểu đồ cho đến khi chúng tôi
// đạt xấp xỉ tuyến tính của mật mã đầy đủ.
#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;
// Hiển thị mặt nạ bit 64 bit, chỉ hiển thị các chỉ số bit đang "bật".
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;
}
// Ý nghĩa của xấp xỉ này là với xác suất p = xác suất(),
// x[alpha] + F(x, k)[beta] = k[gamma]
// Đối với bất kỳ chuỗi 32 bit x và chuỗi 48 bit k.
//
// Độ lệch được định nghĩa là |xác suất() - 0,5|.
struct Xấp xỉ OneRound {
const char* tên;
uint32_t alpha;
uint32_t phiên bản thử nghiệm;
uint64_t gamma; // Chỉ cần 48 bit.
nhân đôi log2_bias; // log_2(độ lệch)
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;
}
};
// Đây là một xấp xỉ liên quan đến một số bit bản rõ, một số bản mã
// bit, một số bit chính, và có thể là một số bit trạng thái ẩn, theo cách tuyến tính,
// sử dụng mặt nạ bit cố định.
//
// 2 trạng thái đầu là 2 bản rõ, 2 trạng thái cuối là 2
// từ bản mã và mọi trạng thái khác là trạng thái ẩn - đó là giá trị
// của một dây trong mạng Feistel.
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;
}
};
// Đây là một giá trị gần đúng với xác suất cho trước.
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))}
}};
// Với một xấp xỉ hiện có, điều gì sẽ xảy ra nếu chúng ta xor một vòng
// xấp xỉ vào nó? Cụ thể, xấp xỉ một vòng đó sẽ là
// khởi tạo tại vòng `vị trí`.
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;
}
// Trả về có bao nhiêu trạng thái ẩn có mặt nạ khác 0 trong trường hợp đã cho
// xấp xỉ.
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) {
// Đối với một xấp xỉ nhất định của j vòng đầu tiên của mật mã, chúng ta có thể áp dụng
// xấp xỉ vòng ở trạng thái hiện tại trong mạng Feistel,
// hoặc cái tiếp theo. Đó là, xấp xỉ một vòng có dạng:
// alpha * x_{i + 1} + beta * (x_{i+2} + x_i) = gamma * k_i
// Có thể được xorred vào trạng thái hiện tại, có dạng:
//
// \sum_{k=0}^N state_mask_k * x_k + \sum_{k=0}^N key_mask * key_i = 0
//
// Trong đó tổng là xor của mọi bit trong đối số.
//
// Điều này sẽ làm cho một số state_masks bằng 0 và một số khác không. Chúng tôi chỉ muốn
// thực hiện quá trình chuyển đổi khi số lượng mặt nạ khác không cho các trạng thái ẩn là
// nhiều nhất là 2, bởi vì đây là tất cả những gì cần thiết để đạt được tiến bộ trong
// Các mạng Feistel mà chúng tôi đã thấy (DES). Một trạng thái bị ẩn khi nó không phải là x_1,
// x_2, x_{N-1} hoặc x_N. Đó là, khi nó không phải là một trong hai bản rõ
// từ, cũng không phải một trong hai từ bản mã.
// Điều này có thể được thực hiện nhanh hơn và tiết kiệm không gian hơn, nhưng tôi không đặc biệt
// quan tâm đến bây giờ.
// Chúng tôi tìm kiếm một vòng để khởi tạo xấp xỉ một vòng.
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;
}
// Chỉ là một hàm băm tiêu chuẩn để có thể đưa các xấp xỉ vào một hàm băm
// cái bàn.
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() {
// Chúng ta sẽ sử dụng thuật toán Dijkstra để khám phá đồ thị này. Trọng lượng của một cạnh
// là log2 của độ lệch của xấp xỉ một vòng mà nó đại diện.
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);
};
// Đây là hàng đợi của các nút mà chúng ta vẫn phải truy cập.
std::set<WeightedApproximation, decltype(compare_by_probability)> hàng đợi;
// Điều này cho chúng tôi biết những nút nào đã được truy cập. Lưu ý trong hàng đợi chúng tôi lưu trữ
// các nút có trọng số, trong khi hàm băm này chỉ lưu trữ giá trị gần đúng
// chính nó, không có xác suất. Điều này là để có thể sửa đổi ước tính
// trọng số của mỗi xấp xỉ khi chúng ta duyệt đồ thị, theo Dijkstra's
// thuật toán.
std::unordered_map<Xấp xỉ, decltype(queue.begin()),
decltype(&HashApproximation)>
đã thấy(1, &Xấp xỉ hàm băm);
// Xấp xỉ ban đầu của chúng ta không có mặt nạ, và đúng với xác suất 1, và
// nên độ lệch của nó là 1 - 0,5 = 0,5..
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ó);
// Chúng tôi theo dõi xấp xỉ tốt nhất mà chúng tôi đã thấy cho đến nay. Duy nhất
// các giá trị gần đúng mà chúng ta sẽ quan tâm là những giá trị liên quan đến bản rõ,
// bản mã và bit khóa. Đối với điều này, họ phải có một số tròn
// NUM_ROUNDS. Điều này có nghĩa là `wa` thực sự không phải là một giá trị gần đúng hợp lệ nhất cho
// mật mã đầy đủ và sẽ được ghi đè lần đầu tiên khi chúng tôi tìm thấy bất kỳ mã hợp lệ nào
// xấp xỉ.
Xấp xỉ có trọng số best_approximation = wa;
trong khi (!queue.empty()) {
WeightedApproximation v = queue.extract(queue.begin()).value();
// Chúng tôi báo hiệu rằng nó đã được đưa ra khỏi hàng đợi.
đã thấy[v.a] = queue.end();
// Nếu đây là giá trị gần đúng của mật mã đầy đủ (nghĩa là tất cả NUM_ROUNDS của
// nó), và không liên quan đến bất kỳ trạng thái ẩn nào (nghĩa là chỉ có văn bản rõ,
// bản mã và các bit khóa), thì đó là một ứng cử viên sáng giá cho vị trí tốt nhất
// xấp xỉ tuyến tính cho toàn bộ mật mã. Chúng tôi sẽ giữ khả năng nhất
// một, đó là cái có độ chệch cao nhất.
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;
}
// Bây giờ chúng ta duyệt qua tất cả các cạnh đi ra từ xấp xỉ`v`, bằng cách liệt kê tất cả
// các xấp xỉ một vòng khả thi mà chúng ta có thể áp dụng ở phép tính gần đúng này.
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()) {
// Nếu chúng ta chưa bao giờ nhìn thấy xấp xỉ này trước đây, hãy thêm nó vào hàng đợi,
// và đánh dấu nó là đã xem. Đây phải là một phần tử mới trong hàng đợi và
// chúng tôi khẳng định như vậy.
auto [jt, đã chèn] = queue.insert(std::move(w));
khẳng định (đã chèn);
đã thấy.emplace(jt->a, std::move(jt));
} khác {
// Chúng ta đã thấy nó trước đây. Nếu chúng tôi đã đưa nó ra khỏi hàng đợi,
// không cần làm gì cả, chúng ta đã tìm được đường cân ngắn nhất
// với nó, theo bất biến của thuật toán Dijkstra..
if (it->second == queue.end()) tiếp tục;
// Thư giãn cạnh nếu có thể.
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;
}
```
