Часть 2

Q: А какие есть симметричные алгоритмы шифрования?

A: Да их немеряно! Приведем наиболее известные:

Шифр Цезаря
Великий император, с целью сокрытия содержания написанного заменял каждую
букву на третью следующую за ней по счету букву алфавита. Цезарь применял
сдвиг на три буквы; в общем случае это может быть любое число, меньшее, чем
длина алфавита. Это число и является ключом в данном шифре:
А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Ь Ъ Э Ю Я
Г Д Е Е Ж 3 И И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Ь Ъ Э Ю Я А Б В
КРИПТОГРАФИЯ -> НУЛТХСЕУГЧЛВ

Шифр Виженера
Является модификацией шифра Цезаря, в котором величина сдвига является
переменной и зависит от ключевого слова. Например, если в качестве ключевого
слова использовать слово "ТАЙНА", то это будет означать, что первую букву
сообщения необходимо сдвинуть на 20 (порядковый номер буквы "Т"), вторую -
на 1 (порядковый номер буквы "А"), третью - на 11, четвертую - на 15,
пятую - на 1, шестую - снова на 20 (ключевое слово начинаем использовать
с начала) и т.д. Таким образом, ключевое слово "накладывается" на защищаемый
текст.

Шифр Вернама
Алгоритм был изобретен в 1917 г. сотрудником компании AT&T по фамилии
Vernam и называется одноразовым блокнотом (one-time pad).
В этом алгоритме ключ представляет собой последовательность битов не менее
длинную, чем шифруемое сообщение m.
Результат шифрования получается в результате побитового сложения по модулю 2
сообщения и ключа.
Расшифровка состоит в побитовом сложении шифрограммы с ключом.
Отметим, что данный алгоритм утрачивает свою надежность, если два сообщения
оказываются зашифрованы одним и тем же ключом. В этом случае путем побитового
сложения шифрограмм можно исключить биты ключа, а получившаяся побитовая
сумма осмысленных сообщений поддается методам статистического анализа.
Ключ должен быть надежным образом передан адресату, что само по себе не
проще, чем передача сообщения. Единственная выгода метода состоит в том,
что ключ можно передать заранее, а сообщение - по открытому каналу и тогда,
когда это будет нужно.

AES.
Победителем конкурса AES стал алгоритм Rijndael (см. ниже).

BlowFish.
Блочный алгоpитм, сбалансиpованная сеть Файстеля, 16 итеpаций пpостого
кpиптогpафического пpеобpазования. Длина ключа 40 - 448
бит, отсюда сложная фаза инициализации до опеpаций шифpования.
Разработан в 1993 году.
Автор: Брюс Шнаейр (Bruce Schneier)
Параметры:
- pазмер блока 64 бита
- pазмер ключа 32-448 бит
- число раундов 16

CAST.
В некотором смысле аналог DES.
Авторы: C.M. Adams и S.E.Tavares.
Параметры:
CAST-128
- размер блока 64 бита
- размер ключа 128 бит
- число раундов 16
CAST-256
- размер блока 128 бит
- размер ключа 256 бит

DEAL.
Базируется на DES (DEA). Увеличение длины блока уменьшает вероятность удачной
криптоатаки методом сравнения криптограмм, уровень стойкости шифрования
сопоставим с уровнем triple-DES.
Автор: Lars R. Knudsen.
Параметры:
- размер блока 128 бит
- размер ключа 128/192/256 бит
- число раундов: 6 (DEAL-128, DEAL-192); 8 (DEAL-256)

DES.
Алгоритм с эффективной длиной ключа в 56-bits (хотя часто говорят о 8 байтах,
но старший бит в байте не используется).
Автор: National Institute of Standards and Technology (NIST).
Параметры:
- размер блока 64 бита
- размер ключа 56 бит
- число раундов 16

IDEA (International Decryption-Encryption Algorithm)
Время/место разработки 1990-1991 годы, Цюрих, Швейцария.
Архитектура Общая сбалансированная шифрующая SP-сеть, инвариант раунда -
побитовая сумма по модулю 2 старшей и младшей половин блока.
Авторы: Xuejia Lai, James Massey.
Параметры:
- pазмер блока 64 бита
- pазмер ключа 128 бит
- число раундов 8

Lucifer.
первый (опубликованный в открытой печати) блочный алгоритм. Предтеча DES
Автор: Horst Feisstel, Walter Tuchman (IBM)
тип - сеть Файстеля
Параметры:
- размер блока 128 bit
- размер ключа 128 bit
- число раундов 16 .
В каждом используется подключ в 72 бита, порождаемый из главного
ключа. Поскольку имеет бОльший размер ключа и блока по отношению к DES,
поэтому более устойчив к дифф. криптоанализу


NewDES.
Создан в 1985 как творческая переработка DES. Это самостоятельный алгоритм, а
не вариант DES. NewDES несколько проще, чем DES, поскольку у него нет начальной
и, понятно, конечной перестановки. Операции производятся над байтами, а не
битами как в DES. Brute-force атака на NewDES требует 2^119 операций, против
2^111 для TripleDES.
Автор: Robert Scott.
Параметры:
- размер блока 64 бита
- размер ключа 120 бит
- число раундов 17

RC2.
Блочный алгоpитм шифpования. Длина ключа пpеменная - от 8 до 1024 бит.
Разpабатывался под 16-ти битное слово. Реализyет
16 pаyндов "пеpемешивающих" (mixing) и 2 pаyнда "pазмазывающих" (mashing)
пpеобpазований. Описан в RFC2268. Разpаботал Ron Rivest (RSA Laboratories).
Режимы: ECB, CBC, CFB 8bit, OFB, OFB counter 8bit
ECB, CBC, OFB: шифруют данные блоками по 64 бита (8 байт)
CFB, OFBC: шифруют данные блоками по 8 бит (1 байту)
Автор: RSA Data Security (Ron Rivest)
/RC - Ron's Code/
Параметры:
- размер блока 64 бита
- размер ключа до 1024 бит
- число раундов 16

RC4.
Описывать RC4 просто. Алгоритм работает в режиме OFB: поток ключей не
зависит от открытого текста.
Используется S-блок размером 8*8: S0, S1, . . . , S255. Элементы
представляют собой перестановку чисел от 0 до
255, а перестановка является функцией ключа переменной длины. В алгоритме
применяются два счетчика, i и j,
с нулевыми начальными значениями.
Для генерации случайного байта выполняется следующее:
i = (i + 1) mod 256
j = (j + Si) mod 256
поменять местами Si и Sj
t = (Si + Sj) mod 256
K = St
Байт K используется в операции XOR с открытым текстом для получения
шифротекста или в операции XOR с шифротекстом для получения открытого
текста. Шифрование выполняется примерно в 10 раз быстрее, чем DES.
Также несложна и инициализация S-блока. Сначала заполним его линейно:
S0 = 0, S1 = 1, . . . , S255 = 255. Затем заполним ключом другой 256-байтовый
массив, при необходимости для заполнения всего массива повторяя ключ: K0, K1,
. . . , K255. Установим значение индекса j равным 0. Затем:
for i = 0 to 255:
j = (j + Si + Ki) mod 256
поменять местами Si и Sj
Автор: RSA Data Security (Ron Rivest)
/RC - Ron's Code/

RC5
Блочный шифр с переменными параметрами.
Режимы: ECB, CBC, CFB 8bit, OFB, OFB counter 8bit
Шифр RC5 "словоориентированный"; все простейшие вычислительные операции
производятся над w-битными словами. RC5 блочный шифр с размерностью входного и
выходного блоков 2 слова. Номинальный выбор для w - 32 бита, при котором
входной и выходной блоки RC5 имеют размер 64 бита. В принципе, RC5 допускает
любое значение w>0, однако для простоты принимают допустимые значения w - 16,
32 и 64 бита.
Число раундов r является вторым параметром RC5. Выбор большего числа раундов
увеличивает степень защиты. Возможные значения для r: 0,1,...,255.
Заметим также, что RC5 имеет расширенную ключевую таблицу S, получаемую из
предоставляемого пользователем секретного ключа. Размер t таблицы S также
зависит от числа раундов r и составляет t=2(r+1) слов. Выбор большего числа
раундов, таким образом, увеличивает требования к памяти.
Для записи параметров RC5 применяют следующую нотацию: RC5-w/r/b. Например,
запись RC5-32/16/10 означает, что используются 32-битные слова, 16 раундов и
10-байтовый (80-битный) секретный ключ, а также расширенная ключевая таблица
размером 2(16+1)=34 слов. "Номинальным" набором параметров считается
RC5-32/12/16 (размер слова 32 бита, число раундов - 12 и 16-байтовый ключ).
ECB, CBC, OFB: шифруют данные блоками по 64 бита (8 байт)
CFB, OFBC: шифруют данные блоками по 8 бит (1 байту)
Автор: RSA Data Security (Ron Rivest)
/RC - Ron's Code/
Параметры:
- размер блока 32/64/128 бит
- размер ключа до 2048 бит

RC6
Блочный шифр
Автор: RSA Data Security (Ron Rivest)
/RC - Ron's Code/
Параметры:
- размер блока 128 бит
- размер ключа до 2048 бит
- число раундов 16-24


Rijndael.
Является нетрадиционным блочным шифром, поскольку выполнен в архитектуре
SQUARE. Алгоритм представляет каждый блок кодируемых данных в виде двумерного
массива байт размером 4х4, 4х6 или 4х8 в зависимости от установленной длины
блока. Далее на соответствующих этапах преобразования производятся либо над
независимыми столбцами, либо над независимыми строками, либо вообще над
отдельными байтами в таблице.
Автор: Joan Daemen and Vincent Rijmen
Параметры:
- размер блока 128, 192, 256 бит, в качестве AES допускается
использование шифра с размером блока 128 бит;
- размер ключа 128, 192, 256 бит
- число раундов 10, 12, 14. Зависит от размера блока (Nb) и ключа (Nk),
заданных в битах, по следующей формуле: Nr=max(Nb,Nk)/32+6;

SAFER.
Автор: J. L. Massey
Параметры:
- размер блока 64 бит
- размер ключа 64/128
- число раундов, r:
SAFER K64 6 (5<r<11)
SAFER SK64 8 (5<r<11)
SAFER K128 10 (9<r<13)
SAFER SK128 10 (9<r<13)

SAFER+ ("Secure And Fast Encryption Routine")
один из кандидатов на AES
Автор: Cylink Corporation
Параметры:
- размер блока 16 байт
- размер ключа 128/192/256
- число раундов 8/12/16

Skipjack.
Старательно пропихиваемый госдепом США симметричный алгоритм шифрования с
разделяемым ключом и бэкдором. Используется в чипах Clipper и Capstone, которые
хотят засунуть до Интернет унитазов включительно .
Интересен тем, что ломается 31 раунд (по аналогии с DES запас сделан
минимальный). Еще интересен тем, что по аналогии с ГОСТ ключевое расширение
получается простым повторением ключа.
Режимы: ECB, CBC, CFB 8bit, OFB, OFB counter 8bit
ECB, CBC, OFB: шифруют данные блоками по 64 бита (8 байт)
CFB, OFBC: шифруют данные блоками по 8 бит (1 байту)
Автор: NSA
Параметры:
- размер блока 64 бита
- размер ключа 80 бит
- число раундов 32


TEA (Tiny Encryption Algorithm).
Авторы: David Wheeler, Roger M. Needham
Параметры алгоритма :
- размер блока - 64 бита.
- размер ключа - 128 бит.

TripleDES.
Алгоритм зашифрования состоит в следующем: исходный текст зашифровывается DESом
с ключом K1, результат расшифровывается DESом с ключом K2, а этот результат
опять зашифровывается DESом с ключом K1. Итого длина ключа составляет 112 бит.
Иногда применяют 3 разных ключа, но стойкость от этого не меняется.
DES - не группа, то есть композиция двух операций шифрования с разными
ключами не является в общем случае DES-шифрованием с некоторым третьим
ключом [2.5]. Следовательно, можно пытаться увеличить пространство ключей
за счет многократного применения DES.
Двойной DES, c=К1(К2(m)), не обеспечивает увеличение в 2 в 56 степени
раз объема перебора, необходимого для определения ключа, поскольку при
атаке с известным открытым текстом можно подбирать параллельно исходный
текст m и шифрограмму c, накапливать в хэш-таблице значения К2(m),К1^-1(c)
и искать совпадения между ними.
Тройной DES рекомендуется специалистами в качестве замены DES:
В режиме ECB c=К1(К2(К3(m))) или c=К1(К2^-1(К3(m)))
В других режимах c=К1(К2^-1(К1(m)))
Применение функции расшифрования на втором шаге объясняется желанием достичь
совместимости с однократным алгоритмом DES в случае, если все ключи равны.
Тройное шифрование с двумя ключами все равно сводится к одинарному при
использовании атаки с выбором открытого текста [2.6].
Автор: NIST ANSI X9.17, "American National Standard, Financial Institution
Key Management (Wholesale)", 1985.
ISO/IEC 8732:1987, "Banking - Key Management (Wholesale)".
Параметры:
- размер ключа 112 бит
- остальное - см. DES

ГОСТ 28147-89
Российский федеральный стандарт шифрования. Фактически, описывает несколько
алгоритмов (режимы работы ГОСТ). Кроме ключа ему необходима еще одна таблица
(таблица замен, 128 ячеек 4-битовых чисел) для формирования узлов замены. ГОСТ
ее не определяет, посему она может рассматриваться как долговременный ключевой
элемент. Определены следующие режимы работы: режим простой замены (ECB), режим
гаммирования (SM) и режим гаммирования с обратной связью (OFB). Несколько
особняком стоит режим выработки имитовставки. В принципе, у него такое же
назначение как у хэш-функции, только ее значение еще зависит от секретного
ключа. Из полученного в результате 64 битного значения выбирается l битов, где
l<=32. Минимальный размер данных для имитозащиты - 2 64-битных блока.
Автор: КГБ СССР
Параметры:
- размер блока 64 бита
- размер ключа 256 бит
- число раундов 32 (16 - для имитовставки)

Q: Каковы должны быть правила построения таблиц (узлов) замены в ГОСТе?

A: Основная задача -- сделать S-box'ы (так называют эти таблицы) устойчивыми к
дифференциальному и линейному криптоанализу. Можно попробовать
сформулировать критерии, глядя на те критерии, которые Тучман использовал в
начале 70-х для DES. /* потребовалось около 10 месяцев */
Итак, можно сформулировать следующие правила:
1. Hи один выходной бит не должен сколь-нибудь хорошо приближаться линейной
функцией от входных бит.
2. Если два входных значения отличаются на один бит, выходные значения
должны отличаться не менее чем на 2 бита.
3. Если два входных значения отличаются в двух соседних битах (как минимум
центральных), то выходные значения должны отличаться не менее чем на 2 бита.
4. Для любого значения XOR между входными значениями, следует минимизировать
количество пар, чьи XOR на входе и на выходе равны этому значению (это
весьма хитроумное требование вытекает из попытки защититься от
дифференциального
криптоанализа).
5. S-box'ы не должны быть похожи друг на друга. Hапример, количество входных
значений, дающих одно и тоже значение на выходе из разных S-box'ов, должно
быть минимально.
6. Узлы замены в идеале должны учитывать особенности входного текста: если
используются только алфавитно-цифровой диапазон ASCII-таблицы, то он должен
отображаться (после замены) на все множество используемого алфавита, скрывая
статистические свойства открытого текста.