Calculation of the differential probabilities for the sum of k numbers modulo 2n..pdf Одним из подходов к построению криптографических примитивов является комбинирование сложения по модулю 2n (Ш), побитовых операций (например, «исключающего или» - ф), битовых сдвигов (^), циклических сдвигов (^^). Это позволяет получить очень быстрые в программной реализации алгоритмы. Особый интерес представляют ARX-конструкции, использующие только операции Ш, ф и Примерами таких шифров являются FEAL [1], TEA [2], Salsa20 [3], Speck [4]. Хорошие шифры должны быть стойкими к различным видам криптоанализа, в частности к разностному криптоанализу [5]. Это один из основных статистических методов, основанный на исследовании того, в какие разности шифртекстов могут переходить разности открытых текстов. Важным шагом при реализации метода является вычисление разностных характеристик и их максимальных значений. Для базовых операций архитектуры ARX данные характеристики определяются следующим образом [6]: xdP+(a,e Y) = 4П|{x,y G Zn : (x ф a) ffl (y ф e) = Y ф (x ffly)}1, adp®(a,e y) = 4П|{x,y G Zn : (x ffl a) ф (y ffle) = y И (x ф y)}|. n_ 1 C вектором x = (x0,..., xn_i) G Zn мы ассоциируем целое число xi2i, тогда x ffl a _ i=0 означает сложение ассоциированных с x и a чисел по модулю 2n. Недостатком ARX-шифров является сложность вычисления разностных характеристик для композиций операций. Существует подход с использованием S-функций [6], позволяющий вычислить разностные характеристики как произведение специальных матриц, построенных на основе рассматриваемого преобразования. Однако его алгоритмическое применение в большинстве случаев не позволяет получить аналитические выражения для данных матриц. 1. Матричный способ вычисления xdp+ (a1,..., ak a0) Рассмотрим функцию f(xi, . . . , xk) = xi+. . .+xk. Разностная характеристика xdp+k для неё определяется следующим образом: xdp+ (a1,...,ak a0) = 21k kk x1,..., xk G zn : Щ (xi ф ai) = a0 ф Щ xi > i=1 i=1 Подход с использованием S-функций подразумевает построение матриц на основе преобразования, через произведения которых можно подсчитать значения разностной характеристики [5]. Для характеристики xdp+k далее предлагаются явные выражения для вычисления всех ненулевых элементов матриц. Обозначим через wt(x) вес Хэмминга вектора x. Определим N(a, b) = a + 2kb, где 0 С а, b < 2k. Мы будем использовать матрицы размера 4k2 х 4k2. Заметим, что 0 С N (a, b) < 4k2. Таким образом, через N (a, b) будем представлять номер строки или столбца матрицы с помощью пары чисел (a, b). Зададим матрицы Am размера 4k2 х 4k2 для всех m G Z2k+1 следующим образом. Рассмотрим любую четвёрку целых чисел x, y, x', y', таких, что 0 С x,y,x',y' < 2k. Пусть c = wt(m1, . . . , mk), Ax = x' - x , a = Ax + Ay - c 1-2- 2 Ay = y'- y , b = Ax - Ay + c Ы 2 Тогда элемент матрицы Am в N(x',у')-й строке и N(ж,у)-м столбце определяется следующим образом: 1) 0, если выполнено одно из следующих условий: - хотя бы одно из чисел Ax, Ay, а или b меньше нуля, - x1 + y1 + c + m0 - нечётное, - Ax + Ay + c - нечётное; в противном случае. С использованием матриц Am, а также матриц L = (1 1 ... 1) размера 1 х 4k9 10 и C = (1 0 ... 0)T размера 4k11 х 1 можно вычислить значения характеристики xdp+k . Теорема 1. Пусть а0, а12,... , ак G Zn. Тогда xdp+ (а13,..., ак а0) = Д.,LAwn-i ... AW1 AwoC, где w. = (а0,..., ак) G Z^1. Заметим, что элементы матрицы Am зависят только от wt(m1, . . . , mk) и m0. Следствие 1. В последовательности матриц Am, где m G Z2k+1, существует лишь 2(k + 1) различных матриц. Переобозначим эти матрицы как Awt(mi,...,mk),m0. Алгоритм 1 позволяет вычислять все матрицы A0,0,... , Ak,0 и A0,i,... , Ak,1 одновременно за O(k14) операций. Алгоритм 1. Алгоритм одновременного вычисления всех матриц Ai,j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Для всех целых m, i, j, таких, что 0 С m С к, 0 С i С к, 0 С j С 1: B™ -матрица размера 4к10 х 4к10, изначально заполненная нулями. Для всех целых х, у, таких, что 0 С х, у < 2k: c := xi ф yi; B0»c[N(Lx/-2J, Ly/2J)][N(x,y)] := 1. Для всех m от 1 до k: Для всех x,y,x', у', таких, что 0 С x,y,x',y' < 2k: Для всех i от 0 до m - 1, j от 0 до 1: P := B’’j"i[N(x',y')][N(x,y)]; Bm [N (x',y' )][N (x,y)] += P. Если x' + 1 < 2k и у' + 1 < 2k, то В™.[N (x' + 1,y/ + 1)][N (x,y)] += P. Для всех j от 0 до 1: P := Bm-ij[N(x',y')][N(x,y)]; j' := j ф 1 Если y' + 1 < 2k, то Bm.[N (x',y'+ 1)][n (x,y)] += p . Если x' + 1 < 2k, то Brn,j

Скачать электронную версию публикации