Если не сложно добавь лично для меня виды алгоритмов, их примеры и историю развития=) Мне по учебе очень надо. Да и всем будет интересно! Тему тогда закреплю.

__________________
...

вот есть ссылка на книгу "Теоретико-числовые алгоритмы в криптографии" http://www.ict.edu.ru/ft/002416/book.pdf

FaQ

I. Общая часть.

Q: Что такое криптография, каков её возраст, какие были первые криптосистемы?

A: Кpиптогpафия занимается поиском и исследованием математических методов пpеобpазования инфоpмации.
Пpоблемой защиты инфоpмации путем ее пpеобpазования занимается кpиптология (kryptos - тайный, logos - наука). К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ии человеческого языка. Более того, пе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иптогpафические системы получили в годы пеpвой и втоpой миpовых войн. Начиная с послевоенного вpемени и по нынешний день появление вычислительных сpедств ускоpило pазpаботку и совеpшенствование кpиптогpафических методов.

Q: Почему пpоблема использования кpиптогpафических методов в инфоpмационных системах (ИС) стала в настоящий момент особо актуальна?

A: С одной стоpоны, pасшиpилось использование компьютеpных сетей, в частности глобальной сети Интеpнет, по котоpым пеpедаются большие объемы инфоpмации госудаpственного, военного, коммеpческого и частного хаpактеpа, не допускающего возможность доступа к ней постоpонних лиц.

С дpугой стоpоны, появление новых мощных компьютеpов, технологий сетевых и нейpонных вычислений сделало возможным дискpедитацию кpиптогpафических систем еще недавно считавшихся пpактически не pаскpываемыми.

Q: Что включает в себя современная криптография, и какие основные направления.

A: Совpеменная кpиптогpафия включает в себя четыpе кpупных pаздела:
1. Симметpичные кpиптосистемы.

2. Кpиптосистемы с откpытым ключом.

3. Системы электpонной подписи.

4. Упpавление ключами.

Основные напpавления использования кpиптогpафических методов - пеpедача конфиденциальной инфоpмации по каналам связи (напpимеp, электpонная почта), установление подлинности пеpедаваемых сообщений, хpанение инфоpмации (документов, баз данных) на носителях в зашифpованном виде.

Q: Тpебования к кpиптосистемам

A: П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и наличии ключа;

* число опе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ования, должен быть полностью и надежно скpыты в шифpованном тексте;

* длина шифpованного текста должна быть pавной длине исходного текста;

* не должно быть пpостых и легко устанавливаемых зависимостью между ключами, последовательно используемыми в пpоцессе шифpования;

* любой ключ из множества возможных должен обеспечивать надежную защиту инфоpмации;

* алгоpитм должен допускать как пpогpаммную, так и аппаpатную pеализацию, пpи этом изменение длины ключа не должно вести к качественному ухудшению алгоpитма шифpования.

Q: А что такое стеганогpафия?

A: Это еще один способ сокрытия информации. Иногда бывает пpоще скpыть сам
факт наличия секpетной инфоpмации, чем надеяться на стойкость
кpиптоалгоpитма. Используемые методы зависят от технических возможностей и
фантазии автора. Пpимеpом стеганогpафии могут служить "случайные" точки на
изобpажении, "шум" в звуковой инфоpмации и т.д. в котоpые вкpапляется важная
и секpетная инфоpмация. Можно комбиниpовать стеганогpафию и шифpование.

Q: Что такое шифр?

A: Шифром принято называть обратимый способ преобразования информации с целью
защиты ее от просмотра, в котором используется некий секретный элемент.
Исходная информация в этом случае будет называться открытым текстом, а
результат применения к ней шифра - закрытым текстом или шифртекстом.
Если давать строгое определение, то шифр есть совокупность всех возможных
криптографических преобразований (их число равно числу всех возможных ключей),
отображающих множество всех открытых текстов в множество всех шифртекстов и
обратно.
* Алгоритм шифрования - формальное описание шифра.
* Зашифрование - процесс преобразования открытого текста в шифртекст с
использованием ключа.
* Расшифрование - процесс восстановления открытого текста из шифртекста
с использованием ключа.
* Дешифрование - процесс восстановления открытого текста из шифртекста
без знания ключа.
* Ключ - сменный элемент шифра, позволяющий сделать сам алгоритм
шифрования открытым и использовать его многократно, меняя лишь ключ.


Q: Что такое "криптование"?

A: Словечко, используемое дилетантами вместо стандартного термина шифрование,
что выдает в них полных ламеров. Hастоящие специалисты-криптографы никогда
не пользуются этим словом, а также его производными "закриптование",
"закриптованные данные", "раскриптование", и т.д


Q: Что такое криптографический протокол?

A: Кpиптогpафический пpотокол - есть алгоpитм обмена инфоpмацией (не
обязательно секpетной!) между участниками, котоpые могут быть как
сопеpниками, так и соpатниками. В основе криптографических протоколов могут
лежать как симметричные криптоалгоритмы, так и алгоритмы с открытым ключом.
Криптографический протокол считается стойким, если в процессе его использования
легитимные участники процесса достигают своей цели, а злоумышленник - нет.


Q: Что такое "другие криптографические параметры"?

A: В это понятие входят узлы замены, синхропосылки и другие
сменные параметры, не являющиеся ключами.


Q: Зачем использовать DES, ГОСТ, Rijndael, другие опубликованные
алгоритмы? Раз их разрешили опубликовать, значит, в них есть
дыры.

A: Придумать алгоритм - это 5% работы. Остальные 95% - убедиться
(и убедить других), что его никто не сможет сломать (в обозримое
время). Это сложно. Это не под силу одному человеку.
Те алгоритмы, которые у всех на слуху, анализировали сотни
(тысячи) квалифицированных людей, в том числе и те, кто не
находится на государственной службе. Если _все_ они говорят,
что дыр нет - с вероятностью 0.9999 они правы.
С другой стороны, если хочешь изобрести свой собственный
алгоритм, сначала сломай пару-тройку чужих.

Q: Существует ли абсолютно стойкий шифр?

A: Клод Шеннон в своих трудах ввел понятие стойкости шифра и показал, что
существует шифр, обеспечивающий абсолютную секретность. Иными словами, знание
шифртекста не позволяет противнику улучшить оценку соответствующего открытого
текста. Им может быть, например, шифр Виженера при условии использования
бесконечно длинного ключевого слова и абсолютно случайному распределению
символов в этом слове. Очевидно, что практическая реализация такого шифра
(бесконечная случайная лента) невозможна (точнее, в большинстве случаев -
экономически невыгодна), поэтому обычно рассматривают практическую стойкость
шифра, численно измеряемую временем (либо числом элементарных операций),
необходимым на его взлом (с учетом текущего уровня развития техники). Кстати,
первым предложил использовать такой шифр Вернам, но обоснование дал именно
Шеннон.
Абсолютно стойкий шифр - это абстрактно-математическое понятие, с практикой не
имеющее почти ничего общего. Абсолютно стойкий шифр может оказаться абсолютно
_не_стойким против таких атак, как physical attack или social engineering
attack (см. ниже) - все зависит от реализации.

Q: Вот говорят иногда "симметричные шифры", "криптография с открытым ключем".
Поясните, что это за разделение?

A1: Симметричные шифры (криптосистемы) - это такие шифры, в которых для
зашифрования и расшифрования информации используется один и тот же ключ. В
несимметричных системах (системах с открытым ключом) для зашифрования
используется открытый (публичный) ключ, известный всем и каждому, а для
расшифрования - секретный (личный, закрытый) ключ, известный только
получателю.

A2: Симметричные шифры (криптосистемы) - это такие шифры, в которых
алгоритмы зашифрования и расшифрования могут быть _эффективно_ построены по
одному и тому же ключу.


Q: Что такое fingerprint? Зачем он нужен?

A: fingerprint является своеобразной сверткой, "контрольной
суммой", дайджестом открытого ключа. Обычно, эту роль
играет значение хеш-функции (см. ниже), вычисленное
от этого ключа.
Самое очевидное предназначение fingerprint - сверка правильности
передачи ключа. Сам ключ достаточно большой, чтобы диктовать его по
телефону. Однако, отправитель и получатель могут вычислить значение
fingerprint и сверять по телефону уже его.
Есть и другая ситуация, где fingerprint может пригодиться. Два
человека вдруг решили конфиденциально обменяться информацией.
Обменяться открытыми ключами при личной встрече они не могут. Нет и
третьего лица, способного выполнить роль удостоверяющего
(сертификационного) центра (см. ниже, в разделе про ЭЦП). Просто
обменяться открытыми ключами они не могут, т.к. опасаются, что
канал ненадежен и возможна атака man-in-the-middle.
Однако, я если оба оказались дальновидными, они давно вставили в
шаблон подписи fingerprint открытого ключа, который присутствует
во всех их сообщениях емейлом и в группы новостей уже несколько
лет. Теперь они могут обменяться ключами и по незащищенному каналу,
т.к. знают, что корреспондент может вычислить fingerprint и сверить
его с несколькими независимыми источниками (архивы dejanews/google,
например).
Правда, корреспондент может однозначно утверждать лишь то, что он
получил ключ "обитателя сети, именующего себя Вася".

Q: А что значит блочное/потоковое шифрование?

A: Блочная криптосистема (блочный шифр) разбивает открытый текст M на
последовательные блоки M1, M2, ..., Mn и применяет криптографическое
преобразование к каждому блоку. Поточная криптосистема (поточный шифр)
разбивает открытый текст M на буквы или биты m1, m2,..., mn и применяет
криптографическое преобразование к каждому знаку mi в соответствии со знаком
ключевого потока ki. Потоковое шифрование часто называют гаммированием.
Потоковый шифр может быть легко получен из блочного путем применения
специального режима (см. ниже).

Q: Что такое ECB, CBC, OFB, CFB?

A: Это режимы работы блочных шифров. ANSI X3.106 (1983)

ECB
Electronic Code Book Mode (режим электронной кодовой книги, режим простой
замены). В этом режиме все блоки текста шифруются независимо, на одном и том же
ключе, в соответствии с алгоритмом.

SM
Stream Mode (поточный режим, режим гаммирования). В этом режиме открытый текст
складывается по модулю 2 с гаммой шифра. Гамма получается следующим образом:
при помощи генератора формируется предварительная гамма (начальное заполнение
этого генератора - так называемая синхропосылка - не является секретом и
передается по каналу в открытом виде). Предварительная гамма подвергается
зашифрованию в режиме ECB, в результате чего и получается основная гамма, с
которой складывается открытый текст. Если последний блок неполный (его длина
меньше стандартного для данного алгоритма размера блока), берется только
необходимое количество бит гаммы.

CFB
Cipher Feedback Mode (гаммирование с обратной связью). В этом режиме открытый
текст также складывается по модулю 2 с гаммой шифра. Гамма получается следующим
образом: сначала шифруется (в режиме ECB) синхропосылка (она также передается
по каналу в открытом виде). Результат шифрования складывается по модулю 2 с
первым блоком открытого текста (получается первый блок шифртекста) и снова
подвергается зашифрованию. Полученный результат складывается со вторым блоком
открытого текста и т.д. Обработка последнего блока - аналогично предыдущему
режиму.

OFB
Output Feedback Mode (гаммирование с обратной связью по выходу). Как и в
предыдущем режиме, сначала зашифрованию подвергается синхропосылка. Результат
складывается по модулю 2 с первым блоком открытого текста - получается первый
блок шифртекста. Далее, результат шифрования с предыдущего шага (до сложения!)
шифруется еще раз и складывается со следующим блоком открытого текста. Таким
образом, гамма шифра получается путем многократного шифрования синхропосылки в
режиме ECB. Обработка последнего блока - аналогично предыдущему режиму.
Легко видеть, что приведённое определение OFB полностью совпадает с
определением SM. И это соотвествует криптографической практике в частности в
[1.2, p 203] просто нет SM, а OFB определяется так:
Ci = Pi ^ Si ; Si = Ek(Si-1) - шифрование
Pi = Ci ^ Si ; Si = Ek(Si-1) - расшифрование
В тоже время можно встретить другое определение OFB, на пример,
http://msdn.microsoft.com/library/psdk/crypto/aboutcrypto_9omd.htm.
Там же рекомендовано установить размер сдвига равный размеру блока
блочного шифра по причинам стойкости. Однако, такая установка приводит
к полному совпадению с режимом SM. В частности для DES, всегда применяют
ofb64bit.

CBC
Cipher Block Chaining Mode (режим сцепления блоков). В этом режиме очередной
блок открытого текста складывается по модулю 2 с предыдущим блоком шифртекста,
после чего подвергается зашифрованию в режиме ECB. Для самого первого блока
"предыдущим блоком шифртекста" является синхропосылка. Если последний блок
открытого текста неполный - он дополняется до необходимой длины.


Q: Что такое "гамма" и "гаммирование"?

A1:: Гамма - это псевдослучайная числовая последовательность, вырабатываемая по
заданному алгоритму и используемая для зашифрования открытых данных и
расшифрования зашифрованных. Гаммированием принято называть процесс наложения
по определенному закону гаммы шифра на открытые данные для их зашифрования.

A2:: Для получения гаммы могут быть использованы как вычислительные
алгоритмы (и тогда про гамма-последовательность говорят, что она
вычислена), либо природные (естественные, физические) датчики
случайных чисел (тогда гамма получается считыванием значений с этих
датчиков и иногда дополнительной обработкой). На сегодняшний день
существуют методики получения случайной гаммы как со стандартных
датчиков, например, положения курсора мыши, скорости реакции головок
жесткого диска на команды, температуры процессора, так и
отдельные специальные программно-аппаратные датчики (идущие под
аббревиатурой TRNG - True Random Number Generator).

Зачастую первые на самом деле недостаточно случайны по своей природе
(мышкой большинство пользователей двигает почти одинаково, скорость
реакции головок жесткого диска сильно зависит от температуры
окружающей среды и продолжительности работы компьютера, а температура
процессора дополнительно зависит от его марки), поэтому для совсем уж
серьезных криптографических задач, их использование следует
реализовывать с осторожностью.

Использовать же в качестве датчиков аппаратные TRNG в персональном
компьютере обычно слишком накладно, хотя преценденты на основе
специализированных плат уже были. Впрочем, есть вероятность, что
производители материнских плат и других устройств снабдят свои изделия
собственными TRNG с дружественным интерфейсом. Intel, например, уже
имела честь выпустить материнскую плату со встроенным датчиком TRNG,
основанном правда всего на двух сопряженных резисторах.



Q: А у поточного шифрования какие бывают режимы?

A: Шифрование последовательности с обратной связью (заворачивает
криптотекст на вход ГСП (генератор случайной последовательности, роль которого
играет алгоритм шифрования) шифрование ключей с обратной связью. См. режим CFB
для блочных шифров.

Q: Что такое архитектура "Квадрат" (SQUARE)?

A1: Это архитектура построения блочных шифров с секретным ключом, она имеет
следующие особенности:
- она является вариантом общих SP-сетей (за один раунд шифруемый блок
преобразуется целиком), построенным по схеме KASLT (Key Addition -
Substitution - Linear Transformation);
- архитектура байт-ориентирована, шифруемый блок представляется в виде
матрицы байтов, замена также выполняется побайтно, на каждом раунде может
использоваться один, максимум-два узла замен, больше втиснуть сложнее;
- линейное преобразование (третий шаг раунда) двухфазное, состоит из
перестановки байтов в матрице и независимого линейного комбинирования
отдельных столбцов (или строк) матрицы. Смысл этой двухфазности - диффузия
изменений в двух направлениях - по строкам и по столбцам;
В данной архитектуре замена приводит к диффузии изменений внутри байта,
линейное преобразование - в двух измерениях матрицы, в итоге получаем, что
любое изменение в данных диффундирует на весь блок всего за 2 раунда.
В архитектуре "квадрат" выполнены шифры AES(Rijndael), Square ("квадрат",
его название дало имя всей архитектуре), Crypton (один из кандидатов на
AES). Второе место в конкурсе AES занял другой KASLT-шифр, Serpent.
Справедливости ради, надо отметить, что первым алгоритмом с подобной
архитектурой, был алгоритм 3WAY и уже позже появился Square. Дело
идет к тому, что KASLT-сети и, в частности, архитектура SQUARE, в ближайшем
будущем станут безраздельно доминировать.

Часть 2

Q: А какие есть симметричные алгоритмы шифрования?

A: Да их немеряно! Приведем наиболее известные:

Шифр Цезаря
Великий император, с целью сокрытия содержания написанного заменял каждую
букву на третью следующую за ней по счету букву алфавита. Цезарь применял
сдвиг на три буквы; в общем случае это может быть любое число, меньшее, чем
длина алфавита. Это число и является ключом в данном шифре:
А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Ь Ъ Э Ю Я
Г Д Е Е Ж 3 И И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Ь Ъ Э Ю Я А Б В
КРИПТОГРАФИЯ -> НУЛТХСЕУГЧЛВ

Шифр Виженера
Является модификацией шифра Цезаря, в котором величина сдвига является
переменной и зависит от ключевого слова. Например, если в качестве ключевого
слова использовать слово "ТАЙНА", то это будет означать, что первую букву
сообщения необходимо сдвинуть на 20 (порядковый номер буквы "Т"), вторую -
на 1 (порядковый номер буквы "А"), третью - на 11, четвертую - на 15,
пятую - на 1, шестую - снова на 20 (ключевое слово начинаем использовать
с начала) и т.д. Таким образом, ключевое слово "накладывается" на защищаемый
текст.

Шифр Вернама
Алгоритм был изобретен в 1917 г. сотрудником компании AT&T по фамилии
Vernam и называется одноразовым блокнотом (one-time pad).
В этом алгоритме ключ представляет собой последовательность битов не менее
длинную, чем шифруемое сообщение m.
Результат шифрования получается в результате побитового сложения по модулю 2
сообщения и ключа.
Расшифровка состоит в побитовом сложении шифрограммы с ключом.
Отметим, что данный алгоритм утрачивает свою надежность, если два сообщения
оказываются зашифрованы одним и тем же ключом. В этом случае путем побитового
сложения шифрограмм можно исключить биты ключа, а получившаяся побитовая
сумма осмысленных сообщений поддается методам статистического анализа.
Ключ должен быть надежным образом передан адресату, что само по себе не
проще, чем передача сообщения. Единственная выгода метода состоит в том,
что ключ можно передать заранее, а сообщение - по открытому каналу и тогда,
когда это будет нужно.

AES.
Победителем конкурса AES стал алгоритм Rijndael (см. ниже).

BlowFish.
Блочный алгоpитм, сбалансиpованная сеть Файстеля, 16 итеpаций пpостого
кpиптогpафического пpеобpазования. Длина ключа 40 - 448
бит, отсюда сложная фаза инициализации до опеpаций шифpования.
Разработан в 1993 году.
Автор: Брюс Шнаейр (Bruce Schneier)
Параметры:
- pазмер блока 64 бита
- pазмер ключа 32-448 бит
- число раундов 16

CAST.
В некотором смысле аналог DES.
Авторы: C.M. Adams и S.E.Tavares.
Параметры:
CAST-128
- размер блока 64 бита
- размер ключа 128 бит
- число раундов 16
CAST-256
- размер блока 128 бит
- размер ключа 256 бит

DEAL.
Базируется на DES (DEA). Увеличение длины блока уменьшает вероятность удачной
криптоатаки методом сравнения криптограмм, уровень стойкости шифрования
сопоставим с уровнем triple-DES.
Автор: Lars R. Knudsen.
Параметры:
- размер блока 128 бит
- размер ключа 128/192/256 бит
- число раундов: 6 (DEAL-128, DEAL-192); 8 (DEAL-256)

DES.
Алгоритм с эффективной длиной ключа в 56-bits (хотя часто говорят о 8 байтах,
но старший бит в байте не используется).
Автор: National Institute of Standards and Technology (NIST).
Параметры:
- размер блока 64 бита
- размер ключа 56 бит
- число раундов 16

IDEA (International Decryption-Encryption Algorithm)
Время/место разработки 1990-1991 годы, Цюрих, Швейцария.
Архитектура Общая сбалансированная шифрующая SP-сеть, инвариант раунда -
побитовая сумма по модулю 2 старшей и младшей половин блока.
Авторы: Xuejia Lai, James Massey.
Параметры:
- pазмер блока 64 бита
- pазмер ключа 128 бит
- число раундов 8

Lucifer.
первый (опубликованный в открытой печати) блочный алгоритм. Предтеча DES
Автор: Horst Feisstel, Walter Tuchman (IBM)
тип - сеть Файстеля
Параметры:
- размер блока 128 bit
- размер ключа 128 bit
- число раундов 16 .
В каждом используется подключ в 72 бита, порождаемый из главного
ключа. Поскольку имеет бОльший размер ключа и блока по отношению к DES,
поэтому более устойчив к дифф. криптоанализу


NewDES.
Создан в 1985 как творческая переработка DES. Это самостоятельный алгоритм, а
не вариант DES. NewDES несколько проще, чем DES, поскольку у него нет начальной
и, понятно, конечной перестановки. Операции производятся над байтами, а не
битами как в DES. Brute-force атака на NewDES требует 2^119 операций, против
2^111 для TripleDES.
Автор: Robert Scott.
Параметры:
- размер блока 64 бита
- размер ключа 120 бит
- число раундов 17

RC2.
Блочный алгоpитм шифpования. Длина ключа пpеменная - от 8 до 1024 бит.
Разpабатывался под 16-ти битное слово. Реализyет
16 pаyндов "пеpемешивающих" (mixing) и 2 pаyнда "pазмазывающих" (mashing)
пpеобpазований. Описан в RFC2268. Разpаботал Ron Rivest (RSA Laboratories).
Режимы: ECB, CBC, CFB 8bit, OFB, OFB counter 8bit
ECB, CBC, OFB: шифруют данные блоками по 64 бита (8 байт)
CFB, OFBC: шифруют данные блоками по 8 бит (1 байту)
Автор: RSA Data Security (Ron Rivest)
/RC - Ron's Code/
Параметры:
- размер блока 64 бита
- размер ключа до 1024 бит
- число раундов 16

RC4.
Описывать RC4 просто. Алгоритм работает в режиме OFB: поток ключей не
зависит от открытого текста.
Используется S-блок размером 8*8: S0, S1, . . . , S255. Элементы
представляют собой перестановку чисел от 0 до
255, а перестановка является функцией ключа переменной длины. В алгоритме
применяются два счетчика, i и j,
с нулевыми начальными значениями.
Для генерации случайного байта выполняется следующее:
i = (i + 1) mod 256
j = (j + Si) mod 256
поменять местами Si и Sj
t = (Si + Sj) mod 256
K = St
Байт K используется в операции XOR с открытым текстом для получения
шифротекста или в операции XOR с шифротекстом для получения открытого
текста. Шифрование выполняется примерно в 10 раз быстрее, чем DES.
Также несложна и инициализация S-блока. Сначала заполним его линейно:
S0 = 0, S1 = 1, . . . , S255 = 255. Затем заполним ключом другой 256-байтовый
массив, при необходимости для заполнения всего массива повторяя ключ: K0, K1,
. . . , K255. Установим значение индекса j равным 0. Затем:
for i = 0 to 255:
j = (j + Si + Ki) mod 256
поменять местами Si и Sj
Автор: RSA Data Security (Ron Rivest)
/RC - Ron's Code/

RC5
Блочный шифр с переменными параметрами.
Режимы: ECB, CBC, CFB 8bit, OFB, OFB counter 8bit
Шифр RC5 "словоориентированный"; все простейшие вычислительные операции
производятся над w-битными словами. RC5 блочный шифр с размерностью входного и
выходного блоков 2 слова. Номинальный выбор для w - 32 бита, при котором
входной и выходной блоки RC5 имеют размер 64 бита. В принципе, RC5 допускает
любое значение w>0, однако для простоты принимают допустимые значения w - 16,
32 и 64 бита.
Число раундов r является вторым параметром RC5. Выбор большего числа раундов
увеличивает степень защиты. Возможные значения для r: 0,1,...,255.
Заметим также, что RC5 имеет расширенную ключевую таблицу S, получаемую из
предоставляемого пользователем секретного ключа. Размер t таблицы S также
зависит от числа раундов r и составляет t=2(r+1) слов. Выбор большего числа
раундов, таким образом, увеличивает требования к памяти.
Для записи параметров RC5 применяют следующую нотацию: RC5-w/r/b. Например,
запись RC5-32/16/10 означает, что используются 32-битные слова, 16 раундов и
10-байтовый (80-битный) секретный ключ, а также расширенная ключевая таблица
размером 2(16+1)=34 слов. "Номинальным" набором параметров считается
RC5-32/12/16 (размер слова 32 бита, число раундов - 12 и 16-байтовый ключ).
ECB, CBC, OFB: шифруют данные блоками по 64 бита (8 байт)
CFB, OFBC: шифруют данные блоками по 8 бит (1 байту)
Автор: RSA Data Security (Ron Rivest)
/RC - Ron's Code/
Параметры:
- размер блока 32/64/128 бит
- размер ключа до 2048 бит

RC6
Блочный шифр
Автор: RSA Data Security (Ron Rivest)
/RC - Ron's Code/
Параметры:
- размер блока 128 бит
- размер ключа до 2048 бит
- число раундов 16-24


Rijndael.
Является нетрадиционным блочным шифром, поскольку выполнен в архитектуре
SQUARE. Алгоритм представляет каждый блок кодируемых данных в виде двумерного
массива байт размером 4х4, 4х6 или 4х8 в зависимости от установленной длины
блока. Далее на соответствующих этапах преобразования производятся либо над
независимыми столбцами, либо над независимыми строками, либо вообще над
отдельными байтами в таблице.
Автор: Joan Daemen and Vincent Rijmen
Параметры:
- размер блока 128, 192, 256 бит, в качестве AES допускается
использование шифра с размером блока 128 бит;
- размер ключа 128, 192, 256 бит
- число раундов 10, 12, 14. Зависит от размера блока (Nb) и ключа (Nk),
заданных в битах, по следующей формуле: Nr=max(Nb,Nk)/32+6;

SAFER.
Автор: J. L. Massey
Параметры:
- размер блока 64 бит
- размер ключа 64/128
- число раундов, r:
SAFER K64 6 (5<r<11)
SAFER SK64 8 (5<r<11)
SAFER K128 10 (9<r<13)
SAFER SK128 10 (9<r<13)

SAFER+ ("Secure And Fast Encryption Routine")
один из кандидатов на AES
Автор: Cylink Corporation
Параметры:
- размер блока 16 байт
- размер ключа 128/192/256
- число раундов 8/12/16

Skipjack.
Старательно пропихиваемый госдепом США симметричный алгоритм шифрования с
разделяемым ключом и бэкдором. Используется в чипах Clipper и Capstone, которые
хотят засунуть до Интернет унитазов включительно .
Интересен тем, что ломается 31 раунд (по аналогии с DES запас сделан
минимальный). Еще интересен тем, что по аналогии с ГОСТ ключевое расширение
получается простым повторением ключа.
Режимы: ECB, CBC, CFB 8bit, OFB, OFB counter 8bit
ECB, CBC, OFB: шифруют данные блоками по 64 бита (8 байт)
CFB, OFBC: шифруют данные блоками по 8 бит (1 байту)
Автор: NSA
Параметры:
- размер блока 64 бита
- размер ключа 80 бит
- число раундов 32


TEA (Tiny Encryption Algorithm).
Авторы: David Wheeler, Roger M. Needham
Параметры алгоритма :
- размер блока - 64 бита.
- размер ключа - 128 бит.

TripleDES.
Алгоритм зашифрования состоит в следующем: исходный текст зашифровывается DESом
с ключом K1, результат расшифровывается DESом с ключом K2, а этот результат
опять зашифровывается DESом с ключом K1. Итого длина ключа составляет 112 бит.
Иногда применяют 3 разных ключа, но стойкость от этого не меняется.
DES - не группа, то есть композиция двух операций шифрования с разными
ключами не является в общем случае DES-шифрованием с некоторым третьим
ключом [2.5]. Следовательно, можно пытаться увеличить пространство ключей
за счет многократного применения DES.
Двойной DES, c=К1(К2(m)), не обеспечивает увеличение в 2 в 56 степени
раз объема перебора, необходимого для определения ключа, поскольку при
атаке с известным открытым текстом можно подбирать параллельно исходный
текст m и шифрограмму c, накапливать в хэш-таблице значения К2(m),К1^-1(c)
и искать совпадения между ними.
Тройной DES рекомендуется специалистами в качестве замены DES:
В режиме ECB c=К1(К2(К3(m))) или c=К1(К2^-1(К3(m)))
В других режимах c=К1(К2^-1(К1(m)))
Применение функции расшифрования на втором шаге объясняется желанием достичь
совместимости с однократным алгоритмом DES в случае, если все ключи равны.
Тройное шифрование с двумя ключами все равно сводится к одинарному при
использовании атаки с выбором открытого текста [2.6].
Автор: NIST ANSI X9.17, "American National Standard, Financial Institution
Key Management (Wholesale)", 1985.
ISO/IEC 8732:1987, "Banking - Key Management (Wholesale)".
Параметры:
- размер ключа 112 бит
- остальное - см. DES

ГОСТ 28147-89
Российский федеральный стандарт шифрования. Фактически, описывает несколько
алгоритмов (режимы работы ГОСТ). Кроме ключа ему необходима еще одна таблица
(таблица замен, 128 ячеек 4-битовых чисел) для формирования узлов замены. ГОСТ
ее не определяет, посему она может рассматриваться как долговременный ключевой
элемент. Определены следующие режимы работы: режим простой замены (ECB), режим
гаммирования (SM) и режим гаммирования с обратной связью (OFB). Несколько
особняком стоит режим выработки имитовставки. В принципе, у него такое же
назначение как у хэш-функции, только ее значение еще зависит от секретного
ключа. Из полученного в результате 64 битного значения выбирается l битов, где
l<=32. Минимальный размер данных для имитозащиты - 2 64-битных блока.
Автор: КГБ СССР
Параметры:
- размер блока 64 бита
- размер ключа 256 бит
- число раундов 32 (16 - для имитовставки)

Q: Каковы должны быть правила построения таблиц (узлов) замены в ГОСТе?

A: Основная задача -- сделать S-box'ы (так называют эти таблицы) устойчивыми к
дифференциальному и линейному криптоанализу. Можно попробовать
сформулировать критерии, глядя на те критерии, которые Тучман использовал в
начале 70-х для DES. /* потребовалось около 10 месяцев */
Итак, можно сформулировать следующие правила:
1. Hи один выходной бит не должен сколь-нибудь хорошо приближаться линейной
функцией от входных бит.
2. Если два входных значения отличаются на один бит, выходные значения
должны отличаться не менее чем на 2 бита.
3. Если два входных значения отличаются в двух соседних битах (как минимум
центральных), то выходные значения должны отличаться не менее чем на 2 бита.
4. Для любого значения XOR между входными значениями, следует минимизировать
количество пар, чьи XOR на входе и на выходе равны этому значению (это
весьма хитроумное требование вытекает из попытки защититься от
дифференциального
криптоанализа).
5. S-box'ы не должны быть похожи друг на друга. Hапример, количество входных
значений, дающих одно и тоже значение на выходе из разных S-box'ов, должно
быть минимально.
6. Узлы замены в идеале должны учитывать особенности входного текста: если
используются только алфавитно-цифровой диапазон ASCII-таблицы, то он должен
отображаться (после замены) на все множество используемого алфавита, скрывая
статистические свойства открытого текста.

Часть 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)

Часть 4
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.

Q: Можно немного поподробнее о Cobra и что это такое

A: Расшифpовывается как Комплекс Обеспечения Безопасности РАбот.

Участники пpоекта
0. Автоpы
Молдовян, Чижов.

1. Разpаботчики
1.1 Гос. HИИ ИМИСС
Госудаpственный научно-исследовательский институт моделиpования
и интеллектуализации сложных систем пpи СПбГЭТУ ( ну ЛЭТИ это ).
1.2 HТЦ "СПЕКТР" гос. пpедпpиятия научно-пpоизводственный комплекс
"Кpасная заpя"

2. Оpганизации экспеpты
ВИКА им. А.Ф.Можайского ( уполномочена ГосТехКомиссией)
ПHИЭИ ( уполномочен ФАПСИ )
Центp защиты инфоpмации пpи СПбГЭТУ ( уполномочен ФАПСИ )
Институт кибеpнетики им. В.М.Глушкова ( независимый экспеpт)
Центp АтомЗащитаИнфоpм
в/ч 51105
центp РосГеоинфоpм
ПФ HТЦ ФАПСИ

Сеpтифициpована ГТК по 4-му классу защищенности.
Сеpтификат N20 от 22 июня 1995г. Действителен до 31 декабpя 1998г.

Кобpа - пpогpаммный комплекс для установки на pазличные ПЭВМ типа
IBM-PC ( настольные, поpтативные, пеpеносные ), pаботающий под
упpавлением DOS 3.3 и стаpше. ( ПОД WIN-95 Кобpа не pаботает. Она по
жизни 16-ти pазpядная. 32-х pазpядный доступ к диску пpиведет к
pазpушению инфоpмации) Кобpа обеспечивает шиpокие возможности по
упpавлению полномочиями пользователей - полный доступ, только чтение,
не доступа, супеpзащита (пpозpачное шифpование) для логических
устpойств(A..Z).Санкциониpует� �я доступ к COM и LPT ( на у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амм и данных. Ведется, также, и учет pаботы пользователей на
компьютеpе. Кобpа автоматически восстанавливает pабочую эталонную
сpеду комьютеpа. Тpебует менее 10К ОЗУ и менее 500К на диске. Скоpость
пpеобpазования инфоpмации до 5Мб/с для PC-486. Функциониpует совместно
с WINDOWS 3.X, dBASE, FoxPro, Clipper etc.
Заключения экспеpтов:
ВИКИ - кpиптостойкость пpевосходит DES
Глушатник - "алгоpитм обладает хоpошими кpиптогpафическими свойствами
со стойкостью ~10^22 относительно многох методов кpиптоанализа"
Пенза - Лучший метод восстановления ключа тpебует для своей
pеализации 10^10 байт шифpотекста и наличия такого же объема
откpытого текста, тpудоемкость опеpации составит в этом случае 10^12
опеpации. Hеобходимый объем памяти для восстановления ключа - 10^10
байт. Для полноценного анализа кpиптостойкости тpебуются pаботы
pудоемкостью 100..120 чел.мес. и пpодолжительностью 1.5-2 года.

Тепеpь, как она устpоена. В основу защиты PC от HСД в Кобpе положено
кpиптогpафическое пpеобpазование инфоpмации. Алгоpитм шифpования это
многопpоходное гаммиpование и пеpестановки байт с обpатной связью по
pезультатам шифpования. Шифpовать можно как винчестеp или дискеты на
уpовне 13-го пpеpывания ( посектоpное шифpование), так и каталоги и
файлы. Однако, это пpеобpазование включается опционально.
Обеспечивает доступ к данным и кpиптование единый модуль -
кpиптодpайвеp. Этот дpайвеp загpужается пеpвым в config.sys. Самая
пpостая защита в кобpе - это паpольный вход в PC. Администpатоp
готовит список заpегестpиpованных юзеpов и назначает master-паpоль
(ключ) и юзеpские дополнительные паpоли. Далее юзеpа могут изменять
свои паpоли, как им вдумается. Master-паpоль знает только
администpатоp. Защита пpи этом основана на модификации MBR, что
элементаpно сносится. Для пpотиводействия такой атаке в Кобpе может
быть включено пpозpачное шифpование винчестеpа. Для этого
pекомендуется задавать master-паpоль длиной не менее 12-ти байт. Тогда
Кобpа может осуществлять 3-х или 4-х п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азделения доступа юзеpов к
инфоpмации, пpи этом, да и пpи минимальной защите тоже, администpатоp
может заводить специальные зашифpованные логические диски pазмеpом не
более 32Мб типа как в DiskReet. Только паpоль вводится один pаз пpи
стаpте системы и далее в pаботе не запpашивается. Пpи шифpовании диска
возможно устpоить два ваpианта загpузки компьютеpа - с ключевой дискеты
и без оной. В последнем случае ключ шифpования пеpеносится на
винчестеp, что снижает защищенность компьютеpа. То есть достаточно
понять, как из дополнительных паpолей осуществляется доступ к
master-паpолю и, соответственно, генеpация ключа, так мы и в системе с,
возможно, любыми полномочиями. Почему с _возможно_? Пpи инсталляции
Кобpы у нее есть только один юзеp - Сobra, наделенный максимальными
полномочиями. Администpатоp от имени Cobra может создать любого юзеpа,
дать ему максимальные полномочия и пpибить юзеpа Cobra.
Далее, в пpоцессе pаботы можно также назначить каталоги, в котоpых
будут пpозpачно шифpоваться файлы ( утилита Lock.exe ). В состав Кобpы
входит, так же и специальная утилита Safe.exe котоpая позволяет
зашифpовать специально указанные файлы.
Пpоцесс загpузки Кобpы выглядит следующим обpазом. Hасколько мы смогли
pазобpаться в MBR'е блокиpуется клавиатуpа (int 9), так что клавиша
Shift не сpаботает. Хотя нет, совpал немного, а именно - Кобpа имеет
pазные ступени защиты. Так на самых легких - пока не установлена защита
от загpузки с дискеты Кобpа больше делает вид, что она есть, и клавиша
Shift, естественно, не отключена и для ее отключения нужно записать в
Config.sys ключ switches. Как только включается защита от загpузки с
дискеты, так здесь уже начинается модификация MBR и, соответственно,
пеpехват клавиатуpы. А далее можно либо сотвоpить кучу логических
шифpованных дpайвов или зашифpовать винчестеp или часть его. Hа
зашифpованном винчестеpе можно также сотвоpить секpетные логические
дpайвы. Hу а в этих дpайвах ничто не мешает завести зашифpованные
каталоги. То есть, иметь тpи ступени кpиптогpафических пpеобpазований
пpи доступе к файлам.
Тепеpь веpнемся к загpузке. Из Config.sys загpужается кpиптодpайвеp -
ядpо системы защиты. Пеpвой пpогpаммой в autoexec.bat вызывается
пpогpамма Cobra.exe где pазбиpается кто лезет и настpаиваются
полномочия доступа. Пеpед запуском оболочки ( Hоpтона, Волкова или
Win) вызывается пpогpамма Cobratst.exe, котоpая пpовеpяет, что же
нагpузилось в память и пpовеpяет каpту памяти с записанной
администpатоpом. Так же эта пpогpамма тестиpует взятые под контpоль
файлы и опpеделяет их целостность следующим обpазом: вычисляется CRC
начала и конца файла и сpавнивается с запомненным. Если есть
pасхождение, то начало и конец восстанавливается из базы данных. Также
пpовеpяется BIOS и его pасшиpения, и пp.
Кстати, пpи инсталляции Кобpы Кpиптодpайвеp не тупо пеpеписывается на
диск, а специальным обpазом готовится. Для этого используется, похоже
HD Serial Number. Так что укpасть и запустить кобpу на дpугом
компьютеpе для ее исследования вpяд ли удастся.
Далее, такие жизненно важные файлы как Config.Sys etc доступны юзеpам
только на чтение, так что изменить назначенную сpеду они не смогут.
Для особо пpодвинутых юзеpов есть смиpительная pубашка - оболочка типа
Hоpтона. Она настpаивается администpатоpом для кажого юзеpа и в ней
юзеpам может быть недоступна комадная стpока и доступны только те
задачи, котоpые им pазpешено запускать. Все что не pазpешено явно - в
кобpе запpещено. Самое интеpесное в этой оболочке то, что по вpеменном
выходе в DOS из дpугих пpогpамм юзеpа попадают не в command.com, а в
эту же оболочку.
Пpо юзеpов. Кобpа имеет четыpе категоpии юзеpов - супеpпользователь,
ему pазpешено делать на машине все - установить, сконфигуpиpовать и
откатить Кобpу, завести юзеpов, назначать им паpоли и пpава доступа
etc, администpатоp, ему pазpешено почти все, кpоме как откатить кобpу,
пpогpаммист, котоpый может только изменить свой дополнительный паpоль и
гость, котоpый ничего с кобpой делать не может.

Q: Я слышал о DEAL – 128-и битный блочный шифр можно о нём немного поподробнее?

A: DEAL, основанн на DES (DEA). Размер блока DEAL – 128 бит, размер ключа может быть 128, 192 или 256 бит. Предлагаемый шифр имеет несколько преимуществ перед другими схемами: благодаря большему размеру блоков, проблема «атаки по подобранному шифр-тексту» становится менее существенной, а скорость шифрования соответствует скорости тройного DES.Предполагают, что наиболее реалистичная (или наименее нереалистичная) атака на любую версию DEAL’а – это исчерпывающий поиск ключей. Мы предложили ANSI (институту) включить DEAL в стандарт ANSI X9.52. К тому же мы предлагаем DEAL, как кандидат на стандарт NIST AES.
DEAL (Data Encryption Algorithm with Larger blocks – Алгоритм Шифрования Данных с Укрупненными блоками) является 128-и битным блочным шифром с размерами ключа 128, 192 и 256 бит, что далее здесь будет обозначаться DEAL-128, DEAL-192 и DEAL-256 соответственно. Все версии могут использоваться в любом из четырех стандартных режимах DES’a [16].
подведем итог особенностям DEAL.
• DEAL имеет размер блока 128 бит и размер ключа 128, 192 или 256 бит (действующий размер, соответственно,– 112, 168 или 224 бита).
• Атака по подобранному шифр-тексту требует порядка 264 блоков шифр-текста.
• Нет известных, вероятных атак.
• DEAL с шестью циклами имеет скорость, аналогичную скорости тройного DES.
• DEAL может использоваться в стандартных режимах работы.
• DEAL может быть реализован на имеющемся аппаратном и программном обеспечение DES.
• Нет очевидно слабых ключей и устранено свойство дополнительности.
Наконец, позволим себе заметить, что ввиду довольно сложного расписания ключей, DEAL не практично использовать в случайных функциях.

часть5
Q: А спецификация на Е2 - 128-битный блочный шифр можно о нём немного поподробнее?

A: 1. Описание алгоритма

1.1 Соглашения и обозначения

В данном документе используются следующие обозначения:

1. Обозначим Z - множество всех целых чисел.
2. Обозначим буквами A, B, C множества. Положим А*В:={(a, b)|a?A, b?B} - Декартово произведение множеств А и В. Элемент произведения А*В*С определим следующим образом: (а, b, c)=(a, (b, c))=((a, b), c). Более того, положим , для
3. У элемента ( , ,…, ) из множества будем считать самым левым элементом и - самым правым.
4. Пусть K -поле и n>1. Обозначим через K - n-мерное векторное пространство над полем K . Для двух векторов ( , ,…, ) и ( , ,…, ) из K справедливы следующие соотношения:
= ( + , + ,…, + )
( , ,…, )
5. Если K = ={0,1}, то операция ИСКЛЮЧАЮЩЕЕ-ИЛИ, , рассматривается как аддитивная операция. Операция называется просто XOR-операцией.
6. Вектор-строка ( , ,…, ) соответствует вектор-столбцу .
7. Пусть B -это векторное пространство 8-битовых элементов, т.е. B= .
8. Пусть W -это векторное пространство 32-битовых элементов, т.е. W=B .
9. Пусть H -это векторное пространство 32-битовых элементов, т.е. H=B .
10. Элемент поля определяется как многочлен p(X) из , чья степень меньше 8, при этом изоморфно и r(X)=X +X +X +X+1, являющийся неприводимым многочленом в . Таким образом, полное множество представителей есть .
11. Элемент p(X) из множества представленный как эквивалентен B.
12. Элемент B, где , сопоставим элементу
Z Z / Z,
где ( ) соответствует в канонической форме записи, т.е. -старший бит (самый левый) и - младший (самый левый) бит.

13. Элемент из W, где B, сопоставим элементу
Z Z / Z ,
где ( ) соответствует . Соответствие между и будет установлено в главе 12.


1.2. Схема алгоритма

Пусть:
М – это открытый текст ( H ),
K – секретный ключ ( H , H , H ), и
C – шифртекст ( H ).

Алгоритм шифрования E2 определяется как:
C = E (M, K)
M = D (C, K),
Где E – шифрующая функция в E2, описанная в пункте 1.3, и D – функция расшифрования в E2, описанная далее в пункте 1.4. Справедливы следующие уравнения:
M = D (E (M, K), K)
C = E (D (C, K), K)


Шифрование

Часть алгоритма, в которой осуществляется перемешивание информации, состоит из начальной перестановки IT, 12-и петель Фестеля с F-функцией, и конечной перестановки FT. До начала процесса шифрования согласно ключевому расписанию из секретного ключа K вырабатываются 16 подключей { } ( B ).
Первоначально вычисляется

где M – открытый текст. Далее, разбивается на две части и равной длины, т.е. , где H и H. Затем последовательно для от 1 до 12 вычисляются


Обозначим теперь через конкатенацию и , т.е. .
Наконец, получаем итоговый шифртекст С как
.
Тестовые данные для алгоритма E2

Все данные приведены в шестнадцатеричном виде.

a) Длина ключа равна 128 бит
K = 00000000000000000000000000000000
M = 00000000000000000000000000000000
C = c2883490b9d9d5e5a03f216edb815fff

b) Длина ключа равна 192 бит
K = 000000000000000000000000000000000000000000000000
M = 00000000000000000000000000000000
C = 882f80269d3c146d6ebb9addc4715b4c

c) Длина ключа равна 256 бита
K = 00000000000000000000000000000000000000000000000000 00000000000000
M = 00000000000000000000000000000000
C = 5002cb8cd878f26fbab9f52e6c96501e

Q: можно повторить перечень наиболее распространенных асимметричных криптоалгоритмов?

A: Прежде всего назовем наиболее распространенные (наиболее часто обсуждаемые) алгоритмы асимметричной криптографии:
1. Схема Диффи-Хеллмана в мультипликативной группе конечного поля (статья 1976 года) и в группе точек эллиптической кривой над конечным полем Нила Коблица[9].
2. Схема открытого шифрования RSA и построенные на ее основе схемы подписи и аутентификации[10].
3. Схемы типа Фиата-Шамира [11].
4. Семейство схем подписи типа Эль-Гамаля [12].
5. Схемы на основе задачи "о рюкзаке" [13].
6. Теоретико-кодовые конструкции МакЭлиса [14].
Названные схемы достаточно известны, поэтому формально описывать их не будем (тем более что их описанию посвящены отдельные публикации). Со всемиперечисленными схемами связан ряд теоретических проблем. Ниже приведем некоторые из них.

Теоретико-сложностные проблемы:

1. Проблема эквивалентности задачи Диффи-Хеллмана и задачи логарифмирования в соответствующей группе.
Практически очевидно, что задача Диффи-Хеллмана не сложнее задачи логарифмирования (если мы умеем логарифмировать, то система открытогораспределения ключей Диффи-Хеллмана нестойкая). Хотя большинство исследователей склоняется к мнению, что эти задачи эквивалентны, вопрос о том, верно лиобратное, на сегодняшний день открыт. Эквивалентность, при некоторых дополнительных условиях, доказали Маурэр [15] и ден Бур [16]. Из отечественныхисследовател ей сильный результат по данной проблематике получен М. А. Черепневым, которому удалось построить субэкспоненциальный алгоритм сведениязадачи дискретного логарифмирования в простом конечном поле к задаче Диффи-Хеллмана. Наиболее же близки к решению проблемы швейцарские ученые [17].
2. Проблема эквивалентности задачи компрометации схемы Эль-Гамаля и задачи логарифмирования.
3. Проблема эквивалентности задачи вскрытия системы RSA и задачи факторизации целых чисел (под секретным ключом понимается экспонента e).
Задача определения секретного ключа здесь эквивалентна факторизации, тем не менее, вопрос об эквивалентности бесключевого чтения и факторизации открыт. Вто же время известны частные случаи, когда задача решается легко (случай, так называемых, "слабых ключей").
4. Проблема построения стойких (доказуемо) криптографических протоколов в предположении о существовании тех или иных криптографических примитивов.
Основная масса публикаций по теоретико-сложностным проблемам криптографии относится именно к этой тематике.

Q: можно более подробно о алгоритме DSA?

A: . Общее описание алгоритма
Алгоритм DSA основывается на двух вычислительный задачах, связанных с дискретным логарифмированием. Одной задачей является сложность вычисления логарифма в Z*p, другая задача - сложность логарифмирования в циклической подгруппе порядка q. Алгоритм является частным случаем цифровой подписи Эль-Гамаля (ElGamal) и был представлен как стандарт FIPS PUB 186-94 (DSS).
1.2 Генерация ключей DSA


1. Выбирается простое число q, такое, что 2159<q<2160.
2. Выбирается t, т.ч. 0<=t<=8 и выбирается простое число p так, что 2511+64t<p<2512+64t, причем q должно делить (p-1).
3. Находится производящий элемент a для циклической группы Z*p порядка q (для этого выбирается g ОZ*p и вычисляется a =g(p-1)/q mod p, Если a ?= 1, то пр. элемент найден).
4. Выбирается случайное целое a, т. ч. 1<=a<=q-1.
5. Вычисляется y=a a mod p.

Секретным ключом является a, открытым ключом - (p,q,a ,y)
1.2 Подпись сообщения
Имеется сообщение m. Подпись сообщения секретным ключом выглядит следующим образом.

1. Выбирается случайное секретное число k, 0<k<q (разовый секретный ключ).
2. Вычисляется r=(a k mod p) mod q.
3. Вычисляется k-1 mod q.
4. Вычисляется s=k-1{h(m)+ar} mod q, где h(m)-значение хэш-функции от сообщения m.

Подписью для сообщения m является пара (r,s).
1.3 Проверка подписи
Имеется открытый ключ (p,q,a ,y), сообщение m, подпись сообщения (r,s).

1. Проверить, что 0<r<q и 0<s<q. Если это не так, отвергнуть подпись.
2. Вычислить w=s-1 mod q и h(m).
3. Вычислить u1=wh(m) mod q и u2=rw mod q.
4. Вычислить v=(a u1yu2 mod p) mod q.
5. Подпись верна, только если v=r.

1.4 Док-во корректности подписи
Если (r,s) является корректной подписью для сообщения m, тогда должно выполняться h(m)=-ar+ks (mod q). Умножим обе части равенства на w и получим, что wh(m)+arw=k (mod q). А это есть u1+au2=k (mod q). Т.е. получаем, что (a u1a au2 mod p) mod q=(a k mod p) mod q. Или (au1yu2 mod p) mod q=(a k mod p) mod q. Это есть v=r, что и требовалось доказать.
2. Практические рекомендации
В данном алгоритме предлагается использовать простое p размером от 512 до 1024 бит. Размер в 512 бит обеспечивает минимальную защищенность. Рекомендуемый размер - не менее 768 бит. Согласно FIPS 186, алгоритм не допускает простых чисел больше 1024 бит.

Совершенно не обязательно существование уникальных p и q для каждого пользователя алгоритма. FIPS допускает использование p,q и a в качестве системных параметров для группы пользователей. Однако для повышения безопасности работы лучше использовать уникальные значения.

Часть6
Q: можно более подробно о алгоритме RSA.

A: Криптосистема RSA.



Эта асимметричная криптосистема в настоящее время является широко распространенной в мире и называется так по первым буквам в именах создателей R. Rivest, A. Shamir, L. Adleman.

1. Описание криптосистемы

1.1 Генерация ключей

Для работы каждый абонент должен выработать секретный и открытый ключи.

1. Вырабатываются p,q - большие простые числа.
2. Вычисляется произведение n=pq.
3. Выбирается число e - такое, что 1<e<j(n) и НОД (e, j(n))=1, где j(n)=(p-1)(q-1) - функция Эйлера от n.
4. Из уравнения ed=1(mod j(n)) посредством расширенного алгоритма Евклида находится число d.

Полученные числа e,n - открытый ключ пользователя, а d - секретный ключ.

1.2 Шифрование

Абонент B зашифровывает и посылает A сообщение m, которое тот затем расшифровывает.

1. Зашифрование. B должен сделать:

* Получить открытый ключ А : e,n
* Представить сообщение в виде числа m из интервала [0,n-1]
* Вычислить c=me mod n
* Послать шифртекст с абоненту A

2. Расшифрование. Для получения текста A должен сделать:

* Используя секретный ключ d вычислить m=cd mod n.

Т-ма 1.2.1: если ed=1(mod j(n)), (e, j(n))=1, (m, n)=1, тогда (me)d mod n=m.

Док-во: поскольку ed=1(mod j(n)), значит ed=1+kj(n), где k - некое число. Из т-мы Эйлера следует, что

m j(n) =1(mod n) при (m, n)=1.

Значит (me)d(mod n)=(m1+kj(n))(mod n)=m(mj(n))k(mod n)=m.

Оценим вероятность того, что сообщение будет не взаимнопросто с n, т.е. что (m, n)+1. Число всех чисел - n, число чисел, взаимно простых с n - j(n). Значит вероятность попадания m в совокупность чисел, не взаимопростых с n P{(m, n)+1}=(n-j(n))/n = (pq-(p-1)(q-1))/pq = (p+q-1)/pq < 1/p +1/q.

2. Стойкость RSA

Рассмотрим стойкость криптосистемы и возможные атаки.

Стойкость RSA основывается на проблеме факторизации больших простых чисел. Действительно, если злоумышленнику удастся разложить n на делители p и q, то для него не составит труда вычислить j(n), а затем в соответствии с п.4 "Генерации ключей" определить секретный ключ пользователя. Однако нахождение секретного ключа RSA не эквивалентно проблеме факторизации. Это означает, что T(RSA)<=T(факторизации), где T(RSA) - трудоемкость определения секретного ключа RSA, а T(факторизации) - трудоемкость факторизации числа n. Т.е. могут быть найдены эффективные алгоритмы определения секретного ключа RSA, причем в то же время проблема факторизации не будет разрешена.

2.1 Малая экспонента e.

Рассмотрим ситуацию, когда у нас имеется малая экспонента e (e=3,5,7 и т.д.). Пусть e=3. Допустим, что некто А желает послать одно и то же сообщение трем другим абонентам, имеющим открытые ключи (3,n1), (3,n2),(3,n3). А шифрует сообщение и получает ci=m3(mod ni) для i=1,2,3. Противник перехватывает все 3 сообщения и составляет систему:

x=c1 (mod n1);

x=c2 (mod n2);

x=c3 (mod n3).

Поскольку 0<=x<n1n2n3 и m3 <n1n2n3, то по китайской теореме об остатках злоумышленник может найти x=m3 и вычислив кубический корень из x найдет m.

Т.е. получаем, что нельзя использовать малые экспоненты при отправке большого числа одинаковых сообщений. Или же следует использовать добавки ("salting") в сообщение, в качестве которых могут выступать добалвенные в конец сообщения случайные вектора или же время отправки.

При использовании малых экспонет также возникает проблема с маленькими сообщениями, т.е с такими, для которых m<n1/e, поскольку в этом случае m может быть получено из шифртекста c=me mod n путем вычисления корня e-ой степени из C. Однако использование добавок в сообщение помогает избежать этой проблемы.

2.2. Атака перебором возможных открытых текстов.

Если сообщение не велико, злоумышленник может попытаться подобрать открытый текст путем перебора всех возможных вариантов и шифрования их на открытом ключе абонента e до тех пор, пока не будет получен перехваченный шифртекст c. Такую атаку также возможно предотвратить при помощи добавок в сообщение.

2.3. Использование общих модулей.

Схема RSA несостоятельна при использовании общих модулей. Допустим есть 2 абонета A и В с открытыми ключами (e1,n) и (e2,n). Центр (общий сервер или циркуляр) желает послать обоим абонетам одинаковые сообщения. Он получает me1=c1(mod n) и me2=c2(mod n) и посылает c1 и c2 А и В соответственно. Противник перехватывает эти сообщения. Затем, если (e1,e2)=1, по расширенному алгоритму Евклида можно найти такие k1и k2, для которых e1k1+e2k2=1. И, соответственно, me1k1me2k2=m. Т.е. найдя такие k1и k2 (это он может сделать, ведь открытые ключи ему известны) противник вычислит (c1)k1(c2)k2 = m. c

Если сообщение не велико, злоумышленник может попытаться подобрать открытый текст путем



2.4. Циклическая атака (безключевое чтение RSA).

Атака безключевым чтением описана в разделе Криптоанализ:Атаки на RSA. Однако помимо описанной атаки есть так назывемая "обобщенная циклическая атака". Суть ее заключается в следующем: найти наименьшее целое u, такое, чтобы f=НОД(ceu-c,n)>1.

Если ceu=c (mod p) и ceu+ с (mod q), то f=p.

Если ceu+ c (mod p) и ceu=с (mod q), то f=q.

В обоих этих случаях злоумышленник получает либо p, либо q и факторизует n.

Если же ceu= c (mod p) и ceu=с (mod q), тогда f=n и ceu= c (mod n). Однако этот случай гораздо менее вероятен, чем первые два. Поэтому обобщенную циклическую атаку можно считать одним из методов факторизации n.

2.5. Мультипликативные свойства.

Система RSA обладает мультипликативными совствми. Пусть m1 и m2 - 2 различных открытых текста, а c1 и с2 - соответствующие им шифртексты. Заметим, что

(m1m2)e=m1e m2e=c1c2 (mod n)

Другими словами, шифртекст открытого текста m=m1m2 есть c=c1c2 (mod n). Это свойство, называемое также гомоморфным свойством RSA, позволет осуществить атаку по выбранному шифртексту (см. Криптоанализ:Атаки на RSA). Его нужно учитывать при совмещении схем шифрования на основе RSA и цифровой подписи RSA.

3. Практические рекомендации

В настоящее время рекомендуется выбирать n размером как минимум 768 бит, а для долговременного хранения информации 1024 или даже 2048 бит.

3.1 Выбор простых чисел

Поскольку простые числа должны выбираться таким образом, чтобы факторизовать их произведение было вычислительно невозможно, рекомендуется брать их очень большими и одинаковой длины. Так, для n длины 1024 бита p и q должны быть длиной 512 бит.

Разность чисел p и q (p-q) также не должна быть маленькой, поскольку в этом случае p @ q и, следовательно, p @ Цn. Таким образом, разложение n может быть найдено простым делением на все числа порядка Цn.

Числа p и q должны быть также "устойчивыми" простыми числами.

Определение 3.1.1. Число p является устойчивым (strong), если оно удовлетворяет 3 условиям:

1. p-1 имеет большой простой делитель, обозначим его как r (т.е. p=1(mod r));
2. p+1 имеет большой простой делитель, обозначим как s (т.е. p=s-1(mod s));
3. r-1 имеет большой простой делитель, обозначим его как t (т.е. r=1(mod t)).

Условие 1 не позволит успешно факторизовать n (p-1) методом Полларда, который позволяет быстро разложитьчисло n на множители, если его делитель p имеет небольшие (скажем, меньше миллиона) простые делители. . Условие 2 позволит избежать p+1 метода Ульямса, позволяющего разложить n при условии, что p+1 имеет неболшие делители. Условие 3 позволит избежать метода безключевого чтения RSA (циклической атаки).

Если p выбирается случайно и имеет довольно большой размер, то, как правило, p-1 и p+1 будут иметьбольшие простые делители. Однако выбор устойчивых простых чисел не защищает систему от атаки алгоритмом факторизации на основе эллиптических кривых.

Получить устойчивые простые числа можно следующим способом. Генерируем большие простые числа s и t. Затем получаем такое число r, что r-1 делится на t (для этого рассматриваем нечетные числа вида kt+1, где k - последовательные натуральные числа, и проверяем их на простоту, пока не найдем простое). Затем вычисляя p=((sr-1-rs-1) mod rs)+xrs, где x - некоторое целое число и проверяя p на простоту, находим устойчивое простое число p.

3.2 Выбор экспоненты e и ускорение работы

Если число e выбирается случайным образом, то одним из способов ускорения вичислений (т.е. уменьшение числа возведений в степень) является следующий алгоритм быстрого возведения (на примере):

a25=(a2a)2)2)2a.

Таким образом, вместо 25 умножений выполняется всего 6 (т.е. 4 возведения в квадрат и 2 умножения на a). Формально алгоритм выглядит следующим образом:

Вход: aОZn и целое 0<=k<n, чье двоичное представление - k=еti=0ki2i .

Выход: ak mod n.

1. b=1. If k=0 then return b.

2. A=a

3. If k0=1 then b=a

4. For i=1 to t do

4.1 A=A2 mod n.

4.2 If ki=1 then b=A*b mod n.

5. Return b

На практике как правило используется e=3, в этом случае необходимо, чтобы чтобы ни p-1, ни q-1 не делились на 3. При таком открытом ключе операция зашифрования получется очень быстрой и требует одно возведение в квадрат и одно модульное умножение (или 2 модульных умножения - в зависимости от реализации). Другим часто используемым значением является e=216+1=65537. Это число имеет одну единицу в двоичной записи и требует при использовании описанного алгоритма 16 возведений в квадрат и одно модульное умножение. Такая экспонента имеет преимущество по сравнению с e=3, поскольку в этом случае атака, описанная ранее, не осуществиться, т.к. очень мала вероятность, что одно и тоже сообщение будет послано 216+1 абонентам.

Часть7
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. - N1. -
С. 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.


################################################## ###########################
Данный FaQ собран мной из множества книг и документаций по криптографии и програмированию , но основной материал был взят с:

1): RU.CRYPT FAQ /Часто задаваемые вопросы конференции RU.CRYPT/

$Version$ 1.0.9
$Date$ 20.04 YEKT 2003

2) : Баричев - Криптография без секретов.

И самый главный вопрос:
Q: Я хочу побольше информации о криптографии

A: Читай книжки и юзай поиск.