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 SAFER SK64 8 (5 SAFER K128 10 (9 SAFER SK128 10 (9 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
Параметры:
- размер блока 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-таблицы, то он должен отображаться (после замены) на все множество используемого алфавита, скрывая статистические свойства открытого текста.
A2: Запросить узел замены в ФАПСИ.
III. Несимметричные шифры.
Q: А какие есть несимметричные алгоритмы шифрования?
A: А вот этих немного : ) В принципе, вся несимметричная криптография строится на 2 проблемах: проблеме разложения большого числа на простые множители и проблеме дискретного логарифмирования. Собственно, для шифрования используется алгоритм RSA (Rivest-Shamir-Adleman), разработанный в 1977 году математиками Роном Райвестом (R. Rivest), Ади Шамиром (A. Shamir) и Леонардом Аделманом (L. Adleman). Используется не только для шифрования, но и для формирования ЭЦП. Схема примерно такая:
Абонент А, желающий вступить в переписку, ЗАРАHЕЕ:
- вырабатывает различные простые числа p, q, примерно равной разрядности, и вычисляет n=p*q;
- генерирует случайное числе e < n и вычисляет d, такое что e*d == 1(mod ф(n)); (ф(n) - функция Эйлера)
- рассылает открытый ключ (e, n);
- сохраняет в тайне секретный ключ (p, q, d).
Абонент B, желающий ЗАШИФРОВАТЬ сообщение для абонента А, выполняет следующие действия:
- открытый текст разбивается на блоки, каждый из которых представляется как число m, 0
Для РАСШИФРОВАHИЯ абонент А выполняет следующие действия:
- вычисляет m' = E(n, d, c) = c^d (mod n).
A2:
Если приводить к фундаментальным математическим
проблемам, то все существующие алгоритмы с открытым ключём стремятся построить таким образом что бы они были похожи на полиномиальные для владельца секретного ключа и на NP-полные проблемы для всех остальных. В [1. 2, pp. 461-482] приведено
9 таких систем (ну, скажем, популярные ныне элипические кривые это просто смена конечного поля, ещё парочку можно свести к другим, но 6 принципиально разных алгоритмов имеется).
В тоже время доказательств NP-полноты нет ни у большинства из них, а про RSA имеются серьёзные подозрения на его полиномиальность.
Всех их можно использовать для шифрования, но большинство (кроме RSA) можно использовать для одновременной аутентификации за те же деньги. Поэтому более корректно сказать, что RSA можно использовать только для шифрования (в нём даже ЭЦП является формой шифрования, так и пишут: encrypted digest : )
IV. Хэш-функция.
Q: Что такое хэш-функция (hash, hash-function)?
A: Это преобразование, получающее из данных произвольной длины некое значение (свертку) фиксированной длины. Простейшими примерами являются контрольные суммы (например, crc32). Бывают криптографические и программистские хэши. Криптографический хэш отличается от программистского следующими двумя свойствами: необратимостью и свободностью от коллизий. Обозначим m -- исходные данные, h(m) -- хэш от них. Hеобратимость означает, что если известно число h0, то трудно подобрать m такое, что h(m) = h0. Свободность от коллизий означает, что трудно подобрать такие m1 и m2, что m1 ! = m2, но h(m1) = h(m2).
Криптографические хэш-функции разделяются на два класса:
- хэш-функции без ключа (MDC (Modification (Manipulation) Detect Code) коды),
- хэш-функции c ключом (MАC (Message Authentication Code) - коды). Хэш-функции без ключа разделяются на два подкласса:
- слабые хэш-функции,
- сильные хэш-функции.
Слабой хэш-функцией назывется односторонняя функция H(x), удовлетворяющая следующим условиям:
1) аргумент х может быть строкой бит произвольной длины;
2) значение H(x) должно быть строкой бит фиксированной длины; 3) значение H(x) легко вычислить;
4) для любого фиксированного x вычислительно невозможно найти другой x' ! = x, такой что H(x')=H(x).
Пара x' ! = x, когда H(x')=H(x) называется коллизией хэш-функции. Сильной хэш-функцией называется односторонняя функция H(x), удовлетворяющая условиям 1-3 для слабой хэш-функции и свойству 4':
4') вычислительно невозможно найти любую пару x' ! = x, такой что H(x')=H(x).
Поскольку из свойств 1-2 следует, что множество определения хэш-функции значительно шире множества значений, то коллизии должны существовать. Свойство 4 требует, чтобы найти их для заданного значения х было практически невозможно. Требование 4' говорит о том, что у сильной хэш-функции вычислительно невозможно вообще найти какую-либо коллизию.
Хэш-функцией с ключом (MAC) называется функция H(k, x) удовлетворяющая свойствами:
1) аргумент х функции H(k, x) может быть строкой бит произвольной длины; 2) значение H(k, x) должно быть строкой бит фиксированной длины; 3) при любых k и x легко вычислить H(k, x);
4) для любого х должно быть трудно вычислить H(k, x) не зная k; 5) должно быть трудно определить k даже при большом числе неизвестных пар {x, H(k, x)} при выбранном наборе х или вычислить по этой информации H(k, x') для x' ! = x.
Q: А зачем она нужна?
A: Дело в том, что многие криптографические преобразования (в частности, вычисление и проверка электронной цифровой подписи, ЭЦП) выполняются над данными фиксированного размера. Поэтому перед простановкой электронной подписи под многомегабайтным файлом обычно рассчитывают значение хэш-функции от него, а уже от этого значения считают ЭЦП. Кроме того, удобно, например, пароли в базе хранить не в открытом виде, а в хэшированном (так сделано во всех юниксах).
Q: А какие есть алгоритмы хэш-функций?
A: Вот некоторые из них:
MD2
Автор: RFC 1319, "The MD2 Message Digest Algorithm", Burt Kaliski, 1992. Размер: 128 бит.
MD4
Автор: RSA Data Security
Размер: 128 бит.
MD5
Капитально переделанный MD4.
Каждая итерация алгоритма состоит из 64 операций.
Hедавно обнаружена нестойкость к обнаружению коллизий [2. 1. 9, 2. 1. 10, 2. 1. 11], но пока не построена настоящая атака на эту функцию.
Автор: RSA Data Security
Размер: 128 бит.
SHA (Secure Hash Standard)
Один из (относительно) новых алгоритмов свертки.
Функция предложена в качестве национального стандарта США.
Каждая итерация алгоритма состоит из 80 операций.
Автор: NIST (National Institut of Standards and Technology) FIP-180 (Federal Information Processing Standards Publication 180) ANSI X9. 30-2, "American National Standard, Public-Key Cryptography Using Irreversible Algorithms for the Financial Services Industry", 1993. FIPS PUB 180, "Secure Hash Standard", 1993
FIPS PUB 180-1, "Secure Hash Standard", 1994
Размер: 160 бит.
ГОСТ Р34. 11-94
Российский алгоритм. Размерность получаемого значения очень удобна для формирования по паролю ключа для ГОСТ 28147-89.
Автор: Стандарт ГОСТ Р 34. 11-94 разработан ГУБС
ФАПСИ и ВHИИС, внесён ТК 22 "Информационная технология" и ФАПСИ, принят и введён в действие Госстандартом России 23. 05. 94.
Размер: 256 бит.
V. Электронная цифровая подпись.
Q: Что такое электронная цифровая подпись (ЭЦП)?
A: ЭЦП - это для автора документа способ убедить читателей в том, что автор - именно он. Способ работает примерно так.
Вначале автор документа (файла и т. п. ) должен сгенерировать пару ключей, один секретный, один открытый. Секретный ключ
он оставляет при себе, открытый - передает всем потенциальным читателям (под роспись, или по другому доверенному каналу). Теперь при необходимости послать документ автор вычисляет
некоторое число (ЭЦП), которое зависит от самого файла и от секретного ключа. Без знания секретного ключа это число подобрать крайне сложно.
Получатель вычисляет другое число на основе полученного файла, полученной ЭЦП и открытого ключа. Если получилась 1 - значит, документ не был искажен, и автор соответствует предполагаемому. Если получился 0 - значит, это подделка.
