I. Общая часть.
Q: Что такое криптография, криптология, криптоанализ?
A: Криптология - это наука о шифрах и всем, что с ними связано.
Криптологию принято подразделять на криптографию и криптоанализ.
Если криптограф занимается вопросами защиты информации при помощи
криптографических методов, то криптоаналитик, напротив, старается
эту защиту преодолеть. Чья работа сложнее - вопрос сложный, но
существует устоявшееся мнение, что только хороший криптоаналитик,
имеющий большой опыт в "раскалывании" шифров может разработать
хороший (устойчивый) новый шифр.
Q: А что такое стеганогpафия?
A: Это еще один способ сокрытия информации. Иногда бывает пpоще скpыть сам
факт наличия секpетной инфоpмации, чем надеяться на стойкость
кpиптоалгоpитма. Используемые методы зависят от технических возможностей и
фантазии автора. Пpимеpом стеганогpафии могут служить "случайные" точки на
изобpажении, "шум" в звуковой инфоpмации и т.д. в котоpые вкpапляется важная
и секpетная инфоpмация. Можно комбиниpовать стеганогpафию и шифpование.
Q: Что такое шифр?
A: Шифром принято называть обратимый способ преобразования информации с целью
защиты ее от просмотра, в котором используется некий секретный элемент.
Исходная информация в этом случае будет называться открытым текстом, а
результат применения к ней шифра - закрытым текстом или шифртекстом.
Если давать строгое определение, то шифр есть совокупность всех возможных
криптографических преобразований (их число равно числу всех возможных ключей),
отображающих множество всех открытых текстов в множество всех шифртекстов и
обратно.
* Алгоритм шифрования - формальное описание шифра.
* Зашифрование - процесс преобразования открытого текста в шифртекст с
использованием ключа.
* Расшифрование - процесс восстановления открытого текста из шифртекста
с использованием ключа.
* Дешифрование - процесс восстановления открытого текста из шифртекста
без знания ключа.
* Ключ - сменный элемент шифра, позволяющий сделать сам алгоритм
шифрования открытым и использовать его многократно, меняя лишь ключ.
Q: Что такое "криптование"?
A: Словечко, используемое дилетантами вместо стандартного термина шифрование,
что выдает в них полных ламеров. Hастоящие специалисты-криптографы никогда
не пользуются этим словом, а также его производными "закриптование",
"закриптованные данные", "раскриптование", и т.д
Q: Что такое криптографический протокол?
A: Кpиптогpафический пpотокол - есть алгоpитм обмена инфоpмацией (не
обязательно секpетной!) между участниками, котоpые могут быть как
сопеpниками, так и соpатниками. В основе криптографических протоколов могут
лежать как симметричные криптоалгоритмы, так и алгоритмы с открытым ключом.
Криптографический протокол считается стойким, если в процессе его использования
легитимные участники процесса достигают своей цели, а злоумышленник - нет.
Q: Что такое "другие криптографические параметры"?
A: В это понятие входят узлы замены, синхропосылки и другие
сменные параметры, не являющиеся ключами.
Q: Зачем использовать DES, ГОСТ, Rijndael, другие опубликованные
алгоритмы? Раз их разрешили опубликовать, значит, в них есть
дыры. Я вчера придумал свой супер-алгоритм, его-то точно никто
сломать не сможет. Почему бы не использовать его?
A: Придумать алгоритм - это 5% работы. Остальные 95% - убедиться
(и убедить других), что его никто не сможет сломать (в обозримое
время). Это сложно. Это не под силу одному человеку.
Те алгоритмы, которые у всех на слуху, анализировали сотни
(тысячи) квалифицированных людей, в том числе и те, кто не
находится на государственной службе. Если _все_ они говорят,
что дыр нет - с вероятностью 0.9999 они правы.
С другой стороны, если хочешь изобрести свой собственный
алгоритм, сначала сломай пару-тройку чужих.
Q: А зачем pазбиpаться в алгоpитме. Разве не за тем, чтобы его потом сделать?
A: Прежде всего разбираться - затем, чтобы ПОHЯТЬ, какие алгоритмы следует
применить и как их правильно состыковать между собой. А найти (при
необходимости) в И-нете исходник, если точно знаешь, что искать - не проблема.
Ну, или здесь попросить 8-))
Q: Hу вот я изобрел алгоритм, помогите мне проверить, что он надежен.
Я зашифровал им файл, зашифрованный файл поместил в письмо.
Расшифруйте его! Сам алгоритм я не покажу - секрет фирмы.
A1: Спешу разочаровать: никому из присутствующих в эхе людей
неинтересно заниматься фигней. А именно ломать алгоритм
только по зашифрованному тексту. Если кому-то очень надо
будет посмотреть зашифрованные данные - он раздобудет
алгоритм (купит экземпляр программы для себя, украдет и т.п.).
Так что нет никаких оснований скрывать сами алгоритм: если
он - твоя интеллектуальная собственность, запатентуй его.
По этим же причинам нет оснований доверять алгоритмам,
разработчики которых держат их в секрете.
A2: Криптограф всегда должен следовать правилу Керкхоффа: весь механизм
шифрования кроме значения секретного ключа, известен криптоаналитику
противника (часто это правило формулируется так: стойкость шифра должна
определяться только секретностью ключа).
Q: Я хочу защитить свою информацию, зашифровав ее...
A: Огромное количество людей HЕ ПОHИМАЕТ, что шифрование не есть единственный и
универсальный способ скрыть свои секреты, а всего лишь способ уменьшить свои
проблемы, заменив один (большой) секрет на другой (маленький).
Q: Существует ли абсолютно стойкий шифр?
A: Клод Шеннон в своих трудах ввел понятие стойкости шифра и показал, что
существует шифр, обеспечивающий абсолютную секретность. Иными словами, знание
шифртекста не позволяет противнику улучшить оценку соответствующего открытого
текста. Им может быть, например, шифр Виженера при условии использования
бесконечно длинного ключевого слова и абсолютно случайному распределению
символов в этом слове. Очевидно, что практическая реализация такого шифра
(бесконечная случайная лента) невозможна (точнее, в большинстве случаев -
экономически невыгодна), поэтому обычно рассматривают практическую стойкость
шифра, численно измеряемую временем (либо числом элементарных операций),
необходимым на его взлом (с учетом текущего уровня развития техники). Кстати,
первым предложил использовать такой шифр Вернам, но обоснование дал именно
Шеннон.
Абсолютно стойкий шифр - это абстрактно-математическое понятие, с практикой не
имеющее почти ничего общего. Абсолютно стойкий шифр может оказаться абсолютно
_не_стойким против таких атак, как physical attack или social engineering
attack (см. ниже) - все зависит от реализации.
Q: Вот говорят иногда "симметричные шифры", "криптография с открытым ключем".
Поясните, что это за разделение?
A1: Симметричные шифры (криптосистемы) - это такие шифры, в которых для
зашифрования и расшифрования информации используется один и тот же ключ. В
несимметричных системах (системах с открытым ключом) для зашифрования
используется открытый (публичный) ключ, известный всем и каждому, а для
расшифрования - секретный (личный, закрытый) ключ, известный только
получателю.
A2: Симметричные шифры (криптосистемы) - это такие шифры, в которых
алгоритмы зашифрования и расшифрования могут быть _эффективно_ построены по
одному и тому же ключу.
II. Симметричные шифры.
Q: А что значит блочное/потоковое шифрование?
A: Блочная криптосистема (блочный шифр) разбивает открытый текст M на
последовательные блоки M1, M2, ..., Mn и применяет криптографическое
преобразование к каждому блоку. Поточная криптосистема (поточный шифр)
разбивает открытый текст M на буквы или биты m1, m2,..., mn и применяет
криптографическое преобразование к каждому знаку mi в соответствии со знаком
ключевого потока ki. Потоковое шифрование часто называют гаммированием.
Потоковый шифр может быть легко получен из блочного путем применения
специального режима (см. ниже).
Q: Что такое ECB, CBC, OFB, CFB?
A: Это режимы работы блочных шифров. ANSI X3.106 (1983)
ECB
Electronic Code Book Mode (режим электронной кодовой книги, режим простой
замены). В этом режиме все блоки текста шифруются независимо, на одном и том же
ключе, в соответствии с алгоритмом.
SM
Stream Mode (поточный режим, режим гаммирования). В этом режиме открытый текст
складывается по модулю 2 с гаммой шифра. Гамма получается следующим образом:
при помощи генератора формируется предварительная гамма (начальное заполнение
этого генератора - так называемая синхропосылка - не является секретом и
передается по каналу в открытом виде). Предварительная гамма подвергается
зашифрованию в режиме ECB, в результате чего и получается основная гамма, с
которой складывается открытый текст. Если последний блок неполный (его длина
меньше стандартного для данного алгоритма размера блока), берется только
необходимое количество бит гаммы.
CFB
Cipher Feedback Mode (гаммирование с обратной связью). В этом режиме открытый
текст также складывается по модулю 2 с гаммой шифра. Гамма получается следующим
образом: сначала шифруется (в режиме ECB) синхропосылка (она также передается
по каналу в открытом виде). Результат шифрования складывается по модулю 2 с
первым блоком открытого текста (получается первый блок шифртекста) и снова
подвергается зашифрованию. Полученный результат складывается со вторым блоком
открытого текста и т.д. Обработка последнего блока - аналогично предыдущему
режиму.
OFB
Output Feedback Mode (гаммирование с обратной связью по выходу). Как и в
предыдущем режиме, сначала зашифрованию подвергается синхропосылка. Результат
складывается по модулю 2 с первым блоком открытого текста - получается первый
блок шифртекста. Далее, результат шифрования с предыдущего шага (до сложения!)
шифруется еще раз и складывается со следующим блоком открытого текста. Таким
образом, гамма шифра получается путем многократного шифрования синхропосылки в
режиме ECB. Обработка последнего блока - аналогично предыдущему режиму.
Легко видеть, что приведённое определение OFB полностью совпадает с
определением SM. И это соотвествует криптографической практике в частности в
[1.2, p 203] просто нет SM, а OFB определяется так:
Ci = Pi ^ Si ; Si = Ek(Si-1) - шифрование
Pi = Ci ^ Si ; Si = Ek(Si-1) - расшифрование
В тоже время можно встретить другое определение OFB, на пример,
http://msdn.microsoft.com/library/psdk/crypto/aboutcrypto_9omd.htm.
Там же рекомендовано установить размер сдвига равный размеру блока
блочного шифра по причинам стойкости. Однако, такая установка приводит
к полному совпадению с режимом SM. В частности для DES, всегда применяют
ofb64bit.
CBC
Cipher Block Chaining Mode (режим сцепления блоков). В этом режиме очередной
блок открытого текста складывается по модулю 2 с предыдущим блоком шифртекста,
после чего подвергается зашифрованию в режиме ECB. Для самого первого блока
"предыдущим блоком шифртекста" является синхропосылка. Если последний блок
открытого текста неполный - он дополняется до необходимой длины.
Q: Что такое "гамма" и "гаммирование"?
A: Гамма - это псевдослучайная числовая последовательность, вырабатываемая по
заданному алгоритму и используемая для зашифрования открытых данных и
расшифрования зашифрованных. Гаммированием принято называть процесс наложения
по определенному закону гаммы шифра на открытые данные для их зашифрования.
Q: А у поточного шифрования какие бывают режимы?
A: Шифрование последовательности с обратной связью (заворачивает
криптотекст на вход ГСП (генератор случайной последовательности, роль которого
играет алгоритм шифрования) шифрование ключей с обратной связью. См. режим CFB
для блочных шифров.
Q: Что такое архитектура "Квадрат" (SQUARE)?
A. Это архитектура построения блочных шифров с секретным ключом, она имеет
следующие особенности:
- она является вариантом общих SP-сетей (за один раунд шифруемый блок
преобразуется целиком), построенным по схеме KASLT (Key Addition -
Substitution - Linear Transformation);
- архитектура байт-ориентирована, шифруемый блок представляется в виде
матрицы байтов, замена также выполняется побайтно, на каждом раунде может
использоваться один, максимум-два узла замен, больше втиснуть сложнее;
- линейное преобразование (третий шаг раунда) двухфазное, состоит из
перестановки байтов в матрице и независимого линейного комбинирования
отдельных столбцов (или строк) матрицы. Смысл этой двухфазности - диффузия
изменений в двух направлениях - по строкам и по столбцам;
В данной архитектуре замена приводит к диффузии изменений внутри байта,
линейное преобразование - в двух измерениях матрицы, в итоге получаем, что
любое изменение в данных диффундирует на весь блок всего за 2 раунда.
В архитектуре "квадрат" выполнены шифры AES(Rijndael), Square ("квадрат",
его название дало имя всей архитектуре), Crypton (один из кандидатов на
AES). Второе место в конкурсе AES занял другой KASLT-шифр, Serpent. Дело
идет к тому, что KASLT-сети и, в частности, архитектура SQUARE, в ближайшем
будущем станут безраздельно доминировать.
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