<< Предыдущая

стр. 22
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

вания состоят в обратном линейном преобразовании и вычислении
мультипликативного обратного. Эти преобразования байтов можно
осуществить, используя табличный поиск или микросхему, реализу­
ющую вычисление обратных элементов в F28 и линейные преобра­
зования.

5.3.1.2. ShiftRows. Операция Shift Rows в Rijndael осуществля­
ет раундическии сдвиг матрицы состояний. Каждая из ее строк
сдвигается на свое число позиций. В рассматриваемой версии ши-
142 Глава 5. Симметричные шифры

фра это преобразование имеет вид:

' 5о,0 5о,1 5о,2 5о,3 ^ ' 50,0 «50,1 -^0,2 50,3 ^
51,0 51,1 51,2 51,3 51.1 51,2 51,3 51,0
52,0 52,1 52,2 52,3 52.2 52,3 52,0 52,1
У 53,3 53,0 53,1 5з,2 J
У 5з,0 53,1 53,2 5з,3 J
Обратная операция — тоже простой циклический сдвиг, но в про­
тивоположном направлении. Операция Shif tRows гарантирует, что
столбцы матрицы состояний будут «взаимодействовать» друг с дру­
гом на протяжении нескольких раундов.

5.3.1.3. MixColumns. Операция MixColumns задумана с тем,
чтобы строки матрицы состояний «взаимодействовали» друг с дру­
гом на протяжении всех раундов. В комбинации с предыдущей опе­
рацией она наделяет каждый байт выходных данных зависимостью
от каждого байта на входе.
Мы представляем каждый столбец матрицы состояний как мно­
гочлен степени 3 с коэффициентами из F28:
а{Х) = ао + aiX Н- а2Х^ Н- а^Х .
Новый столбец получается умножением многочлена а{Х) на фикси­
рованный многочлен^
с{х) = 'Q2h' + 'Qlh' • X + 'Qlh' • Х2 + '03/i' • Х^
по модулю многочлена М{Х) — Х^ + 1. Так как умножение на мно­
гочлен — линейная операция, ее можно представить в виде действия
матрицы:

1ьЛ 1аЛ
'01/i' \
/ '02/i' '03/i' 'Qlh'
'Qlh' '{)2h' '03/i' '01^'
6i 0>1

'Ol/i' 'Qlh' 'mh' 'mh'
b2 «2

\h) \а, )
у 'OZh' 'Qlh' 'Qlh' '{)2h'
1
Матрица коэффициентов невырождена над F28, поэтому операция
MixColumns обратима, а обратное к ней действие реализуется ма­
трицей, обратной к выписанной.

^Элементы поля F28 мы записываем либо как битовый вектор, либо как байт. В
частности, '03/г' — это элемент поля F28, представляемый многочленом X + 1 по
модулю М{х). — Прим. перев.
5.3. Rijndael

5.3.1.4- AddRoundKey. Сложение с подключом осуществляется
просто. Нужно сложить по модулю 2 (применить операцию исключа­
ющего ИЛИ) все байты матрицы состояний (которую мы посто­
янно меняли) с соответствующими элементами матрицы подключа.
Обратная операция, очевидно, совпадает с исходной.

5.3.2. С т р у к т у р а раундов
Запишем алгоритм Rijndael на псевдокоде.

AddRoundKey(S,K[0]);
for ( i = l ; i<=9; i++)
{ SubBytes(S);
ShiftRows(S);
MixColuinns(S) ;
AddRoundKey(S,K[i]);
}
SubBytes(S);
ShiftRows(S);
AddRoundKey(S,К[10])

Блок открытого текста, предназначенный для шифрования, за­
писывается в виде матрицы состояний S, Полученный в результате
алгоритма шифротекст представляется той же матрицей. Обратите
внимание, что в последнем раунде операция MixColumns не осуш;е-
ствляется.
Процедура расшифрования представлена следуюш;ей программой
на псевдокоде.

AddRomidKey(S,K[10]);
InverseShiftRows(S);
InverseSubBytes(S);
for (i=9; i > = l ; i ˜ )
{ AddRoшldKey(S,K[i]);
1пуег8еМ1хСо1шш18(8);
InverseShiftRows(S);
InverseSubBytes(S)
}
AddRoundKey(S,KCO]);
Глава 5. Симметричные шифры

5.3.3. Разворачивание ключа
Единственное, что осталось осветить, это вычисление подключен.
Напомним, что основной ключ алгоритма состоит из 128 битов, а
нам нужно произвести 10 подключей Ki^... ,ii^io, каждый из кото­
рых включает в себя четыре 32-битовых слова. Эти слова соответ­
ствуют столбцам матрицы, описанной на стр. 140. Здесь использу­
ется константа раунда RCi^ вычисляющаяся по правилу
RCi = X' (modX^ + Х^ + Х^ + X + 1).
Обозначим г-ый подключ через (VF4b 1^4г+ь М^4г+2^ ^4г+з)- Основной
ключ алгоритма делится на четыре 32-битовых слова (А;о, A;i, А;2, А:з),
после чего подключи получаются в результате выполнения приве­
денного ниже алгоритма. В нем через RotBytes обозначена процеду­
ра циклического сдвига слова влево на один байт, а через SubBytes —
применение S-блока (из этапа шифрования) к каждому байту слова.

W[0]=K[0]; W[l]=K[l]; W[2]=K[2]; W[3]=K[3];
for ( i = l ; i<=10; i++)
{ T=RotBytes(W[4*i-l]);
T=SubBytes(T);
Т=ТЛКС [ i ] ;
W[4*i]=W[4*i-4]AT;
W[4*i+l]=W[4*i-3]AW[4*i] ;
W[4*i+2]=W[4*i-2]AW[4*i+l] ;
W [4*i+3] = [ 4 * i - l ] A [4*i+2] ; }
W W


5.4. Режимы работы DES
Блочный шифр, подобный DES или Rijndael^ можно по-разному ис­
пользовать д^ля шифрования строк данных. Вскоре после DES в
США был принят еш;е один федеральный стандарт, рекомендующий
четыре способа эксплуатации алгоритма DES р^ля шифрования дан­
ных. С тех пор эти режимы стали обш;епринятыми и применяются
с любыми блочными шифрами. Перечислим их.
- ЕСВ. Этот режим прост в обраш;ении, но слабо заш;ищен от
возможных атак с удалениями и вставками. Ошибка, допуш;ен-
ная в одном из битов шифротекста, влияет на целый блок в
расшифрованном тексте.
- СВС— наилучший способ эксплуатации блочного шифра, по­
скольку предназначен ^\ля предотврап];ения потерь в результа-
5,4- PeoicuMbi работы DES

те атаки с использованием удалений и вставок. Здесь ошибоч­
ный бит шифротекста при расшифровании не только превра-
ш;ает в ошибочный блок, в котором содержится, но и портит
один бит в следующем блоке открытого текста, что можно лег­
ко определить и интерпретировать как сигнал о предпринятой
атаке.
- OFB. При таком методе блочный шифр превращается в по­
точный. Режим обладает тем свойством, что ошибка в один
бит, просочившаяся в шифротекст, дает только один ошибоч­
ный бит в расшифрованном тексте.
- CFB. Как и в предыдуш;ем случае, здесь блочный шифр транс­
формируется в поточный. Отдельная ошибка в криптограмме
при этом влияет как на блок, в котором она была допуш;ена,
так и на следуюш;ий блок, как при режиме СВС.
Разберем каждый из стандартных режимов шифрования подробно.

5.4.1, Р е ж и м ЕСВ
Режим ЕСВ (Electronic Code Book — электронная кодовая книга)
является простейшим среди стандартных способов использования
блочного шифра. Данные т , которые предстоит зашифровать, де­
лятся на блоки по п битов:
mi, m2, . . . , гпд.
Последний из них, при необходимости, дополняют до длины п. По
ним определяются блоки Ci, . . . , Cq как результат воздействия ши­
фрующей функции
d = Ekirrii),
как показано на рис. 5.8. Расшифрование здесь — простое обраще­
ние предыдущей операции (см. рис. 5.9).
С режимом ЕСВ связан ряд проблем. Пер­
вая возникает из-за того, что при равенстве "?i ^2 '"з
гщ = rrij МЫ получим одинаковые блоки ши- i i i
фротекста Ci = Cj^ т.е. одинаковые блоки
^к \ \ ^к \ \ ^к
на входе индуцируют совпадающие блоки на
выходе. Это, действительно, проблема, по- 1 1 1
скольку шаблонные начало и конец сообще- 1 i i
НИИ совпадают. Вторая проблема связана с ^ ^ з
тем, что удаление из сообщения какого-либо р^^^ 5.8. Шифровани
блока не оставляет следов, и атакующий мо- в режиме ЕСВ
жет таким образом исказить передаваемую
Глава 5. Симметричные шифры

информацию. Третья очень близка ко второй, но связана со встав­
кой блоков из других сообщений.
Чтобы лучше представить себе эти про­
(-\ с, с, блемы, возьмем простейшую модель шифра,
\ i 1 в которой блок соответствует слову, и пред­
положим, что открытое сообщение
L\ ^* 4j
Плати Алисе сто фунтов,
I I I Яе плати Бобу двести фунтов
^^ ^"2 '"з в зашифрованном виде выглядит так:
Рис. 5.9. Расшифровы- у КОШКИ ЧЕТЫРЕ НОГИ,
вание в режиме ЕСВ ^ у ЧЕЛОВЕКА ДВЕ НОГИ.

Мы можем теперь заставить получателя
оплатить Алисе две сотни фунтов, вместо од­
ной, отправив ему сообщение
У КОШКИ ДВЕ НОГИ,
которое получено из первого заменой одного из блоков на блок из
второго сообщения. Кроме того, мы можем приостановить выплаты
Алисе, поставив блок «А» шифротекста в начало первого сообщения.
Надеюсь, Вы заметили, что «А»— шифрованный вариант частицы
«не» открытого текста. Сообразите, как мы можем побудить полу­
чателя криптограммы выплатить Бобу двести фунтов.
Таким атакам можно противостоять, добавляя контрольные сум­
мы нескольких блоков открытого текста или используя режим, при
котором к каждому блоку шифротекста добавляется «контекстный
идентификатор».

5.4.2. Режим СВС
Один из путей обхода проблем, возникающих при использовании ре­
жима ЕСВ^ состоит в «зацеплении» шифра, т.е. в добавлении к ка­
ждому блоку шифротекста контекстного идентификатора. Самый
простой способ сделать это — применить режим «сцепления блоков
шифра» или СВС (сокращение от «Cipher Block Chaining»).
В этом режиме открытый текст, как обычно, разбивается на
серию блоков:
m i , . . . , mq.
Как и в предыдущем режиме, последний блок может потребовать
дополнения, чтобы длина открытого текста стала кратной длине
5.4' Режимы работы DES

блока. Шифрование осуш;ествляется согласно формулам
Ci = Ek{mi е IV), Ci = Ekirui 0 C^-i) при г > 1,
(см. рис. 5.10).
Обратите внимание на то, что в вычисле-
/Из
НИИ первого блока шифротекста участвует ве­
i i
i
личина IV (начальное значение), которую сле­ / ^ - • (
дует отнести к заданию шифруюш;ей функ­
i ii
ции. Величину IV привлекают к шифрованию Е,
Е,
с тем, чтобы шифрованные версии одинако­
вых частей открытого текста выглядели по-
разному. Нет необходимости скрывать значе­
ние IV, и на практике ее передают в открытом
Рис. 5.10. Шифрова­
виде как часть сообщения. ние в режиме СВС
Естественно, величина IV участвует и
в расшифровании. Этот процесс выглядит следуюш;им образом
(рис. 5.11):
ГГЦ = Dk{Ci) е IV, mi = Dk{Ci) 0 Q-i при i > 1.

Напомним, что при шифровании в режиме ЕСВ ошибка в одном
знаке шифротекста, появляюш;аяся на стадии передачи сообщения,
повлияет на весь блок, в котором она допущена, и он, естественно,
будет расшифрован неверно. В случае режима СВС, как видно из
формул, ошибочный знак повлияет не только на свой блок, но и на
соответствующий бит в следующем блоке.

5.4.3. Р е ж и м OFB

Режим, называемый «обратной связью по вы­
ходу», или OFB (Output Feedback), адапти­
рует блочный шифр к его поточному исполь­
зованию. Для этого выбирается переменная j
А А А
(1 ^ j ^ п), обозначающая число битов на вы­
ходе генератора потока ключей при каждой
IV-^i
итерации. С помощью блочного шифра созда­
i i
1
ется поток ключей, j битов за один раз. Ре­ от, ОТ2
комендуется брать j равное п, поскольку при

<< Предыдущая

стр. 22
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>