Ce îmi lipsește din raționamentul meu?
Doua lucruri:
Există și alte strategii decât sortarea pentru a găsi coliziuni; una evidentă este să construiești o masă hash uriașă. Acum, în practică, sortarea ar fi probabil mai rapidă (pentru că o tabelă hash atât de mare ar fi nepractică), dar teoretic, o tabelă hash ar permite $O(1)$ accese pe care această analiză de complexitate le presupune implicit.
$O(n \log n)$ nu este de fapt timpul optim de sortare. Este dacă singurele operațiuni pe care le puteți efectua asupra datelor sunt comparațiile și mișcarea datelor; cu toate acestea, nu suntem de fapt constrânși în acest fel. O abordare evidentă ar fi să faceți o metodă de sortare radix, care poate avea o complexitate de timp considerabil mai bună.
Acum, pentru a fi sincer, ignorăm de obicei timpul necesar acestor operațiuni noncriptografice (cum ar fi căutarea și sortarea), cu excepția cazului în care ocupă o fracțiune foarte mare din timpul total. Sincer, pot exista o mulțime de detalii atunci când coborâți la acel nivel (cum ar fi complexitatea confruntării cu $O(2^{56})$ date), și în schimb numărăm doar evaluările DES.
De fapt, nu încercăm să spargem 2DES; în schimb, arătăm că ruperea 2DES ar putea fi de fapt realizabilă în timp practic. Dacă am încerca de fapt să o distrugem, am putea ajunge să folosim în schimb o căutare lambda, care ar avea o creștere constantă a complexității și nu este garantată, ar fi mai ușor de implementat (deoarece căutarea lambda ar folosi mult mai puțină memorie și fiind totusi usor de paralelizat).
