Главная База знаний "Allbest" Программирование, компьютеры и кибернетика Основы криптографии

Основы криптографии

История, предпосылки развития, необходимость применения криптографии в жизни общества. Описание протоколов, цифровых подписей, алгоритмов, ключей. Криптоанализ, формальный анализ протоколов проверки подлинности и обмена ключами. Практическая криптография.

Рубрика	Программирование, компьютеры и кибернетика
Вид	дипломная работа
Язык	русский
Дата добавления	23.12.2011
Размер файла	767,2 K

посмотреть текст работы

скачать работу можно здесь

полная информация о работе

весь список подобных работ

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Страница:

32-битовый выход подстановки с помощью S-блоков, перетасовываются в соответствии с Р-блоком. Эта пeрестановка перемещает каждый входной бит в другую позицию, ни один бит не используется дважды, и ни один бит не игнорируется. Этот процесс называется прямой перестановкой или просто перестановкой. Позиции, в которые перемещаются биты, показаны в нижеслеюующей таблице. Например, бит 21 перемещается в позицию 4, а бит 4 - в позицию 31.

Перестановка с помощью Р-блоков

16	7	20	21	29	12	28		1	15	23	26	5	18	31	10
2	8	24	14	32	27	3	9	19	13	30	6	22	11	4	25

Наконец, результат перестановки с помощью Р-блока объединяется посредством XOR с левой половиной первоначального 64-битового блока. Затем левая и правая половины меняются местами, и начинается следующий этап.

Заключительная перестановка

Заключительная перестановка является обратной по отношению к начальной перестановке. Обратите внимание, что левая и правая половины не меняются местами после последнего этапа DES, вместо этого объединенный блок R₁₆L₁₆ используется как вход заключительной перестановки. В этом нет ничего осoбенного, перестановка половинок с последующим циклическим сдвигом привела бы к точно такому же результату. Это сделано для того, чтобы алгоритм можно было использовать как для шифрования, так и для дешифрирования.

Заключительная перестановка

40,	8,	48,	16,	56,	24,	64,	32,	39,	7,	47,	15,	55,	23,	63,	31,
38,	6,	46,	14,	54,	22,	62,	30,	37,	5,	45,	13,	53,	21,	61,	29,
36,	4,	44,	12,	52,	20,	60,	28,	35,	3,	43,	11,	51,	19,	59,	27,
34,	2	42,	10,	50,	18,	58,	26,	33,	1,	41,	9,	49,	17,	57,	25

Дешифрирование DES

После всех подстановок, перестановок, операций XOR и циклических сдвигов можно подумать, что алгoритм дешифрирования, резко отличаясь от алгоритма шифрования, точно также запутан. Напротив, различные компоненты DES были подобраны так, чтобы выполнялось очень полезное свойство: для шифрования и дешифрирования используется один и тот же алгоритм.

DES позволяет использовать для шифрования или дешифрирования блока одну и ту же функцию. Единственное отличие состоит в том, что ключи должны использоваться в обратном порядке. To есть, если на этапах шифрования использовались ключи K₁, К₂, К₃, ..., K₁₆, то ключами дешифрирования будут K₁₆, K_l₅, K₁₄, ..., K₁. Алгоритм, который создает ключ для каждого этапа, также цикличен. Ключ сдвигается направо, а число позиций сдвига равно 0, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1.

Безопасность DES

Люди давно интересуются безопасностью DES. Было много рассуждений о длине ключа, количестве итераций и схеме S-блоков. S-блоки были наиболее таинственными - какие-то константы, без видимого объяcнения для чего и зачем они нужны. Хотя IBM утверждала, что работа алгоритма была результатом 17 человеко-лет интенсивного криптоанализа, некоторые люди опасались, что АНБ вставило в алгоритм лазейку, которая позволит агентству легко дешифрировать перехваченные cooбщения.

Комитет по разведке Сената США чрезвычайно тщательно расследовал этот вопрос в 1978 году. Результаты работы комитета были засекречены, но в открытых итогах этого расследования с АНБ были сняты все обвинeния в неуместном вмешательстве в проектирование алгоритма . "Было сказано, что АНБ убедило IBM в достаточности более короткого ключа, косвенно помогло разработать структуры S-блоков и подтвердило, что в окончательном варианте DES, с учетом всех знаний АНБ, отсутствовали статистические или математические бреши". Однако, так как правительство не опубликовало подробности расследования, многих людей убeдить не удалось.

С другой стороны, Копперсмит писал: "Агентство национальной безопасности также помoгало IBM техническими советами." А Конхейм (Konheim) утверждал: "Мы послали S-блоки в Вашингтон. Они вернулись полностью переработанными. Мы проверили их, и они прошли нашу проверку." На этот факт и ccылаются как на доказательство, что АНБ вставило лазейку в DES.

Тогда почему они изменили S-блоки? Может быть, чтобы гарантировать, что лазейка не будет встроена в DES самой IBM. У АНБ не было причин доверять исследователям IBM, и оно могло решить, что не до конца исполнит свой долг, если не обеспечит отсутствие лазеек в DES. Задание S-блоков и могло быть одним из спoсобов гарантировать это.

Совсем недавно новые результаты криптоанализа прояснили этот вопрос, который в течение многих лет был предметом спекуляций.

Слабые ключи

Из-за того, что первоначальный ключ изменяется при получении подключа для каждого этапа алгоритма, определенные первоначальные ключи являются слабыми. Вспомните, первоначальное значение расщепляется на две половины, каждая из которых сдвигается независимо. Если все биты каждой половины равны 0 или 1, то для всех этапов алгоритма используется один и тот же ключ. Это может произойти, если ключ состоит из одних 1, из одних 0, или если одна половина ключа состоит из одних 1, а другая - из одних 0. Кроме того, два слабых ключа обладают другими свойствами, снижающими их безопасность .

Слабые ключи DES

	Значение слабого ключа			Действительный ключ
0101	0101	0101	0101	0000000 0000000
1F1F	1F1F	ОЕОЕ	ОЕОЕ	0000000 FFFFFFF
ЕОЕО	ЕОЕО	F1F1	F1F1	FFFFFFF 0000000
FEFE	FEFE	FEFE	FEFE	FFFFFFF FFFFFFF

Кроме того, некоторые пары ключей при шифровании переводят открытый текст в идентичный шифротекст. Иными словами, один из ключей пары может расшифровать сообщения, зашифрованные другим ключом пары. Это происходит из-за метода, используемого DES для генерации подключей - вместо 16 различных подключей эти ключи генерируют только два различных подключа. В алгоритме каждый из этих подключей используется восемь раз. Эти ключи, называемые полуслабыми ключами, в шестнадцатеричном виде приведены ниже.

Полуслабые пары ключей DES

01FE	01FE	01FE	01FE	и	FE01	FE01	FE01	FE01
1FEO	1FEO	OEF1	OEF1	и	E01F	E01F	F10E	F10E
01ЕО	01ЕО	01F1	01F1	и	Е001	Е001	F101	F101
1FFE	IEEE	OEFE	OEFE	и	FE1F	FE1F	FEOE	FEOE
01 IF	011F	010Е	010E	и	1F01	1F01	ОЕ01	ОЕ01
EOFE	EOFE	FIFE	FIFE	и	FEEO	FEEO	FEE1	FEE1

Ряд ключей генерирует только четыре подключа, каждый из которых четыре раза используется в алгоритме.

Эти возможно слабые ключи перечислены таблице.

Возможно слабые ключи DES

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

ОЕ

ЕО

Прежде, чем порицать DES слабые ключи, обратите внимание на то, что эти 64 ключа - это крошечная часть полного набора из 72057594037927936 возможных ключей. Если вы выбираете ключ случайно, вероятность выбрать один из слабых ключей пренебрежимо мала. Если вы настоящий параноик, можете всегда проверять "на слабость" сгенерированный ключ. Некоторые думают, что нечего и беспокоиться на этот счет. Другие утверждают, что проверка очень легка, почему бы ее и не выполнить.

Дальнейший анализ слабых и полуслабых ключей приведен в. Других слабых ключей в процессе иcследований найдено не было.

Теперь, пожалуй можно приступить к описанию другого довольно популярного стандарта шифрованиея-ГОСТ. Вы конечно можите спросить- а почему не к AES? Да всё довольно просто- дело в том что буквально на днях, АНБ, в связи с войной в Ираке пересмотрело недавно ими же одобренный стандарт AES- и пришло к выводу что алгоритм недостаточно хорош…. Было решено найти новый, более устойчивый алгоритм.. Единственный алгоритм который удовлетворил требованиям оказался…. ГОСТ 28147-89! Так что в обозримом будущем именно ГОСТ станет новым национальным стандартом шифрования США. Называться он скорее всего будет по другому- но это уже другая история…

Я решил что описывать AES не стоит- не выдержал главного- испытание временем

Единственное что я замечу- обозначения отличаются от предыдущих- ибо ГОСТ описан не русском, неплохо, и менять что-либо опасно- всё-таки это фактически выдержки из официального документа.

Логика построения шифра и структура ключевой информации ГОСТа

Если внимательно изучить оригинал ГОСТа 28147-89, можно заметить, что в нем содержится описание алгоритмов нескольких уровней. На самом верхнем находятся практические алгоритмы, предназначенные для шифрования массивов данных и выработки для них имитовставки. Все они опираются на три алгоритма низшего уровня, называемые в тексте ГОСТа циклами. Эти фундаментальные алгоритмы упоминаются в как базовые циклы, чтобы отличать их от всех прочих циклов. Они имеют следующие названия и обозначения, последние приведены в скобках и смысл их будет объяснен позже:

цикл зашифрования (32-З);

цикл расшифрования (32-Р);

цикл выработки имитовставки (16-З).

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

Таким образом, чтобы разобраться в ГОСТе, надо понять три следующие вещи:

а) что такое основной шаг криптопреобразования;

б) как из основных шагов складываются базовые циклы;

в) как из трех базовых циклов складываются все практические алгоритмы ГОСТа.

В ГОСТе ключевая информация состоит из двух структур данных. Помимо собственно ключа, необходимого для всех шифров, она содержит еще и таблицу замен. Ниже приведены основные характеристики ключевых структур ГОСТа.

Ключ является массивом из восьми 32-битных элементов кода, далее в настоящей работе он обозначается символом К:. В ГОСТе элементы ключа используются как 32-разрядные целые числа без знака: . Таким образом, размер ключа составляет 32·8=256 бит или 32 байта.

Таблица замен является матрицей 816, содержащей 4-битовые элементы, которые можно представить в виде целых чисел от 0 до 15. Строки таблицы замен называются узлами замен, они должны содержать различные значения, то есть каждый узел замен должен содержать 16 различных чисел от 0 до 15 в произвольном порядке. В настоящей статье таблица замен обозначается символом H: . Таким образом, общий объем таблицы замен равен: 8 узлов 16 элементов/узел 4 бита/элемент = 512 бит или 64 байта.

Основной шаг криптопреобразования

Основной шаг криптопреобразования по своей сути является оператором, определяющим преобразование 64-битового блока данных. Дополнительным параметром этого оператора является 32-битовый блок, в качестве которого используется какой-либо элемент ключа. Схема алгоритма основного шага приведена на рисунке. Ниже даны пояснения к алгоритму основного шага:

Определяет исходные данные для основного шага криптопреобразования:

N - преобразуемый 64-битовый блок данных, в ходе выполнения шага его младшая

(N₁) и старшая (N₂) части обрабатываются как отдельные 32-битовые целые числа без знака.

Таким образом, можно записать N=(N₁,N₂).X-32-битовый элемент ключа;

Сложение с ключом. Младшая половина преобразуемого блока складывается по модулю 232 с используемым на шаге элементом ключа, результат передается на следующий шаг;

Поблочная замена. 32-битовое значение, полученное на предыдущем шаге, интерпретируется как массив из восьми 4-битовых блоков кода: S=(S₀,S₁,S₂,S₃,S₄,S₅,S₆,S₇).

Далее значение каждого из восьми блоков заменяется на новое, которое выбирается по таблице замен следующим образом: значение блока Si заменяется на Si-тый по порядку элемент (нумерация с нуля) i-того узла замен (т.е. i-той строки таблицы замен, нумерация также с нуля). Другими словами, в качестве замены для значения блока выбирается элемент из таблицы замен с номером строки, равным номеру заменяемого блока, и номером столбца, равным значению заменяемого блока как 4-битового целого неотрицательного числа. Теперь становится понятным размер таблицы замен: число строк в ней равно числу 4-битных элементов в 32-битном блоке данных, то есть восьми, а число столбцов равно числу различных значений 4-битного блока данных, равному как известно 24, шестнадцати.

Схема основного шага криптопреобразования алгоритма ГОСТ 28147.

Циклический сдвиг на 11 бит влево. Результат предыдущего шага сдвигается циклически на 11 бит в сторону старших разрядов и передается на следующий шаг. На схеме алгоритма символом ?11 обозначена функция циклического сдвига своего аргумента на 11 бит в сторону старших разрядов.

Побитовое сложение: значение, полученное на шаге 3, побитно складывается по модулю 2 со старшей половиной преобразуемого блока.

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

Полученное значение преобразуемого блока возвращается как результат выполнения алгоритма основного шага криптопреобразования.

Базовые циклы криптографических преобразований

Базовые циклы построены из основных шагов криптографического преобразования, рассмотренного в предыдущем разделе. В процессе выполнения основного шага используется только один элемент ключа, в то время как ключ ГОСТ содержит восемь таких элементов. Следовательно, чтобы ключ был использован полностью, каждый из базовых циклов должен многократно выполнять основной шаг с различными его элементами. Вместе с тем кажется вполне естественным, что в каждом базовом цикле все элементы ключа должны быть использованы одинаковое число раз, по соображениям стойкости шифра это число должно быть больше одного.

Все сделанные выше предположения, опирающиеся просто на здравый смысл, оказались верными. Базовые циклы заключаются в многократном выполнении основного шага с использованием разных элементов ключа и отличаются друг от друга только числом повторения шага и порядком использования ключевых элементов. Ниже приведен этот порядок для различных циклов.

Цикл зашифрования 32-З:

K0,K1,K2,K3,K4,K5,K6,K7,K0,K1,K2,K3,K4,K5,K6,K7,K0,K1,K2,K3,K4,K5,K6,K7,K7,K6,K5,K4,K3,K2,K1,K0.

Цикл расшифрования 32-Р: K0,K1,K2,K3,K4,K5,K6,K7,K7,K6,K5,K4,K3,K2,K1,K0,K7,K6,K5,K4,K3,K2,K1,K0,K7,K6,K5,K4,K3,K2,K1,K0.

Цикл выработки имитовставки 16-З:

K0,K1,K2,K3,K4,K5,K6,K7,K0,K1,K2,K3,K4,K5,K6,K7.

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

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

Ц32-Р(Ц32-З(T))=T,

где T - произвольный 64-битный блок данных, ЦX(T) - результат выполнения цикла X над блоком данных T.

Для выполнения этого условия для алгоритмов, подобных ГОСТу, необходимо и достаточно, чтобы порядок использования ключевых элементов соответствующими циклами был взаимно обратным. В справедливости записанного условия для рассматриваемого случая легко убедиться, сравнив приведенные выше последовательности для циклов 32-З e 32-Р. Из сказанного вытекает одно интересное следствие: свойство цикла быть обратным другому циклу является взаимным, то есть цикл 32-З является обратным по отношению к циклу 32-Р (В пришципе так работает почти любой блочный алгоритм- в DES мы уже это видели) . Другими словами, зашифрование блока данных теоретически может быть выполнено с помощью цикла расшифрования, в этом случае расшифрование блока данных должно быть выполнено циклом зашифрования. Из двух взаимно обратных циклов любой может быть использован для зашифрования, тогда второй должен быть использован для расшифрования данных, однако стандарт закрепляет роли за циклами и не предоставляет пользователю права выбора в этом вопросе.

Схема цикла зашифрования 32-З. Схема цикла расшифрования 32-Р.

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

Схема цикла выработки имитовставки 16-З.

Схемы базовых циклов приведены на рисунках 2а-в. Каждый из них принимает в качестве аргумента и возвращает в качестве результата 64-битный блок данных, обозначенный на схемах N. Символ Шaa(N,X) обозначает выполнение основного шага криптопреобразования для блока N с использованием ключевого элемента X. Между циклами шифрования и вычисления имитовставки есть еще одно отличие, не упомянутое выше: в конце базовых циклов шифрования старшая и младшая часть блока результата меняются местами, это необходимо для их взаимной обратимости.

Основные режимы шифрования

ГОСТ предусматривает три следующих режима шифрования данных:

простая замена,

гаммирование,

гаммирование с обратной связью,

и один дополнительный режим выработки имитовставки.

В любом из этих режимов данные обрабатываются блоками по 64 бита, на которые разбивается массив, подвергаемый криптографическому преобразованию, именно поэтому ГОСТ относится к блочным шифрам. Однако в двух режимах гаммирования есть возможность обработки неполного блока данных размером меньше 8 байт, что существенно при шифровании массивов данных с произвольным размером, который может быть не кратным 8 байтам.

Прежде чем перейти к рассмотрению конкретных алгоритмов криптографических преобразований, необходимо пояснить обозначения, используемые на схемах в следующих разделах:

Tо,Tш - массивы соответственно открытых и зашифрованных данных;

, - i-тые по порядку 64-битные блоки соответственно открытых и зашифрованных данных:, , ??i?n, последний блок может быть неполным: ;

n - число 64-битных блоков в массиве данных;

ЦX - функция преобразования 64-битного блока данных по алгоритму базового цикла «X»;

Опишем основные режимы шифрования:

Простая замена

Зашифрование в данном режиме заключается в применении цикла 32-З к блокам открытых данных, расшифрование - цикла 32-Р к блокам зашифрованных данных. Это наиболее простой из режимов, 64-битовые блоки данных обрабатываются в нем независимо друг от друга. Схемы алгоритмов зашифрования и расшифрования в режиме простой замены приведены на рисунках 3а и б соответственно, они тривиальны и не нуждаются в комментариях.

Размер массива открытых или зашифрованных данных, подвергающийся соответственно зашифрованию или расшифрованию, должен быть кратен 64 битам: |Tо|=|Tш|=64·n, после выполнения операции размер полученного массива данных не изменяется.

Алгоритм зашифрования данных в режиме простой замены.

Алгоритм расшифрования данных в режиме простой замены.

Режим шифрования простой заменой имеет следующие особенности:

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

Если длина шифруемого массива данных не кратна 8 байтам или 64 битам, возникает проблема, чем и как дополнять последний неполный блок данных массива до полных 64 бит. Эта задача не так проста, как кажется на первый взгляд, поскольку очевидные решения типа «дополнить неполный блок нулевыми битами» или, более обще, «дополнить неполный блок фиксированной комбинацией нулевых и единичных битов» могут при определенных условиях дать в руки криптоаналитика возможность методами перебора определить содержимое этого самого неполного блока, и этот факт означает снижение стойкости шифра. Кроме того, длина шифротекста при этом изменится, увеличившись до ближайшего целого, кратного 64 битам, что часто бывает нежелательным.

На первый взгляд, перечисленные выше особенности делают практически невозможным использование режима простой замены, ведь он может применяться только для шифрования массивов данных с размером кратным 64 битам, не содержащим повторяющихся 64-битных блоков. Кажется, что для любых реальных данных гарантировать выполнение указанных условий невозможно. Это почти так, но есть одно очень важное исключение: вспомните, что размер ключа составляет 32 байта, а размер таблицы замен - 64 байта. Кроме того, наличие повторяющихся 8-байтовых блоков в ключе или таблице замен будет говорить об их весьма плохом качестве, поэтому в реальных ключевых элементах такого повторения быть не может. Таким образом мы выяснили, что режим простой замены вполне подходит для шифрования ключевой информации, тем более, что прочие режимы для этой цели менее удобны, поскольку требуют наличия дополнительного синхронизирующего элемента данных - синхропосылки. Догадка верна, ГОСТ предписывает использовать режим простой замены исключительно для шифрования ключевых данных.

Гаммирование

Как же можно избавиться от недостатков режима простой замены? Для этого необходимо сделать возможным шифрование блоков с размером менее 64 бит и обеспечить зависимость блока шифротекста от его номера, иными словами, рандомизировать процесс шифрования. В ГОСТе это достигается двумя различными способами в двух режимах шифрования, предусматривающих гаммирование. Гаммирование - это наложение (снятие) на открытые (зашифрованные) данные криптографической гаммы, то есть последовательности элементов данных, вырабатываемых с помощью некоторого криптографического алгоритма, для получения зашифрованных (открытых) данных. Для наложения гаммы при зашифровании и ее снятия при расшифровании должны использоваться взаимно обратные бинарные операции, например, сложение и вычитание по модулю 264 для 64-битных блоков данных. В ГОСТе для этой цели используется операция побитного сложения по модулю 2, поскольку она является обратной самой себе и к тому же наиболее просто реализуется. Гаммирование решает обе упомянутые проблемы; во первых, все элементы гаммы различны для реальных шифруемых массивов и, следовательно, результат зашифрования даже двух одинаковых блоков в одном массиве данных будет различным. Во вторых, хотя элементы гаммы и вырабатываются одинаковыми порциями в 64 бита, использоваться может и часть такого блока с размером, равным размеру шифруемого блока.

Теперь перейдем непосредственно к описанию режима гаммирования. Гамма для этого режима получается следующим образом: с помощью некоторого алгоритмического Рекуррентного Генератора Последовательности Чисел (РГПЧ) вырабатываются 64-битные блоки данных, которые далее подвергаются преобразованию по циклу 32-З, то есть зашифрованию в режиме простой замены, в результате получаются блоки гаммы. Благодаря тому, что наложение и снятие гаммы осуществляется при помощи одной и той же операции побитового исключающего или, алгоритмы зашифрования и расшифрования в режиме гаммирования идентичны.

РГПЧ, используемый для выработки гаммы, является рекуррентной функцией: ?_i₊₁=f(?_i), где ?_i - элементы рекуррентной последовательности, f - функция преобразования. Следовательно, неизбежно возникает вопрос о его инициализации, то есть об элементе ?₀. В действительности, этот элемент данных является параметром алгоритма для режимов гаммирования, на схемах он обозначен как S, и называется в криптографии синхропосылкой, а в нашем ГОСТе - начальным заполнением одного из регистров шифрователя. По определенным соображениям разработчики ГОСТа решили использовать для инициализации РГПЧ не непосредственно синхропосылку, а результат ее преобразования по циклу 32-З: ?₀=Ц_32-З(S). Последовательность элементов, вырабатываемых РГПЧ, целиком зависит от его начального заполнения, то есть элементы этой последовательности являются функцией своего номера и начального заполнения РГПЧ: ?_i=f_i(?₀), где f_i(X)=f(f_i-1(X)), f₀(X)=X. С учетом преобразования по алгоритму простой замены добавляется еще и зависимость от ключа:

Г_i=Ц_32-З(?_i)=Ц_32-З(f_i(?₀))=Ц_32-З(f_i(Ц_32-З(S)))=?_i(S,K),

где Гi - i-тый элемент гаммы, K - ключ.

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

Схема алгоритма шифрования в режиме гаммирования приведена на рисунке ниже и изложены пояснения к схеме:

Алгоритм зашифрования (расшифрования) данных в режиме гаммирования.

1) Определяет исходные данные для основного шага криптопреобразования:

Tо(ш) - массив открытых (зашифрованных) данных произвольного размера, подвергаемый процедуре зашифрования (расшифрования), по ходу процедуры массив подвергается преобразованию порциями по 64 бита;

S - синхропосылка, 64-битный элемент данных, необходимый для инициализации генератора гаммы;

2) Начальное преобразование синхропосылки, выполняемое для ее «рандомизации», то есть для устранения статистических закономерностей, присутствующих в ней, результат используется как начальное заполнение РГПЧ;

3) Один шаг работы РГПЧ, реализующий его рекуррентный алгоритм. В ходе данного шага старшая (S1) и младшая (S0) части последовательности данных вырабатываются независимо друг от друга;

4) Гаммирование. Очередной 64-битный элемент, выработанный РГПЧ, подвергается процедуре зашифрования по циклу 32-З, результат используется как элемент гаммы для зашифрования (расшифрования) очередного блока открытых (зашифрованных) данных того же размера.

5) Результат работы алгоритма - зашифрованный (расшифрованный) массив данных.

Ниже перечислены особенности гаммирования как режима шифрования.

Одинаковые блоки в открытом массиве данных дадут при зашифровании различные блоки шифротекста, что позволит скрыть факт их идентичности.

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

Синхропосылка, использованная при зашифровании, каким-то образом должна быть передана для использования при расшифровании. Это может быть достигнуто следующими путями:

хранить или передавать синхропосылку вместе с зашифрованным массивом данных, что приведет к увеличению размера массива данных при зашифровании на размер синхропосылки, то есть на 8 байт;

использовать предопределенное значение синхропосылки или вырабатывать ее синхронно источником и приемником по определенному закону, в этом случае изменение размера передаваемого или хранимого массива данных отсутствует;

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

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

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

где обозначает инвертированное по отношению к t значение бита ().

Выработка имитовставки к массиву данных

Выше мы обсудили влияние искажения шифрованных данных на соответствующие открытые данные. Мы установили, что при расшифровании в режиме простой замены соответствующий блок открытых данных оказывается искаженным непредсказуемым образом, а при расшифровании блока в режиме гаммирования изменения предсказуемы. В режиме гаммирования с обратной связью искаженными оказываются два блока, один предсказуемым, а другой непредсказуемым образом. Значит ли это, что с точки зрения защиты от навязывания ложных данных режим гаммирования является плохим, а режимы простой замены и гаммирования с обратной связью хорошими? Ни в коем случае. При анализе данной ситуации необходимо учесть то, что непредсказуемые изменения в расшифрованном блоке данных могут быть обнаружены только в случае избыточности этих самых данных, причем чем больше степень избыточности, тем вероятнее обнаружение искажения. Очень большая избыточность имеет место, например, для текстов на естественных и искусственных языках, в этом случае факт искажения обнаруживается практически неизбежно. Однако в других случаях, например, при искажении сжатых звуковых образов, мы получим просто другой образ, который сможет воспринять наше ухо. Искажение в этом случае останется необнаруженным, если, конечно, нет априорной информации о характере звука. Вывод здесь такой: поскольку способность некоторых режимов шифрования обнаруживать искажения, внесенные в шифрованные данные, существенным образом опирается на наличие и степень избыточности шифруемых данных, эта способность не является имманентным свойством соответствующих режимов и не может рассматриваться как их достоинство.

Алгоритм выработки имитовставки для массива данных.

Для решения задачи обнаружения искажений в зашифрованном массиве данных с заданной вероятностью в ГОСТе предусмотрен дополнительный режим криптографического преобразования - выработка имитовставки. Имитовставка - это контрольная комбинация, зависящая от открытых данных и секретной ключевой информации. Целью использования имитовставки является обнаружение всех случайных или преднамеренных изменений в массиве информации. Проблема, изложенная в предыдущем пункте, может быть успешно решена с помощью добавления к шифрованным данным имитовставки. Для потенциального злоумышленника две следующие задачи практически неразрешимы, если он не владеет ключевой информацией:

вычисление имитовставки для заданного открытого массива информации;

подбор открытых данных под заданную имитовставку;

Схема алгоритма выработки имитовставки приведена на рисунке 6. В качестве имитовставки берется часть блока, полученного на выходе, обычно 32 его младших бита. При выборе размера имитовставки надо принимать во внимание, что вероятность успешного навязывания ложных данных равна величине 2-|И| на одну попытку подбора. При использовании имитовставки размером 32 бита эта вероятность равна 2-32?0.23·10-9.

Так ну вроде все с симметричными криптосистемами…. Два основных и наиболее испытанных стандарта разобраны. Пора бы приступить к криптографии с открытыми ключами.

RSA

Безопасность RSA основана на трудности разложения на множители больших чисел. Открытый и закрытый ключи являются функциями двух больших (100-200 разрядов или даже больше) простых чисел. Предполагается, что восстановление открытого текста по шифротексту и открытому ключу эквивалентно разложению на множители двух больших чисел .

Для генерации двух ключей используются два больших случайных простых числа , p и q. Для максимальной безопасности выбирайте p и q равной длины. Рассчитывается произведение:

n=pq

Затем случайным образом выбирается ключ шифрования e, такой что e и (p-1)(q-1) являются взаимно простыми числами. Наконец расширенный алгоритм Эвклида используется для вычисления ключа дешифрировaния d, такого что

ed=l(mod (p-l))(q-l)) Другими словами

d=e^-1 mod ((p-1)(q-1))

Заметим, что d и n также взаимно простые числа. Числа e и n - это открытый ключ, а число d - закрытый. Два простых числа p и q больше не нужны. Они должны быть отброшены, но не должны быть раскрыты .

Для шифрования сообщения т оно сначала разбивается на цифровые блоки, меньшие n (для двоичных данных выбирается самая большая степень числа 2, меньшая n). To есть, если p и q - 100-разрядные простые числа, то n будет содержать около 200 разрядов, и каждый блок сообщения w, должен быть около 200 разрядов в длину. (Если нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями слeва, чтобы гарантировать, что блоки всегда будут меньше п. Зашифрованное сообщение с будет состоять из блоков c_i той же самой длины . Формула шифрования выглядит так

c_i=m_i^e mod m

Для расшифровки сообщения возьмите каждый зашифрованный блок с, и вычислите

mi = Cid mod n

Так как

ci = (mie)d = mied = m_i^k⁽^p^-1)(^q^-1)+1= m_i m_i ^k⁽^p^-1)(^q^-1) =m_i*1

все (mod n)

формула восстанавливает сообщение.

Шифрование RSA

Открытый ключ:

n произведение двух простых чисел p и q (p и q должны храниться в секрете) e число, взаимно простое c (p-1)(q-1)

Закрытый ключ:

d e mod ((p-1)(q-1))

Шифрование:

с = m^e mod n

Дешифрирование:

m = c^d mod n

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

Короткий пример возможно поможет пояснить работу алгоритма . Если p = 47 и q = 71 , то

n=pq=3337

Ключ e не должен иметь общих множителей

(p-1)(q-1)=46*70=3220

Выберем (случайно) e равным 79. B этом случае d= 79^-1 mod 3220 = 1019

При вычислении этого числа использован расширенный алгоритм Эвклида. Опубликуем e и n, сохранив в секрете d. Отбросим p и q. Для шифрования сообщения

m = 6882326879666683

сначала разделим его на маленькие блоки. Для нашего случая подойдут трехбуквенные блоки . Сообщение разбивается на шесть блоков m_i:

m₁ = 688

m₂ = 232

m₃ = 687

m₄ = 966

m₅ = 668

m₆ = 003

Первый блок шифруется как 688⁷⁹ mod 3337 = 1570 = c_i

Выполняя те же операции для последующих блоков, создает шифротекст сообщения :

с = 1570 2756 2091 2276 2423 158

Для дешифрирование нужно выполнить такое же возведение в степень, используя ключ дешифрирования 1019:

1570¹⁰¹⁹mod 3337 = 688 = m_i

Аналогично восстанавливается оставшаяся часть сообщения .

Скорость RSA

Аппаратно RSA примерно в 1000 раз медленнее DES. Скорость работы самой быстрой СБИС-реализации RSA с 512-битовым модулем - 64 килобита в секунду. Существуют также микросхемы, которые выполняют 1024-битовое шифрование RSA. B настоящее время разрабатываются микросхемы, которые, используя 512-битовый модуль, приблизятся к рубежу 1 Мбит/с. Производители также применяют RSA в интеллектуальных карточках, но эти реализации медленнее.

Программно DES примерно в 100 раз быстрее RSA. Эти числа могут незначительно измениться при изменении технологии, но RSA никогда не достигнет скорости симметричных алгоритмов . B 15-й приведены примеры скоростей программного шифрования RSA.

Скорости RSA для различных длин модулей при 8-битовом открытом ключе

	512 битов	768 битов	1024 бита
Шифрование ДешифрированиПодпись Проверка	0.03с 0.16с 0.16с 0.02с	0.05с 0.48с 0.52с 0.07с	0.08с 0.93с 0.97с 0.08с

Шифрование RSA выполняется намного быстрей, если вы правильно выберете значение e. Тремя наиболее частыми вариантами являются 3, 17 и 65537 (216 + 1). (Двоичное представление 65537 содержит только две единицы, поэтому для возведения в степень нужно выполнить только 17 умножений.) X.509 советует 65537 , PEM рекомендует 3 , a PKCS #1 - 3 или 65537 . He существует никаких проблем безопасности, связанных с использованием в качестве e любого из этих трех значений (при условии, что вы дополняете сообщения случайными числами - см. раздел ниже), даже если одно и то же значение e используется целой группой пользователей.

Безопасность RSA

Безопасность RSA полностью зависит от проблемы разложения на множители больших чисел. Технически, это утверждение о безопасности лживо. Предполагается, что безопасность RSA зависит от проблемы разложения на множители больших чисел. Никогда не было доказано математически, что нужно разложить n на множители, чтобы восстановить т по с и e. Понятно, что может быть открыт совсем иной способ криптоанализа RSA. Однако, если этот новый способ позволит криптоаналитику получить d, он также может быть использован для разложения на множители больших чисел. Я не слишком волнуюсь об этом.

Также можно вскрыть RSA, угадав значение (p-1)(q-1). Это вскрытие не проще разложения n на множители.

Для сверхскептиков: доказано, что некоторые варианты RSA также сложны, как и разложение на множители

Самым очевидным средством вскрытия является разложение n на множители. Любой противник сможет получить открытый ключ e и модуль п. Чтобы найти ключ дешифрирования d, противник должен разложить n на множители. Современное состояние технологии разложения на множители рассматривалось в разделе 11.4. B настоящее время передним краем этой технологии является число, содержащее 129 десятичных цифр . Значит, n должно быть больше этого значения. Рекомендации по выбору длины открытого ключа приведены дополнении

Конечно, криптоаналитик может перебирать все возможные d, пока он не подберет правильное значение. Ho такое вскрытие грубой силой даже менее эффективно, чем попытка разложить n на множители.

Время от времени появляются заявления о том, что найден простой способ вскрытия RSA, но пока ни одно из подобных заявлений не подтвердилось. Например, в 1993 году в черновике статьи Вильяма Пейна (William Payne) был предложен метод, основанный на малой теореме Ферма . K сожалению, (а может и по счастью) этот метод оказался медленнее разложения на множители

Существует еще один повод для беспокойства. Большинство общепринятых алгоритмов вычисления простых чисел p и q вероятностны, что произойдет, если p или q окажется составным? Hy, во первых, можно свести вероятность такого события до нужного минимума. И даже если это произойдет, скорее всего такое событие будет сразу же обнаружено - шифрование и дешифрирование не будут работать. Существует ряд чисел, называемых числами Кармайкла, которые не могут обнаружить определенные вероятностные алгоритмы поиcка простых чисел. Они небезопасны, но чрезвычайно редки. Честно говоря, меня бы это не обеспокоило.

Вскрытие с выбранным шифротекстом против RSA

Некоторые вскрытия работают против реализаций RSA. Они вскрывают не сам базовый алгоритм, а надстроенный над ним протокол. Важно понимать, что само по себе использование RSA не обеспечивает безопасности. Дело в реализации.

Сценарий 1: Е, подслушавшему линии связи А, удалось перехватить сообщение с, шифрованное с помощью RSA открытым ключом А. Е хочет прочитать сообщение. Ha языке математики, ему нужно т, для которого

т = c^d

Для раскрытия т он сначала выбирает первое случайное число r, меньшее п. Она достает открытый ключ А e. Затем он вычисляет

x = r^e mod n

y = xc mod n

t = r^-1 mod n

Если x = r^e mod n, то r = x^dmod n.

Теперь E просит А подписать у его закрытым ключом, таким образом расшифровав у He забывайте, А никогда раньше не видел у. А посылает Е

и = y^d mod n

Теперь Е вычисляет

tu mod n = r^-1 y^d mod = r ^-1x^d c^d mod n = c^d mod n = m

И получает т.

Сценарий 2: С - это компьютер-нотариус. Если А хочет заверить документ, он посылает его С. С подписывает его цифровой подписью RSA и отправляет обратно. (Однонаправленные хэш-функции не используются, С шифрует все сообщение своим закрытым ключом .)

F хочет, чтобы С подписал такое сообщение, которое в обычном случае он никогда не подпишет. Может быть это фальшивая временная метка, может быть автором этого сообщения является другое лицо. Какой бы ни была причина, С никогда не подпишет это сообщение, если у него будет возможность выбора. Назовем это сообщение т'.

Сначала F выбирает произвольное значение x и вычисляет у = x^e mod n. e он может получить без труда - это открытый ключ С, который должен быть опубликован, чтобы можно было проверять подписи С. Теперь F вычисляет m = ym' mod n и посылает т С на подпись. С возвращает m^d mod n. Теперь F вычисляет (m^d mod n)x^-1mod n, которое равно n^d mod n и является подписью m'.

Ha самом деле F может использовать множество способов решить подобную задачу. Слабым местом, которое используют такие вскрытия, является сохранение мультипликативной структуры входа при возведении в степень. To есть:

(xm)d mod n = x d md mod n

Сценарий 3: Е хочет, чтобы А подписал m₃. Он создает два сообщения, m₁и m₂, такие что

m³=m¹m² mod m

Если Ева сможет заставить А подписать m₁ и m₂, она может вычислить подпись для m₃:

M3d =(m₁^d mod n)(m₂^d mod n)

Мораль: Никогда не пользуйтесь алгоритмом RSA для подписи случайных документов, подсунутых вам посторонними. Всегда сначала воспользуйтесь однонаправленной хэш-фунцией.

Вскрытие общего модуля RSA

При реализации RSA можно попробовать раздать всем пользователям одинаковый модуль и, но каждому свои значения показателей степени e и d. K сожалению, это не работает. Наиболее очевидная проблема в том, что если одно и то же сообщение когда-нибудь шифровалось разными показателями степени (с одним и тем же модулем), и эти два показателя - взаимно простые числа (как обычно и бывает), то открытый текст может быть раскрыт, даже не зная ни одного ключа дешифрирования.

Пусть т - открытый текст сообщения. Два ключа шифрования - e¹ и e²- Общий модуль - п. Шифротекстами сообщения являются:

С₁= m^e1 mod n

C₂ = m^e2 mod n

Криптоаналитик знает n,e₁,e₂,c₁ и c₂ Вот как он узнает m.

Так как e₁ и e₂ - взаимно простые числа, то с помощью расширенного алгоритма Эвклида r и s, для которых:

re₁ + se₂ = 1

Считая r отрицательным (или r, или s должно быть отрицательным, пусть отрицательным будет r), то снова можно воспользоваться расширенным алгоритмом для вычисления c₁^-1. Затем

(c₁^-1)^-^r *c₂^s = m mod n

Полученные уроки

На основании перечисленных вскрытий приводит следующие ограничения RSA:

Ш Знание одной пары показателей шифрования/дешифрирования для данного модуля позволяет взломщику разложить модуль на множители.

Ш Знание одной пары показателей шифрования/дешифрирования для данного модуля позволяет взломщику вычислить другие пары показателей, не раскладывая модуль на множители.

Ш B протоколах сетей связи, применяющих RSA, не должен использоваться общий модуль. (Это является быть очевидным следствием предыдущих двух пунктов.)

Ш Для предотвращения вскрытия малого показателя шифрования сообщения должны быть дополнены слyчайными значениями.

Ш Показатель дешифрирования должен быть большим.

He забывайте, недостаточно использовать безопасный криптографический алгоритм, должны быть безопаcными вся криптосистема и криптографический протокол. Слабое место любого из трех этих компонентов сделaет небезопасной всю систему-впрочем, я об этом говорил в самом начале.

Вскрытие шифрования и подписи с использованием RSA

Имеет смысл подписывать сообщение перед шифрованием но на практике никто не выполняет этого. Для RSA можно вскрыть протоколы, шифрующие сообщение до его подписания.

А хочет послать сообщение B. Сначала он шифрует его открытым ключом B, а затем подписывает своим закрытым ключом. Eго зашифрованное и подписанное сообщение выглядит так:

(m^eb mod _nb)^da mod _na

Вот как B может доказать, что А послал ему m', а не т. Так как B известно разложение на множители п_в (это его собственный модуль), он может вычислить дискретные логарифмы по основанию n_в. Следовательно, ему нужно только найти x, для которого

m^x = m mod n_в

Тогда, если он может опубликовать хе_в в качестве своего нового открытого показателя степени и сохранить свой прежний модуль n_в, он сможет утверждать, что А послал ему сообщение m', зашифрованное этим новым показателем.

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

Шифр Эль Гамаля

1. Криптографы постоянно вели поиски более эффективных систем открытого шифрования, и в 1985 году Эль Гамаль предложил следующую схему на основе возведения в степень по модулю большого простого числа. Для этого задается большое простое число Р. Сообщения представляются целыми числами S из интервала (1, Р). Оригинальный протокол передачи сообщения S выглядит в варианте Шамира, одного из авторов RSA, так: 1. Отправитель А и получатель В знают лишь Р. А генерирует случайное число Х из

2. интервала (1,Р) и В тоже генерирует случайное число Y из того же интервала.

3. А шифрует сообщение S1=SX MOD Р и посылает В. 3. В шифрует его своим ключом S2=S1Y MOD Р и посылает S2 к А. 4. А "снимает" свой ключ S3=S2(-X) MOD Р и возвращает S3 к В. 5. Получатель В расшифровывает сообщение: S=S3(-Y) MOD Р.

Этот протокол можно применить, например, для таких неожиданных целей, как игра в очко или блэкджек по телефону. Крупье шифрует карты своим ключом и передает их игроку. Игрок выбирает наугад одну из карт, шифрует карты своим ключом и возвращает их крупье. Крупье "снимает" с выбранной карты свой ключ и отсылает ее игроку. "Сняв" с этой карты свой ключ игрок узнает ее номинал и принимает решение: спасовать, тянуть еще или раскрываться. Теперь, хотя колода находится у крупье, но он не может ее раскрыть, так как карты зашифрованы ключом игрока. Крупье выбирает свою карту аналогично игроку. (Аналогичный алгоритм для игры в карты можно реализовать и на основе шифрования заменой операцией XOR. Однако им нельзя распространять ключи из-за легкого перехвата и взлома.)

В системе Эль Гамаля большая степень защиты, чем у алгоритма RSA достигается с тем же по размеру N, что позволяет почти на порядок увеличить скорость шифрования и расшифрования. Криптостойкость системы ЭльГамаля основана на том, что можно легко вычислить степень целого числа, то есть произвести умножение его самого на себя любое число раз так же, как и при операциях с обычными числами. Однако трудно найти показатель степени, в которую нужно возвести заданное число, чтобы получить другое, тоже заданное. В общем случае эта задача дискретного логарифмирования кажется более трудной, чем разложение больших чисел на простые сомножители, на основании чего можно предположить, что сложности вскрытия систем RSA и Эль Гамаля будут сходными. С точки зрения практической реализации, как программным, так и аппаратным способом ощутимой разницы между этими двумя стандартами нет. Однако в криптостойкости они заметно различаются. Если рассматривать задачу разложения произвольного целого числа длиной в 512 бит на простые множители и задачу логарифмирования целых чисел по 512 бит, вторая задача, по оценкам математиков, несравненно сложнее первой. Однако есть одна особенность. Если в системе, построенной с помощью алгоритма RSA, криптоаналитику удалось разложить открытый ключ N одного из абонентов на два простых числа, то возможность злоупотреблений ограничивается только этим конкретным пользователем. В случае же системы, построенной с помощью алгоритма Эль Гамаля, угрозе раскрытия подвергнутся все абоненты криптографической сети. Кроме того, упомянутые выше Ленстра и Манасси не только поколебали стойкость RSA, разложив девятое число Ферма на простые множители за неприлично короткое время, но и, как было замечено некоторыми экспертами, указали "брешь" в способе Эль Гамаля. Дело в том, что подход, применявшийся при разложении на множители девятого числа Ферма, позволяет существенно усовершенствовать методы дискретного логарифмирования для отдельных специальных простых чисел. То есть тот, кто предлагает простое Р для алгоритма Эль Гамаля, имеет возможность выбрать специальное простое, для которого задача дискретного логарифмирования будет вполне по силам обычным ЭВМ. Следует заметить, что этот недостаток алгоритма Эль Гамаля не фатален. Достаточно предусмотреть процедуру, гарантирующую случайность выбора простого Р в этой системе, и тогда только что высказанное возражение теряет силу. Стоит отметить, что чисел специального вида, ослабляющих метод Эль Гамаля, очень мало и случайным их выбором можно пренебречь.