Пособие «Защита информации» (МФТИ)

Round

{

ByteSub()

ShiftRow()

MixColomn()

AddRoundKey()

}

Последний раунд не содержит операции MixColomn().

ByteSub (Замена байтов)

ShiftRow (Сдвиг строк)

MixColomn (Смешивание столбцов)

Опишем каждую из операций более подробно:

1.Замена байтов представляет собой нелинейную замену байтов, действующую на каждый байт состояния независимо. Таблица замены является обратимой и строится на основе произведения двух преобразований:

1)вычисляется “обратный байт” (обратимость понимается над полем GF(256), а 0 элемент отображается в себя).

2)К полученному байту применяется афинное преобразование:

Для выполнения обратной замены байтов применяется обратная таблица замены, которая получается следующим образом: сначала производится обратное афинное преобразование, а затем вычисляется обратный элемент над GF(256).

2.Под сдвигом строк понимается следующая операция:

10

Строки состояния циклически сдвигаются на различные смещения. Нулевая строка не сдвигается, первая сдвигается на 1 байт, вторая на 2 байта и третья на три байта (при других значениях длины блока значения смещений меняются).

Обратной операцией является циклический сдвиг в другую сторону.

3.Смешивание столбцов происходит следующим образом:

столбец состояния рассматривается как полином над GF(256) и умножается по модулю x4 +1 на фиксированный полином c(x) , где c(x) ='03' x3 +'01' x2 +'01' x+'02'. Это преобразование обратимо, поскольку полином c(x) взаимно прост с x4 +1.

Это преобразование можно записать в матричном виде: b(x) = c(x) a(x) ,

Для выполнения обратного преобразования необходимо произвести умножение на полином d (x) ='0B' x3 +'0D' x2 +'09' x+'0E' .

4.Добавление ключа.

На этом этапе происходит с помощью битового сложения по модулю 2 круговой ключ складывается с состоянием.

11

Получение кругового ключа.

Ключ шифрования для каждого раунда получается следующим образом: Сначала происходит расширение ключа, а затем последовательная выборка из расширенного ключа ключа для каждого раунда.

Полное число битов кругового ключа, необходимго для шифрования, равно длине блока умноженной на количество раундов плюс 1, те для блока длиной 128 бит и 10 раундов необходимо 1408 бит. Первые 128 бит кругового ключа совпадают с самим ключом.

Формирование ключа происходит следующим образом: первые четыре столбца (с номерами 0-3)совпадают с самим ключом, далее столбец с номером четыре получается из третьего с помощью следующей композиции преобразований:

применение операции замены байт, а RotByteсдвиг, преобразующий столбец

(a,b,c,d) в (b,c,d,a).

Тогда весь процесс шифрования можно записать так:

Изначальное добавление кругового ключа N-1 раунд

Последний раунд.

III.Алгоритм дешифрования.

Выше было отмечена реализация обратного к каждому из преобразований раунда:

{

Добавление кругового ключа Обратное смешивание столбцов Обратный сдвиг строк Обратная замена байт

}

Единственное что необходимо это изменить порядок операций каждого раунда. Сложность операций для алгоритма шифрования не изменяется. Однако исходя из алгебраических свойств входящих в раунд преобразований, можно прийти к структуре, не отличающийся от прямого алгоритма. Рассмотрим двухраундовый обратный алгоритм:

AddRoundKey();

12

InvShiftRow();

InvByteSub();

AddRoundKey();

InvMixColumn();

InvShiftRow();

InvByteSub();

AddRoundKey();

Легко заметить, что операции сдвига строк и замены байт можно поменять местами, т.к. замена байт действует на каждый байт независимо. Кроме того, последовательность

AddRoundKey();

InvMixColumn();

можно заменить на

InvMixColumn()

AddRoundKey(InvRoundKey); Здесь InvRoundKey обозначает результат применения операции

InvMixColumn() к ключу. Это следует из линейности операций. Тогда мы получим следующую структуру для двухраундового обратного алгоритма: AddRoundKey();

InvByteSub();

InvShiftRow();

InvMixColumn();

AddRoundKey(Inv);

InvByteSub();

InvShiftRow();

AddRoundKey();

Таким образом, мы получили структуру прямого двухраундового алгоритма. Для большего числа раундов получаем такой же результат. Таким образом, обратный алгоритм имеет ту же структуру.

IV.Реализация алгоритма.

Простая структура операций алгоритма обеспечивает легкость реализации и быстроту исполнения. Основные операции, применяемы при этомэто EXOR, применение S-box, и сдвиг. При этом особенно легко реализовать данный алгоритм на процессорах с длиной слова 32 бит и более. При этом для быстроты реализации в памяти создается таблица, содержащая значения S(a), а также еще 4 таблицы, определяемые через S(a) (всего около 4 кбайт памяти), после чего все преобразования сводятся к циклическим сдвигам и операциям XOR с этими таблицами и ключом. В силу того, что структура обратного алгоритма совпадает со структурой прямого, схема реализации не изменится, но значения элементов в таблицах будут другие, и к расширеннуму ключу необходимо применить операцию обратного смешивания столбцов при его формировании.

Скорость алгоритма (расчеты на P-200)

V.Стойкость алгоритма.

13

Такое произведение не всегда обратимо, но в применении к алгоритму будут использоваться полиномы, для которых существуют обратные.

Практическое задание.

1.Перевод байта в 16 форме в 2 форму и соответствующий многочлен в

GF(256).

2.Сложение двух байтов.

3.Умножение по модулю.

4.Умножение на х, применение для умножения на произвольные

многочлены

5. Определение полиномов с коэффицентами в GF(256), сложение полиномов

6.Умножение полиномов.

VI. Режимы сцепления блоков: ECB, CBC, CFB, OFB.

1.ECB (Electronic Code Book). Блоки шифруются независимо и не сцепляются.

2. CBC (Cipher Block Chaining).

15

ТЕОРИЯ ПРОСТЫХ ЧИСЕЛ

10.2. Нахождение простых чисел

В связи с системой RSA возникают две математические задачи, примыкающие к компьютерной алгебре:

1.разработка методов для нахождения больших простых чисел, позволяющих каждому пользователю построить на компьютере два достаточно случайных простых числа р и q,

2.создание алгоритмов факторизации больших чисел. Эту задачу должен решить противник, чтобы расшифровать информацию, не зная секретного ключа.

Наиболее древний алгоритм нахождения простых чисел — решето Эратосфена (III в. до н.э.) — позволяет выписать все простые числа, не превосходящие данного числа n, а также найти наименьший простой делитель числа n, если n — составное число. Алгоритм заключается в следующем: записываем последовательно все числа от 2 до n, затем в полученной таблице вычеркиваем каждое второе число после 2, каждое третье после 3, каждое пятое после 5 и т.д. При этом каждый раз считаются и уже вычеркнутые числа. После каждой процедуры вычеркивания первое, оставшееся невычеркнутым, число k является простым, а затем вычеркиваются все числа,

следующие за k и кратные k. Вычеркивания производят до тех пор, пока k≤ n , так как, очевидно,

любое составное число а имеет делитель ≤ a .

Отсюда получается и «наивный» алгоритм проверки простоты числа n и, заодно, нахождения собственного делителя n в случае, когда n — составное число. Надо n делить с остатком на числа ≤

n (достаточно делить на нечетные числа). Однако этот алгоритм (как и решето Эратосфена) имеет экспоненциальную сложность: если n имеет длину k, т.е. n в двоичной записи содержит k бит, то надо

k

проделать порядка n ≈ 2 2 операций деления с остатком. Поэтому для больших n (порядка 10100) наивный алгоритм практически неприменим.

Асимптотический закон распределения простых чисел

Пусть π (х) — количество простых чисел, не превосходящих х. Согласно асимптотическому

превосходящее х, окажется простым. Поэтому из асимптотического закона распределения можно сделать вывод, что эта вероятность приблизительно равна ln1x . Следовательно, если взять порядка ln

x случайных чисел от 1 до х, то очень высока вероятность, что хотя бы одно из этих чисел будет простым. Например, если n = 10100, то ln n ≈ 230, и для нахождения простого числа ≤ 10100 надо проверить на простоту 230 случайно выбранных чисел. Впрочем, достаточно рассматривать только нечетные числа, что сокращает проверку практически в два раза, и мы получаем 115 чисел для проверки на простоту. Это уже вполне посильная задача для компьютера. Отметим, что наугад выбранное число ≤ 10100 с вероятностью ≈ 0,9 имеет в своей записи 100 цифр, с вероятностью ≈ 0,99

— не менее 99 цифр, с вероятностью ≈ 0,999 — не менее 98 цифр и т.д. Поэтому с большой вероятностью среди 115 случайно выбранных нечетных чисел ≤ 10100 будет содержаться большое простое число (около 100 десятичных знаков).

Итак, для нахождения больших простых чисел нужен генератор случайных чисел и тесты проверки на простоту. Мы подробно рассмотрим один из вероятностных тестов на простоту, дающий неплохие результаты.

17

Вероятностный тест на простоту Миллера-Рабина

Согласно малой теореме Ферма для любого простого n и любого а Zn+ = {1, 2, ···, n-1}

Определение. Натуральное число n называется псевдопростым по основанию а Zn+ , если

выполнено соотношение (1).

Очевидно, если n — псевдопростое по основанию а, то (а,n) = 1, значит, а U(Zn).

Если найдется а U(Zn), такое, что (1) не выполняется, т.е. n не является псевдопростым по основанию а, то число n составное. Обратное неверно. Существуют составные числа n, для которых

(1) выполняется для всех а U(Zn). Такие составные числа n называются числами Кармайкла по имени математика, исследовавшего эти числа в начале ХХ века. Первые числа Кармайкла — 561 = 3 · 11 · 17, 1105 = 5 · 13 · 17, 1729 = 7 · 13 · 19.

В 1994 г. Алфорд, Гранвилл и Померанц1 доказали, что множество чисел Кармайкла бесконечно, хотя они и достаточно редки. Среди первых ста миллионов положительных чисел имеется только 255 чисел Кармайкла.2 Число n является числом Кармайкла тогда и только тогда, когда:

1.n — произведение, по крайней мере, трех различных простых чисел,

2.n — свободно от квадратов (т.е. n не делится на число, являющееся квадратом, 3.если простое р делит n, то p-1 делит n-1 (Кармайкл, 1912).

Итак, для чисел Кармайкла проверка условия (1) не дает результата: для любого а U(Zn) (1) выполняется. Однако для простого числа n из (1) можно получить и другие сравнения.

Действительно, пусть 2s — максимальная степень 2, делящая n-1, n-1 = 2s·u. Так как an-1-1 = a2s u - 1 =(au-1) (au+1)(a2u+1)(a4u+1)··· (a2s −1 u +1)≡ 0(mod n) и кольцо Zn является полем (n — простое), то одна из скобок равна 0 в Zn. Поэтому косвенным подтверждением, что n — простое число, является выполнение для любого а Zn+ одного из следующих сравнений:

Следовательно, если найдется число а Zn+ для которого либо не выполняется (1), либо не выполняется ни одной из соотношений (2), то число n — составное. Будем называть такие числа а Zn+ хорошими для n. Мы покажем, что для составного числа n хорошие числа существуют, и их достаточно много, чтобы использовать случайно выбранные а Zn+ для исследования числа n. Вероятностный тест на простоту Миллера-Рабина заключается в проверке соотношений (1),(2) для случайно выбранных а Zn+ .

Анализ алгоритма Миллера-Рабина

Мы покажем, что для составного числа n количество хороших а Zn+ не меньше n 2−1 .

Следовательно, вероятность случайного выбора плохого а не больше ½, а, значит, при t-кратном случайном выборе вероятность того, что все выбранные а являются плохими, не превосходит 2-t. Это и есть вероятность того, что при составном n алгоритм MILLER-RABIN (n, t) дает на выходе значение PRIME. Например, при t = 50 вероятность ошибки значения PRIME очень мала и не превосходит 2-50. Понятно, что такой вероятностью можно пренебречь.

Теорема. Для нечетного составного числа n количество хороших чисел а Zn+ не меньше n 2−1 .

1Alford W.R., Granville A., Pomerance C. There are infinitly many Carmichael numbers // Ann. Math. 140, 1994/ P/ 703-722/

2Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999. — 960 с.

18

n 2−1 . Для плохих а

вычисляются все соотношения (1) — (2). В частности из (1) следует, что плохое число а взаимно

просто с n, т.е. а U(Zn).

Идея доказательства состоит в том, чтобы показать, что все плохие а лежат в некоторой собственной подгруппе H U(Zn). По теореме Лагранжа порядок Н является делителем n и, значит, число элементов в любой собственной подгруппе не превосходит половины элементов группы.

Рассмотрим два случая:

1)n не является числом Кармайкла, т.е. существует а U(Zn) такое, что an-1 ≡ 1(mod n). Тогда множество H = {x U(Zn) | xn-1 ≡ 1(mod n)} является собственной подгруппой в U(Zn) (т.е. а

H). Так как все плохие числа лежат в Н, то утверждение справедливо.

2)Пусть n — число Кармайкла, т.е. для всех а U(Zn) выполнено сравнение (1). Покажем, что n с, pделится на два различных простых числа. Если n = p —простое, с>1, то

U (Zn ) =ϕ(n) = ( p −1) pc−1 . Так как группа U(Zn) — циклическая, то ϕ(n) | n −1. Следовательно

р|n-1 = pc-1. Противоречие. Представим n в виде n = m1m2, (m1, m2) = 1, mi > 1. Запишем n-1 в виде n-1 = 2s·u, где 2s — наибольшая степень двойки, делящая n-1. Рассмотрим часть последовательности значений в Zn, которые принимает переменная d в алгоритме GOOD

NUMBER (a, n) для произвольного а Zn+ .

которого существует максимальное j с условием b2s u ≡-1(mod n) среди всех элементов а U(Zn), для которых в последовательности Dа встречается -1.

Пусть Н = { х U(Zn) | x2s u ≡ ± 1(mod n)}. Н — подгруппа в U(Zn).

а) все плохие числа лежат в Н.

Действительно, если а — плохое число, то а U(Zn) и для a2s u = аn-1 ≡ 1(mod n), т.е. полезный элемент в последовательности Dа равен 1. Если au ≡ 1(mod n), то a2s u = 1 и а Н. Если au ≡ 1(mod n),

то среди чисел a2s u есть -1 по определению плохого числа. В силу выбора j, k ≤ j. Поэтому a2 j u ≡ ±

1(mod n) и а Н.

в) Н — собственная подгруппа в U(Zn).

Для элемента в имеем сравнение b2·u ≡-1(mod n). Следовательно, b2 j u ≡-1(mod m1). Применим китайскую теорему об остатках. Существует f Zn+ , такой, что f ≡b(mod m1) и f ≡ 1(mod m2). Тогда

f 2 j u ≡ - 1(mod m1) и f 2 j u ≡ 1(mod m2).

Следовательно, f 2 j u ≡ ± 1(mod n). По построению f ≡ b(mod m1), поэтому (f, m1) = 1. Аналогично,

(f, m2) = 1. Поэтому (f, n) = 1 и f U(Zn). Итак, существует f U(Zn), такой, что f Н.

Мы снова показали, что все плохие числа лежат в собственной подгруппе группы U(Zn). Согласно более сильной оценке Рабина для n ≠ 9 вероятность случайного выбора плохого числа

не превосходит ¼ и эта оценка не улучшаема.

19