Шпаргалки по криптографии - (шпаргалка)

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 является вектор (256 бит)||(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)

Страницы: 1, 2, 3, 4, 5