Нашел ответ.
Во-первых, я немного изменю обозначения, чтобы уравнения стали немного более симметричными.
Используя эту нотацию, слово открытого текста $PH$ в статье Мацуи становится $x_0$, и $PL$ становится $x_1$. Зашифрованное слово $СН$ становится $x_{n+1}$, и $CL$ становится $x_n$.
Мы можем найти приближение к $n$ раунды через поиск по графу. Узел на этом графике будет выглядеть так:
$$
\bigoplus_{i=0}^{n+1} x_i[\delta_i] = \bigoplus_{i=1}^n k_i[\epsilon_i] \tag{1}
$$
куда $\delta_i$ и $\epsilon_i$ являются битовыми масками.
Чтобы увидеть, каковы ребра, скажем, у нас есть 1-раундовое приближение, подобное этому:
$$
x[\alpha] \oplus F(x, k)[\beta] = k[\gamma] \tag{2}
$$
Мы можем создать его экземпляр в раунде, скажем, $я$, получить:
$$
x_i[\alpha] \oplus F(x_i, k_i)[\beta] = k_i[\gamma] \tag{3}
$$
и теперь мы можем использовать структуру Фейстеля, зная, что $x_{i+1} = x_{i-1} \oplus F(x_i, k_i)$, переписать $F(x_i, k_i)$ как $x_{i+1} \oplus x_{i-1}$, и другие:
$$
x_i[\alpha] \oplus \left(x_{i+1} \oplus x_{i-1}\right)[\beta] = k_i[\gamma] \tag{4}
$$
Это будет ребро в нашем графе. То есть для всех линейных приближений и для всех раундов инстанцирования. $я$, мы можем создать такое ребро. Если источником ребра является уравнение $(1)$, целью ребра является следующее уравнение, полученное с помощью $\имя_оператора{исключающее ИЛИ}$инг $(1)$ и $(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}
$$
Ан $n$-круговое приближение — это такой узел, как $(1)$, где маски $\delta_2 \точки \delta_{n-1}$ все $0$. То есть уравнение включает только открытые тексты, зашифрованные тексты и ключи.
Начнем поиск графа с тривиального приближения, где $\forall i, \delta_i = 0$, и $\forall i, \gamma_i = 0$. Чтобы увидеть, какие ребра мы на самом деле возьмем, немного номенклатуры:
- Штат $x_i$ называется «скрытым», когда $1 < я < п $. То есть это не открытый текст и не зашифрованный текст. Маска $\delta_i$ называется «скрытым» при тех же условиях.
Мы возьмем только край $е$, который выводит нас из узла $v: \bigoplus_{i=0}^{n+1} x_i[\delta_i] = \bigoplus_{i=1}^n k_i[\epsilon_i]$ к узлу $w: \bigoplus_{i=0}^k x_i[\delta'_i] = \bigoplus_{i=1}^k k_i[\epsilon'_i]$, когда не более 2 скрытых масок в $w$ отличны от нуля.
Мы достигаем конечного состояния, когда все скрытые маски равны нулю, и мы не находимся в начальном узле.
Мы используем лемму о накоплении для вычисления весов по мере продвижения, что мы можем сделать в логарифмическом пространстве для повышения точности.
Ниже приведен исходный код C++ для воспроизведения таблицы результатов Мацуи в приложении. Я использовал алгоритм Дейкстры для поиска по графу, но на самом деле это излишество, решение динамического программирования также подойдет. Это связано с тем, что единственные пути, о которых мы заботимся, увеличиваются в том месте, где они применяют однораундовые приближения (т. е. они начинают с пустого приближения и применяют его на раундах, скажем, 1, 2, 3, 5, 6, 8, 9, 10, и дойти до конечного состояния). Однако Dijkstra уже запускается мгновенно, поэтому не нужно переусердствовать.
Единственная специфичная для DES вещь здесь — однораундовые аппроксимации. один_раунд_аппроксимации. Изменение этого позволяет находить линейные цепи для любой сети Фейстеля с учетом приближений к круглой функции.
За NUM_ROUNDS = 10, этот код выводит:
Лучшее приближение:
круглое_число: 10
маски состояния = [1: [7, 18, 24, 29], 10: [15], 11: [7, 18, 24, 29]]
маски клавиш = [1: [22], 2: [44], 3: [22], 5: [22], 6: [44], 7: [22], 9: [22]]
применяемые приближения: [-ACD-DCA-A]
Вероятность: 0,500047
Лог2 (смещение): -14,3904
что точно соответствует статье Мацуи.
// Находит цепочки линейных приближений в шифре Фейстеля.
//
// Раунд шифра Фейстеля можно описать так:
// х0 х1
// | к |
// | | |
// v v |
// + <- Ф ---
// | |
// v v
// х2
//
// Где + — это побитовое исключающее ИЛИ, а F — функция перестановки с ключом. Алгебраически,
// x2 = x0 + F(k, x1) (1)
// Провод, по которому передается x1, остается неизменным и будет заменен на x2
// перед следующим раундом в сети Фейстеля. Тогда вся сеть смотрит
// вот так, где ===><== означает, что мы меняем два провода местами:
// х0 х1
// | к1 |
// | | |
// v v |
// + <- Ф ---
// | |
// v v
// х2 х1
// | |
// х1===><==х2
// | |
// | к2 |
// | | |
// v v |
// + <- Ф ---
// | |
// v v
// х3 х2
// | |
// ...
//
//
// Однократное приближение к F состоит из трех битовых масок, альфа, бета, гамма и т.д.
// что
// х[альфа] + F(х, к)[бета] = к[гамма]
// выполняется с некоторой вероятностью p. Здесь обозначение a[m] означает, что мы исключаем
// биты в битовой строке a, обозначенной маской m. Итак, a[0b101] означает
// ((а и 100) >> 2) ^ (а и 1).
//
// Заметим, что уравнение (1) говорит нам, что F(k, x1) = x2 ^ x0. В общем, если мы
// смотрим на i-й раунд, уравнение (1) говорит нам, что
// F(x_{i + 1}, k_{i + 1}) = x_{i + 2} + x_i (2)
//
// Таким образом, если у нас есть приближение типа:
//
// х[альфа] + F(х, к)[бета] = к[гамма]
//
// Мы можем создать его экземпляр в любом заданном раунде, например:
//
// x1[альфа] + F(x1, k1)[бета] = k1[гамма]
//
// И затем используйте уравнение (2), чтобы переписать это как:
//
// x1[альфа] + (x2 + x0)[бета] = k1[гамма]
//
// Таким образом, мы получаем уравнения для значений проводов в системе Фейстеля
// сеть. В общем, они всегда будут иметь форму:
//
// x_{i + 1}[альфа] + (x_{i + 2} + x_i)[бета] = k_{i + 1}[гамма] (3)
//
// Наша цель — начать с очень простого уравнения:
//
// х0[0] + х1[0] = 0
//
// которое выполняется с вероятностью 1, и применяя полученные уравнения, достигаем
// уравнение, которое включает только:
// * x0, старшее слово в открытом тексте.
// * x1, младшее слово в открытом тексте.
// * x_{n+1}, старшее слово в зашифрованном тексте.
// * x_n, младшее слово в зашифрованном тексте.
// * Некоторые круглые ключи k_i.
// и мы хотим знать вероятность, с которой они выполняются. Мы называем этот сорт
// уравнения линейная аппроксимация полного шифра.
//
// Эта программа рассматривает граф, в котором каждый узел имеет вид:
// (m_0, m_1, ..., m_{N+1}, km_0, km_1, ..., km_0, p)
// где N — количество раундов, каждый m_i — это 32-битная битовая маска, каждый km_i — это
// 64-битная битовая маска, p — вероятность. Значение этого узла:
//
// с вероятностью p,
// (\sum_{i=0}^{N + 1} x_i[m_i]) + (\sum_{i=0}^{N-1} k_i[km_i]) = 0
//
// где x_i — значения проводов в сети Фейстеля, k_i —
// ключи раунда, m_i — это битовые маски для x_i, а km_i — маски для k_i.
//
// Начиная с узла, где m_i = 0 для всех i и km_j = 0 для всех j, и p =
// 1, мы хотим достичь состояния, которое представляет собой линейное приближение
// полный шифр.
//
// Ребра этого графа будут использовать однораундовое приближение,
// создано в каком-то раунде в сети. Например, если у нас есть узел
//
// x_0[0b101] + x_1[0b11] = k_1[0b110] (4)
//
// и мы знаем уравнение вида (3):
// x_{i+1}[0b1011] + (x_{i + 2} + x_i)[0b11] = k_{i + 1}[0b101]
//
// мы могли бы реализовать это при i = 1, чтобы получить
//
// x_2[b1011] + (x_3 + x_1)[0b11] = k_2[0b101] (5)
// Если мы затем объединим это уравнение (5) с (4), мы получим
//
// x_0[0b101] + x_2[0b1011] + x_3[0b11] = k_1[0b110] + k_2[0b101]
//
// который является еще одним узлом в нашем графе. Таким образом, мы исследуем граф до тех пор, пока не
// достигаем линейного приближения полного шифра.
#include <массив>
#include <cstdint>
#include <иопоток>
#include <набор>
#include <unordered_map>
#include <кассета>
#include <вектор>
#include <cmath>
#include <необязательно>
constexpr size_t NUM_ROUNDS = 10;
// Показывает 64-битную битовую маску, показывающую только битовые индексы, которые включены.
std::ostream& show_mask(std::ostream& o, uint64_t m) {
интервал я = 0;
первое логическое значение = истина;
о << "[";
в то время как (м) {
если (м & 1) {
если (! сначала) {
о << ", ";
} еще {
первый = ложь;
}
о << я;
}
м >>= 1;
++я;
}
о << "]";
вернуться о;
}
// Смысл этой аппроксимации в том, что при вероятности p = вероятности(),
// х[альфа] + F(х, к)[бета] = к[гамма]
// Для любой 32-битной строки x и 48-битной строки k.
//
// Смещение определяется как |вероятность() - 0,5|.
структура OneRoundApproximation {
const char* имя;
uint32_t альфа;
uint32_t бета;
uint64_t гамма; // Нужно только 48 бит.
двойной log2_bias; // log_2 (смещение)
двойная вероятность() const {
двойной х = std::pow(2.0, log2_bias) + 0,5;
вернуть std::max(x, 1.0 - x);
}
автоматический оператор друга<=>(const OneRoundApproximation&,
const OneRoundApproximation&) = по умолчанию;
друг std::ostream& operator<<(std::ostream& o,
const OneRoundApproximation& ra) {
о << ра.имя;
вернуться о;
}
};
// Это приближение, которое связывает некоторые биты открытого текста, некоторые биты зашифрованного текста
// биты, некоторые ключевые биты и, возможно, некоторые биты скрытого состояния линейным образом,
// использование фиксированных битовых масок.
//
// Первые 2 состояния — это 2 слова открытого текста, последние 2 состояния — это 2 слова
// слова зашифрованного текста, а любое другое состояние является скрытым состоянием — это значение
// провода в сети Фейстеля.
структура Приближение {
std::array<uint32_t, NUM_ROUNDS + 2> state_mask;
std::array<uint64_t, NUM_ROUNDS> round_key_mask;
std::array<std::Optional<OneRoundApproximation>, NUM_ROUNDS>
прикладные_приближения;
целый круглый_номер;
автоматический оператор друга<=>(const Approximation&, const Approximation&) = default;
друг std::ostream& operator<<(std::ostream& o, const Approximation& a) {
o << "round_number: " << a.round_number << std::endl;
o << "маски состояния = [";
инт снт = 0;
for (size_t i = 0; i < NUM_ROUNDS + 2; ++i) {
если (!a.state_mask[i]) продолжить;
если (cnt++ > 0) o << ", ";
о << я << ": ";
show_mask(o, a.state_mask[i]);
}
о << "]" << std::endl;
цент = 0;
o << "маски ключей = [";
for (size_t i = 0; i < NUM_ROUNDS; ++i) {
если (!a.round_key_mask[i]) продолжить;
если (cnt++ > 0) o << ", ";
о << я << ": ";
show_mask(o, a.round_key_mask[i]);
}
о << "]" << std::endl;
o << "примененные приближения: [";
for (size_t i = 0; i < NUM_ROUNDS; ++i) {
auto ma = a.прикладные_аппроксимации[i];
если (ma == std::nullopt) {
о << "-";
} еще {
о << *ма;
}
}
о << "]" << std::endl;
вернуться о;
}
};
// Это приближение выполняется с заданной вероятностью.
struct WeightedApproximation {
приближение а;
двойной log2_bias;
двойная вероятность() const {
двойной х = std::pow(2.0, log2_bias) + 0,5;
вернуть 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))}
}};
// Учитывая существующее приближение, что произойдет, если мы выполним операцию xor с одним раундом
// приближение к нему? В частности, это однораундовое приближение будет
// создается в раунде `position`.
Аппроксимация apply_one_round_ Approximation(const Approximation& a,
const OneRoundApproximation& o,
позиция size_t) {
Приближение б = а;
b.round_number = позиция + 1;
b.state_mask[позиция] ^= o.beta;
b.state_mask[позиция + 1] ^= o.alpha;
b.state_mask[позиция + 2] ^= o.beta;
b.round_key_mask[позиция] ^= o.gamma;
b.приложенные_аппроксимации[позиция] = o;
вернуть б;
}
// Возвращает, сколько скрытых состояний имеют ненулевую маску в заданном
// приближение.
size_t HiddenSize(Приближение& b) {
результат size_t = 0;
for (size_t i = 2; i < NUM_ROUNDS; ++i) {
результат += b.state_mask[i] != 0;
}
вернуть результат;
}
std::vector<WeightedApproximation> Переходы(
const WeightedApproximation& a, const OneRoundApproximation& o) {
// Для данного приближения первых j раундов шифра мы можем применить
// аппроксимация раунда либо в текущем состоянии в сети Фейстеля,
// или следующий. То есть однораундовое приближение вида:
// альфа * x_{i + 1} + бета * (x_{i+2} + x_i) = гамма * k_i
// Может быть удалено на текущее состояние, которое имеет форму:
//
// \sum_{k=0}^N state_mask_k * x_k + \sum_{k=0}^N key_mask * key_i = 0
//
// Где сумма является xor каждого бита в аргументе.
//
// Это сделает некоторые state_masks нулевыми, а некоторые ненулевыми. Мы только хотим
// выполняем переход, когда количество ненулевых масок для скрытых состояний равно
// не более 2, потому что это все, что нужно для продвижения в
// Сети Фейстеля, которые мы видели (DES). Состояние скрыто, если оно не x_1,
// x_2, x_{N-1} или x_N. То есть, когда это не один из двух открытых текстов
// слова, ни одно из двух слов зашифрованного текста.
// Это можно сделать быстрее и эффективнее, но я особо не
// позаботься сейчас.
// Мы ищем раунд, в котором можно реализовать однораундовое приближение.
std::vector<WeightedApproximation> результат;
for (size_t i = a.a.round_number; i < NUM_ROUNDS; ++i) {
Приближение b = apply_one_round_approimation(a.a, o, i);
если (HiddenSize(b) > 2) продолжить;
результат.push_back(
{.a = std::move(b),
.log2_bias = 1 + a.log2_bias + o.log2_bias});
}
вернуть результат;
}
std::ostream& operator<<(std::ostream& o, const WeightedApproximation& wa) {
о << wa.a << std::endl;
o << "Вероятность: " << wa.probability() << std::endl;
o << "Log2(Bias): " << wa.log2_bias << std::endl;
вернуться о;
}
// Просто стандартная хеш-функция, чтобы иметь возможность помещать приближения в хэш
// Таблица.
шаблон <класс T>
inline void hash_combine (std::size_t& seed, const T& v) {
хеширование std::hash<T>;
seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
size_t HashApproximation(const Approximation& a) {
размер_т ч = 0;
for (size_t i = 0; i < NUM_ROUNDS + 2; ++i) {
hash_combine(h, a.state_mask[i]);
}
hash_combine(h, a.round_number);
вернуть ч;
};
интервал основной () {
// Мы воспользуемся алгоритмом Дейкстры для исследования этого графа. Вес края
// это log2 смещения однораундового приближения, которое он представляет.
auto compare_by_probability = [](const WeightedApproximation& a,
const WeightedApproximation& b) {
если (a.log2_bias > b.log2_bias) вернуть true;
если (a.a.round_key_mask < b.a.round_key_mask) вернуть true;
return HashApproximation(a.a) < HashApproximation(b.a);
};
// Это очередь узлов, которые нам еще предстоит посетить.
очередь std::set<WeightedApproximation, decltype(compare_by_probability)>;
// Это сообщает нам, какие узлы уже были посещены. Примечание в очереди, которую мы храним
// узлы с весом, тогда как этот хэш хранит только приближение
// сам по себе, без вероятности. Это необходимо для того, чтобы можно было изменить предполагаемое
// веса каждого приближения при обходе графика согласно Дейкстре
// алгоритм.
std::unordered_map<Приближение, decltype(queue.begin()),
decltype(&HashApproximation)>
видел(1, &HashApproximation);
// Наше начальное приближение не имеет масок и выполняется с вероятностью 1, а
// поэтому его смещение равно 1 - 0,5 = 0,5..
Взвешенная аппроксимация wa = {.a = аппроксимация {},
.log2_bias = std::log2(0.5)};
auto it = queue.insert(wa).first;
увиденное.emplace(wa.a, оно);
// Мы отслеживаем наилучшее приближение, которое мы видели до сих пор. Единственный
// нас интересуют приближения, которые связывают открытые тексты,
// зашифрованные тексты и ключевые биты. Для этого они должны иметь круглое количество
// NUM_ROUNDS. Это означает, что `wa` на самом деле не является допустимым наилучшим приближением к
// полный шифр, и он будет перезаписан в первый раз, когда мы найдем какой-либо действительный
// приближение.
Взвешенное приближение лучшее_приближение = wa;
в то время как (! очередь.пусто()) {
Взвешенное приближение v = очередь.извлечение(очередь.начало()).значение();
// Мы сигнализируем, что он был извлечен из очереди.
увиденный[v.a] = очередь.конец();
// Если это приближение к полному шифру (т. е. все NUM_ROUNDS из
// это) и не включает никаких скрытых состояний (т.е. только открытые тексты,
// зашифрованные тексты и биты ключа), то это хороший кандидат на лучший
// линейное приближение для всего шифра. Мы сохраним наиболее вероятные
// тот, который имеет наибольшее смещение.
if (v.a.round_number == NUM_ROUNDS && HiddenSize(v.a) == 0) {
если (лучшее_приближение.a.круглое_число == 0 ||
лучшее_приближение.log2_bias < v.log2_bias) {
лучшее_приближение = v;
}
Продолжить;
}
// Теперь мы проходим все ребра, исходящие из приближения`v`, путем перечисления всех
// возможные однораундовые приближения, которые мы могли бы применить в этом приближении.
for (const auto& o : one_round_appimations) {
for (WeightedApproximation w : Transitions(v, o)) {
авто это = видел.найти(ва);
если (это == увиденное.конец()) {
// Если мы никогда раньше не видели этого приближения, добавляем его в очередь,
// и пометить как увиденное. Это должен быть новый элемент в очереди, и
// мы утверждаем так.
auto [jt, вставлено] = queue.insert(std::move(w));
утверждать (вставлено);
увиденное.emplace(jt->a, std::move(jt));
} еще {
// Мы видели это раньше. Если мы уже вытащили его из очереди,
// ничего делать не надо, мы уже нашли кратчайший весовой путь
// к нему по инварианту алгоритма Дейкстры..
if (it->second == queue.end()) continue;
// Расслабить край, если это возможно.
если (it->второй->log2_bias < w.log2_bias) {
очередь.стирать(это->секунда);
auto jt = queue.insert(w).first;
это-> секунда = jt;
}
}
}
}
}
std::cout << "Наилучшее приближение: " << std::endl
<< лучшее_приближение << std::endl;
}
```
