2. АЛГОРИТМИЧЕСКИЕ АСПЕКТЫ ОБЕСПЕЧЕНИЯ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ

2.1. Асимметричные алгоритмы шифрования

2.1.1. Стандарт асимметричного шифрования RSA

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

шифрование/расшифрование

2.1.2. Алгоритм Эль-Гамаля

шифрование сообщений

подтверждение подлинности отправителя

2.1.3. Алгоритм шамира

передача сообщений

2.1.4. Криптосистемы на основе эллиптических уравнений

2.2. Электронно-цифровая подпись

2.2.1. Алгоритм DSA

генерация электронно-цифровой подписи

проверка электронно-цифровой подписи

2.2.2. Стандарт на процедуры электронно-цифровой подписи гост р 34.10-94

генерация электронно-цифровой подписи

проверка электронно-цифровой подписи

2.2.3. Цифровые подписи, основанные на симметричных криптосистемах

2.2.4. Атаки на электронно-цифровую подпись

2.2.5. Некоторые средства работы с электронно-цифровой подписью

PGP

Gnu Privacy Guard (Gnupg)

криптон

вербао

2. АЛГОРИТМИЧЕСКИЕ АСПЕКТЫ ОБЕСПЕЧЕНИЯ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ

2.1. АСИММЕТРИЧНЫЕ АЛГОРИТМЫ ШИФРОВАНИЯ

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

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

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

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

В целом система переписки при использовании асимметричного шифрования выглядит следующим образом. Для каждого из N абонентов, ведущих переписку, выбрана своя пара ключей: "открытый" E_j и "закрытый" D_j, где j – номер абонента. Все открытые ключи известны всем пользователям сети, каждый закрытый ключ, наоборот, хранится только у того абонента, которому он принадлежит. Если абонент, скажем под номером 7, собирается передать информацию абоненту под номером 9, он шифрует данные ключом шифрования E₉ и отправляет ее абоненту 9. Несмотря на то, что все пользователи сети знают ключ E₉ и, возможно, имеют доступ к каналу, по которому идет зашифрованное послание, они не могут прочесть исходный текст, так как процедура шифрования необратима по открытому ключу. И только абонент № 9, получив послание, производит над ним преобразование с помощью известного только ему ключа D₉ и восстанавливает текст послания. Заметим, что если сообщение нужно отправить в противоположном направлении (от абонента 9 к абоненту 7), то нужно будет использовать уже другую пару ключей (для шифрования ключ E₇, а для дешифрования – ключ D₇).

2.1.1. СТАНДАРТ АСИММЕТРИЧНОГО ШИФРОВАНИЯ RSA

Самым распространенным алгоритмом асимметричного шифрования является алгоритм RSA. Он был предложен тремя исследователями-математиками Рональдом Ривестом (R. Rivest), Ади Шамиром (A. Shamir) и Леонардом Адльманом (L. Adleman) в 1977-78 годах. Разработчикам данного алгоритма удалось эффективно воплотить идею односторонних функций с секретом. Стойкость RSA базируется на  сложности факторизации больших целых чисел. В 1993 году метод RSA  был обнародован и принят в качестве стандарта (PKCS #1: RSA Encryption standart). RSA можно применять как для шифрования/расшифрования, так и для генерации/проверки электронно-цифровой подписи.

ГЕНЕРАЦИЯ КЛЮЧЕЙ

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

Выбираются два простых (!) числа p и q

Вычисляется их произведение n(=p*q)

Выбирается произвольное число e (e<n), такое, что НОД(e,(p-1)(q-1))=1, то есть e должно быть взаимно простым с числом (p-1)(q-1).

Решается в целых числах (!) уравнение:

e*d+(p-1)(q-1)*y=1.

Здесь неизвестными являются переменные d и y, каждая из которых является решением уравнения в целых числах.

Два числа (e,n) – публикуются как открытый ключ.

Число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e,n).

ШИФРОВАНИЕ/РАСШИФРОВАНИЕ

Как же производится собственно шифрование с помощью этих чисел: Отправитель разбивает свое сообщение на блоки, равные k=[log₂(n)] бит, где квадратные скобки обозначают, взятие целой части от дробного числа.

Подобный блок, как Вы знаете, может быть интерпретирован как число из диапазона (0;2^k-1). Для каждого такого числа (назовем его m_i) вычисляется выражение c_i=((m_i)^e)mod n. Блоки c_i и есть зашифрованное сообщение, и их можно спокойно передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название "логарифмирование в конечном поле" и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по c_i прочесть исходные сообщения m_i он не может никак, кроме как полным перебором m_i.

На приемной стороне процесс дешифрования возможен, при помощи хранимого в секрете числа d. Это возможно по доказанной теореме Эйлера, частный случай которой утверждает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство:

(x^(p-1)(q-1))mod n = 1.

Для дешифрования RSA-сообщений воспользуемся этой формулой.

Возведем обе ее части в степень (-y):

(x^{(-y)(p-1)(q-1)})mod n = 1^(-y) = 1.

Теперь умножим обе ее части на x:

(x^{(-y)(p-1)(q-1)+1})mod n = 1*x = x.

А теперь тем же методом, что мы создавали открытый и закрытый ключи, мы подберем такое d, что:

e*d+(p-1)(q-1)*y=1,

то есть e*d=(-y)(p-1)(q-1)+1.

А следовательно в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e*d). Получаем (x^e*d)mod n = x. То есть для того чтобы прочесть сообщение c_i=((m_i)^e)mod n достаточно возвести его в степень d по модулю m:

((c_i)^d)mod n = ((m_i)^e*d)mod n = m_i.

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

2.1.2. АЛГОРИТМ ЭЛЬ-ГАМАЛЯ

Криптографы со своей стороны вели поиски более эффективных систем открытого шифрования и в 1985 году Т.Эль-Гамаль (США) предложил следующую схему на основе возведения в степень по модулю большого простого числа P. Задается большое простое число P и целое число A, 1 < A < P. Сообщения представляются целыми числами M из интервала 1 < M < P.

ШИФРОВАНИЕ СООБЩЕНИЙ

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

абоненты знают числа A и P; абоненты генерируют независимо друг от друга случайные числа:

Ka, Kb

удовлетворяющих условию:

1 < K < P

получатель вычисляет и передаёт отправителю число B, определяемое последовательностью:

В = A ^Kb mоd(P)

отправитель шифрует сообщение M и отправляет полученную последовательность получателю

C = M * B ^Ka mоd(P)

получатель расшифровывает полученное сообщение

D = ( A ^Ka ) ^-Kb mоd(P)

M = C * D mоd(P)

В этой системе открытого шифрования та же степень защиты, что для алгоритма RSA с модулем N из 200 знаков, достигается уже при модуле P из 150 знаков. Это позволяет в 5-7 раз увеличить скорость обработки информации. Однако, в таком варианте открытого шифрования нет подтверждения подлинности сообщений.

ПОДТВЕРЖДЕНИЕ ПОДЛИННОСТИ ОТПРАВИТЕЛЯ

Для того, чтобы обеспечить при открытом шифровании по модулю простого числа P также и процедуру подтверждения подлинности отправителя Т.ЭльГамаль предложил следующий протокол передачи подписанного сообщения M:

абоненты знают числа A и P;

отправитель генерирует случайное число и хранит его в секрете:

Ka

удовлетворяющее условию:

1 < Ka < P

вычисляет и передаёт получателю число B, определяемое последовательностью:

В = A ^Ka mоd(P)

Для сообщения M (1 < M < P):

выбирает случайное число L (1 < L < P), удовлетворяющее условию

( L , P - 1 ) = 1

вычисляет число

R = A ^L mоd(P)

решает относительно S

M = Ka * R + L * S mоd(P)

передаёт подписанное сообщение

[ M, R, S ]

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

A M = ( B ^R ) *  ( R ^S ) mоd(P)

В этой системе секретным ключом для подписи сообщений является число X, а открытым ключом для проверки достоверности подписи число B. Процедура проверки подписи служит также и для проверки правильности расшифрования, если сообщения шифруются.

2.1.3. АЛГОРИТМ ШАМИРА

Еще один интересный пример использования возведения в степень по модулю большого простого числа P для открытого шифрования предложил А.Shamir (один из авторов RSA). Как и в системе Эль Гамаля сообщения M представляются целыми числами из интервала 1 < M < P.

ПЕРЕДАЧА СООБЩЕНИЙ

Передача сообщения происходит следующим образом:

абоненты знают числа P;

абоненты генерируют независимо друг от друга случайные числа:

Ka, Kb

удовлетворяющих условию:

1 < K < P

отправитель вычисляет значение и передаёт получателю:

C = M ^Ka mоd(P)

получатель вычисляет и передаёт отправителю число B, определяемое последовательностью:

D = C ^Kb mоd(P)

отправитель аннулирует свой шифр и отправляет полученную последовательность получателю

E=D^(X-1) mоd(P) E = D ^Fa mоd(P)

где:

Fa = Ka -1

получатель расшифровывает полученное сообщение

M = E ^Fb mоd(P)

где:

Fb = Kb –1

2.1.4. КРИПТОСИСТЕМЫ НА ОСНОВЕ ЭЛЛИПТИЧЕСКИХ УРАВНЕНИЙ

Эллиптические кривые - математический объект, который может, определен над любым полем (конечным, действительным, рациональным или комплексным). В криптографии обычно используются конечные поля. Эллиптическая кривая есть множество точек (x,y), удовлетворяющее следующему уравнению:

y² = x³ + ax + b,

а также бесконечно удаленная точка. Для точек на кривой довольно легко вводится операция сложения, которая играет ту же роль, что и операция умножения в криптосистемах RSA и Эль-Гамаля.

В реальных криптосистемах на базе эллиптических уравнений используется уравнение

y² = x³ + ax + b mod p,

где p - простое.

Проблема дискретного логарифма на эллиптической кривой состоит в следующем: дана точка G на эллиптической кривой порядка r (количество точек на кривой) и другая точка Y на этой же кривой. Нужно найти единственную точку x такую, что Y = xG, то есть Y есть х-я степень G.

2.2. ЭЛЕКТРОННО-ЦИФРОВАЯ ПОДПИСЬ

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

-       Гарантирование истинности письма путем сличения подписи с имеющимся образцом;

-       Гарантирование авторства документа (с юридической точки зрения)

Выполнение данных требований основывается на следующих свойствах подписи:

-       подпись аутентична, то есть с ее помощью получателю документа можно доказать, что она принадлежит подписывающему;

-       подпись не подделываемая; то есть служит доказательством, что только тот человек, чей автограф стоит на документе, мог подписать данный документ, и никто иной;

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

-       документ с подписью является неизменяемым;

-       подпись неоспорима;

-       любое лицо, владеющее образцом подписи может удостоверится, что документ подписан владельцем подписи.

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

Существует несколько методов построения электронно-цифровой подписи, а именно:

-       шифрование электронного документа на основе симметричных  алгоритмов. Данная схема предусматривает наличие в системе третьего лица – арбитра, пользующегося доверием обеих сторон. Авторизацией документа в данной схеме является сам факт шифрования электронного документа секретным ключом и передача его арбитру;

-       использование асимметричных алгоритмов шифрования. Фактом подписания документа является шифрование его на секретном ключе отправителя;

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

Кроме перечисленных, существуют и другие методы построения схем электронно-цифровой подписи

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

2.2.1. АЛГОРИТМ DSA

В 1991 г. в США был опубликован проект федерального стандарта цифровой подписи - DSS (Digital Signature Standard, [DSS91], описывающий систему цифровой подписи DSA (Digital Signature Algorithm). Одним из основных критериев при создании проекта была его патентная чистота.

Предлагаемый алгоритм DSA, имеет, как и RSA, теоретико-числовой характер, и основан на криптографической системе Эль-Гамаля в варианте Шнорра. Его надежность основана на практической неразрешимости определенного частного случая задачи вычисления дискретного логарифма. Современные методы решения этой задачи имеют приблизительно ту же эффективность, что и методы решения задачи факторизации; в связи с этим предлагается использовать ключи длиной от 512 до 1024 бит с теми же характеристиками надежности, что и в системе RSA. Длина подписи в системе DSA меньше, чем в RSA, и составляет 320 бит.

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

Функции DSA ограничены только цифровой подписью, система принципиально не предназначена для шифрования данных. По быстродействию система DSA сравнима с RSA при формировании подписи, но существенно
(в 10-40 раз) уступает ей при проверке подписи.

Вместе с проектом DSS опубликован проект стандарта SHS (Secure Hash Standard), описывающий однонаправленную хэш-функцию SHA (Secure Hash Algorithm), рекомендованную для использования вместе с DSA. Хэш-функция SHA является модификацией алгоритма MD4, хорошо известного в криптографической литературе.

ГЕНЕРАЦИЯ ЭЛЕКТРОННО-ЦИФРОВОЙ ПОДПИСИ

При генерации электронно-цифровой подписи используются параметры трех групп:

-       общие параметры

-       секретный ключ

-       открытый ключ

Общие параметры необходимы для функционирования системы в целом. Секретный ключ используется для формирования электронно-цифровой подписи, а открытый – для проверки электронно-цифровой подписи. Общими параметрами системы являются простые целые числа p,q,g, удовлетворяющие следующим условиям:

p: 2^511<p<2^512

q: простой делитель числа (p-1), который удовлетворяет условию

2^159<q<2^160

g: так называемый генератор, удовлетворяющий

равенству                               g=h^((p-1)/q)mod p >1.

Параметры p,q,g публикуются для всех участников обмена  электронными документами с электронно-цифровой подписью.

Секретный ключ x случайно выбирается из диапазона [1,q] и держится в секрете.

Открытый ключ вычисляется:  y=g^x mod p.

Также при описании данной схемы будут использоваться следующие обозначения и дополнительные параметры: m – входное сообщение пользователя для схемы с электронно-цифровой подписью; k - случайное число, удовлетворяющее условию  0<k<q, хранящееся в секрете и меняющееся от одной подписи к другой; H – хэш-функция, h – хэш-код сообщения.

Процесс генерации электронно-цифровой подписи состоит из нескольких этапов:

1.Вычисляется хэш-код сообщения m h=H(m)

2.Из диапазона [1,q] случайным образом  выбирается значение k и вычисляется

r= (g^k mod p) mod q

3. Вычисляется

S= (k^-1(h+xr)) mod q,

где k^-1 удовлетворяет условию

(k^-1*k) mod q =1

Значения r,s являются электронно-цифровой подписью сообщения m и передаются вместе с ним по каналам связи.

ПРОВЕРКА ЭЛЕКТРОННО-ЦИФРОВОЙ ПОДПИСИ

Пусть принято сообщение m1 и его подпись s1,r1.

Проверка электронно-цифровой подписи происходит следующим образом:

-            проверяется выполнение условий 0<r1<q, 0<s1<q, и если хотя бы одно из них нарушено, подпись отвергается.

-            Вычисляются значения:

w= s1^-1 mod q

u1 = (H(m1)w) mod q

u2 = ((r1/w) mod q

v = (( g^u1y^u2) mod p ) mod q

-            проверяется равенство v = r1

Если последнее равенство выполняется, то подпись принимается. В данном стандарте специфицируется также процедура генерации основных параметров системы и проводится доказательство того, что если v=r1, то m1=m, r1=r, s1=s.

2.2.2. СТАНДАРТ НА ПРОЦЕДУРЫ ЭЛЕКТРОННО-ЦИФРОВОЙ ПОДПИСИ ГОСТ Р 34.10-94

Отечественным стандартом на процедуры выработки и проверки электронно-цифровой подписи является ГОСТ  Р 34.10-94. Схема электронно-цифровой подписи, предложенная в данном стандарте, во многом напоминает подпись в DSA.

Цифровая подпись представляет собой два больших целых простых  числа. Общедоступные параметры схемы электронно-цифровой подписи (p,q,a) должны удовлетворять следующим условиям:

p: 2^501<p<2^512  или 2^1020<p<2^1020

q: простой делитель числа (p-1), который удовлетворяет условию

2^254<q<2^256

a:

1<a<p-1, a^q(mod p) =1

Секретный ключ x случайно выбирается из диапазона [1,q] и держится в секрете.

Открытый ключ вычисляется:  y=a^x mod p.

ГЕНЕРАЦИЯ ЭЛЕКТРОННО-ЦИФРОВОЙ ПОДПИСИ

Процесс генерации электронно-цифровой подписи состоит из нескольких этапов:

1. Вычисляется хэш-код сообщения

m h=H(m)

(хэш-функция, используемая в данном стандарте в соответствии с ГОСТ Р 34.10-94), если h(m)(mod p) = 0,  то h(m) присваивается значение 0…02551

2. Из диапазона [1,q] случайным образом  выбирается значение k

3. вычисляется:

r= (a^k mod p) , r1=r(mod p);

если r1=0, следует вернуться к предыдущему этапу и выработать другое значение k.

4. Вычисляется:

s= (xr1+kh(m))(mod p);

если s=0, то необходимо выработать другое значение k.

Значения r1,s1 являются электронно-цифровой подписью сообщения m и передаются вместе с ним по каналам связи.

ПРОВЕРКА ЭЛЕКТРОННО-ЦИФРОВОЙ ПОДПИСИ

Проверка электронно-цифровой подписи происходит следующим образом:

-       проверяется выполнение условий 0<r<q, 0<s<q, и если хотя бы одно из них нарушено, подпись отвергается.

-       Вычисляется хэш-код данного сообщения  h=H(m); Если h(m)(mod p) = 0, то битовое представление h(m): 0…02551

-       Вычисляется значение  v=(h(m))^q-2(mod p).

-       Вычисляется значения z1=sv(mod p); z2=(q-r1)v(mod p).

-       Вычисляется значение u=(a^z1y^z2(mod p))(mod q)

-       проверяется равенство u = r1

Если последнее равенство выполняется, то подпись принимается.

2.2.3. ЦИФРОВЫЕ ПОДПИСИ, ОСНОВАННЫЕ НА СИММЕТРИЧНЫХ КРИПТОСИСТЕМАХ

На первый взгляд, сама эта идея может показаться абсурдом. Действительно, общеизвестно, что так называемая «современная», она же двухключевая криптография возникла и стала быстро развиваться в последние десятилетия именно потому, что ряд новых криптографических протоколов типа протокола цифровой подписи не удалось эффективно реализовать на базе традиционных криптографических алгоритмов, широко известных и хорошо изученных к тому времени. Тем не менее, это возможно. И первыми, кто обратил на это внимание, были родоначальники криптографии с открытым ключом У. Диффи и М. Хеллман, опубликовавшие описание подхода, позволяющего выполнять процедуру цифровой подписи одного бита с помощью блочного шифра. Прежде чем изложить эту идею, сделаем несколько замечаний о сути и реализациях цифровой подписи.

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

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

Всего пару десятилетий назад, на заре криптографии с открытым ключом считалось, что для реализации схемы подписи RSA достаточно даже 128-битовых чисел. Сейчас эта граница отодвинута до 1024-битовых чисел – практически на порядок, – и это далеко еще не предел. Это приводит к необходимости переписывать реализующие схему программы, и зачастую перепроектировать аппаратуру.

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

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

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

Итак, вернемся к схеме Диффи и Хеллмана подписи одного бита сообщения с помощью алгоритма, базирующегося на любом классическом блочном шифре. Предположим, в нашем распоряжении есть алгоритм шифрования E_K, оперирующий блоками данных X размера n и использующий ключ размером n_K: |X|=n, |K|=n_K. Структура ключевой информации в схеме следующая: секретный ключ подписи k_S выбирается как произвольная (случайная) пара ключей k₀, k₁ используемого блочного шифра:

k_S=(k₀,k₁);

Таким образом, размер ключа подписи равен удвоенному размеру ключа использованного блочного шифра:

|K_S|=2|K|=2n_K.

Ключ проверки представляет собой результат шифрования двух блоков текста X₀ и X₁ с ключами k₀ и k₁ соответственно:

k_V=(C₀, C₁) =

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

|k_V|=2|X|=2n.

Алгоритм Sig выработки цифровой подписи для бита t (t О {0,1}) заключается просто в выборе соответствующей половины из пары, составляющей секретный ключ подписи:

s = S(t) = k_t.

Алгоритм Ver проверки подписи состоит в проверке уравнения E_kt(X_t)=C_t, которое, очевидно, должно выполняться для нашего t. Получателю известны все используемые при этом величины.

Таким образом, функция проверки подписи будет следующей:

.

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

1.   Невозможность подписать бит t, если неизвестен ключ подписи. Действительно, для выполнения этого злоумышленнику потребовалось бы решить уравнение E_s(X_t)=C_t относительно s, что эквивалентно определению ключа для известных блоков шифрованного и соответствующего ему открытого текста, что вычислительно невозможно в силу использования стойкого шифра.

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

E_s(X₀)=C₀,
E_s(X₁)=C₁.

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

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

размер ключа подписи: n_kS=2n_H Ч n_K.

размер ключа проверки подписи: n_С=2n_Hn.

размер подписи: n_S =n_H Ч n_K.

Если, например, в качестве основы в данной схеме будет использован шифр ГОСТ 28147–89 с размером блока n=64  бита и размером ключа n_K=256 бит, и для выработки хэш–блоков будет использован тот же самый шифр в режиме выработки имитовставки, что даст размер хэш–блока  n_H=64 то размеры рабочих блоков будут следующими:

размер ключа подписи: n_kS=2n_H Ч n_K =2 Ч 64 Ч 256бит=4096 байт;

размер ключа проверки подписи: n_С=2n_Hn = 2 Ч 64 Ч 64 бит = 1024 байта.

размер подписи: n_S =n_H Ч n_K = 64 Ч 256 бит = 2048 байт.

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

Однако, несколько лет назад Березин и Дорошкевич предложили модификацию схемы Диффи–Хеллмана, фактически устраняющую ее недостатки.

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

Пусть в нашем распоряжении также имеется некоторая функция отображения n–битовых блоков данных в n_K–битовые Y=P_{n ® nK}(X),  |X|=n,  |Y|=n_K. Определим рекурсивную функцию R_k «односторонней прокрутки» блока данных T размером n бит k раз (k і 0) при помощи следующей формулы:

где X – произвольный несекретный n-битовый блок данных, являющийся параметром процедуры прокрутки.

По своей идее функция односторонней прокрутки чрезвычайно проста, надо всего лишь нужное количество раз (k) выполнить следующие действия: расширить n-битовый блок данных T до размера ключа использованного алгоритма шифрования (n_K), на полученном расширенном блоке как на ключе зашифровать блок данных X, результат шифрования занести на место исходного блока данных (T). По определению операция  R_k(T) обладает двумя важными для нас свойствами:

1.   Аддитивность и коммутативность по числу прокручиваний:

R_k+k'(T)=R_k'(R_k(T)) = R_k(R_k'(T)).

2.   Односторонность или необратимость прокрутки: если известно только некоторое значение функции R_k(T), то вычислительно невозможно найти значение R_k'(T) для любого  k'<k  –  если бы это было возможно, в нашем распоряжении был бы способ определить ключ шифрования по известному входному и выходному блоку алгоритма E_K. что противоречит предположению о стойкости шифра.

Теперь покажем, как указанную операцию можно использовать для подписи блока T, состоящего из n_T битов.

Секретный ключ подписи k_S выбирается как произвольная пара блоков k₀, k₁, имеющих размер блока данных используемого блочного шифра, т.е. размер ключа выработки подписи равен удвоенному размеру блока данных использованного блочного шифра: |k_S|=2n;

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

k_C=(C₀,C₁) = (R_2nT–1(K₀), R_2nT–1(K₁)).

В этих вычислениях также используются несекретные блоки данных X₀ и X₁, являющиеся параметрами функции «односторонней прокрутки», они обязательно должны быть различными. Таким образом, размер ключа проверки подписи также равен удвоенному размеру блока данных использованного блочного шифра: |k_C|=2n.

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

Алгоритм Sig_nT выработки цифровой подписи для  n_T-битового блока T заключается в выполнении «односторонней прокрутки» обеих половин ключа подписи T и 2^nT–1–T раз соответственно:

s=Sig_nT(T)=(s₀,s₁)= .

Алгоритм Ver_nT  проверки подписи состоит в проверке истинности соотношений , которые, очевидно, должны выполняться для подлинного блока данных  T:

R_2nT–1–T(s₀)=R_2nT–1–T(R_T(k₀))=R_{2nT–1–T+T}(k₀)=R_2nT–1(k₀)=C₀,
R_T(s₁)=R_T(R_2nT–1–T(k₁))=R_{T+2nT–1–T}(k₁)=R_2nT–1(k₁)=C₁.

Таким образом, функция проверки подписи будет следующей:

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

Предположим, что в распоряжении злоумышленника есть n_T-битовый блок T, его подпись s=(s₀,s₁), и ключ проверки  k_C=(C₀,C₁). Пользуясь этой информацией, злоумышленник пытается найти правильную подпись s'=(s'₀,s'₁)  для другого n_T-битового блока T'. Для этого ему надо решить следующие уравнения относительно s'₀ и s'₁:

R_2nT–1–T'(s'₀)=C₀,
R_T'(s'₁)=C₁.

В распоряжении злоумышленника есть блок данных T с подписью s=(s₀,s₁), что позволяет ему вычислить одно из значений s'₀,s'₁, даже не владея ключом подписи:

(a)    если T<T', то s'₀=R_T'(k₀)=R_T'–T(R_T(k₀))=R_T'–T(s₀),

(b)    если T>T', то s'₁=R_2nT–1–T'(k₁)=R_T–T'(R_2nT–1–T(k₁))=R_T–T'(s₁).

Однако для нахождения второй половины подписи (s'₁ и s'₀ в случаях (a) и (b) соответственно) ему необходимо выполнить прокрутку в обратную сторону, т.е. найти R_k(X), располагая только значением для большего k, что является вычислительно невозможным. Таким образом, злоумышленник не может подделать подпись под сообщением, если не располагает секретным ключом подписи.

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

s=S_nT(T)=(s₀,s₁)=(R_T(k₀),  R_2nT–1–T(k₁)),
s'=S_nT(T')=(s'₀,s'₁)=(R_T'(k₀),  R_2nT–1–T'(k₁)),

но s=s', следовательно:

R_T(k₀)=R_T'(k₀) и R_2nT–1–T(k₁)=R_2nT–1–T'(k₁).

Положим для определенности T Ј T', тогда справедливо следующее:

R_T'–T(k₀^*)=k₀^*,R_T'–T(k₁^*)=k₁^*,где k₀^*=R_T(k₀), k₁^*=R_2nT–1–T'(k₁)

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

Таким образом рассмотренная модификация схемы Диффи–Хеллмана делает возможным подпись не одного бита, а целой битовой группы. Это позволяет в несколько раз уменьшить размер подписи и ключей подписи/проверки данной схемы. Однако надо понимать, что увеличение размера подписываемых битовых групп приводит к экспоненциальному росту объема необходимых вычислений и начиная с некоторого значения делает работу схемы также неэффективной. Граница «разумного размера» подписываемой группы находится где-то около десяти бит, и блоки большего размера все равно необходимо подписывать «по частям».

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

 бит,

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

при выработке ключевой информации оно равно:

,

при выработке и проверке подписи оно вдвое меньше:

.

Размер ключа подписи и проверки подписи можно дополнительно уменьшить следующими приемами:

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

2.   Аналогично, нет необходимости хранить массив ключей проверки подписи отдельных битовых групп блока, достаточно хранить его значение хэш-функции этого массива. При этом алгоритм выработки ключа подписи и алгоритм проверки подписи будут дополнены еще одним шагом – вычислением хэш-функции массива проверочных комбинаций отдельных битовых групп.

Таким образом, проблема размера ключей и подписи решена, однако, второй недостаток схемы – одноразовость ключей – не преодолен, поскольку это невозможно в рамках подхода Диффи–Хеллмана.

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

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

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

Предположим, что наша схема рассчитана на 2^L сообщений. Обозначим через  i-тую комбинацию  l-того уровня. Если нумерацию комбинаций и уровней начинать с нуля, то справедливо следующее условие: 0 Ј i < 2^L–l, а i-ая проверочная комбинация l-того уровня рассчитана на 2^l сообщений с номерами от  i Ч 2^l до (i+1) Ч 2^l–1  включительно. Число комбинаций нижнего, нулевого уровня равно 2^L, а самого верхнего, L-того уровня – одна, она и является контрольной комбинацией всех 2^L сообщений, на которые рассчитана схема.

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

,

где через A||B обозначен результат конкатенации двух блоков данных A и B, а через H(X) – процедура вычисления хэш-функции блока данных X.

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

Пример организации проверочных комбинаций в виде двоичного дерева в схеме на восемь сообщений при­ведена на рисунке 4. Так, при передаче сообще­ния № 5 (контрольная комбинация выделена рамкой) вместе с его под­писью должны быть переданы кон­трольная комбинация сообщения № 4 (C₄⁽⁰⁾), общая для сообщений №№ 6–7 (C₃⁽¹⁾) и общая для сообще­ний №№ 0–3 (C₀⁽²⁾), все они выделены на рисунке другим фоном.

При проверке подписи значение C₅⁽⁰⁾ будет вычислено из сообщения и его подписи, а итоговая контрольная комбинация, подлежащая сравнению с эталонной, по следующей формуле:

C=C₀⁽³⁾=H(C₀⁽²⁾||H(H(C₄⁽⁰⁾||C₅⁽⁰⁾)||C₃⁽¹⁾)).

Необходимость отправлять вместе с подписью сообщения дополнительную информацию, нужную для проверки подписи, на самом деле не очень обременительна. Действительно, в системе на 1024=2¹⁰ подписей вместе с сообщением и его подписью необходимо дополнительно передавать 10 контрольных комбинаций, а в системе на 1048576=2²⁰ подписей – всего 20 комбинаций. Однако, при большом числе подписей, на которые рассчитана система, возникает другая проблема – хранение дополнительных комбинаций, если они рассчитаны предварительно, или их выработка в момент формирования подписи.

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

Первый подход предполагает затраты дисковой памяти, так как необходимо хранить 2^L+1–2 значений хэш-функции всех уровней, а второй требует большого объема вычислений в момент формирования подписи. Можно использовать и компромиссный подход – хранить все хэш-комбинации начиная с некоторого уровня  l^*, а комбинации меньшего уровня вычислять при формировании подписи.

В рассмотренной выше схеме подписи на 8 сообщений можно хранить все 14 контрольных комбинаций, используемых при проверки (всего их 15, но самая верхняя не используется), тогда при проверке подписи их не надо будет вычислять заново. Можно хранить 6 комбинаций начиная с уровня 1 (C₀⁽¹⁾, C₁⁽¹⁾, C₂⁽¹⁾, C₃⁽¹⁾, C₀⁽²⁾, C₁⁽²⁾), тогда при проверке подписи сообщения № 5 необходимо будет заново вычислить комбинацию C₄⁽⁰⁾, а остальные (C₀⁽²⁾,C₃⁽¹⁾) взять из таблицы, и т.д. Указанный подход позволяет достичь компромисса между быстродействием и требованиям к занимаемому количеству дискового пространства.

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

2.2.4. АТАКИ НА ЭЛЕКТРОННО-ЦИФРОВУЮ ПОДПИСЬ

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

Существует следующая классификация атак на схемы электронно-цифровой подписи:

-       атака с известным открытым ключом.

-       Атака и известными подписанными сообщениями – противник, кроме открытого ключа имеет и набор подписанных сообщений.

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

-       Направленная атака с выбором сообщения

-       Адаптивная атака с выбором сообщения.

Каждая атака преследует определенную цель, которые можно разделить на несколько классов:

-       полное раскрытие. Противник находит секретный ключ пользователя;

-       универсальная подделка.  Противник находит алгоритм, функционально аналогичный  алгоритму генерации электронно-цифровой подписи;

-       селективная подделка. Подделка подписи под выбранным сообщением;

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

На практике применение  электронно-цифровой подписи позволяет выявить или предотвратить  следующие действия нарушителя:

-       отказ одного из участников авторства документа.

-       Модификация принятого электронного документа.

-       Подделка документа.

-       Навязывание сообщений в процессе передачи – противник перехватывает обмен сообщениями и модифицирует их.

-       Имитация передачи сообщения.

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

2.2.5. НЕКОТОРЫЕ СРЕДСТВА РАБОТЫ С ЭЛЕКТРОННО-ЦИФРОВОЙ ПОДПИСЬЮ

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

Приведем некоторые из них:

PGP

Наиболее известный - это пакет PGP (Pretty Good Privacy) – (www.pgpi.org ), без сомнений являющийся на сегодня самым распространенным программным продуктом, позволяющим использовать современные надежные криптографические алгоритмы для защиты информации в персональных компьютерах.

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

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

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

3. Бесплатность. Готовые базовые продукты PGP (равно как и исходные тексты программ) доступны в Интернете в частности на официальном сайте PGP Inc. ( www.pgpi.org ).

4. Поддержка как централизованной (через серверы ключей) так и децентрализованной (через «сеть доверия») модели распределения открытых ключей.

5. Удобство программного интерфейса. PGP изначально создавалась как продукт для широкого круга пользователей, поэтому освоение основных приемов работы отнимает всего несколько часов

Текущая версия – 7.0.3 для платформ Windows 9x/NT/2000, MacOS.

GNU PRIVACY GUARD (GNUPG)

GnuPG  (www.gnupg.org ) - полная и свободно распространяемая замена для пакета PGP. Этот пакет не использует патентованный алгоритм IDEA, и поэтому может быть использован без каких-нибудь ограничений. GnuPG соответствует стандарту RFC2440 (OpenPGP).

Текущая версия – 1.0.4, платформы – Unices, Windows 9x/NT

КРИПТОН

Пакет программ КРИПТОН®Подпись

(http://www.ancud.ru/crypto/crpodpis.htm) предназначен для использования электронной цифровой подписи электронных документов.

Программы пакета КРИПТОН®Подпись функционируют на компьютере, удовлетворяющем следующим требованиям:

• наличие операционной системы Windows-95/98 или Windows NT 4.0;
• наличие УКЗД серии КРИПТОН с соответствующим драйвером для Windows-95/98/NT или его программного драйвера-эмулятора для Windows - Crypton Emulator версии 1.3 или выше.
• наличие Crypton API для Windows версии 2.2 или выше (входит в поставку УКЗД серии КРИПТОН и содержит также драйвер поставляемого УКЗД);
• наличие манипулятора "мышь".

В стандартной поставке для хранения файлов открытых ключей используются дискеты. Помимо дискет, пакет КРИПТОН®Подпись дает возможность использования всех типов ключевых носителей (смарт-карт, электронных таблеток Touch Memory и др.), поддерживаемых текущей версией интерфейса SCApi, входящего в поставку Crypton API v2.2 и выше.

ВЕРБАО

( http://www.ntc.spb.ru/def/verbao.htm )

  Система криптографической защиты информации "Верба - О"

Система криптографической защиты информации (СКЗИ) "Верба - О" разработана Московским отделением Пензенского научно - исследовательского электротехнического института (МО ПНИЭИ), полномочным представителем которого в регионе является наш филиал.

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

• шифрование/расшифрование информации на уровне файлов;
• генерацию электронной цифровой подписи;
• проверку электронно-цифровой подписи;
• обнаружение искажений, вносимых злоумышленниками или вирусами в защищаемую информацию.

СКЗИ "Верба - О" может поставляться в следующих вариантах:

• в виде автономного рабочего места;
• в виде модулей, встраиваемых в ПО заказчика.

СКЗИ "Верба - О" в различных модификациях функционирует под управлением операционных систем MS DOS v5.0 и выше, Windows95, Windows NT, UNIX (HP UX) на персональных ЭВМ, совместимых с IBM PC/ AT. Требуемый объем оперативной памяти не более 155 Кбайт. Кроме того, необходим накопитель на гибком магнитном диске (НГМД).

Алгоритм шифрования выполнен в соответствии с требованиями ГОСТ 28147-89 "Системы обработки информации. Защита криптографическая". Цифровая подпись выполнена в соответствии с требованиями ГОСТ Р34.10-94 "Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма." Функция хэширования выполнена в соответствии с требованиями ГОСТ Р 34.11-94 "Информационная технология. Криптографическая защита информации. Функция хэширования".

Ключи шифрования симметричные. Ключи для подписи асимметричные.

При обработке информации на компьютере СКЗИ "Верба - О" обеспечивает следующие показатели: