I. Общая часть.
Q: Что такое криптография, криптология, криптоанализ?
A: Криптология - это наука о шифрах и всем, что с ними связано.
Криптологию принято подразделять на криптографию и криптоанализ.
Если криптограф занимается вопросами защиты информации при помощи
криптографических методов, то криптоаналитик, напротив, старается
эту защиту преодолеть. Чья работа сложнее - вопрос сложный, но
существует устоявшееся мнение, что только хороший криптоаналитик,
имеющий большой опыт в "раскалывании" шифров может разработать
хороший (устойчивый) новый шифр.
Q: А что такое стеганогpафия?
A: Это теоpия о том, как пpятать инфоpмацию. Иногда бывает пpоще скpыть сам
факт наличия секpетной инфоpмации, чем надеяться на стойкость
кpиптоалгоpитма. Можно комбиниpовать стеганогpафию и шифpование.
Пpимеpом стеганогpафии могут служить "случайные" точки на изобpажении,
"шум" в звуковой инфоpмации и т.д. в котоpые вкpапляется важная и секpетная
инфоpмация.
Q: Что такое шифр?
A: Шифром принято называть обратимый способ преобразования информации с целью
защиты ее от просмотра, в котором используется некий секретный элемент.
Исходная информация в этом случае будет называться открытым текстом, а
результат применения к ней шифра - закрытым текстом или шифртекстом.
Если давать строгое определение, то шифр есть совокупность всех возможных
криптографических преобразований (их число равно числу всех возможных ключей),
отображающих множество всех открытых текстов в множество всех шифртекстов и
обратно.
* Алгоритм шифрования - формальное описание шифра.
* Зашифрование - процесс преобразования открытого текста в шифртекст с
использованием ключа.
* Расшифрование - процесс восстановления открытого текста из шифртекста
с использованием ключа.
* Дешифрование - процесс восстановления открытого текста из шифртекста
без знания ключа.
* Ключ - сменный элемент шифра, позволяющий сделать сам алгоритм
шифрования открытым и использовать его многократно, меняя лишь ключ.
Q: Что такое "криптование"?
A: Словечко, используемое дилетантами вместо стандартного термина шифрование,
что выдает в них полных ламеров. Настоящие специалисты-криптографы никогда
не пользуются этим словом, а также его производными "закриптование",
"закриптованные данные", "раскриптование", и т.д
Q: Что такое криптографический протокол?
A: Кpиптогpафический пpотокол - есть алгоpитм обмена инфоpмацией (не
обязательно секpетной!) между участниками, котоpые могут быть как
сопеpниками, так и соpатниками. В основе криптографических протоколов могут
лежать как симметричные криптоалгоритмы, так и алгоритмы с открытым ключом.
Криптографический протокол считается стойким, если в процессе его использования
легитимные участники процесса достигают своей цели, а злоумышленник - нет.
Q: Что такое "другие криптографические параметры"?
A: В это понятие входят узлы замены, синхропосылки и другие
сменные параметры, не являющиеся ключами.
Q: Зачем использовать DES, ГОСТ, Rijndael, другие опубликованные
алгоритмы? Раз их разрешили опубликовать, значит, в них есть
дыры. Я вчера придумал свой супер-алгоритм, его-то точно никто
сломать не сможет. Почему бы не использовать его?
A: Придумать алгоритм - это 5% работы. Остальные 95% - убедиться
(и убедить других), что его никто не сможет сломать (в обозримое
время). Это сложно. Это не под силу одному человеку.
Те алгоритмы, которые у всех на слуху, анализировали сотни
(тысячи) квалифицированных людей, в том числе и те, кто не
находится на государственной службе. Если _все_ они говорят,
что дыр нет - с вероятностью 0.9999 они правы.
С другой стороны, если хочешь изобрести свой собственный
алгоритм, сначала сломай пару-тройку чужих.
Q: Ну вот я изобрел алгоритм, помогите мне проверить, что он надежен.
Я зашифровал им файл, зашифрованный файл поместил в письмо.
Расшифруйте его! Сам алгоритм я не покажу - секрет фирмы.
A1: Спешу разочаровать: никому из присутствующих в эхе людей
неинтересно заниматься фигней. А именно ломать алгоритм
только по зашифрованному тексту. Если кому-то очень надо
будет посмотреть зашифрованные данные - он раздобудет
алгоритм (купит экземпляр программы для себя, украдет и т.п.).
Так что нет никаких оснований скрывать сами алгоритм: если
он - твоя интеллектуальная собственность, запатентуй его.
По этим же причинам нет оснований доверять алгоритмам,
разработчики которых держат их в секрете.
A2: Криптограф всегда должен следовать правилу Керкхоффа: весь механизм
шифрования кроме значения секретного ключа, известен криптоаналитику
противника (часто это правило формулируется так: стойкость шифра должна
определяться только секретностью ключа).
Q: Существует ли абсолютно стойкий шифр?
A: Клод Шеннон в своих трудах ввел понятие стойкости шифра и показал, что
существует шифр, обеспечивающий абсолютную секретность. Иными словами, знание
шифртекста не позволяет противнику улучшить оценку соответствующего открытого
текста. Им может быть, например, шифр Виженера при условии использования
бесконечно длинного ключевого слова и абсолютно случайному распределению
символов в этом слове. Очевидно, что практическая реализация такого шифра
(бесконечная случайная лента) невозможна (точнее, в большинстве случаев -
экономически невыгодна), поэтому обычно рассматривают практическую стойкость
шифра, численно измеряемую временем (либо числом элементарных операций),
необходимым на его взлом (с учетом текущего уровня развития техники). Кстати,
первым предложил использовать такой шифр Вернам, но обоснование дал именно
Шеннон.
Абсолютно стойкий шифр - это абстрактно-математическое понятие, с практикой не
имеющее почти ничего общего. Абсолютно стойкий шифр может оказаться абсолютно
_не_стойким против таких атак, как physical attack или social engineering
attack (см. ниже) - все зависит от реализации.
Q: Вот говорят иногда "симметричные шифры", "криптография с открытым ключем".
Поясните, что это за разделение?
A: Симметричные шифры (криптосистемы) - это такие шифры, в которых для
зашифрования и расшифрования информации используется один и тот же ключ. В
несимметричных системах (системах с открытым ключом) для зашифрования
используется открытый (публичный) ключ, известный всем и каждому, а для
расшифрования - секретный (личный, закрытый) ключ, известный только
получателю.
II. Симметричные шифры.
Q: А что значит блочное/потоковое шифрование?
A: Потоковое шифрование принципиально отличается от блочного тем, что априори
неизвестна длина шифруемой последовательности и элементарная операция
шифрования производится не над блоком, а над битом. применяется в цифровой
телефонии (SIS в NMT-450, A3-A8 в GSM вроде так обзываются, ну поправят в эхе,
ежели чего 8-) FIXME!), телеметрии, т.е. там, где защита передачи производится
в реальном масштабе времени. использует те-же алгоритмы с секретным ключом.
Особенность работы - необходимость синхропосылок при начале работы, либо
начальное заполнение сдвиговых регистров (что может рассматриваться как
элемент ключа).
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. Обработка последнего блока - аналогично предыдущему режиму.
CBC
Cipher Block Chaining Mode (режим сцепления блоков). В этом режиме очередной
блок открытого текста складывается по модулю 2 с предыдущим блоком шифртекста,
после чего подвергается зашифрованию в режиме ECB. Для самого первого блока
"предыдущим блоком шифртекста" является синхропосылка. Если последний блок
открытого текста неполный - он дополняется до необходимой длины.
Q: Что такое "гамма" и "гаммирование"?
A: Гамма - это псевдослучайная числовая последовательность, вырабатываемая по
заданному алгоритму и используемая для зашифрования открытых данных и
расшифрования зашифрованных. Гаммированием принято называть процесс наложения
по определенному закону гаммы шифра на открытые данные для их зашифрования.
Q: А у поточного шифрования какие бывают режимы?
A: Шифрование последовательности с обратной связью (заворачивает
криптотекст на вход ГСП (генератор случайной последовательности, роль которого
играет алгоритм шифрования) шифрование ключей с обратной связью. См. режим CFB
для блочных шифров.
Q: А какие есть симметричные алгоритмы шифрования?
A: Да их немеряно! ;) Приведем наиболее известные:
Шифр Цезаря
Великий император, с целью сокрытия содержания написанного заменял каждую
букву на третью следующую за ней по счету букву алфавита. Цезарь применял
сдвиг на три буквы; в общем случае это может быть любое число, меньшее, чем
длина алфавита. Это число и является ключом в данном шифре:
А Б В Г Д Е Е Ж З И Й К Л М H О П Р С Т У Ф Х Ц Ч Ш Щ Ы Ь Ъ Э Ю Я
Г Д Е Е Ж 3 И И К Л М H О П Р С Т У Ф Х Ц Ч Ш Щ Ы Ь Ъ Э Ю Я А Б В
КРИПТОГРАФИЯ -> НУЛТХСЕУГЧЛВ
Шифр Виженера
Является модификацией шифра Цезаря, в котором величина сдвига является
переменной и зависит от ключевого слова. Например, если в качестве ключевого
слова использовать слово "ТАЙНА", то это будет означать, что первую букву
сообщения необходимо сдвинуть на 20 (порядковый номер буквы "Т"), вторую -
на 1 (порядковый номер буквы "А"), третью - на 11, четвертую - на 15,
пятую - на 1, шестую - снова на 20 (ключевое слово начинаем использовать
с начала) и т.д. Таким образом, ключевое слово "накладывается" на защищаемый
текст.
Шифр Вернама - FIXME!
AES
Авторы: FIXME!
Параметры:
- размер блока FIXME!
- размер ключа FIXME!
- число раундов FIXME!
BlowFish.
Разработан в 1993 году.
Автор: Брюс Шнаейр (Bruce Schneier)
Параметры:
- pазмер блока 64 бита
- pазмер ключа 32-448 бит
- число раундов 16
CAST.
В некотором смысле аналог DES.
Авторы: C.M. Adams и S.E.Tavares.
Параметры:
- размер блока FIXME!
- размер ключа 64 бита
- число раундов FIXME!
DEAL.
Базируется на DES (DEA). Уувеличение длины блока уменьшает вероятность удачной
криптоатаки методом сравнения криптограмм, уровень стойкости шифрования
сопоставим с уровнем triple-DES.
Автор: Lars R. Knudsen.
Параметры:
- размер блока 128 бит
- размер ключа 128/192/256 бит
- число раундов FIXME!
DES.
Алгоритм с эффективной длиной ключа в 56-bits (хотя часто говорят о 8 байтах,
но старший бит в байте не используется).
Автор: National Institute of Standards and Technology (NIST).
Параметры:
- размер блока 64 бита
- размер ключа 56 бит
- число раундов FIXME! (16?)
IDEA (International Decryption-Encryption Algorithm)
Время/место разработки 1990-1991 годы, Цюрих, Швейцария.
Архитектура Общая сбалансированная шифрующая SP-сеть, инвариант раунда -
побитовая сумма по модулю 2 старшей и младшей половин блока.
Авторы: Xuejia Lai, James Massey.
Параметры:
- pазмер блока 64 бита
- pазмер ключа 128 бит
- число раундов 8
Lucifer.
Автор: FIXME!
Параметры:
- размер блока FIXME!
- размер ключа FIXME!
- число раундов FIXME!
NewDES.
Создан в 1985 как творческая переработка DES. Это самостоятельный алгоритм, а
не вариант DES. NewDES несколько проще, чем DES, поскольку у него нет начальной
и, понятно, конечной перестановки. Операции производятся над байтами, а не
битами как в DES. Brute-force атака на NewDES требует 2^119 операций, против
2^111 для TripleDES.
Автор: Robert Scott.
Параметры:
- размер блока 64 бита
- размер ключа 120 бит
- число раундов FIXME!
RC2.
Автор: FIXME!
Параметры:
- размер блока 64 бита
- размер ключа FIXME!
- число раундов FIXME!
RC4.
Автор: FIXME!
Параметры:
- размер блока FIXME!
- размер ключа FIXME!
- число раундов FIXME!
Rijndael.
Автор: FIXME!
Параметры:
- размер блока FIXME!
- размер ключа FIXME!
- число раундов FIXME!
Skipjack.
Старательно пропихиваемый госдепом США симметричный алгоритм шифрования с
разделяемым ключом и бэкдором. Используется в чипах Clipper и Capstone, которые
хотят засунуть до Интернет унитазов включительно :).
Автор: FIXME!
Параметры:
- размер блока FIXME!
- размер ключа 80 бит
- число раундов FIXME!
TripleDES.
Алгоритм зашифрования состоит в следующем: исходный текст зашифровывается DESом
с ключом K1, результат расшифровывается DESом с ключом K2, а этот результат
опять зашифровывается DESом с ключом K1. Итого длина ключа составляет 112 бит.
Иногда применяют 3 разных ключа, но стойкость от этого не меняется.
Автор: FIXME!
Параметры:
- размер ключа 112 бит
- остальное - см. DES
ГОСТ 28147-89
Российский алгоритм, федеральный стандарт шифрования. Кроме ключа ему
необходима еще одна таблица (таблица замен, 128 ячеек 4-битовых чисел) для
формирования S-boxes. ГОСТ ее не определяет, посему она может рассматриваться
как долговременный ключевой элемент. Определены следующие режимы работы: режим
простой замены (ECB), режим гаммирования (SM) и режим гаммирования с
зацеплением (OFB). Несколько особняком стоит режим выработки имитовставки. В
принципе, у него такое же назначение как у хэш-функции, только ее значение еще
зависит от секретного ключа. Размер получаемой имитовставки - 64 бита.
Автор: КГБ СССР
Параметры:
- размер блока 64 бита
- размер ключа 256 бит
- число раундов 32 (16 - для имитовставки)
Q: Каковы д.б. правила построения таблиц (узлов) замены в ГОСТе?
A: Основная задача -- сделать S-box'ы (так называют эти таблицы) устойчивыми к
дифференциальному и линейному криптоанализу. Можно попробовать
сформулировать критерии, глядя на те критерии, которые Тучман использовал в
начале 70-х для DES. /* потребовалось около 10 месяцев */
Итак, можно сформулировать следующие правила:
1. Ни один выходной бит не должен сколь-нибудь хорошо приближаться линейной
функцией от входных бит.
2. Если два входных значения отличаются на один бит, выходные значения
должны отличаться не менее чем на 2 бита.
3. Если два входных значения отличаются в двух соседних битах (как минимум
центральных), то выходные значения должны отличаться не менее чем на 2 бита.
4. Для любого значения XOR между входными значениями, следует минимизировать
количество пар, чьи XOR на входе и на выходе равны этому значению (это
весьма хитроумное требование вытекает из попытки защититься от
дифференциального
криптоанализа).
5. S-box'ы не должны быть похожи друг на друга. Например, количество входных
значений, дающих одно и тоже значение на выходе из разных S-box'ов, должно
быть минимально.
6. Узлы замены в идеале должны учитывать особенности входного текста: если
используются только алфавитно-цифровой диапазон ASCII-таблицы, то он должен
отображаться (после замены) на все множество используемого алфавита, скрывая
статистические свойства открытого текста.
III. Несимметричные шифры.
Q: А какие есть несимметричные алгоритмы шифрования?
A: А вот этих немного :) В принципе, вся несимметричная криптография строится
на 2 проблемах: проблеме разложения большого числа на простые множители и
проблеме дискретного логарифмирования. Собственно, для шифрования используется
алгоритм RSA (Rivest-Shamir-Adleman), разработанный в 1977 году математиками
Роном Райвестом (R. Rivest), Ади Шамиром (A. Shamir) и Леонардом Аделманом
(L. Adleman). Используется не только для шифрования, но и для формирования ЭЦП.
Схема примерно такая:
Абонент А, желающий вступить в переписку, ЗАРАНЕЕ:
- вырабатывает различные простые числа p, q, примерно равной разрядности,
и вычисляет n=p*q;
- генерирует случайное числе e < n и вычисляет d, такое что
e*d == 1(mod ф(n)); (ф(n) - функция Эйлера)
- рассылает открытый ключ (e,n);
- сохраняет в тайне секретный ключ (p, q, d).
Абонент B, желающий ЗАШИФРОВАТЬ сообщение для абонента А, выполняет следующие
действия:
- открытый текст разбивается на блоки, каждый из которых представляется как
число m, 0 <= m <= (n-1), и преобразуется в блок c, 0 <= c <= (n-1),
шифрованного текста с = E(n,e,m) = m^e (mod n).
Для РАСШИФРОВАНИЯ абонент А выполняет следующие действия:
- вычисляет m' = E(n,d,c) = c^d (mod n).
IV. Хэш-функция.
Q: Что такое хэш-функция (hash, hash-function)?
A: Это преобразование, получающее из данных произвольной длины некое значение
(свертку) фиксированной длины. Простейшими примерами являются контрольные
суммы (например, crc32). Бывают криптографические и программистские хэши.
Криптографический хэш отличается от программистского следующими
двумя свойствами: необратимостью и свободностью от коллизий.
Обозначим m -- исходные данные, h(m) -- хэш от них. Необратимость
означает, что если известно число 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
Автор: FIXME!
Размер: 128 бит.
MD4
Автор: Р.Райвест (R. Rivest).
Размер: 128 бит.
MD5
Капитально переделанный MD4.
Автор: Р.Райвест (R. Rivest).
Размер: 128 бит.
SHA.
Один из (относительно) новых алгоритмов свертки.
Автор: FIXME!
Размер: 160 бит.
ГОСТ Р34.11-94
Российский алгоритм. Размерность получаемого значения очень удобна
для формирования по паролю ключа для ГОСТ 28147-89.
Автор: FIXME!
Размер: 256 бит.
V. Электронная цифровая подпись.
Q: Что такое электронная цифровая подпись (ЭЦП)?
A: ЭЦП - это для автора документа способ убедить читателей в том,
что автор - именно он. Способ работает примерно так.
Вначале автор документа (файла и т.п.) должен сгенерировать
пару ключей, один секретный, один открытый. Секретный ключ
он оставляет при себе, открытый - передает всем потенциальным
читателям (под роспись, или по другому доверенному каналу).
Теперь при необходимости послать документ автор вычисляет
некоторое число (ЭЦП), которое зависит от самого файла и от
секретного ключа. Без знания секретного ключа это число подобрать
крайне сложно.
Получатель вычисляет другое число на основе полученного файла,
полученной ЭЦП и открытого ключа. Если получилась 1 - значит,
документ не был искажен, и автор соответствует предполагаемому.
Если получился 0 - значит, это подделка.
Несложно понять, что эту систему правильнее было бы назвать
"Электронная цифровая печать", так как подпись - это нечто
индивидуальное. А печать (как и секретный ключ) можно
украсть, со всеми вытекающими.
RSA.
ПРЕДВАРИТЕЛЬНО:
- те же предварительные действия что и для криптосистемы RSA.
ВЫЧИСЛЕНИЕ ПОДПИСИ:
- c = H(m)^d (mod n) (H(m) - результат хэширования сообщения m);
ПРОВЕРКА ПОДПИСИ:
- проверка равества H(m) == c^e (mod n).
('==' - операция сравнения (это не больше или меньше :-)))Авторы: Рональд Райвест (R. Rivest), Ади Шамир (A. Shamir)
и Леонард Аделман (L. Adleman)
Размеры ключей: FIXME!
Размер подписи: FIXME!
DSS
Стандарт цифровой подписи - Digital Signature Standard. Использует алгоритм
цифровой подписи - Digital Signature Algorithm (DSA), который основан на шифрах
с открытым ключом. Для шифрования данных не используется.
Автор: FIXME!
Размеры ключей: FIXME!
Размер подписи: FIXME!
ElGamal
ПРЕДВАРИТЕЛЬНО:
1. Во всей сети выбираются простое число p и Alfa - образующая поля GF(p).
2. Во всей сети выбирается хэш-функция H со значениями в поле GF(p)
3. Абонент случайным образом генерирует свой секретный ключ x из интервала
{2,...,p-1}, который сохраняет в тайне.4. Абонент вычисляет свой открытый ключ y=Alfa^x (mod p), который рассылает
своим корреспондентам.
ВЫЧИСЛЕНИЕ ПОДПИСИ:
1. Абонент выбирает случайное число k {1,...,p-1}, взаимно простое с p-12. Абонент вычисляет r=Alfa^k (mod p)
3. Абонент вычисляет s=(1/k)*(H(m)-rx) (mod (p-1)), где H(m) - хэш-функция
от подписываемого сообщения.
4. Абонент уничтожает k.
5. Абонент посылает свое сообщение m вместе с подписью (r,s).
ПРОВЕРКА ПОДПИСИ:
1. Корреспондент проверяет r и s принадлежат {1,...,p-1}2. Корреспондент проверяет сравнение Alfa^H(m) == (y^r)*(r^s) (mod p)
Если хотя бы одно из условий проверки не выполнено, то считается что
подпись неверна.
Автор: El Gamal
Размеры ключей: FIXME!
Размер подписи: FIXME!
ГОСТ Р34.10
Российский алгоритм, федеральный стандарт.
ПРЕДВАРИТЕЛЬНО:
1. Во всей сети выбираются простые числа p и q : p-1 делится на q.
2. Во всей сети выбирается число Alfa : Alfa < p, Alfa^q == 1(mod p)
3. Во всей сети выбирается хэш-функция H со значениями {1,...,q-1}4. Абонент случайным образом генерирует свой секретный ключ x из интервала
{1,...,q-1}, который сохраняет в тайне.5. Абонент вычисляет свой открытый ключ y=Alfa^x (mod p), который рассылает
своим корреспондентам.
ВЫЧИСЛЕНИЕ ПОДПИСИ:
1. Абонент выбирает случайное число k {1,...,q-1}.2. Абонент вычисляет r=(Alfa^k (mod p))(mod q)
3. Абонент вычисляет s=(kH(m)+rx) (mod q), где H(m) - хэш-функция
от подписываемого сообщения.
4. Если r=0 или s=0, то процедура вычисления подписи повторяется с п.1,
иначе пара чисел (r,s) есть подпись сообщения m.
ПРОВЕРКА ПОДПИСИ:
1. Корреспондент проверяет, что 0 < r < q и 0 < s < q.
2. Корреспондент проверяет, что (Alfa^ws)*(y^(-wr))(mod p) == r(mod q),
где w = (1/H(m))(mod q).
Если хотя бы одно из условий проверки не выполнено, то считается что
подпись неверна.
Автор: FIXME!
Размеры ключей: FIXME!
Размер подписи: FIXME!
Q: Получается, что открытый ключ никак не защищен? Как проверяющий подпись
может быть уверен, что имеющийся у него для проверки открытый ключ
действительно принадлежит автору сообщения?
A: Для этого используются не просто открытые ключи, а их сертификаты,
формируемые Центром Сертификации Ключей (Центром Распределения Ключей,
Certificate Authority). В качестве центра сертификации выбирается организация,
которой доверяют все участники обмена и которой они лично предъявляют свои
открытые ключи. Центр формирует из собранных ключей сертификаты путем
подписания их своей электронной подписью. После этого каждый участник получает
сертификат (собственный открытый ключ, подписанный центром) и открытый ключ
центра. Теперь при установлении связи корреспонденты обмениваются не просто
открытыми ключами, а сертификатами, что дает возможность однозначно
идентифицировать второго участника обмена путем проведения процедуры проверки
электронной подписи центра под его сертификатом.
Существуют рекомендации X.509, в которых описано, что должен в себя включать
сертификат.
Содержание сертификата по рекомендации X.509:
- номер сертификата;
- имя владельца сертификата;
- имя Центра сертификации, выдавшего сертификат;
- идентификатор алгоритма подписи, используемого для подтверждения
подлинности сертификата;
- открытый ключ (собственно, то, ради чего весь этот цирк :) );
- срок действия сертификата;
- подпись всей этой информации на секретном ключе Центра сертификации.
VI. Криптографические протоколы.
/Подбрасывание костей, подписание контракта, выработка общего секрета
(Диффи-Хеллман) и т.п./
DH
Diffie-Hellman. Протокол передачи секретных ключей с использованием
алгоритмов на открытом ключе. Для шифрования данных не используется.
Если обозначить секретный ключ абонента как X, открытый ключ как Y и
установить соответствие между ними как Y=A^X (A в степени X, где A
является константой), то приближенно получение общего секретного
ключа можно записать так.
Каждый участник вычисляет K на основе своего секретного ключа и открытого
ключа другого абонента:
K=Y2^X1=(A^X2)^X1= A^X2X1
K=Y1^X2=(A^X1)^X2= A^X1X2
Как видим, вычисленное на обоих концах канала связи значение K одинаково, при
этом по каналу передавались только значения Y1 и Y2, на основании которых
потенциальный злоумышленник, прослушивавший канал, не сможет вычислить X1 и
X2, равно как и общий секрет K.
KEA
Key Exchange Algorithm. Вариации на тему Diffie-Hellman.
Q. Что такое Perfect Forward Secrecy?
A1. Если мне не изменяет мой склероз, Perfect Forward Secrecy -- это
свойство протокола, заключающееся в том, что захват противником
_криптографических_ параметров не приводит к нарушению
конфиденциальности данных, передаваемых _после_ события захвата.
Пример.
Рассмотрим протокол, в котором передача очередного сообщения
осуществляется следующим образом.
1. Обе стороны генерируют пару секретный ключ - открытый
ключ, и каждая сторона передает другой по доверенному, но
_неконфиденциальному_ каналу, свой открытый ключ.
2. Передающая сторона генерирует свой секретный сеансовый ключ.
3. По протоколу открытого распределения ключей Диффи-Хеллмана
сеансовый ключ передается стороне-получателю.
4. Отправитель шифрует сообщение на сеансовом ключе, отправляет
получателю, а тот расшифровывает его.
5. Каждая из сторон уничтожает все ключи, а именно сеансовый ключ
и свой секретный.
Передача одного сообщения должна являться одной транзакцией.
В этом протоколе ни до, ни после передачи сообщения стороны
не владеют секретной информацией, которая может привести
к раскрытию сообщения или ключей.
A2. Согласно IPSEC, Perfect Forward Secrecy -- это следующее свойство
протокола: компрометация ключа приводит к раскрытию только тех
данных, которые были зашифрованы на этом ключе.
VII. Криптоанализ.
/
Методы, перспективы, минимальная длина ключа и т.п.
/
Q: Какие есть методы криптоанализа, атаки на шифры?
A: Распространена следующая классификация: FIXME!
* ciphertext only attack (атака с известным шифртекстом).
* known plaintext attack (атака с известным открытым текстом)
* chosen plaintext attack (атака с выбором открытого текста)
* adaptive chosen plaintext attack (адаптивная атака с выбором открытого
текста)
* chosen ciphertext attack (атака с выбором шифртекста)
* adaptive chosen ciphertext attack (адаптивная атака с выбором шифртекста)
* chosen text attack (атака с выбором текста)
* chosen key attack (атака с выбором ключа)
* physical attack - атака, при которой используются физические методы
перехвата;
например, так секретный ключ из смарт-карт вынимали - измеряя ток потребления
при шифровании или облучая их гамма-излучением для того, чтобы сбросить ключ
в ноль;
* social engineering attack - позвонить по телефону и грозным голосом приказать
немедленно принести дискетку с ключом по такому-то адресу; :)
* man-in-the-middle attack (атака "человек посередине") - злоумышленник
"разрывает" канал связи и взаимодействует с каждым из участников обмена от
имени другого. Применяется, в частности, против алгоритма распределения ключей
Диффи-Хэллмана. Легко нейтрализуется использованием вместо открытых ключей их
сертификатов.
Рассмотрим подробнее:
Допустим есть два законных абонента A и B, при этом у противника есть два
варианта атаки:
- противник С выдает себя за абонета А и от его имени говорит с B;
- противник C вклинивается между A и B и в протоколе с А выдает себя
за В, а в протоколе с В выдет себя за А, то есть пропускает разговор
через себя и тем самым подслушивает его. Также может навязывать ложную
информацию.
Решение этой проблемы - центр доверия, куда помещаются открытые ключи абонентов
сети. Центру доверия все верят. Предполагается, что Центр доверия не подвержен
атакам.
В частности для рассылки открытых ключей предложена система сертификатов.
Рекомендация X.509 ITU-T описывает эти структуры и предложения по их
использованию.
Q: Насколько стойким является шифрование ZIP-архива с паролем?
A: Как доказал Paul Kocher, его стойкость оценивается в 2^38
операций. Подробнее см. статью "A Known Plaintext Attack on
the PKZIP Stream Cipher" (Eli Biham, Paul C. Kocher).
Q: Какова минимально безопасная длина ключа?
A: Ответ на этот вопрос сложно зафиксировать, т.к. очень быстро меняется
производительность техники. Развитие методов криптоанализа тоже не стоит на
месте. Вобщем, лучше почитать статью Ю.Пудовченко на эту тему и перевод FAQ`а
Thomas Pornin. Оба материала доступны на страничке "Криптографический ликбез"
Длины ключей считаются по-разному для симметричных и несимметричных алгоритмов
(и вообще для разных алгоритмов). Правильнее было бы говорить о мощности
ключевого пространства. Так вот, для хороших симметричных алгоритмов в
настоящее время считается достаточной длина ключа в 256 бит (ГОСТ, AES). Если
полностью перебирать все возможные варианты (их придется перебрать в среднем
около 10^77), даже если мы возьмем для этого 10 миллиардов компьютеров, каждый
из которых способен перебрать 10 миллиардов ключей в секунду, то нам
потребуется около 10^49 лет, чтобы найти ключ. Разговор про стойкость
несимметричных алгоритмов, основанных на задаче факторизации, может идти
начиная с ключей длиной 2048 бит (лучше 4096:).
VIII. Практическая эксплуатация.
/Договора, разбор конфликтов и т.п./
Q: А зачем вообще эти юридические заморочки? Шифруется и ладно!
A: Математические абстpакции (из коих в частности выpосла кpиптогpафия с
откpытыми ключами) используются в пpикладных вещах, где используются для
доказательства достовеpности сообщения, подтвеpждения автоpства, etc.
после чего включаются законы данной стpаны.
Q: А вот закон об ЭЦП пока не принят, как мне грамотно организовать ее
использование?
A: Придется потрудиться :)
Между тобой и клиентом pисуется (пpимеpное название, можешь обозвать
"пpотоколом", "договоpом" или еще более умно 8-)) "соглашение о пpизнании
данного способа защиты инфоpмации". Высокие договаpивающиеся стоpоны _пpизнают_
данный способ обмена инфоpмацией между собой достовеpным и
_пpинимают_документы_, пеpеданные данным способом _к_ _исполнению_ (будь то
платежки, договоpы, записки "пошли пива нажpемся"), пpи выполнении следующих
условий... (или вытащи это в пpиложение) начинается самая суpьезная часть, где
оговаpиваются такие моменты:
* администpативно - оpганизационные: отдельное, помещение с огpаниченным
доступом, дискеты с ключами только в сейфе - у пpедседателя в своем у главбуха
в своем (это для фоpмиpования ЭЦП), тут за тpемя печатями спpятан эталонный
обpазец софта. откpытые ключи pаспечатаны в двух экземляpах, подписаны и синимя
печятямя 8-)) пpопечатаны. вот этот и этот специальный мужик, ответственны со
своих стоpон за эксплуатацию. вот тута к договоpу пpилагаем ихие должностные
инстpукции (покоpмил собак и ниче не тpогай). поpядок смены (даже в случае
только подозpения о компpометации) ключей и ответственности за их
неpазглашение. особенно оговаpивается, что ежели где чего сдохло в pезультате
чего-то не пpедусмотpенного, то создается комиссия из пpедставителей
заинтеpесованных стоpон и "базаp pазводят по понятиям без стволов и гнилых
базаpов в суде" 8-)) - тpетейский суд или пеpеговоpы (вpоде так это юpидически)
* технические и софтвеpные особенности эксплуатации ТВОЕГО кpиптокомплекса.
типа - балалайка - пень с установленным ДОСом, "СупеpКpиптоСофт", пpогpамма для
мудема и ВСЕ!!
* _особенно_ оговаpивается, что оpигиналы и соответствующие им кpиптотексты
хpанятся "стоко-то" (если пункта нет, то хpани 3 года, в соответствии с ГК),
после чего все пpетензии стоpон посылаются к...
Q: Ну, а если всеже по электронному документу возник спор, что делать?
A: Пpимеpный "поpядок pазpешения конфликтов".
Отвечает А. Межутков:
// "непpокоцаный тикет - повод для гнилого базаpа" 8-))
если одна из стоpон чего то начинает опpотестовывать - "не писали, в тексте
д.б. 100 тыщев, а не сто pублев", создается комиссия (+ желательно независимый
экспеpт. это не обязательно кpиптогpаф, если все опеpации в данном документе
пpописаны). и пошли по пунктам: достали эталонный софт, пpовеpили печати на
пакете, вскpыли, установили, взяли опpотестованный документ... далее ваpианты -
либо пpовеpили эцп, pасшифpовав из аpхива и сpавнив с откpытым текстом либо
зашифpовали и сpавнили с вытащенным из аpхива либо... (пpидумай сам - не знаю я
для чего ты всю эту хpень использовать собpался) 8-)) составляем акт: мы,
комиссия в составе... в соответствии с... пpоизвели пpовеpку..., каковая
показала, что козлом является тот-то. дата подпись. этот акт, как пpавило,
является достаточным условием для почти любого аpбитpажного суда.
Добавляет В.Мяснянкин:
Эталонную копию софта можно заложить на хранение к нотариусу. А с принятием
"Закона об ЭЦП" и появлением у нас удостоверяющих центров, весь этот разбор
полетов можно (и нужно) будет осуществлять у них. Во-первых, меньше головных
болей, во-вторых, для удостоверения идентичности электронной цифровой подписи
необходимо будет иметь лицензию ФАПСИ.
Q: Так что получается, что для использования ЭЦП мне нужна лицензия?
A: Нет, если вы не собираетесь быть удостоверяющим центром. В каких случаях
нужна лицензия ФАПСИ читайте в постановлении Правительства РФ N326 от
11.04.2000.
IX. Криптографическое программное обеспечение (ссылки и краткое описание).
Q: Я не хочу глубоко вникать во все эти тонкости, где найти готовое?
A: Неистребимую жажду халявы гасит интернет:
куча библиотек на все вкусы:
http://www.pscs.umich.edu/LAB/Doc/SwarmStuff/swarm-1.3.1-docs/refbook/swarm.random.sgml.reference.html
Ranlib: ftp://odin.mda.uth.tmc.edu/pub/source
и зеркало ftp://odin.mda.uth.tmc.edu/pub/msdos
RngPack: аналогично на Java: http://www.honeylocust.com/RngPack/
если хочется взять просто последовательность, то по ФТП можно вытянуть
сидюк целиком или любой из 60 ~10М файлов с "хорошими" случайными
последовательностями. всего на CDROM ок 4.8 миллиардов случайных бит:
ftp://stat.fsu.edu/pub/diehard/cdrom/
Q: Ну, это реализации и библиотеки. А что-нибудь для укрепления теоретических
знаний?
A: Для начала рекомендуется посетить приведенные ниже странички. На них уйма
материала и ссылок. Приведены именно эти, т.к. они живут давно и
устойчиво, в то время как другие периодически появляются и исчезают.
- страничка А.Винокурова о блочных шифрах:
http://www.halyava.ru/crypto
- страничка П.Семьянова "Криптографический ликбез"
http://www.ssl.stu.neva.ru/psw/crypto.html
- http://home.od.ua/~blackw/Crypt/crypt.html
Q: А у меня напряги с интернетом. В бумажном виде что посоветуете?
A: Вот список:
* А. Саломаа "Криптография с открытым ключом",
М., МИР, 1996, ISBN 5-03-0011991-X
* Т.Кормен, Ч.Лейзерсон, Р.Ривест "Алгоритмы. Построение и анализ",
М., МЦНМО, 1999, ISBN 5-900916-37-5
* Петров А.А. "Компьютерная безопасность. Криптографические методы",
М., "ДМК", 2000, ISBN 5-89818-064-8
* "25 этюдов о шифрах" FIXME!
* В.Жельников "Криптография от папируса до компьютера"
М., ABF, 1996, ISBN 5-87484-054-0
* Под общ. pед. В. В. Ященко, "Введение в кpиптогpафию"
М.: МЦНМО, "ЧеНо", 1998, 272 c., ISBN 5-900916-26-X, Тиpаж 3000 экз.
Q: А что есть стандартного в области криптографии в Windows?
A: Криптографические функции есть начиная с Win95 osr 2, WinNT 4.0.
В частности функция зашифрования называется CryptEncrypt(a,w), а расшифрования
CryptDecrypt(a,w).
Q: Где взять более подробное описание (прототипы функций) и
что там используется ?
A: Как обычно - берешь Win32 API... Алгоpитмы могyт быть любыми, поcколькy
cиcтема pаcшиpяемая и позволяет подключение дополнительных кpиптопpовайдеpов.
Cтандаpтный кpиптопpовайдеp, входящий в cоcтав Win* иcпользyет RSA для обмена
ключами и ЭЦП, RC2 и RC4 для шифpования и MD5 и SHA для хэшиpования. Описание
констант и функций, например, в wincrypt.h от C++ Builder-а 3.0. Алгоритм-это
преимущественно RSA или сделанный на ее платформе.
Provider Type Key Exchange Signature Encryption Hashing
PROV_RSA_FULL RSA RSA RC2, RC4 MD5, SHA
PROV_RSA_SIG n/a RSA n/a MD5, SHA
PROV_DSS n/a DSS n/a SHA
PROV_FORTEZZA KEA DSS Skipjack SHA
PROV_MS_EXCHANGE RSA RSA CAST MD5
PROV_SSL RSA RSA varies varies
X. ПРИЛОЖЕНИЯ.
1. Пример реализации ...
2. Пример реализации ...
3. Пример реализации ...
4. Пример реализации ...
XI. Здесь пары вопрос/ответ, которые я затруднился определить в какой-либо
раздел. Вобщем, "разное" :)
Q: Как проверить "случайность" моего ГСП (генератор случайной
последовательности).
A: В интеpнете есть "Diehard test battery". Этот комплект содеpжит 15 тестов
чисел на случайность. Адpес http://members.home.net/whuber/arcview.htm
Q: Я тут написал программу и хочу построить уникальный ключ, привязав
его к "железу", номеру материнки, процессора, жесткого диска, сетевой
карте. К чему лучше?
A: Ни к чему. Привязка к "железу" (любому) неэффективна в случае, если
комп взят из "большой китайской партии" и неудобна в использовании,
поскольку апгрейд "железа" явление достаточно частое, чтобы при
сколь-нибудь серьезном тираже программы ты поимел много забот с поддержкой.
Q: Что такое необратимое шифрование?
A: Такого термина нет. Шифрование по определению обратимо, иначе это
действие бессмысленно. обычно используется понятие хэш (свертка).
См. раздел "хэш-функции".
Q: А возможно ли создание аpхиватоpа у котоpого будет коэффициент
сжатия 1 к миллиону?
A1: Один из постулатов теории информации гласит - информация несжимаема.
Максимальная степень сжатия не может перескочить этот рубеж. Если файл в 1
гигабайт создан алгоритмическим путем из инициализационного массива в 16
байт тогда _теоретически_ может существовать архиватор, который его так
ужмет. Во всех остальных случаях - нет. Случайные данные вообще не сжимаемы.
A2: Все архиваторы построены на избыточности того языка, который они
архивируют. Больше некоторой величины ты теоретически не сожмешь. Но к этой
величине можешь подбираться сколь угодно близко (Шеннон).
A3: Вважное следствие - учитывая, что все алгоритмы шифрования приводят
статические параметры шифротекста к случайному распределению, сжатие
необходимо производить ДО операции собственно шифрования.
Q: Дайте описание файла ... (MP3, JPG, etc)
A: Ребята, возьмите в интернете. Что любопытно, там описаны и заголовки,
из которых можно почерпнуть "открытые тексты" для "частично" "plain-text
known attack"
XII. Заключение.
Спасибо всем, кто дочитал до этого места ;)
===============
