On properties of additive differential probabilities of XOR.pdf ARX - одна из современных архитектур в симметричной криптографии. В компонентах таких шифров используются только три операции: сложение по модулю 2n, циклический сдвиг и покомпонентное сложение по модулю 2 (XOR). Архитектуру ARX имеют блочные шифры FEAL [1], Threefish [2], один из победителей eSTREAM поточный шифр Salsa20 [3] и его модификация ChaCha [4], входящая в TLS, а также финалисты SHA-3 хэш-функции BLAKE [5] и Skein [2]. Разностный криптоанализ [6] основан на изучении преобразования разностей открытых текстов в разности шифртекстов, сложность такого изучения является недостатком ARX-шифров. Выбирая в качестве разности разность по модулю 2n, вероятности разностных характеристик операции XOR определяются функцией adp®: adp®(Q,fl y) = #{x,y G 2П :(x + g) ®(y + в) = ОГ ' y)+ Y}. C вектором x G Z2n мы ассоциируем целое число x0 + x1 25 + . . . + xn-1 2n-1 , x + a означает сложение по модулю 2n ассоциированных c x и a чисел, - x является обратным к ассоциированному с x числу относительно сложения по модулю 2n. Известно [7], что adp® (a, в 7) при a, в, 7 G Zn представимо в виде произведения матриц размера 8x8, что позволяет эффективно вычислять adp® за линейное по n время. Отметим, что данная работа началась в рамках Первого воркшопа Математического центра в Академгородке (см. http://mca.nsu.ru/workshop/). Приведём преобразования аргументов, не меняющие значение adp®. Утверждение 1. Пусть a, в, y G Z2n. Тогда справедливо следующее: 1) adp® является симметрической, т. е. не меняет значение при перестановке a, в, y; 2) значение adp® не изменится, если к любым двум аргументам прибавить 2n-1 по модулю 2n: adp®(a, в 7) = adp®(a + 2n-1, в + 2n-1 7); 3) adp®(a,e 7) = adp®(a,e -7); в силу п. 1 можно поставить « -» перед любым аргументом. В [7, теорема3] сформулирована теорема о максимальном значении adp®(а. в^7) при фиксированном 7. Однако доказательство не было приведено («The proof is omitted from the conference version») и впоследствии нигде не было опубликовано. Мы доказали, что это утверждение действительно является верным. Теорема 1. Для любого Y G Z2n выполняется max adp®(a.e 7) = adp®(0,7 а,в&2 Метод доказательства позволяет также найти количество пар (a, в), на которых достигается значение adp®(0,7 Следствие 1. Количество пар (а. в) G Zn х Z£, таких, что adp®(a. в 7) = adp® (0.7 7), где 7 G Z£, равно: 1) 2, если 7 = 0 или 7 = 2n-1, а именно это пары (0. 0). (2n-1. 2n-1) при 7 = 0 и (0. 2n-1). (2n-1. 0) при 7 = 2n-1; 2) 8 для всех других 7, а именно это пары (0. 7). (7. 0). (2n-1. -7 + 2n-1). (-7 + 2n-1. 2n-1). (0. -7). (-7. 0). (2n-1. 7 + 2n-1). (7 + 2n-1. 2n-1). Заметим, что все приведённые пары являются симметриями, описанными в утверждении 1. Кроме того, если 7 равна 0 или 2П-1, то adp®(0.7 7) = 1. Используя S-функции [8], величину adp® (0.7 7) можно представить в виде произведения матриц размера 3 х 3. Однако если исключить старший бит, достаточно матриц размера 2 х 2. Теорема 2. Для любого 7 G Z2n выполнено adp®(0.7 7) = (1,1)BYn-2 BYn-з ...BY0(1. 0)T. где Bo 4(0 0; B 4 10. 14. Более прозрачную формулу для adp® (0.7 7) получить не удалось. Косвенным подтверждением сложности этой задачи является непростое выражение для минимального из значений adp®(0.7 7) при фиксированном n. Теорема 3. Пусть mn = min adp®(0.7 7). Тогда для любого n выполнено Y^Zn 11 mn+2 = 4 mn+1 + 4 mn. Следствие 2. Числа mn, n = 1. 2. . . ., образуют последовательность Хорадама [9] и для них верно mn = 3 8 ((17 + 417)(1 + 417)n + (17 - 7417)(1 - 417)n) . Тем не менее сумму всех элементов adp® (0.7 7) вычислить несложно. Утверждение 2. Для любого n выполнено £ adp® (0.7 7) = 2 (3/2)П-1. ycz;? Подробно с результатами работы можно ознакомиться в [10].

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