Influence of difference hamming weight on it's propagation through arithmetic operations.pdf Дифференциальный криптоанализ [1] вместе со своими модификациями является распространённым подходом к анализу стойкости итеративных блочных шифров, однако далеко не всегда авторы дифференциальных атак обосновывают их строго математически. Тем не менее некоторые шаги в этом направлении предпринимаются. Так, в работе [2] предложена модель марковского шифра, в рамках которой вычисляются вероятности характеристик; там же сформулирована гипотеза стохастической эквивалентности, негласно подразумеваемая в более ранних работах. В [3] показана возможность создания шифра, доказуемо стойкого к дифференциальному криптоанализу, а в [4] разработана модель, позволяющая создать такой шифр. Работа [5] посвящена изложению дифференциального криптоанализа в общем виде применительно к произвольным итеративным блочным шифрам с аддитивным раундовым ключом. Автор [6] аналитически вычисляет вероятность успеха дифференциальной атаки в зависимости от параметров шифра. В [7] предложена формализация основных понятий дифференциального криптоанализа и проведена их систематизация. Другой важной проблемой является изучение того, как изменяется разность блоков или подблоков после операций, используемых в блочных шифрах. При этом оценивается вероятность того, что пара величин с определённой разностью преобразуется заданной операцией в пару величин с такой же или другой, но определённой разностью. Для некоторых операций, например циклического сдвига или XOR, данная проблема решается тривиально, но для таких часто используемых операций, как сложение, вычитание и умножение по модулю изучение изменения разности нетривиально. В работе, посвящённой дифференциальному криптоанализу шифра RC5 [8], утверждается, что однобитовая разность остаётся неизменной после операции сложения с вероятностью 1/2 (или с вероятностью 1, если этот единственный бит - старший). Данное утверждение теоретически не доказывается, но проводятся эксперименты, подтверждающие достоверность разработанной атаки. В работах по дифференциальному криптоанализу шифров MARS [9] и CAST-256 [10] данный факт используется со ссылкой на [8] и последующими экспериментами, подтверждающими достоверность разработанных атак. В работе [11] этот факт доказан теоретически. В [10] используется экспериментально найденная зависимость между весом Хэм-минга разности и вероятностью её сохранения после сложения по модулю. В настоящей работе существование этой зависимости доказано теоретически и показано её существование для операции вычитания. Используем обозначения: s -длина двоичного вектора (в битах); X ~ U{0,1}s - X имеет равномерное распределение на {0,1}s; Ш, В - соответственно сложение и вычитание по модулю 2s; $s-1 - старший бит вектора A; H(А) - вес Хэмминга вектора А. Основным результатом работы является следующая Теорема 1. Пусть X, Z ~ U{0,1}s и Y = X 0 А, где H(А) = h, 0 ^ h ^ s - 1. Тогда а) P((X Ш Z) 0 (Y Ш Z) = А)= 2-h, если £в-1 = 0; б) P((x Ш Z) 0 (y Ш Z) = А)= 2-(h-1), если £s-1 = 1. Следствие 1. Пусть X, Z ~ U{0,1}s и Y = X 0 А, где H(А) = h, 0 ^ h ^ s - 1. Тогда ( ) а) P((X В Z) 0 (Y В Z) = А)= 2-h, если ^-1 = 0; б) P((x В Z) 0 (y В Z) = А)= 2-(h-1), если 5в-1 = 1. Доказательства теоремы и следствия можно найти в [12].

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