Approximation table computing algorithms in cryptanalysis of block ciphers

摘要

Approximation algorithms based on definitions of differential and linear equations, developed for computation of single element of the approximation tables, are of exponential time complexity. Fast general algorithms, for computation the best nonzero approximations in at worst linear time for a single element, without memory needed for storage of the whole table are presented in the paper. To frequently used components of block ciphers belong arithmetic sum and subtraction functions. For these functions are presented fast specialized algorithms computing a single element of the approximation tables in linear time.%Do najwa?niejszych ogólnych metod analizy kryptograficznej szyfrów blokowych nale?? kryptoanaliza ró?nicowa i kryptoanaliza liniowa. W obu metodach wykorzystywane s? równania, które w sposób przybli?ony, z pewnym prawdopodobieństwem, opisuj? dzia?anie szyfru. Równania te nazywane s? aproksymacjami ró?nicowymi lub liniowymi. Dla dowolnej funkcji f o n binarnych wej?ciach i m binarnych wyj?ciach zbiór wszystkich aproksymacji ró?nicowych lub liniowych mo?e by? reprezentowany w postaci tablicy aproksymacji o rozmiarze O(2~(n+m)). W artykule przedstawiono algorytmy obliczania tych tablic. Oparte na definicji aproksymacji ró?nicowej lub liniowej algorytmy obliczaj? pojedyncz? warto?? tablicy aproksymacji w czasie wyk?adniczym. Ogranicza to zastosowanie tych podstawowych algorytmów do funkcji sk?adowych szyfru o niewielkiej liczbie binarnych wej?? i wyj??. Przedstawione w artykule szybkie ogólne algorytmy obliczaj? najlepsz? niezerow? aproksymacj? ró?nicow? i liniow? w co najwy?ej liniowym czasie O(n+m) dla pojedynczego elementu bez anga?owania pami?ci potrzebnej do przechowania ca?ych tablic. Do cz?sto stosowanych elementów sk?adowych szyfrów blokowych nale?? funkcje sumy i ró?nicy arytmetycznej. Dla tych funkcji przedstawiono w artykule szybkie specjalizowane algorytmy obliczaj?ce pojedynczy element tablic aproksymacji w czasie liniowym.