Am găsit răspunsul.
În primul rând, voi schimba puțin notația, astfel încât ecuațiile să devină puțin mai simetrice.
Folosind această notație, cuvântul text simplu $PH$ în lucrarea lui Matsui devine $x_0$, și $PL$ devine $x_1$. Cuvântul criptat $CH$ devine $x_{n+1}$, și $CL$ devine $x_n$.
Putem găsi o aproximare a $n$ rotunjite printr-o căutare grafică. Un nod din acest grafic va arăta astfel:
$$
\bigoplus_{i=0}^{n+1} x_i[\delta_i] = \bigoplus_{i=1}^n k_i[\epsilon_i] \tag{1}
$$
Unde $\delta_i$ și $\epsilon_i$ sunt măști de biți.
Pentru a vedea care sunt marginile, să presupunem că avem o aproximare cu 1 rundă ca aceasta:
$$
x[\alpha] \oplus F(x, k)[\beta] = k[\gamma] \tag{2}
$$
Putem să o instanțiem rotund, să spunem, $i$, a obține:
$$
x_i[\alpha] \oplus F(x_i, k_i)[\beta] = k_i[\gamma] \tag{3}
$$
iar acum putem folosi structura Feistel, știind asta $x_{i+1} = x_{i-1} \oplus F(x_i, k_i)$, a rescrie $F(x_i, k_i)$ la fel de $x_{i+1} \oplus x_{i-1}$, Așadar:
$$
x_i[\alpha] \oplus \left(x_{i+1} \oplus x_{i-1}\right)[\beta] = k_i[\gamma] \tag{4}
$$
Aceasta va fi o margine în graficul nostru. Adică pentru toate aproximările liniare și pentru toate rundele de instanțiere $i$, putem crea o astfel de margine. Dacă sursa marginii este ecuația $(1)$, ținta muchiei este următoarea ecuație, obținută prin $\operatorname{XOR}$ing $(1)$ și $(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}
$$
Un $n$-aproximarea rotundă este un astfel de nod $(1)$, unde măștile $\delta_2 \dots \delta_{n-1}$ sunt toti $0$. Adică, ecuația implică doar texte clare, texte cifrate și chei.
Începem căutarea în grafic cu o aproximare trivială, unde $\forall i, \delta_i = 0$, și $\forall i, \gamma_i = 0$. Pentru a vedea ce margini vom lua de fapt, un pic de nomenclatură:
- Un stat $x_i$ se spune „ascuns” când $1 < i < n$. Adică nu este nici un text simplu, nici un text cifrat. O mască $\delta_i$ se numește „ascuns” în aceleași condiții.
Vom lua doar un avantaj $e$, care ne ia dintr-un nod $v: \bigoplus_{i=0}^{n+1} x_i[\delta_i] = \bigoplus_{i=1}^n k_i[\epsilon_i]$ la un nod $w: \bigoplus_{i=0}^k x_i[\delta'_i] = \bigoplus_{i=1}^k k_i[\epsilon'_i]$, când cel mult 2 măști ascunse în $w$ sunt diferite de zero.
Ajungem la starea finală când toate măștile ascunse sunt zero și nu suntem la nodul de pornire.
Folosim lema de acumulare pentru a calcula greutăți pe măsură ce mergem, ceea ce putem face în spațiul de logare pentru a îmbunătăți precizia.
Mai jos este codul sursă C++ pentru a replica tabelul de rezultate al lui Matsui din anexă. Am folosit algoritmul lui Dijkstra pentru căutarea în grafic, dar într-adevăr este exagerat, o soluție de programare dinamică ar fi, de asemenea, utilă. Acest lucru se datorează faptului că singurele căi de care ne pasă sunt în creștere în locația în care aplică aproximări cu o singură rundă (adică încep cu aproximarea goală și o aplică la runde, de exemplu, 1, 2, 3, 5, 6, 8, 9, 10 și ajunge la starea finală). Cu toate acestea, Dijkstra's rulează deja instantaneu, așa că nu este nevoie să ne gândim prea mult la asta.
Singurul lucru specific DES aici sunt aproximările cu o singură rundă one_round_aproximations. Modificarea care face ca aceasta să găsească lanțuri liniare pentru orice rețea Feistel, având în vedere aproximări ale funcției rotunde.
Pentru NUM_ROUNDS = 10, acest cod iese:
Cea mai bună aproximare:
număr_rund: 10
măști de stare = [1: [7, 18, 24, 29], 10: [15], 11: [7, 18, 24, 29]]
măști de cheie = [1: [22], 2: [44], 3: [22], 5: [22], 6: [44], 7: [22], 9: [22]]
aproximări aplicate: [-ACD-DCA-A]
Probabilitate: 0,500047
Log2(bias): -14,3904
care se potrivește exact cu hârtia lui Matsui.
// Găsește lanțuri de aproximări liniare într-un cifr Feistel.
//
// O rundă a unui cifr Feistel poate fi descrisă astfel:
// x0 x1
// | k |
// | | |
// v v |
// + <- F ---
// | |
// v v
// x2
//
// Unde + este xor pe biți și F este o funcție de permutare cu taste. Algebric,
// x2 = x0 + F(k, x1) (1)
// Firul care poartă x1 rămâne nemodificat și va fi schimbat cu x2
// înainte de runda următoare în rețeaua Feistel. Întreaga rețea arată atunci
// așa, unde ===><== înseamnă că schimbăm cele două fire:
// x0 x1
// | k1 |
// | | |
// v v |
// + <- F ---
// | |
// v v
// x2 x1
// | |
// x1===><==x2
// | |
// | k2 |
// | | |
// v v |
// + <- F ---
// | |
// v v
// x3 x2
// | |
// ...
//
//
// O aproximare cu o singură rundă la F este trei măști de biți, alfa, beta, gamma, așa
// acea
// x[alfa] + F(x, k)[beta] = k[gamma]
// se ține cu o oarecare probabilitate p. Aici notația a[m] înseamnă că xor the
// biți în șirul de biți a, indicați de masca m. Deci a[0b101] înseamnă
// ((a & 100) >> 2) ^ (a & 1).
//
// Observăm că ecuația (1) ne spune că F(k, x1) = x2 ^ x0. În general, dacă noi
// uită-te la i-a rundă, ecuația (1) ne spune că
// F(x_{i + 1}, k_{i + 1}) = x_{i + 2} + x_i (2)
//
// Astfel, dacă avem o aproximare de genul:
//
// x[alfa] + F(x, k)[beta] = k[gamma]
//
// Îl putem instanția la orice rundă dată, de exemplu:
//
// x1[alfa] + F(x1, k1)[beta] = k1[gamma]
//
// Și apoi folosiți ecuația (2) pentru a rescrie aceasta ca:
//
// x1[alfa] + (x2 + x0)[beta] = k1[gamma]
//
// În acest fel obținem ecuații pentru valorile firelor din Feistel
// rețea. În general, acestea vor fi întotdeauna de forma:
//
// x_{i + 1}[alfa] + (x_{i + 2} + x_i)[beta] = k_{i + 1}[gamma] (3)
//
// Scopul nostru este să începem cu o ecuație foarte simplă:
//
// x0[0] + x1[0] = 0
//
// care este valabil cu probabilitatea 1, și aplicând aceste ecuații pe care le-am obținut, ajungem la an
// ecuație care implică doar:
// * x0, cuvântul înalt din textul simplu.
// * x1, cuvântul mic din textul simplu.
// * x_{n+1}, cuvântul înalt din textul cifrat.
// * x_n, cuvântul mic din textul cifrat.
// * Unele taste rotunde k_i.
// și vrem să știm probabilitatea cu care se țin. Noi numim acest fel
// a ecuației o aproximare liniară a cifrului complet.
//
// Acest program ia în considerare un grafic în care fiecare nod are forma:
// (m_0, m_1, ..., m_{N+1}, km_0, km_1, ..., km_0, p)
// unde N este numărul de runde, fiecare m_i este o mască de biți de 32 de biți, fiecare km_i este un
// Mască de biți pe 64 de biți, iar p este o probabilitate. Semnificația acestui nod este:
//
// cu probabilitatea p,
// (\sum_{i=0}^{N + 1} x_i[m_i]) + (\sum_{i=0}^{N-1} k_i[km_i]) = 0
//
// unde x_i sunt valorile firelor din rețeaua Feistel, k_i sunt
// cheile rotunde, m_i sunt măști de biți pentru x_i și km_i sunt măști pentru k_i.
//
// Începând de la nodul unde m_i = 0 pentru tot i, și km_j = 0 pentru tot j și p =
// 1, vrem să ajungem la o stare care reprezintă o aproximare liniară a
// cifru complet.
//
// Marginile acestui grafic vor folosi o aproximare cu 1 rundă,
// instanțiat la o rundă în rețea. De exemplu, dacă avem nodul
//
// x_0[0b101] + x_1[0b11] = k_1[0b110] (4)
//
// și știm ecuația de forma (3):
// x_{i+1}[0b1011] + (x_{i + 2} + x_i)[0b11] = k_{i + 1}[0b101]
//
// am putea instanția asta la i = 1, pentru a obține
//
// x_2[b1011] + (x_3 + x_1)[0b11] = k_2[0b101] (5)
// Dacă atunci xorăm această ecuație (5) cu (4), obținem
//
// x_0[0b101] + x_2[0b1011] + x_3[0b11] = k_1[0b110] + k_2[0b101]
//
// care este un alt nod din graficul nostru. În acest fel explorăm graficul până când vom
// ajunge la o aproximare liniară a cifrului complet.
#include <matrice>
#include <cstdint>
#include <iostream>
#include <set>
#include <unordered_map>
#include <cassert>
#include <vector>
#include <cmath>
#include <opțional>
constexpr size_t NUM_ROUNDS = 10;
// Afișează o mască de biți pe 64 de biți, afișând doar indicii de biți care sunt „activați”.
std::ostream& show_mask(std::ostream& o, uint64_t m) {
int i = 0;
bool primul = adevărat;
o << "[";
în timp ce (m) {
dacă (m & 1) {
dacă (!în primul rând) {
o << ", ";
} altfel {
primul = fals;
}
o << i;
}
m >>= 1;
++i;
}
o << "]";
întoarce o;
}
// Sensul acestei aproximări este că cu probabilitate p = probabilitate(),
// x[alfa] + F(x, k)[beta] = k[gamma]
// Pentru orice șir x de 32 de biți și șir de biți k.
//
// Deviația este definită ca |probabilitate() - 0,5|.
struct OneRoundApproximation {
const char* nume;
uint32_t alfa;
uint32_t beta;
uint64_t gamma; // Au nevoie doar de 48 de biți.
dublu log2_bias; // log_2(bias)
probabilitate dublă() const {
dublu x = std::pow(2,0, log2_bias) + 0,5;
return std::max(x, 1.0 - x);
}
operator automat prieten<=>(const OneRoundApproximation&,
const OneRoundApproximation&) = implicit;
prieten std::ostream& operator<<(std::ostream& o,
const OneRoundApproximation& ra) {
o << ra.name;
întoarce o;
}
};
// Aceasta este o aproximare care leagă niște biți de text simplu, niște text cifrat
// biți, niște biți cheie și, eventual, niște biți de stare ascunși, într-un mod liniar,
// folosind măști de biți fixe.
//
// Primele 2 stări sunt cele 2 cuvinte în text simplu, ultimele 2 stări sunt cele 2
// cuvinte criptate, iar orice altă stare este o stare ascunsă - este valoarea
// a unui fir în rețeaua Feistel.
struct Aproximație {
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>
aproximări_aplicate;
int round_number;
friend auto operator<=>(const Aproximation&, const Aproximation&) = implicit;
prieten std::ostream& operator<<(std::ostream& o, const Aproximation& a) {
o << "număr_rotunzi: " << a.număr_rotunzi << std::endl;
o << „măști de stat = [”;
int cnt = 0;
pentru (dimensiunea_t i = 0; i < NUM_ROUNDS + 2; ++i) {
dacă (!a.state_mask[i]) continuă;
dacă (cnt++ > 0) o << ", ";
o << i << ": ";
show_mask(o, a.state_mask[i]);
}
o << "]" << std::endl;
cnt = 0;
o << "key masks = [";
pentru (dimensiunea_t i = 0; i < NUM_ROUNDS; ++i) {
dacă (!a.round_key_mask[i]) continuă;
dacă (cnt++ > 0) o << ", ";
o << i << ": ";
show_mask(o, a.round_key_mask[i]);
}
o << "]" << std::endl;
o << "aproximații aplicate: [";
pentru (dimensiunea_t i = 0; i < NUM_ROUNDS; ++i) {
auto ma = a.aproximații_aplicate[i];
if (ma == std::nullopt) {
o << "-";
} altfel {
o << *ma;
}
}
o << "]" << std::endl;
întoarce o;
}
};
// Aceasta este o aproximare care este valabilă cu o probabilitate dată.
struct WeightedApproximation {
Aproximația a;
dublu log2_bias;
probabilitate dublă() const {
dublu x = std::pow(2,0, log2_bias) + 0,5;
return std::max(x, 1.0 - x);
}
};
std::array<OneRoundApproximation, 5> one_round_aproximations = {{
{„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))}
}};
// Având în vedere o aproximare existentă, ce se întâmplă dacă xorăm o rundă
// aproximare asupra lui? Mai exact, acea aproximare într-o singură rundă va fi
// instanțiat la `poziție` rotundă.
Aproximație apply_one_round_approximation(const Aproximație& a,
const OneRoundApproximation& o,
poziție size_t) {
Aproximarea b = a;
b.număr_rotunzi = poziție + 1;
b.state_mask[poziție] ^= o.beta;
b.state_mask[poziție + 1] ^= o.alpha;
b.state_mask[poziție + 2] ^= o.beta;
b.rotunda_key_mask[poziție] ^= o.gamma;
b.aproximații_aplicate[poziție] = o;
întoarcere b;
}
// Returnează câte stări ascunse au o mască diferită de zero în date
// aproximare.
size_t HiddenSize(Aproximație& b) {
rezultat size_t = 0;
pentru (dimensiune_t i = 2; i < NUM_ROUNDS; ++i) {
rezultat += b.state_mask[i] != 0;
}
returnează rezultatul;
}
std::vector<WeightedApproximation> Tranziții(
const WeightedApproximation& a, const OneRoundApproximation& o) {
// Pentru o aproximare dată a primelor j runde ale cifrului, putem aplica
// aproximarea rotundă fie la starea curentă în rețeaua Feistel,
// sau următorul. Adică, o aproximare cu o singură rundă a formei:
// alfa * x_{i + 1} + beta * (x_{i+2} + x_i) = gamma * k_i
// Poate fi xorred în starea curentă, care este de forma:
//
// \sum_{k=0}^N state_mask_k * x_k + \sum_{k=0}^N key_mask * key_i = 0
//
// Unde suma este xorul fiecărui bit din argument.
//
// Acest lucru va face ca unele state_masks să fie zero, iar altele diferite de zero. Noi vrem doar
// ia tranziția când numărul de măști non-zero pentru stările ascunse este
// cel mult 2, pentru că asta este tot ce este necesar pentru a face progrese în
// Rețele Feistel pe care le-am văzut (DES). O stare este ascunsă atunci când nu este nici x_1,
// x_2, x_{N-1} sau x_N. Adică atunci când nu este niciunul dintre cele două text clar
// cuvinte, nici unul dintre cele două cuvinte cifrate.
// Acest lucru poate fi făcut mai rapid și mai eficient în spațiu, dar nu o fac în mod special
// ai grijă deocamdată.
// Căutăm o rundă unde să instanțiem aproximarea cu o singură rundă.
rezultat std::vector<WeightedApproximation>;
pentru (dimensiunea_t i = a.a.round_number; i < NUM_ROUNDS; ++i) {
Aproximație b = apply_one_round_aproximation(a.a, o, i);
dacă (HiddenSize(b) > 2) continuă;
rezultat.push_back(
{.a = std::move(b),
.log2_bias = 1 + a.log2_bias + o.log2_bias});
}
returnează rezultatul;
}
std::ostream& operator<<(std::ostream& o, const WeightedApproximation& wa) {
o << wa.a << std::endl;
o << "Probabilitate: " << wa.probability() << std::endl;
o << "Log2(Bias):" << wa.log2_bias << std::endl;
întoarce o;
}
// Doar o funcție hash standard pentru a putea pune Aproximații într-un hash
// masa.
șablon <clasa T>
inline void hash_combine(std::size_t& seed, const T&v) {
std::hash<T> hasher;
sămânță ^= hasher(v) + 0x9e3779b9 + (sămânță << 6) + (sămânță >> 2);
}
size_t HashApproximation(const Aproximation& a) {
dimensiunea_t h = 0;
pentru (dimensiunea_t i = 0; i < NUM_ROUNDS + 2; ++i) {
hash_combine(h, a.state_mask[i]);
}
hash_combine(h, a.round_number);
întoarcere h;
};
int main() {
// Vom folosi algoritmul lui Dijkstra pentru a explora acest grafic. Greutatea unei margini
// este log2 al prejudecății aproximării cu o singură rundă pe care o reprezintă.
auto compare_by_probability = [](const WeightedApproximation& a,
const WeightedApproximation& b) {
dacă (a.log2_bias > b.log2_bias) returnează adevărat;
if (a.a.round_key_mask < b.a.round_key_mask) returnează adevărat;
returnează HashApproximation(a.a) < HashApproximation(b.a);
};
// Aceasta este coada de noduri pe care mai avem de vizitat.
std::set<WeightedApproximation, decltype(compare_by_probability)> coada;
// Aceasta ne spune care noduri au fost deja vizitate. Notă în coada pe care o stocăm
// nodurile cu o greutate, în timp ce acest hash stochează doar aproximarea
// în sine, fără probabilitate. Aceasta este pentru a putea modifica estimarea
// ponderile fiecărei aproximări pe măsură ce parcurgem graficul, conform lui Dijkstra
// algoritm.
std::unordered_map<Aproximație, decltype(queue.begin()),
decltype(&HashApproximation)>
văzut(1, &HashApproximation);
// Aproximația noastră inițială nu are măști și este valabilă cu probabilitatea 1 și
// deci părtinirea sa este 1 - 0,5 = 0,5..
WeightedApproximation wa = {.a = Aproximație{},
.log2_bias = std::log2(0.5)};
auto it = queue.insert(wa).first;
seen.emplace(wa.a, it);
// Ținem evidența celei mai bune aproximări pe care am văzut-o până acum. Singura
// aproximațiile de care ne va păsa sunt cele care relaționează textele clare,
// texte cifrate și biți cheie. Pentru aceasta, trebuie să aibă un număr rotund de
// NUM_ROUNDS. Aceasta înseamnă că „wa” nu este de fapt o cea mai bună aproximare validă pentru
// cifrul complet și va fi suprascris prima dată când găsim vreunul valid
// aproximare.
WeightedApproximation best_approximation = wa;
în timp ce (!coada.gol()) {
WeightedApproximation v = queue.extract(queue.begin()).value();
// Semnalăm că a fost scos din coadă.
seen[v.a] = queue.end();
// Dacă aceasta este o aproximare a cifrului complet (adică toate NUM_ROUNDS de
// it), și nu implică nicio stare ascunsă (adică doar texte clare,
// texte cifrate și biți cheie), atunci este un bun candidat pentru cel mai bun
// aproximare liniară pentru întregul cifr. Vom păstra cel mai probabil
// unul, acesta este cel cu cea mai mare părtinire.
dacă (v.a.round_number == NUM_ROUNDS && HiddenSize(v.a) == 0) {
dacă (cea mai bună_aproximare.a.număr_rotunzi == 0 ||
cea mai bună aproximare.log2_bias < v.log2_bias) {
cea mai bună aproximare = v;
}
continua;
}
// Acum parcurgem toate muchiile care ies din aproximation`v`, listând toate
// posibile aproximări cu o singură rundă pe care le-am putea aplica la această aproximare.
pentru (const auto& o: one_round_aproximations) {
pentru (Aproximație ponderată w : Tranziții(v, o)) {
auto it = seen.find(w.a);
if (it == seen.end()) {
// Dacă nu am mai văzut niciodată această aproximare, adăugați-o la coadă,
// și marcați-l așa cum se vede. Acesta trebuie să fie un element nou în coadă și
// afirmăm așa.
auto [jt, inserat] = queue.insert(std::move(w));
afirma (inserat);
seen.emplace(jt->a, std::move(jt));
} altfel {
// Am mai văzut-o. Dacă l-am scos deja din coadă,
// nu trebuie să facem nimic, am găsit deja cea mai scurtă cale de greutate
// la aceasta, prin invarianta algoritmului lui Dijkstra..
if (it->second == queue.end()) continua;
// Relaxați marginea dacă este posibil.
if (it->second->log2_bias < w.log2_bias) {
coada.erase(it->second);
auto jt = queue.insert(w).first;
it->second = jt;
}
}
}
}
}
std::cout << "Cea mai bună aproximare: " << std::endl
<< cea mai bună aproximare << std::endl;
}
```
