ОГЛАВЛЕНИЕ

А. Г. Ростовцев

Большие подстановки для программных шифров

1. Симметричные шифры

В последние годы наблюдается отход от подстановочно-перестано-
вочных шифров, типичными представителями которых являются DES,
ГОСТ 28147-89. С одной стороны, это обусловлено публикацией в откры-
той печати новых методов криптоанализа, в первую очередь, дифференци-
ального и линейного. С другой стороны, такие шифры имеют малую нели-
нейность и диффузию, что компенсируется увеличением количества цик-
лов шифрования (например, 32 цикла в ГОСТ 28147–89). Кроме того, эти
шифры ориентированы на аппаратное построение, поэтому шифраторы
получаются дорогими, а большое число циклов шифрования и короткая
подстановка приводит к низкой производительности.
Зарубежные популярные шифры последних лет [1] (IDEA, SAFER,
RC5, Blowfish и т. п.) имеют другую, процессорно-ориентированную,
структуру. Особенностью этих шифров является работа не с битами, а со
словами, длина которых равна разрядности процессора. Для получения
высокой нелинейности используются операции умножения. Например,
*
шифр IDEA использует умножение в группе F216 + 1 . Другим примером яв-
ляется шифр SAFER, в котором нелинейная операция выполняется возве-
*
дением образующей в степень или логарифмированием в группе F2 8 + 1 .
Подстановки SAFER и IDEA невелики (8 или 16 бит), поскольку они ис-
пользуют поля вычетов по модулю простых чисел Ферма — 28 + 1 и 216 + 1,
тогда как более удобные числа 232 + 1, 264 + 1 — составные.
Приведенные примеры показывают, что проблема создания широко-
го класса больших процессорно-ориентированных нелинейных подстано-
вок с хорошей диффузией является актуальной при разработке шифров.

2. Операция подстановки

Предлагаемая подстановка задается многочленом над кольцом
R = Z/(2m). Разрядность подстановки целесообразно выбирать в соответст-
вии с разрядностью процессора (m = 16, 32, 64, 128). Уравнение подста-
новки над R имеет вид
i
? ai x 2 (mod 2 m ) ,
x< (1)
0 ? i < log 2 m




«Проблемы информационной безопасности. Компьютерные системы»,
СПб., 2000. № 3. С. 31–35
2


где число ненулевых слагаемых в сумме (1) нечетно и не менее 3, и все
ненулевые коэффициенты ai обратимы, a0 ? 0. Наиболее простое уравне-
ние неаффинной подстановки имеет вид
x < a2x4 + a1x2 + a0x (mod 2m), (2)
где a0, a1, a2 — обратимые элементы в R, которые могут являться частью
ключа.

Теорема 1. Уравнение (2) описывает подстановку в R.
Доказательство. Очевидно, что (2) отображает кольцо R в себя.
Функция (2) не является подстановкой тогда и только тогда, когда она при-
нимает какое-нибудь значение дважды. Если предположить, что при пере-
боре x функция (2) принимает дважды некоторое значение b, то сравнение
a2x4 + a1x2 + a0x – b ? 0 (mod 2m) (3)
должно иметь двойной корень. Кратные корни можно определить вычис-
лением наибольшего общего делителя (3) и производной. Поскольку в R
каждый неделитель нуля обратим, нужно рассматривать наибольший об-
щий делитель над каждым главным идеалом, который является делителем
нуля в кольце R. Достаточно рассмотреть случаи колец Z/(2), Z/(22), …,
Z/(2m).
Производная левой части (3) равна 4a2x3 + 2a1x + a0. Нетрудно ви-
деть, что левая часть (3) не делится на производную ни над одним из ука-
занных колец. Кроме того, производная не имеет корней ни в одном из
этих колец, так как коэффициент a0 нечетный, а коэффициенты при степе-
нях x четные. Многочлен, задающий производную, имеет степень три, по-
этому он может раскладываться на множители лишь тогда, когда хоть
один из делителей имеет степень 1, то есть когда производная имеет ко-
рень в указанных кольцах. Поскольку корней нет, то производная от (2) не
раскладывается на множители ни над одним из указанных колец. Следова-
тельно, наибольший общий делитель функции (3) и ее производной над
каждым из указанных колец равен обратимой константе, и (2) задает под-
!
становку в R.

Основной операцией при вычислении (2) является возведение в
квадрат, эта операция может быть несколько упрощена, если m вдвое пре-
вышает разрядность процессора. Пусть x = x0 + x12m/2. Тогда x2 ? x02 +
+ 2x0x12m/2 (mod 2m). Однако второе слагаемое можно не умножать на 2, так
как использование выражения y < x02 + x0x12m/2 (mod 2m) вместо возведе-
ния в квадрат в (2) тоже задает подстановку.

Подстановка (2) может быть использована непосредственно как одна
из операций шифрования над словами длины m бит, так и над более ко-
3


роткими словами. Подстановка (2) переводит нечетные числа в нечетные.
Выберем (m – 1)-битное слово, дополним его единицей в младшем разряде
и применим подстановку (2). Из результата подстановки удалим младший
единичный разряд. Поскольку этот разряд всегда содержит единицу, то (2)
действует указанным образом как подстановка и в Z/(2m–1).
Вместо одного бита можно присоединять произвольное число l
младших битов, выполнять вычисление согласно (2) и затем удалять l
младших битов. В этом случае (2) задает подстановку, которая действует
на кольце Z/(2m–l). Добавляемые младшие биты, как и коэффициенты a0, a1,
a2 являются параметрами подстановки и могут быть частью ключа.
Рассмотренная подстановка задает одновременно и диффузию, и пе-
ремешивание. Если шифратор выполнять по фейстелевой схеме [2], то вы-
числение подстановки, обратной к (2), не понадобится.

3. Нелинейность, диффузия и дифференциалы подстановки

Семейство подстановок (2) задается алгебраическими функциями
над кольцом Z/(2m) с делителями нуля. Наличие делителей нуля приводит
к тому, что у этих подстановок появляются специфические свойства, кото-
рые могут быть использованы в криптоанализе. Однако эти свойства мож-
но скомпенсировать за счет мощной диффузии и нелинейных перемеши-
вающих свойств, присущих данным подстановкам.
Нелинейность подстановки обычно определяется через нелиней-
ность над F2 булевых функций, задающих подстановку. Нелинейность бу-
левой функции как многочлена из F2[X1, .., Xn]/(X1(1 + X1), .., Xn(1 + Xn)) оп-
ределим как кодовое расстояние между таблично заданной функцией и
наилучшей ее аффинной аппроксимацией. Максимально достижимая не-
линейность сбалансированной k-разрядной булевой функции равна
2k–1 – 2[k/2]. Нелинейность такой функции всегда четная.
Младший двоичный разряд подстановки y = f(x) = x4 + x2 + x, рас-
сматриваемой как вектор y = f(X0 + 2X1 + 4X2 + … + 231X31), описывается
аффинной над F2 функцией и равен X0. Второй разряд также описывается
аффинной булевой функцией и равен X0 + X1. Третий разряд описывается
булевой функцией X0X1 + X2 с нелинейностью 2. Четвертый разряд описы-
вается булевой функцией X0X2 + X3 с нелинейностью 4. Пятый разряд опи-
сывается булевой функцией X0X3 + X1X2 + X4 с нелинейностью 12 и т. д.
Видно, что нелинейность булевых функций быстро возрастает. Кроме то-
го, перечисленные булевы функции являются “самыми нелинейными”
среди сбалансированных функций соответственно от 3, 4, 5 переменных.
Определим нелинейность подстановки (над F2) как среднее арифме-
тическое нелинейностей булевых функций. Нелинейность булевых функ-
ций быстро растет с ростом старшинства разрядов. Максимальную нели-
4


нейность имеют старшие разряды подстановки. Экстраполируя на старшие
разряды то свойство, что нелинейность булевых функций, описывающих
младшие разряды подстановки, максимальна, можно получить оценку для
нелинейности подстановки. Для 32-разрядной подстановки (2) эта нели-
нейность равна 108, для 16-разрядной подстановки (2) нелинейность со-
ставляет 2?103. Таким образом, данная подстановка имеет высокую нели-
нейность. Есть основания предполагать, что линейный криптоанализ
шифра, основанный на использовании булевых функций над F2, будет не-
эффективным.
Подстановка обладает значительной диффузией, поэтому остальные
операции, используемые при шифровании, должны обеспечивать диффу-
зию разностей для m-разрядных слов внутри шифруемого блока. Такой
операцией может служить преобразование вида
n
xi < ? x j ? xi (mod 2 m )
j =1

(n — число m-разрядных слов в блоке) в сочетании с циклическими сдви-
гами слов или умножение шифруемого блока как n-мерного вектора над
Z/(2m) на неособую матрицу в сочетании с циклическими сдвигами слов.
Подстановка действует на кольце R = Z/(2m) и задается многочленом
над этим кольцом. Кольцо Z/(2m) имеет гомоморфизмы с кольцами Z/(2m–k)
для натуральных k, которые сохраняются под действием подстановки. По-
этому шифр, построенный на основе указанной подстановки, может быть
уязвим по отношению к анализу на основе гомоморфизмов. Указанная
операция диффузии должна обеспечивать неэффективность криптоанализа
на основе гомоморфизмов.
Оценим стойкость шифра, построенного с использованием подста-
новки (2), к дифференциальному методу анализа (точнее, к его усиленно-
му варианту — методу на пучках дифференциалов). Для этого найдем
наиболее вероятный дифференциал (НВД) подстановки (2) над R из мак-
симального числа решений уравнения f(x + a) – f(x) ? b (mod 2m), где f —
подстановка (2), при всевозможных a, b. После раскрытия скобок послед-
нее уравнение в R примет вид
4aa2x3 + 6a2a2x2 + 4a3a2x + 2aa1x + f(a) – b = 0. (4)
Максимальное число решений уравнения (4) в R равно 2m. Это соответст-
вует случаю a = b = 2m–1. Следовательно, НВД вида (2m–1, 2m–1) для подста-
новки (2) имеет вероятность 1. Аналогично можно показать, что каждый
из четырех дифференциалов вида (c?2m–2, d?2m–2) при нечетных c, d для этой
же подстановки имеет вероятность 1/2 и т. д.
Предположим, что другие операторы шифрования реализуют цикли-
ческие сдвиги m-разрядных слов и операции сложения и что анализ про-
5


водится на основе подобранных открытых текстов. Тогда после второго
цикла шифрования НВД будет иметь вероятность 2–m/2. После трех циклов
НВД будет иметь вероятность 2–m и т. д.
Пусть шифратор с неизвестным ключом работает непрерывно в те-
чение 10 лет со скоростью 108 бит/с и нарушитель знает открытые и соот-
ветствующие зашифрованные тексты. За это время нарушитель сможет
получить 3?1014 128-разрядных блоков текста. Для успешного дифферен-
циального анализа необходимо, чтобы произведение объема статистики на
вероятность НВД было близко к 1. Тогда вероятность появления НВД по-
сле предпоследнего цикла шифрования, меньшая 2–63, представляется
безопасной.
Предположим, что распределение дифференциалов на различных
циклах шифрования независимо и использование пучков дифференциалов
для криптоанализа невозможно (подстановка обладает сильным переме-
шиванием, поэтому предположение допустимо при условии, что осталь-
ные операторы шифрования обеспечивают необходимую диффузию на
уровне слов). Тогда для m = 32 вероятность НВД после двух циклов шиф-
рования не будет превышать 2–16. После трех циклов получаем вероят-
ность наиболее вероятного дифференциала не более 2–32 и т. д. Отсюда
следует, что для успешного противостояния дифференциальному методу
криптоанализа достаточно 6 циклов шифрования. Для m = 16 достаточно 10
циклов, а для m = 64 — только 4 или 5 циклов. Из этих оценок следует, что
возможна реализация программного шифратора со скоростью десятки мега-
бит в секунду на 32-разрядном процессоре со встроенным умножителем.
Отметим, что данная оценка является приблизительной и получена в
предположении, что НВД не зависит от входных текстов и алгоритм шиф-
рования обеспечивает необходимый уровень диффузии на уровне
m-разрядных слов, исключающий возможность использования пучков
дифференциалов. Для повышения стойкости к линейному над R методу
анализа необходимо тщательно выбирать оператор диффузии.

Литература
1. Menezes A., van Oorchot P., Vanstone S. Handbook of applied cryptography. — CRC
Press, 1997.
2. Schneier B. Applied Cryptography: Protocols, Algorithms, and Source Code in C. —
J. Wiley & Sons, New York, 1996.



ОГЛАВЛЕНИЕ