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 <= 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 :)
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 - значит, это подделка.
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:
- номер сертификата;
- имя владельца сертификата;
- имя Центра сертификации, выдавшего сертификат;
- идентификатор алгоритма подписи, используемого для подтверждения
подлинности сертификата;
- открытый ключ (собственно, то, ради чего весь этот цирк :) );
- срок действия сертификата;
- подпись всей этой информации на секретном ключе Центра сертификации.
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: Hасколько стойким является шифрование ZIP-архива с паролем?
A: Как доказал Paul Kocher, его стойкость оценивается в 2^38
операций. Подробнее см. статью "A Known Plaintext Attack on
the PKZIP Stream Cipher" (Eli Biham, Paul C. Kocher).
Q: А как дешифровать пароли в UNIX, WINDOWS, NetWare? Насколько хорошо они
защищены?
A: В этих системах они защищены по-разному.
Если рассматривать проблему укрупненно, то можно выделить два основных
подхода к хранению паролей, и, соответственно, к используемой схеме
аутентификации.
Первый подход заключается в защищенном хранении паролей на сервере.
При этом, в случае хищения базы с паролями, злоумышленник не сможет
воспользоваться этими данными непосредственно, ему понадобится
произвести некоторое количество преобразований (подчас весьма
сложных), так как пароли преобразованы односторонней функцией, и
узнать их можно только "прогоняя" различные варианты паролей через эту
функцию и сравнивая результат; в данной ситуации, это - единственный
способ дешифрования. Очевидно, что при таком подходе пользователь
должен предъявлять серверу пароль в открытом виде, чтобы последний,
произведя над ним соответствующее преобразование, сравнил полученный
результат с записью в базе паролей. Ну, а коль скоро пароль
предъявляется в открытом виде, возможен его перехват при передаче по
каналам связи. Конечно, если использовать даже самую сложную функцию
вида:
y=f(x) (1)
где x - пароль, а y - значение односторонней функции (как правило, в
качестве односторонней используется хэш-функция, которая должна
обладать, как минимум, следующими характеристиками: ее значение имеет
фиксированный размер независимо от размера параметра, а подбор
параметра под заданное значение является сложной задачей), то
одинаковым паролям будут соответствовать одинаковые значения функции.
Злоумышленнику в этом случае достаточно будет один раз обработать
большой словарь и в дальнейшем просто определять пароль по значению
функции. Чтобы устранить эти недостатки в процесс вычисления вводят
дополнительный элемент - salt, который для каждой генерации пароля
выбирается случайным образом, после чего формула (1) приобретает вид:
y=f(salt,x) (2)
а в базе паролей на сервере хранится пара чисел (salt,y). Такой подход
к защите паролей применяется в большинстве UNIX-систем. В качестве
преобразования (2) используется алгоритм шифрования DES (x выступает в
роли ключа шифрования), либо алгоритм хэширования MD5.
Другой подход направлен на невозможность перехвата пароля при его
передаче. В этом случае пользователь доказывает серверу, что ему
известен правильный пароль, не путем предъявления его в открытом виде,
а путем вычисления над предложенным сервером числом некоей функции,
зависящей также и от пароля. В простейшем случае это может быть
шифрование предложенного сервером числа, используя в качестве ключа
пароль. Естественно, что для проверки значения функции, присланного
пользователем, серверу необходимо повторить данное преобразование, а
для этого, в свою очередь, он должен обладать паролем в открытом виде.
Схема похожа на предыдущую, изменяется только место вычисления
односторонней функции, а роль salt играет высылаемое сервером число.
Очевидно, что при этом способе осуществления аутентификации,
необходимо принять меры по недопущению несанкционированного доступа к
базе паролей на сервере. Такой подход применяется в семействе ОС
Novell NetWare, а также Windows NT.
Про атаки типа brute-force лучше прочитать отдельно для каждой системы.
Для unix-подобных систем (и не только) см. программу John-The-Ripper.
(primary site http://www.false.com/security/john/)
Для windows (pwl) - PWLCrack
(primary site http://www.geocities.com/SiliconValley/Hills/7827)
Для NetWare 3.x - http://cybervlad.port5.com/nwpass/index.html (или более
полную версию - netware.pdf, там же).
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: Hет, если вы не собираетесь:
- быть удостоверяющим центром для сторонних организаций;
- распространять средства ЭЦП;
- осуществлять техническое обслуживание средств ЭЦП (у сторонних организаций);
- изготавливать и распространять ключи ЭЦП для сторонних организаций;
В каких случаях нужна лицензия ФАПСИ читайте в постановлении Правительства
РФ 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.enlight.ru/crypto
- страничка П.Семьянова "Криптографический ликбез"
http://www.ssl.stu.neva.ru/psw/crypto.html
- http://home.od.ua/~blackw/Crypt/crypt.html
Q: А у меня напряги с интернетом. В бумажном виде что посоветуете?
A: Вот список, разбитый по разделам:
1. Литература общего характера
1. Gilles Brassard. Modern Cryptology. - Berlin etc.: Springer-Verlag, 1988.
(Lecture Notes in Computer Science; 325).
2. Bruce Schneier Applied Cryptography: Protocols, Algorithms and Source Code
in C. - John Wiley & Sons, 1993. - 618 p.
3. Мафтик С. Механизмы защиты в сетях ЭВМ: Пер. с англ. - М.: Мир, 1993. - 216
с.
4. Дориченко С.А., Ященко В.В.: 25 этюдов о шифрах. - М.: Теис, 1994. - 71 с. -
(Математические основы криптологии).
5. Жельников В. Криптография от папируса до компьютера. - М.: ABF, 1996. - 335
с. ISBN 5-87484-054-0
6. Петров А.А. "Компьютерная безопасность. Криптографические методы",
М., "ДМК", 2000, ISBN 5-89818-064-8
7. Под общ. pед. В. В. Ященко, "Введение в кpиптогpафию"
М.: МЦHМО, 2000, 288 c., ISBN 5-900916-65-0, Тиpаж 3000 экз.
8. Варфоломеев А.А., Пеленицын М.Б. "Методы криптографии и их применение в
банковских технологиях",
М.: МИФИ, 1995, 116 с., УДК 681.3.004.4
(тираж 500 экз.)
2. Криптосистемы с секретным ключом (симметричные)
1. FIPS publication 46 Data Encryption Standard // Federal Information
Processing Standards Publ. - 1977.
2. Eli Biham, Adi Shamir. Differential Cryptanalysis of DES-like cryptosystems
// Journal of Cryptology. - 1991. - + 4(1). - P. 3-72.
3. Eli Biham, Adi Shamir. Differential Cryptanalysis of the full 16-round DES
// Advances in Cryptology - CRYPTO'92. - Berlin etc.: Springer-Vergal, 1993.
(Lecture Notes in Computer Science; 740).
4. Matsui Mitsuru. Linear Cryptoanalysis Method for DES Cipher // Advances in
Cryptology - EUROCRYPT'93. - Berlin ect.: Springer-Vergal, 1994. (Lecture Notes
in Computer Science; 765). - P. 380-397.
5. K.W. Campbell, M.J. Wiener. DES is Not a Group // Advances in Cryptology -
CRYPTO'92. - Berlin etc.: Springer-Vergal, 1993. (Lecture Notes in Computer
Science; 740). - P. 512-520.
6. Merkle R.C., Hellman M.E. On the security of multiple encryption //
Communications of the ACM. - 1981. - Vol. 24. - P. 465-467.
7. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая.
Алгоритм криптографического преобразования.
8. Винокуров А. ГОСТ не прост..., а очень прост! // Монитор. - 1995. - +1. -
С. 60-73.
9. Xuejia Lai, James L. Massey A proposal for a New Block Encryption Standard
// Advances in Cryptology - EUROCRYPT'90. - Berlin ect.: Springer-Vergal, 1991.
(Lecture Notes in Computer Science; 473). - P. 389-404.
10. Willi Meier On the security of the IDEA Block Cipher // Advances in
Cryptology - EUROCRYPT'93. - Berlin ect.: Springer-Vergal, 1994. (Lecture Notes
in Computer Science; 765). - P. 371-385.
2.1. Аутентификация и идентификация с помощью симметричных криптосистем
1. Yvo Desmedt. Unconditionally secure authentification schemes and practical
and theoretical consequences // Advances in Cryptology - CRYPTO'85. - Berlin
ect.: Springer-Vergal, 1986. (Lecture Notes in Computer Science; 218). -
P.42-55.
2. Robert R. Jueneman. A High Speed Manipulation Detection Code // Advances in
Cryptology - CRYPTO'86. - Berlin ect.: Springer-Vergal, 1987. (Lecture Notes in
Computer Science; 263). - P. 327-346.
3. Bart Preneel, Paul C. van Oorshot. MDx- MAC and Building Fast MACs from
Hash Functions // Advances in Cryptology - CRYPTO'95. - Berlin ect.:
Springer-Vergal, 1995. (Lecture Notes in Computer Science; 963). - P. 1-14.
4. Mihir Bellaro, Joe Kilian, Philip Rogaway. The Security of Cipher Block
Chaining. // Advances in Cryptology - CRYPTO'95. - Berlin ect.:
Springer-Vergal,
1995. (Lecture Notes in Computer Science; 963). - P. 341-358.
5. Bart Preneel, Paul C. van Oorschot. On the Security of Two MAC Algorithms
// Advances in Cryptology - EUROCRYPT'96. - Berlin ect.: Springer-Vergal, 1996.
(Lecture Notes in Computer Science; 1070). - P. 19-32.
6. Metzger P., Simpson W. IP Authentication using Keyed MD5. - Network Working
Group. - RFC 1828. - August 1995.
7. Burt Kaliski, Matt Rodshaw. Message Authentication with MD5 // CryptoBytes.
- Spring 1995. - Vol. 1., No. 1. (The technical newsletter of RSA Laboratories,
a division of RSA Data Security, Inc).
8. Ronald Rivest. The MD5 Message-Digest Algorithm. - Network Working Group. -
RFC 1321.
9. Bert den Boer, Antoon Bosselaers. Collisions for the Compression Function
of MD5 // Advances in Cryptology - EUROCRYPT'93. - Berlin ect.:
Springer-Vergal,
1994. (Lecture Notes in Computer Science; 765).
10. Hans Dobbertin. Cryptanalysis of MD5 Compress.
11. Hans Dobbertin. The Status of MD5 After a Recent Attack // CryptoBytes. -
Spring 1996. - Vol. 2., No. 2. (The technical newsletter of RSA Laboratories, a
division of RSA Data Security, Inc). P. 1-6.
12. NIST FIPS PUB 180-1. Secure Hash Standard. - National Institute of
Standards and Technology, US Department of Commerce. - 17 Apr 1995.
13. Martin Abadi, Roger Needham. Prudent Engineering Practice for Cryptographic
Protocols. - June 1, 1994. - 31 p. - (Rep. DEC Systems Research Center, No.
125).
3. Криптосистемы с открытым ключом (асимметричные)
1. Терехов А.H., Тискин А.В. Криптография с открытым ключом: от теории к
стандарту // Программирование. - 1994. - + 5. - Р. 17-22.
2. IEEE P1363: Standard for Public-Key Cryptography (Working Draft).
3. А. Саломаа "Криптография с открытым ключом",
М., МИР, 1996, ISBN 5-03-0011991-X
3.1. Алгебраические основы
1. Виноградов И.М. Основы теории чисел. - М., 1949. - 180 с.
2. Дональд Кнут. Искусство программирования для ЭВМ. Т. 2. Получисленные
алгоритмы: пер. с англ. - М., Мир, 1977. - 724 с.
3. Лидл Р., Hидеррайтер Г. Конечные поля: пер. с англ. - М.: Мир, 1988. - в
2-х т.
4. Ахритас А. Основы компьютерной алгебры с приложениями: пер. с англ. - М.:
Мир, 1994. - 544 с.
5. Victor S. Miller. Use of Elliptic Curves in Cryptography // Advances in
Cryptology - CRYPTO'85. - Berlin etc.: Springer-Verlag , 1986. (Lecture Notes
in
Computer Science; 218). - P. 417-426.
6. Alfred Menezes. Elliptic Curve Public Key Cryptosystems. - Boston: Kluwer
Academic Publishers - 1993.
7. Alfred Menezes. Elliptic Curve Cryptosystems. // CryptoBytes. - Spring
1995. - Vol. 1., No. 2. (The technical newsletter of RSA Laboratories, a
division of RSA Data Security, Inc). P. 1-4.
8. Т.Кормен, Ч.Лейзерсон, Р.Ривест "Алгоритмы. Построение и анализ",
М., МЦНМО, 1999, ISBN 5-900916-37-5
9. Нечаев В.И. "Элементы криптографии (Основы теории защиты информации)",
М.: Высш. шк., 1999. - 109 с. ISBN 5-06-003644-8
3.2. Односторонние функции
1. Erich Bach. Intractable Problems in Number Theory // Advances in Cryptology
- CRYPTO'88. - Berlin etc.: Springer-Vergal, 1989. (Lecture Notes in Computer
Science; 403). - P. 77-93.
2. Andrew M. Odlyzko. The Future of Integer Factorization // CryptoBytes -
Summer 1995. - Vol. 1., No. 2. (The technical newsletter of RSA Laboratories, a
division of RSA Data Security, Inc). - P. 5-12.
3. Pohlig S, Hellman M.E. An improved algorithm for computing logarithms over
GF(p) and its cryptographic significance // IEEE Trans. on Information Theory.
- 1978. - vol. IT - 24. - P. 106-110.
4. Andrew M. Odlyzko. Discrete Logarithms in Finite Fields and their
Cryptographic Significance // Advances in Cryptology - EUROCRYPT'84. - Berlin
etc.: Springer-Vergal, 1985. (Lecture Notes in Computer Science; 209). - P.
224-314.
5. Benny Chor, Oded Goldeich. RSA/Rabin least significant bits are
1/2+1/(poly(log n)) secure // Advances in Cryptology - CRYPTO'84. - Berlin
etc.:
Springer-Vergal, 1985. (Lecture Notes in Computer Science; 196). - P. 303-313.
6. Benny Chor, Oded Goldeich, Shafi Goldwasser. The Bit Security of Modular
Squaring given Partial Factorization of the Modulos // Advances in Cryptology -
CRYPTO'85. - Berlin etc.: Springer-Vergal, 1986.
(Lecture Notes in Computer Science; 218). - P. 448-457.
3.3. Асимметричные криптосистемы
1. Diffie W., Hellman M.E. New directions in cryptography // IEEE Trans. on
Information Theory. - 1976. - vol. IT -22. - P. 644-654.
2. Bert den Boer. Diffie-Hellman is as Strong as Discrete Log for Certain
Primes // Advances in Cryptology - CRYPTO'88. - Berlin etc.: Springer-Verlag,
1989. (Lecture Notes in Computer Science; 403). - P. 530-539.
3. Ueli M. Maurer Towards the Equivalence of Breaking the Diffie-Hellman
Protocol and Computing Discrete Logarithms // Advances in Cryptology -
CRYPTO'94. - Berlin etc.: Springer-Verlag, 1995. (Lecture Notes in Computer
Science; 839). - P. 271-281.
4. Ronald L. Rivest, Adi Shamir, Leonard Adleman. A Method for Obtaining
Digital Signatures and Public-Key Cryptosystems // Communications of the ACM. -
1978. - Vol. 21, No. 2- P. 120-126.
5. Johan Hastad. Using RSA with low exponent in a public key network //
Advances in Cryptology - CRYPTO'85. - Berlin etc.: Springer-Verlag, 1986.
(Lecture Notes in Computer Science; 218). - P. 403-408.
6. Don Coppersmith, Matthew Franklin, Jacques Patarin, Michael Reiter.
Low-Exponent RSA with Related Message // Advances in Cryptology - EUROCRYPT'96.
- Berlin etc.: Springer-Verlag, 1996. (Lecture Notes in Computer Science;
1070). - P. 1-9.
7. Taher El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on
Discrete Logarithms // IEEE Trans. on Inform. Theory. - July 1985. - vol. IT
-31, No. 4. - P.469-472.
8. Taher El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on
Discrete Logarithms // Advances in Cryptology - CRYPTO'84. - Berlin etc.:
Springer-Verlag, 1985. (Lecture Notes in Computer Science; 196). - P. 10-18.
3.4. Цифровая подпись
1. Ross Anderson, Roger Needham. Programming Satan's Computer // (Lecture
Notes in Computer Science; 1000).
2. Daniel Bleichenbacher. Generating ElGamal Signatures Without Knowing the
Secret Key // Advances in Cryptology - EUROCRYPT'96. - Berlin etc.:
Springer-Verlag, 1996. (Lecture Notes in Computer Science; 1070). - P. 10-18.
3. FIPS PUB 186, Digital Signature Standard (DSS). - National Institute of
Standards and Technology, US Department of Commerce. - 19 May 1994.
4. Gustavus J. Simmons. Subliminal Communication is Easy Using the DSA //
Advances in Cryptology - EUROCRYPT'93. - Berlin etc.: Springer-Verlag, 1994.
(Lecture Notes in Computer Science; 765). - P. 218-232.
5. ГОСТ Р 34.10-94. Информационная технология. Криптографическая защита
информации. Процедуры выработки и проверки электронной цифровой подписи на базе
асимметричного криптографического алгоритма. - Введ. 01.01.95. - М.: Изд-во
стандартов, 1994
6. Birgitt Pfotzmann. Digital Signature Schemes. General Framework and
Fail-Stop Signatures. - Berlin etc.: Springer-Verlag, 1990. (Lecture Notes in
Computer Science; 1100). - P. 396.
7. David Chaum, Hans van Antwerpen. Undeniable Signatures // Advances in
Cryptology - CRYPTO'89. - Berlin etc.: Springer-Verlag, 1990. (Lecture Notes in
Computer Science; 435). - P. 212-216.
8. David Chaum. Zero-Knowledge Undeniable Signatures // Advances in Cryptology
- EUROCRYPT'90. - Berlin etc.: Springer-Verlag, 1991. (Lecture Notes in
Computer
Science; 473). - P. 458-464.
9. Amos Fiat, Adi Shamir. How to prove yourself: Practical Solutions to
Identification and Signature Problems // Advances in Cryptology - CRYPTO'86. -
Berlin etc.: Springer-Verlag, 1987. (Lecture Notes in Computer Science; 263). -
P. 186-194.
10. Uriel Feige, Amos Fiat, Adi Shamir. Zero Knowledge Proofs of Identity //
Proc. 19th Annual ACM Symp. on Theory of Computing. - 1987. - P. 210-217.
11. Uriel Feige, Amos Fiat, Adi Shamir. Zero Knowledge Proofs of Identity //
Journal of Cryptology. - Vol. 1, No. 2. - 1988. - P. 77-94.
12. Silvio Micali, Adi Shamir. An Improvement of the Fiat-Shamir Identification
and Signature Scheme // Advances in Cryptology - CRYPTO'88. - Berlin etc.:
Springer-Verlag, 1989. (Lecture Notes in Computer Science; 403). - P. 216-231.
13. Schnorr C.P. Efficient Identification and Signatures for Smart Cards //
Advances in Cryptology - CRYPTO'89. - Berlin etc.: Springer-Verlag, 1990.
(Lecture Notes in Computer Science; 435). - P. 239-251.
================================================
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
A2: Hу зачем сразу читать header-ы (их потом), есть нормальная документация:
Сообщения и сертификаты:
http://msdn.microsoft.com/library/psdk/crypto/cryptovrvw_8395.htm
Аутентификация и шифрование соединений:
http://msdn.microsoft.com/library/psdk/secpack/secpacknavpage_0o1f.htm
Обзор системы на русском:
http://www.microsoft.com/rus/windows2000/library/security/
X. ПРИЛОЖЕНИЯ. Примеры реализации.
Первоначальная мысль вставить это сюда была критически обдумана и отброшена -
слишком большой объем. Вместо этого решено было создать библиотеку реализаций
и сложить в одном месте в инете. Пока это место находится по адресу:
ftp://ftp.wtc-ural.ru/pub/ru.crypt
XI. Здесь пары вопрос/ответ, которые я затруднился определить в какой-либо
раздел. Вобщем, "разное" :)
Q: Как проверить "случайность" моего ГСП (генератор случайной
последовательности).
A1: В интеpнете есть "Diehard test battery". Этот комплект содеpжит 15 тестов
чисел на случайность. Адpес http://stat.fsu.edu/~geo/diehard.html
A2:
Предположим у тебя имеется файл (массив,набор чисел) значений некоторой
случайной величины и ставится задача изучения ее свойств, т.е. являются ли
эти значения равномерно распределенными (равновероятными) в некотором
интервале.
Относительно изучаемой случайной величины можно сделать два предположения,
называемых нуль-гипотезой и альтернативной гипотезой:
1) Случайная величина имеет равномерное распределение (нуль-гипотеза)
2) Случайная величина не имеет равномерного распределения, т.е. закон
распределения случайной имеет уклонения от равномерного распределения
(альтернативная гипотеза).
В математической статистике сущесвуют ряд тестов, назваемых критериями
согласия для проверки функции распределения случайной величины на предмет ее
соответствия теоретически ожидаемому закону распределения. Примерами
таких критериев согласия являются Хи-квадрат (критерий Пирсона) и критерий
Kолмогорова-Смирнова, критерий серий и т.д. Kритериев много.
Статистические критерии могут установить только отличие теоретического
и экспериментального распределений, поэтому нуль-гипотеза,как правило
выдвигается для проверки - нет ли оснований для ее отбрасывания.
Другими словами невозможно доказать "чистую случайность" последовательности,
но можно с определенной степенью вероятности опровергнуть противоположное
утверждение. Таким образом, для решения является ли различие достоверным
необходимо установить границы для близости-различия частот в выборке и
теоретически ожидаемых частот. Данная величина называется уровнем значимости,
и обычно принимает значения 5%, 1%, 0.1%. Результат называется значимым на
уровне 5%, если правильная нуль-гипотеза будет отклонена не более, чем в 5%
случаев.
Kритерий согласия Хи-квадрат.
Пусть необходимо протестировать генератор, выдающий некоторую
последовательность бит, относительно которой выдвигается нуль-гипотеза
о том, что эта последовательность имеет равномерное распределение.
Обозначим объем выборки n. Пусть мы сгенерировали 100 бит, тогда n=100.
Пусть выборка разделена на k классов. Если, например, исследуем частоты
появления только 0 и 1 - тогда количество классов два. Пусть В_i -
наблюдаемая частота=количество появлений некоторого признака в выборке.
Обозначим В_0 - количество нулей, В_1 - количество единиц.
Пусть E_i - ожидаемая частота признака i. Для нашего случая E_0=E_1= 0.5*n.
Формула Хи-квадрат для вычисления различия между экспериментальным и
теоретическим распределениями следующая:
i=k-1
____ 2
(В_i - Е_i)
Хи-квадрат = /___ -------------
i=0 Е
Для численного анализа вводится понятие "степеней свободы" K=(k-1).
В результате обработки экспериментальных данных получаем два числа:
Хи-квадрат и K. Выберем уровень значимости=вероятность ошибки, напрмер 0.1%
Открываем справочник (учебник) по мат.статистике или терии вероятностей
и находим таблицу 5%, 1% и 0.1% границ для Хи-квадрат. Если значение
Хи-квадрат меньше или равно табличному, то нуль-гипотеза принимается.
Иначе - отклоняется.
Если для заданного количества степеней свободы найти в таблице вычисленное
значение Хи-квадрат, то можно узнать уровень значимости=вероятность ошибки.
Чтобы получить польше подтверждений о качестве генератора, тесты необходимо
прогнать для разных значений k, т.е применить изложенный теоретический материал
к случайным величинам вида
- 00,01,10,11 E_i=0.25 = 1/(2^2)
- 000, 001, 010 ... E_i=0.125 = 1/(2^3)
- 0000, 0001, E_i= 1/(2^4)
и т.д
Чем больше тестов, тем больше вероятностей отбросить сомнения.
>Ограничение: для использования критерия согласия Хи-квадрат выборка должна
быть не слишком малой ! т.е. (n >= 40) и ожидаемые частоты должны быть не
менее 5 (Е_i >= 5). Если они меньше, то их необходимо увеличить до требуемого
уровня путем объединения соседних классов.
Kритерий согласия Kолмогорова-Смирнова (K-С)
назначение - аналогично предыдущему. Проверяется гипотеза- выборка
относится к равномерному распределению. Определяют значения Е и В и образуют
функцию накопленной частоты F_e и F_b, находят максимум разности и делят на
объем выборки n.
max | F_b - F_e |
K-С = ---------------------
n
Таблица уровня значимости:
5% 1.36 * Kорень_из(n)
1% 1.63 * Kорень_из(n)
Если вычисленное значение K-С меньше или равно соотвю уровня значимости, то
нуль-гипотеза принимается, иначе отклоняется.
Ограничения объем выборки n>35.
Hа страничке Санкт-Петербургского Технического Университета
http://www.ssl.stu.neva.ru/psw/crypto.html
имеется книга "Поточные шифры. Результаты заруюежной открытой криптологии" -
(автор неизвестен). Глава 3 называется "Статистические свойства и меры
сложности последовательностей" (стр.35-43). В этой главе описаны:
- Частотный тест
- Последовательный тест
- Тест серий
- Автокорреляционный тест
- Универсальный тест
- Тест повторений
- Сравнение тестов l-грамм
- Kомбинирование тестов
- отсечение слабых последовательностей.
Из общематематической литературы можно посоветовать практически любую книгу
по математической статистике, например А.А.Боровков "Теория вероятностей и
мат.статистка", Закс "Статистическое оценивание".
Q: Как проверить число на простоту?
A1:
Вот к чему привели различные поиски. Для общего случая простых чисел
существует по крайней мере два алгоритма проверки их простоты (естественно не
считая всяких там переборов в лоб). Jacobi sum test (точнее APR-CL (Adleman,
Pomerance and Rumely; Cohen and Lenstra), по имени ученых, которые предложили
и развили алгоритм) и ECPP (Elliptic Curve Primality Test). По времени
выполнения они приблизительно одинаковые, но ECPP имеет то преимущество, что оно создает
некий сертификат, используя который можно в любой момент проверить простое
числоили нет в сравнительно короткое время. (на васике)
http://archives.math.utk.edu/software/msdos/number.theory/ubasic/.html
В него входит программы aprt-cle.ub, это APR-CL.
(на С)
А вот ECPP:
http://www.lix.polytechnique.fr/~morain/Prgms/ecpp.english.html
A2:
Читай книжки. Я видел описания тестов на простоту, например, в
ИHТ. Современные проблемы математики.Фундаментальные направления. Т. 49. 1990.
с. 63
Алгебра и теория чисел (с приложениями): Избранные доклады семинара H.Бурбаки:
Сб. статей 1976-1985 гг. Пер. с англ. и франц. - М. Мир, 1987.
с. 47
В первой описаны следующие алгоритмы:
1) Факторизация Ферма
2) Вероятностный алгоритм CLASNO
3) Алгоритм Шенкса SQUFOF
4) Метод непрерывных дробей CFRAC
5) (p-1)-метод Полларда
6) Метод эллиптических кривых
Во второй упор сделан на Adleman-Pomerance-Rumely.
а вот еще:
Riesel H. Prime numbers and computer methods for factorization // Progr. Math.
57. - Birkhaser: Boston, 1985. - 464 c.
статья "A Tale of Two Sieves" на:
http://www.ams.org/publications/notices/199612/pomerance.html
Обзорные статьи (списочек от Alexander Krotoff):
Williams H. C. Primality testing on a computer,
Arts Combin. 5(1978). 127-185.
Lenstra H. W. Jr. Primlity testing algotitms after Adleman,
Rumely and Williams.
Seminare Bourbaki, 34-e annee, 1980/1981 #576, 1-15.
Простейший алгоритм на уcиленной малой теореме Ферма имеет сложность
O(ln(n)^2). Основан на гипотезе Римана.
Solovay R. Strassen V.
A fast Monte-Carlo test for primality, SIAM J. Comput. 6(1977),
84-85, 7(1978), 118
Adleman L. M. On distinguishing prime numbers from composite numbers
(abstract) Proc 21st Annual IEEE Symposium on Foundation of
Science (1980) 387-406.
Adleman L.M., Pomerance C. Rumely R.S.
On distiguishig prime numbers from composite numbers,
Ann. of Math. 117(1983) 173-206
Сложность алгоритма O(ln(n)^{C*ln(ln(ln(n)))})
Pollard J.M. Theorems on factorization and primality testing,
Proc. Cambrdge Philos. Soc. 76(1974), 521-528
сложность O(n^(1/8)).
Q: Я тут написал программу и хочу построить уникальный ключ, привязав
его к "железу", номеру материнки, процессора, жесткого диска, сетевой
карте. К чему лучше?
A: Ни к чему. Привязка к "железу" (любому) неэффективна в случае,
если комп взят из "большой китайской партии" и неудобна в
использовании, поскольку апгрейд "железа" явление достаточно частое,
чтобы при сколь-нибудь серьезном тираже программы ты поимел много
забот с поддержкой.
Q: Что такое необратимое шифрование?
A: Такого термина нет. Шифрование по определению обратимо, иначе это
действие бессмысленно. Обычно используется понятие хэш (свертка).
См. раздел "хэш-функции".
Q: А возможно ли создание аpхиватоpа у котоpого будет коэффициент
сжатия 1 к миллиону?
A: Согласно Шеннону, если некотоpый источник инфоpмации способен
генеpиpовать N pазличных символов S_1, S_2, ..., S_N с
веpоятностями p_1, p_2, ..., p_N, то количество инфоpмации,
поступающее с отдельным символом (т.е. теоpетически минимальное
число бит, котоpое пpидется в сpеднем затpатить на кодиpование
отдельного символа) составляет:
I = - sum_{i=1}^{N} {p_i * log_2 p_i}
(минус сумма пpоизведений веpоятности возникновения i-го символа на
логаpифм по основанию два от этой же веpоятности).
Эта функция достигает максимума в случае, если все веpоятности p_i
pавны между собой, и меньше во всех остальных случаях (наименьшее
значение - 0, достигается тогда, когда веpоятность возникновения
одного из символов pавна 1, а веpоятностивсех остальных pавны
нулю).
Следствие 1: если способ кодиpования и статистические хаpактеpистики
входного потока данных таковы, что в пpинципе допускают сжатие
1:1000000, то любой "пpавильный" аpхиватоp для данного входного
потока обеспечит близкий к этому значению коэффициент сжатия.
Следствие 2: если входной поток пpедставляет собой множество
pеализаций pавномеpно pаспpеделенной случайной величины,
пpедставленных в pавномеpном безызбыточном коде (а такой, видимо,
обычно и получается после опеpации шифpования), то не существует
аpхиватоpа, обеспечивающего хоть какое-нибудь сжатие подобного
потока.
Q: Я, CrYpToGrAf...
A: В этой эхе за никами прятаться не принято. разве, что Disturbo (его
и так все знают), а Harry Вush - это имя такое 8-))
Q: Дайте описание файла ... (MP3, JPG, etc)
A: Ребята, возьмите в интернете. Что любопытно, там описаны и заголовки,
из которых можно почерпнуть "открытые тексты" для "частично" "plain-text
known attack"
XII. Заключение.
Спасибо всем, кто дочитал до этого места ;)
0 комментариев