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

Оценки сложности задачи дискретного логарифмирования в зависимости от длины двоичной записи простого числа P (при правильном его выборе) приведены в таблице:

ElGamal. Разработан в 1985 году. Назван по фамилии автора Эль-Гамаль. Используется в стандарте США на цифровую подпись DSS (Digital Signature Standard). Криптостойкость основана на вычислительной сложности задачи логарифмирования целых чисел в конечных полях.

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

Первой системой такого рода стала система Диффи-Хеллмана, разработанная в 1976 году, построенная на задаче о дискретном логарифмировании. связь несанкционированный информация шифрование

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

Сравнение cимметричных и аcимметричных алгоритмов шифрования

Принципиально новым решением является электронная цифровая подпись (ЭЦП).

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

· удостоверяет, что подписанный текст исходит от лица, поставившего подпись;

· не дает самому этому лицу возможности отказаться от обязательств, связанных с подписанным текстом;

· гарантирует целостность подписанного текста.

Цифровая подпись представляет собой относительно небольшое количество дополнительной цифровой информации, передаваемой вместе с подписываемым текстом.

Система ЭЦП включает две процедуры: 1) процедуру постановки подписи; 2) процедуру проверки подписи. В процедуре постановки подписи используется секретный ключ отправителя сообщения, в процедуре проверки подписи - открытый ключ отправителя.

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

При проверке ЭЦП получатель сообщения снова вычисляет хэш-функцию m = h(М) принятого по каналу текста М, после чего при помощи открытого ключа отправителя проверяет, соответствует ли полученная подпись вычисленному значению m хэш-функции.

Принципиальным моментом в системе ЭЦП является невозможность подделки ЭЦП пользователя без знания его секретного ключа подписывания.

Таким образом, для получения ЭЦП используются хэш-функции (англ. hash мелко измельчать и перемешивать), предназначенные для сжатия подписываемого документа до нескольких десятков или сотен бит. Хэш-функция h(M) принимает в качестве аргумента сообщение (документ) М произвольной длины и возвращает хэш-значение h(М)=Н фиксированной длины. Обычно хэшированная информация является сжатым двоичным представлением основного сообщения произвольной длины. Следует отметить, что значение хэш-функции h(М) ложным образом зависит от документа M и не позволяет восстановить сам документ M.

Хэш-функция должна удовлетворять целому ряду условий:

1. хэш-функция должна быть чувствительна к всевозможным изменениям в тексте М, таким как вставки, выбросы, перестановки и т.п.;

2. хэш-функция должна обладать свойством необратимости, то есть задача подбора документа М', который обладал бы требуемым значением хэш-функции, должна быть вычислительно неразрешима;

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

Российский стандарт ГОСТ Р 34.11-94 определяет алгоритм и процедуру вычисления хэш-функции для любых последовательностей двоичных символов, применяемых в криптографических методах обработки и защиты информации. Этот стандарт базируется на блочном алгоритме шифрования ГОСТ 28147-89, хотя в принципе можно было бы использовать и другой блочный алгоритм шифрования с 64-битовым блоком и 256-битовым ключом.

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

Каждая подпись содержит следующую информацию:

· дату подписи;

· срок окончания действия ключа данной подписи;

· информацию о лице, подписавшем файл (Ф.И.О., должность, краткое наименование фирмы);

· идентификатор подписавшего (имя открытого ключа);

· собственно цифровую подпись.

Процесс электронного подписания документа (рис. ) довольно прост:

- 1-й пользователь приобретает у удостоверяющего центра программное обеспечение (ПО) для создания ЭЦП;

- с программным обеспечением 1-ый пользователь получает сертификат на право создание ЭЦП;

- с программным обеспечением 1-ый пользователь получает закрытый ключ с паролем;

- 1-ый пользователь, используя ПО для создания ЭЦП, на основе закрытого ключа создает открытый ключ;

- 1-ый пользователь пересылает по электронной почте открытый ключ получателю информации (2-й пользователь);

- 2-ой пользователь получает от 1-го пользователя по электронной почте открытый ключ;

- 1-ый пользователь создает файл с массивом информации (текст, графика, звук);

- 1-ый пользователь обрабатывает массив информации ПО для создания ЭЦП используя свой закрытый ключ и открытый ключ 2-го пользователя. Массив становится закодированным. Состоялся факт создания ЭЦП;

- закодированный массив отправляется по электронной почте 2-му пользователю;

- после получения закодированного массива 2-й пользователь обрабатывает массив информации ПО для создания ЭЦП, используя свой закрытый ключ и открытый ключ 1-го пользователя.

Рисунок 19 - Процесс создания ЭЦП

Рассмотрим процесс передачи сообщений с использованием открытого ключа.

Пусть пользователь N1 должен передать сообщение m пользователю N2 так, чтобы пользователь N2 в случае надобности мог доказать, что сообщение послано пользователем N1.

Для этого пользователь N1 разрабатывает систему шифрации E1(D1(X)) = X, справедливую для любых X, которая будет использоваться для его аутентификации. Он рассылает ключ E1 как общий его электронной подписи, в том числе и пользователю N2.

Получив от пользователя N2 общий ключ шифрования E2 открытой системы E2(D2(X)) = X, пользователь N1 вычисляет сигнатуру сообщения S = D1(m), затем шифрует ее открытым ключом E2: C = E2(S) и передает его пользователю N2, который расшифровывает сообщение процедурой

S = D2(C);

m* = E1(S).

Теперь при возникновении спорной ситуации пользователь N1 должен представить арбитру свой личный ключ подписи D1, удовлетворяющий соотношению E1(D1(X)) = X.

Арбитру необходимо лишь проверить, что D1(m*) = S,

и следовательно, сообщение мог послать только пользователь N1. Кроме того и пользователь N2 не может исказить сообщение m, т.к. для доказательства в суде ему необходимо изменить и сигнатуру S, а для этого ему нужно знать личный ключ подписи пользователя N1, а его то и нет.

6. Реализация алгоритмов шифрования

Алгоритмы шифрования реализуются программными или аппаратными средствами. Есть великое множество чисто программных реализаций различных алгоритмов. Из-за своей дешевизны (некoторые и вовсе бесплатны), а также все большего быстродействия процессоров ПЭВМ, простоты работы и безотказности они весьма конкурентоспособны. Широко известна, например, программа Diskreet из пакета Norton Utilities, реализующая DES.

Нельзя не упомянуть пакет PGP (Pretty Good Privacy, автор Philip Zimmermann), в котором комплексно решены практически все проблемы защиты передаваемой информации. Применены сжатие данных перед шифрованием, мощное управление ключами, симметричный (IDEA) и асимметричный (RSA) алгоритмы шифрования, вычисление контрольной функции для цифровой подписи, надежная генерация ключей.

Аппаратная реализация алгоритмов возможна с помощью специализированных микросхем (производятся кристаллы для алгоритмов DH, RSA, DES, Skipjack, ГОСТ 28147-89) или с использованием компонентов широкого назначения (ввиду дешевизны и высокого быстродействия перспективны цифровые сигнальные процессоры - ЦСП, Digital Signal Processor, DSP).

Среди российских разработок следует отметить платы «Криптон» (фирма «Анкад») [2] и «Грим» (методология и алгоритмы фирмы «ЛАН-Крипто», техническая разработка НПЦ «ЭЛиПС»).

«Криптон» - одноплатные устройства, использующие криптопроцессоры (специализированные 32-разрядные микроЭВМ, которые также называются «блюминг»). Блюминги аппаратно реализуют алгоритмы ГОСТ 28147-89, они состоят из вычислителя и ОЗУ для хранения ключей. Причем в криптопроцессоре есть три области для хранения ключей, что позволяет строить многоуровневые ключевые системы.

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

Рассмотрим наиболее известные алгоритмы цифровых подписей.

Алгоритм цифровой подписи RSА

Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSА, математическая схема которой была разработана в 1977 г. в Массачуссетском технологическом институте США.

Обобщенная схема формирования и проверки цифровой подписи RSА показана на рис.20.

Допустим, что отправитель хочет подписать сообщение М перед его отправкой. Сначала сообщение М (блок информации, файл, таблица) сжимают с помощью хэш-функции h(·) в целое число m: m = h(M).

Затем вычисляют цифровую подпись S под электронным документом М, используя хэш-значение m и секретный ключ D: S = mD (mod N).

Пара (М,S) передается партнеру-получателю как электронный документ М, подписанный цифровой подписью S, причем подпись S сформирована обладателем секретного ключа D.

Рисунок 20 - Обобщённая схема цифровой подписи RSA

После приема пары (М,S) получатель вычисляет хэш-значение сообидения М двумя разными способами. Прежде всего он восстанавливает хэш-значение m', применяя криптографическое преобразование подписи S с использованием открытого ключа Е: m' = SE (mod N).

Кроме того, он находит результат хэширования принятого сообщения М с помощью такой же хэш-функции h(·):m = h(М).

Если соблюдается равенство вычисленных значений, т.е. SE ( mod N ) = h ( М), то получатель признает пару (М,S) подлинной. Доказано, что только обладатель секретного ключа D может сформировать цифровую подпись S по документу М, а определить секретное число D по открытому числу Е не легче, чем разложить модуль N на множители.

Кроме того, можно строго математически доказать, что результат проверки цифровой подписи S будет положительным только в том случае, если при вычислении S был использован секретный ключ D, соответствующий открытому ключу Е. Поэтому открытый ключ Е иногда называют «идентификатором» подписавшего.

Недостатки алгоритма цифровой подписи RSА.

1. При вычислении модуля N, ключей Е и D для системы цифровой подписи RSА необходимо проверять большое количество дополнительных условий, что сделать практически трудно. Невыполнение любого из этих условий делает возможным фальсификацию цифровой подписи со стороны того, кто обнаружит такое невыполнение. При подписании важных документов нельзя допускать такую возможность даже теоретически.

2. Для обеспечения криптостойкости цифровой подписи RSА по отношению к попыткам фальсификации на уровне, например, национального стандарта США на шифрование информации (алгоритм DES), т.е. 1018, необходимо использовать при вычислениях N, D и Е целые числа не менее 2512 (или около 10154) каждое, что требует больших вычислительных затрат, превышающих на 20...30% вычислительные затраты других алгоритмов цифровой подписи при сохранении того же уровня криптостойкости.

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

Пример. Допустим, что злоумышленник может сконструировать три сообщения М1, М2, М3, у которых хэш-значения m1 = h (М1), m2 = h (М2), m3 = h (М3), причем m3 = m1 * m2 (mod N).

Допустим также, что для двух сообщений М1 и М2 получены законные подписи S1 = m1D (mod N); S2 = m2D (mod N).

Тогда злоумышленник может легко вычислить подпись S3 для документа М3, даже не зная секретного ключа D: S3 = S1 * S2 (mod N).

Действительно, S1 * S2 (mod N) = m1D * m2D (mod N) = (m1m2)D (mod N) = m3D (mod N) = S3.

Более надежный и удобный для реализации на персональных компьютерах алгоритм цифровой подписи был разработан в 1984 г. американцем арабского происхождения Тахером Эль Гамалем. В 1991 г. НИСТ США обосновал перед комиссией Конгресса США выбор алгоритма цифровой подписи Эль Гамаля в качестве основы для национального стандарта.

Алгоритм цифровой подписи Эль Гамаля (ЕGSА)

Название ЕGSА происходит от слов Е_ Gаmа_ Signaturе Аlgorithm (алгоритм цифровой подписи Эль Гамаля). Идея ЕGSА основана на том, что для обоснования практической невозможности фальсификации цифровой подписи может быть использована более сложная вычислительная задача, чем разложение на множители большого целого числа, задача дискретного логарифмирования. Кроме того, Эль Гамалю удалось избежать явной слабости алгоритма цифровой подписи RSА, связанной с возможностью подделки цифровой подписи под некоторыми сообщениями без определения секретного ключа.

Рассмотрим подробнее алгоритм цифровой подписи Эль-Гамаля. Для того чтобы генерировать пару ключей (открытый ключ - секретный ключ), сначала выбирают некоторое большое простое целое число Р и большое целое число G, причем G < Р. Отправитель и получатель подписанного документа используют при вычислениях одинаковые большие целые числа Р (~10308 или ~21024) и G (~10154 или ~2512), которые не являются секретными.

Отправитель выбирает случайное целое число X, 1 < Х < (Р-1), и вычисляет Y =GX mod Р.

Число Y является открытым ключом, используемым для проверки подписи отправителя. Число Y открыто передается всем потенциальным получателям документов.

Число Х является секретным ключом отправителя для подписывания документов и должно храниться в секрете.

Для того чтобы подписать сообщение М, сначала отправитель хэширует его с помощью хэш-функции h(·) в целое число m:

m = h(М), 1 < m < (Р-1),

и генерирует случайное целое число К, 1 < К < (Р-1), такое, что К и

(Р-1) являются взаимно простыми. Затем отправитель вычисляет целое число а: а = GK mod Р и, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа Х целое число b из уравнения

m = Х * а + К * b (mod (Р-1))/

Пара чисел (а,b) образует цифровую подпись S: S=(а,b), проставляемую под документом М.

Тройка чисел (М,а,b) передается получателю, в то время как пара чисел (Х,К) держится в секрете.

После приема подписанного сообщения (М,а,b) получатель должен проверить, соответствует ли подпись S=(а,b)сообщению М. Для этого получатель сначала вычисляет по принятому сообщению М число m = h(М), т.е. хэширует принятое сообщение М.

Затем получатель вычисляет значение А = Ya ab (mod Р) и признает сообщение М подлинным, только если А = Gm (mod Р).

Иначе говоря, получатель проверяет справедливость соотношения

Ya ab (mod Р) = Gm (mod Р).

Можно строго математически доказать, что последнее равенство будет выполняться тогда, и только тогда, когда подпись S=(а,b) под документом М получена с помощью именно того секретного ключа X, из которого был получен открытый ключ Y. Таким образом, можно надежно удостовериться, что отправителем сообщения М был обладатель именно данного секретного ключа X, не раскрывая при этом сам ключ, и что отправитель подписал именно этот конкретный документ М.

Следует отметить, что выполнение каждой подписи по методу Эль Гамаля требует нового значения К, причем это значение должно выбираться случайным образом. Если нарушитель раскроет когда-либо значение К, повторно используемое отправителем, то он сможет раскрыть секретный ключ Х отправителя.

Пример. Выберем: числа Р = 11, G = 2 и секретный ключ Х = 8. Вычисляем значение открытого ключа: Y = GX mod Р = 28 mod 11 = 3.

Предположим, что исходное сообщение М характеризуется хэш-значением m = 5.

Для того чтобы вычислить цифровую подпись для сообщения М, имеющего хэш-значение m=5, сначала выберем случайное целое число К=9. Убедимся, что числа К и (Р-1) являются взаимно простыми. Действительно, НОД(9,10) = 1. Далее вычисляем элементы а и b подписи:

а = GK mod Р = 29 mod 11 =6,

элемент b определяем, используя расширенный алгоритм Евклида:

m = Х * а + К * b (mod(Р-1)).

При m = 5, а = 6, Х = 8, К = 9, Р = 11 получаем

5 = 8 * 6 + 9 * b (mod 10) или 9 * b = -43 (mod 10).

Решение: b = 3. Цифровая подпись представляет собой пару: а = 6,

b = 3. Далее отправитель передает подписанное сообщение. Приняв подписанное сообщение и открытый ключ Y = 3, получатель вычисляет хэш-значение для сообщения М : m = 5, а затем вычисляет два числа:

Yaab (mod Р) = 36 * 63 (mod 11) = 10 (mod 11);

Gm (mod Р) = 25 (mod 11) = 10 (mod 11).

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

Следует отметить, что схема Эль Гамаля является характерным примером подхода, который допускает пересылку сообщения М в открытой форме вместе с присоединенным аутентификатором (а,b). В таких случаях процедура установления подлинности принятого сообщения состоит в проверке соответствия аутентификатора сообщению.

Схема цифровой подписи Эль Гамаля имеет ряд преимуществ по сравнению со схемой цифровой подписи RSА:

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

2. При выборе модуля Р достаточно проверить, что это число является простым и что у числа (Р-1) имеется большой простой множитель (т.е. всего два достаточно просто проверяемых условия).