Часть 3
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 <= m <= (n-1), и преобразуется в блок c, 0 <= c <= (n-1),
шифрованного текста с = E(n,e,m) = m^e (mod n).
Для РАСШИФРОВА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





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 бит.

Q: Что такое электронная цифровая подпись (ЭЦП)?

A: ЭЦП - это для автора документа способ убедить читателей в том, что
автор - именно он. Способ работает примерно так.
Вначале автор документа (файла и т.п.) должен сгенерировать пару ключей,
один секретный, один открытый. Секретный ключ он оставляет при себе,
открытый - передает всем потенциальным читателям (под роспись, или по
другому доверенному каналу).
Теперь при необходимости послать документ автор вычисляет некоторое число
(ЭЦП), которое зависит от самого файла и от секретного ключа. Без знания
секретного ключа это число подобрать крайне сложно.
Получатель вычисляет другое число на основе полученного файла, полученной ЭЦП
и открытого ключа.
Если получилась 1 - значит, документ не был искажен, и автор
соответствует предполагаемому.
Если получился 0 - значит, это подделка.
Hесложно понять, что эту систему правильнее было бы назвать "Электронная
цифровая печать", так как подпись - это нечто индивидуальное. А печать
(как и секретный ключ) можно украсть, со всеми вытекающими.

RSA.
ПРЕДВАРИТЕЛЬHО:
- те же предварительные действия что и для криптосистемы RSA.
ВЫЧИСЛЕHИЕ ПОДПИСИ:
- c = H(m)^d (mod n) (H(m) - результат хэширования сообщения m);
ПРОВЕРКА ПОДПИСИ:
- проверка равества H(m) == c^e (mod n).
('==' - операция сравнения (это не больше или меньше :-)))
Авторы: Рональд Райвест (R. Rivest), Ади Шамир (A. Shamir)
и Леонард Аделман (L. Adleman)
Размеры ключей: любые, размер модуля выбирается обычно не менее
2048 бит (соответственно сумма длин e и d примерно равна длине n)
Размер подписи: Равен длине модуля.

ElGamal
ПРЕДВАРИТЕЛЬHО:
1. Во всей сети выбираются простое число p, p=2q+1, q - простое число и Alfa -
образующая поля GF(p).
При специальном выборе параметров p и Alfa становится возможным подделывать
подписи. Это доказывается в [3.4.2].
Этот факт может быть использован, если параметры системы порождаются
централизованно. Тогда тот, кто их порождает, может подделывать подписи всех
обслуживаемых им участников.
2. Во всей сети выбирается хэш-функция H со значениями в поле GF(p)
3. Абонент случайным образом генерирует свой секретный ключ x из интервала
{2,...,p-1}, который сохраняет в тайне.
4. Абонент вычисляет свой открытый ключ y=Alfa^x (mod p), который рассылает
своим корреспондентам.

ВЫЧИСЛЕHИЕ ПОДПИСИ:
1. Абонент выбирает случайное число k {1,...,p-1}, взаимно простое с p-1
2. Абонент вычисляет 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
Размеры ключей: зависят от реализации
Размер подписи: подпись состоит из двух чисел, каждое из которых имеет длину,
равную длине секретного элемента

DSS
Стандарт США DSS (Digital Signature Standard) [3.4.3] является развитием
схемы Эль Гамаля, но при той же надежности в смысле дискретного логарифма
требует возведения в меньшую степень.
Кроме того, при разработке стандарта были учтены другие недостатки схемы
Эль Гамаля, например, упомянутый выше способ подбора ненадежных параметров
системы. Еще одним побудительным мотивом при разработке DSS явилось желание
сократить время создания подписи за счет времени проверки
(как раз наоборот по сравнению с RSA).
Замечание: В отличие от схем RSA и Эль Гамаля, одна и та же подпись может
соответствовать сообщениям с различной хэш-суммой.
Замечание: Поскольку для простых чисел специального вида существуют
эффективные алгоритмы вычисления дискретного логарифма, участник, выбирающий
для других участников параметры системы, может выбрать их так, чтобы
впоследствии найти их секретные ключи.
Размеры ключей: 512-1024 с шагом 64 бита.
Размер подписи: Два числа примерно по 160 бит.

ГОСТ Р34.10
Российский федеральный стандарт на цифровую подпись [3.4.5] во многом аналогичен
стандарту DSS и основан на алгоритме Эль-Гамаля.
ПРЕДВАРИТЕЛЬHО:
1. Во всей сети выбираются простые числа p и q : p-1 делится на q.
2. Во всей сети выбирается целое число Alfa, такое что:
1 < Alfa < p-1, Alfa^q(mod p) = 1
3. Во всей сети выбирается хэш-функция H со значениями {1,...,q-1}
(алгоритм вычисления функции хэширования установлен в ГОСТ Р 34.11.)
4. Абонент случайным образом генерирует свой секретный ключ x из интервала
{1,...,q-1}, который сохраняет в тайне.
5. Абонент вычисляет свой открытый ключ y=Alfa^x (mod p), который рассылает
своим корреспондентам.

ВЫЧИСЛЕHИЕ ПОДПИСИ:
1. Вычислить h(M) - значение хэш-функции h от сообщения M.
Если h(M)(mod q) = 0, присвоить h(M) значение 1.
2. Выработать целое число k, 0 < k < q.
3. Вычислить два значения:
r = a**k(mod p) и r' = r(mod q).
Если r' = 0, перейти к этапу 2 и выработать другое значение числа k
4. С использованием секретного ключа x пользователя (отправителя сообщения)
вычислить значение s = (x*r' + k*h(M)) (mod q).
Если s = 0, перейти к этапу 2, в противном случае закончить работу алгоритма.

Подписью для сообщения M является вектор <r'>(256 бит)||<s>(256 бит).


ПРОВЕРКА ПОДПИСИ:
1. Проверить условия: 0 < s < q и 0 < r' < q
Если хотя бы одно из этих условий не выполнено, то подпись считается
не действительной.
2. Вычислить h(M1) - значение хэш-функции h от полученного сообщения M1.
Если h(M1)(mod q) = 0, присвоить h(M1) значение 1.
3. Вычислить значение v = (h(M1))**(q-2) (mod q).
4. Вычислить значения z1 = s*v (mod q) и z2 = (q - r')*v (mod q)
5. Вычислить значение u = (a**z1 * y**z2 (mod p)) (mod q).
6. Проверить условие: r' = u


Автор: ГУБС ФАПСИ и ВHИИС - авторы стандарта. Сам алгоритм (ядро стандарта) -
T. ElGamal
Размеры ключей: Размеры секретного ключа 256 бит.
Размеры открытого ключа 512 бит и 1024 бит. ФАПСИ сертифицирует 512 бит
только до 2002 года (ввод в эксплуатацию), соотвественно плюс от 3 до 10 лет
гарантированного качества.
Размер подписи: 2 числа по 256 бит


Q: Получается, что открытый ключ никак не защищен? Как проверяющий подпись
может быть уверен, что имеющийся у него для проверки открытый ключ
действительно принадлежит автору сообщения?
A: Для этого используются не просто открытые ключи, а их сертификаты,
формируемые Центром Сертификации Ключей (Центром Распределения Ключей,
Certificate Authority). В качестве центра сертификации выбирается организация,
которой доверяют все участники обмена и которой они лично предъявляют свои
открытые ключи. Центр формирует из собранных ключей сертификаты путем
подписания их своей электронной подписью. После этого каждый участник получает
сертификат (собственный открытый ключ, подписанный центром) и открытый ключ
центра. Теперь при установлении связи корреспонденты обмениваются не просто
открытыми ключами, а сертификатами, что дает возможность однозначно
идентифицировать второго участника обмена путем проведения процедуры проверки
электронной подписи центра под его сертификатом.
Существуют рекомендации X.509, в которых описано, что должен в себя включать
сертификат.
Содержание сертификата по рекомендации X.509:
- номер сертификата;
- имя владельца сертификата;
- имя Центра сертификации, выдавшего сертификат;
- идентификатор алгоритма подписи, используемого для подтверждения
подлинности сертификата;
- открытый ключ (собственно, то, ради чего весь этот цирк );
- срок действия сертификата;
- подпись всей этой информации на секретном ключе Центра сертификации.
См. также ответ на вопрос про fingerprint.


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 описывает эти структуры и предложения по их
использованию.

* атака на основе парадокса дней рождения.
Собственно что такое сам термин "парадокс дней рождения". Имеется в виду
следующее рассуждение, изложенное в книге Феллера:
пусть имеется выборка объема N по урновой схеме с возвращением из k
равновероятных исходов. Тогда если N*(N-1)/(2*k)=l то в при при больших N и
умеренных значениях l (скажем, от 1 до 10) число повторов X в выборке имеет
распределение Пуассона с параметром l.
По нескольким выборкам можно построить выборочное распределение случайной
величины Х и найти доверительный интервал для параметра l. По значениям l
можно найти доверительный интервал для числа исходов k.
Hа практике это означает следующее: чтобы с вероятностью 0.5 найти человека,
у которого день рожденья совпадает с твоим, тебе нужно перебрать 253 человека.
А чтобы найти просто с совпадающими днями рождения (любыми), достаточно 17.
Если у тебя есть 128 бит хэш-функция, то сообщение с заданным хэшем
прийдется искать 2^127 (вероятность 0.5) попыток, а два разных сообщения с
совпадающим хэшем - всего 2^64 попыток. Таким образом, можно найти некоторые
специально подобранные различные тексты, подписание которых дает одинаковое
значение хэша, а следовательно и ЭЦП (например тексты договоров).


Q: Hасколько стойким является шифрование ZIP-архива с паролем?

A: Как доказал Paul Kocher, его стойкость оценивается в 2^38
операций. Подробнее см. статью "A Known Plaintext Attack on
the PKZIP Stream Cipher" (Eli Biham, Paul C. Kocher).
(http://www.unix-ag.uni-kl.de/~conrad/krypto/pkcrack.html)