<< Предыдущая

стр. 21
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

При проверке ЭЦП получатель сообщения снова вычисляет хэш-функцию m = h(M) приня-
того по каналу текста M, после чего при помощи открытого ключа отправителя проверяет, соответст-
вует ли полученная подпись вычисленному значению m хэш-функции.
Принципиальным моментом в системе ЭЦП является невозможность подделки ЭЦП пользо-
вателя без знания его секретного ключа подписывания.
В качестве подписываемого документа может быть использован любой файл. Подписанный
файл создается из неподписанного путем добавления в него одной или более электронных подписей.
Каждая подпись содержит следующую информацию:
• дату подписи;
• срок окончания действия ключа данной подписи;
• информацию о лице, подписавшем файл (Ф.И.О., должность, краткое наименование фирмы);
• идентификатор подписавшего (имя открытого ключа);
• собственно цифровую подпись.
6.2. Однонаправленные хэш-функции
Хэш-функция предназначена для сжатия подписываемого документа M до нескольких десят-
ков или сотен бит. Хэш-функция h(·) принимает в качестве аргумента сообщение (документ) M про-
извольной длины и возвращает хэш-значение h(M)=H фиксированной длины. Обычно хэшированная
информация является сжатым двоичным представлением основного сообщения произвольной дли-
ны. Следует отметить, что значение хэш-функции h(M) сложным образом зависит от документа M и
не позволяет восстановить сам документ M.
Хэш-функция должна удовлетворять целому ряду условий:
• хэш-функция должна быть чувствительна к всевозможным изменениям в тексте M, таким как
вставки, выбросы, перестановки и т.п.;
• хэш-функция должна обладать свойством необратимости, то есть задача подбора документа M',
который обладал бы требуемым значением хэш-функции, должна быть вычислительно неразре-
шима;
• вероятность того, что значения хэш-функций двух различных документов (вне зависимости от их
длин) совпадут, должна быть ничтожно мала [123].
Большинство хэш-функций строится на основе однонаправленной функции f(·), которая обра-
зует выходное значение длиной n при задании двух входных значений длиной n. Этими входами яв-
ляются блок исходного текста Mi и хэш-значение Hi–1 предыдущего блока текста (рис.6.1):
Hi = f (Mi, Hi–1).
Хэш-значение, вычисляемое при вводе последнего блока текста, становится хэш-значением
всего сообщения M.

Mi
Hi
Однонаправленная
функция f
Hi–1
Рис.6.1. Построение однонаправленной хэш-функции
В результате однонаправленная хэш-функция всегда формирует выход фиксированной дли-
ны n (независимо от длины входного текста).

Однонаправленные хэш-функции на основе симметричных блочных алгоритмов
Однонаправленную хэш-функцию можно построить, используя симметричный блочный алго-
ритм. Наиболее очевидный подход состоит в том, чтобы шифровать сообщение M посредством
блочного алгоритма в режиме CBC или CFB с помощью фиксированного ключа и некоторого векто-
ра инициализации IV. Последний блок шифртекста можно рассматривать в качестве хэш-значения
сообщения M. При таком подходе не всегда возможно построить безопасную однонаправленную хэш-
функцию, но всегда можно получить код аутентификации сообщения MAC (Message Authentication
Code).
Более безопасный вариант хэш-функции можно получить, используя блок сообщения в каче-
стве ключа, предыдущее хэш-значение – в качестве входа, а текущее хэш-значение – в качестве вы-
хода. Реальные хэш-функции проектируются еще более сложными. Длина блока обычно определяет-
ся длиной ключа, а длина хэш-значения совпадает с длиной блока.
Поскольку большинство блочных алгоритмов являются 64-битовыми, некоторые схемы хэ-
ширования проектируют так, чтобы хэш-значение имело длину, равную двойной длине блока.
Если принять, что получаемая хэш-функция корректна, безопасность схемы хэширования ба-
зируется на безопасности лежащего в ее основе блочного алгоритма. Схема хэширования, у которой
длина хэш-значения равна длине блока, показана на рис. 6.2. Ее работа описывается выраже-
ниями:
H0 = IH,
Hi = EA(B) ? C,
где IH – некоторое случайное начальное значение; A, B и C могут принимать значения Mi, Hi–1, (Mi ?
Hi–1) или быть константами.
А

С
Ключ
B
Шифратор
Рис.6.2. Обобщенная схема формирования хэш-функции


Таблица 6.1
Схемы безопасного хэширования, у которых длина хэш-значения
равна длине блока
Номер схемы Функция хэширования

1 Hi = EH i?1 (Mi) ? Mi
2 Hi = EH i?1 (Mi ? Hi–1) ? Mi ? Hi–1
Hi = EH i?1 (Mi) ? Hi–1 ? Mi
3
Hi = EH i?1 (Mi ? Hi–1) ? Mi
4
5 Hi = EM i (Hi–1) ? Hi–1
6 Hi = EM i (Mi ? Hi–1) Mi ? Hi–1
7 Hi = EM i (Hi–1) Mi ? Hi–1
8
Hi = EM i (Mi ? Hi–1) ? Hi–1
Hi = EM i?H i?1 (Mi) ? Mi
9
10 Hi = EM i?H i?1 (Hi–1) ? Hi–1
11
Hi = EM i?H i?1 (Mi) ? Hi–1
12 Hi = EM i?H i?1 (Hi–1) ? Mi


Сообщение M разбивается на блоки Mi принятой длины, которые обрабатываются поочередно.
Три различные переменные A, B и C могут принимать одно из четырех возможных значений,
поэтому в принципе можно получить 64 варианта общей схемы этого типа. Из них 52 варианта яв-
ляются либо тривиально слабыми, либо небезопасными. Остальные 12 безопасных схем хэширова-
ния перечислены в табл. 6.1 [121].
Первые четыре схемы хэширования, являющиеся безопасными при всех атаках, приведены
на рис.6.3.
Hi–1 Hi–1

Mi Hi Mi Hi
Ключ Ключ

Шифратор Шифратор

(1) (2)
Hi–1 Hi–1

Mi Hi Mi Hi
Ключ Ключ

Шифратор Шифратор

(3) (4)

Рис.6.3. Четыре схемы безопасного хэширования


Отечественный стандарт хэш-функции
Российский стандарт ГОСТ Р 34.11-94 определяет алгоритм и процедуру вычисления хэш-
функции для любых последовательностей двоичных символов, применяемых в криптографических
методах обработки и защиты информации. Этот стандарт базируется на блочном алгоритме шифро-
вания ГОСТ 28147-89, хотя в принципе можно было бы использовать и другой блочный алгоритм
шифрования с 64-битовым блоком и 256-битовым ключом.
Данная хэш-функция формирует 256-битовое хэш-значение.
Функция сжатия Hi = f (Mi, Hi–1) (оба операнда Mi и Hi–1 являются 256-битовыми величинами)
определяется следующим образом:
1. Генерируются 4 ключа шифрования Kj, j = 1…4, путем линейного смешивания Mi, Hi–1 и не-
которых констант Cj.
2. Каждый ключ Kj, используют для шифрования 64-битовых подслов hi слова Hi–1 в режиме
простой замены: Sj= EK j (hj). Результирующая последовательность S4, S3, S2, S1 длиной 256 бит запо-
минается во временной переменной S.
3. Значение Hi является сложной, хотя и линейной функцией смешивания S, Mi и Hi–1.
При вычислении окончательного хэш-значения сообщения M учитываются значения трех
связанных между собой переменных:
Hn – хэш-значение последнего блока сообщения;
Z – значение контрольной суммы, получаемой при сложении по модулю 2 всех блоков сообщения;
L – длина сообщения.
Эти три переменные и дополненный последний блок M? сообщения объединяются в оконча-
тельное хэш-значение следующим образом:
H = f (Z ? M?, f (L, f (M?, Hn))).
Данная хэш-функция определена стандартом ГОСТ Р 34.11-94 для использования совместно с
pоссийским стандартом электронной цифровой подписи [40, 41].


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

Алгоритм цифровой подписи RSA
Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSA,
математическая схема которой была разработана в 1977 г. в Массачуссетском технологическом ин-
ституте США.
Сначала необходимо вычислить пару ключей (секретный ключ и открытый ключ). Для этого
отправитель (автор) электронных документов вычисляет два больших простых числа P и Q, затем
находит их произведение
N=P?Q
и значение функции
? (N) = (P –1)(Q –1).
Далее отправитель вычисляет число E из условий:
E ? ? (N), НОД (E, ? (N)) =1
и число D из условий:
D < N, E ? D ?1 (mod ? (N)).
Пара чисел (E,N) является открытым ключом. Эту пару чисел автор передает партнерам по
переписке для проверки его цифровых подписей. Число D сохраняется автором как секретный ключ
для подписывания.
Обобщенная схема формирования и проверки цифровой подписи RSA показана на рис.6.4.
Допустим, что отправитель хочет подписать сообщение M перед его отправкой. Сначала со-
общение M (блок информации, файл, таблица) сжимают с помощью хэш-функции h(·) в целое число
m:
m = h(M).
Затем вычисляют цифровую подпись S под электронным документом M, используя хэш-значение m
и секретный ключ D:
S = mD (mod N).
Пара (M,S) передается партнеру-получателю как электрон-ный документ M, подписанный
цифровой подписью S, причем подпись S сформирована обладателем секретного ключа D.
После приема пары (M,S) получатель вычисляет хэш-значение сообщения M двумя разными
способами. Прежде всего он восстанавливает хэш-значение m?, применяя криптографиче-


Отправитель Канал Получатель

Сообщение
M

m = h(M)
M
D
SE (mod N)=m?
S = m (mod N)
Блок D E
m S
сжатия


D, N

E, N
Генератор
ключей
?
E
S (mod N) =
= h(M)
Нет Да


M Блок
сжатия m = h(M)


Рис.6.4. Обобщенная схема цифровой подписи RSA


ское преобразование подписи S с использованием открытого ключа E:
m? = SE (mod N).
Кроме того, он находит результат хэширования принятого сообщения M с помощью такой же хэш-
функции h(·):
m = h(M).
Если соблюдается равенство вычисленных значений, т.е.
SE (mod N) = h(M),
то получатель признает пару (M,S) подлинной. Доказано, что только обладатель секретного ключа D
может сформировать цифровую подпись S по документу M, а определить секретное число D по от-
крытому числу E не легче, чем разложить модуль N на множители.
Кроме того, можно строго математически доказать, что результат проверки цифровой подписи
S будет положительным только в том случае, если при вычислении S был использован секретный
ключ D, соответствующий открытому ключу E. Поэтому открытый ключ E иногда называют "иден-
тификатором" подпи-савшего.
Недостатки алгоритма цифровой подписи RSA.
1. При вычислении модуля N, ключей E и D для системы цифровой подписи RSA необходимо
проверять большое количество дополнительных условий, что сделать практически трудно. Невыпол-
нение любого из этих условий делает возможным фальсификацию цифровой подписи со стороны то-
го, кто обнаружит такое невыполнение. При подписании важных документов нельзя допускать такую
возможность даже теоретически.
2. Для обеспечения криптостойкости цифровой подписи RSA по отношению к попыткам фаль-
сификации на уровне, например, национального стандарта США на шифрование информации (алго-
ритм DES), т.е. 1018, необходимо использовать при вычислениях N, D и E целые числа не менее 2512
(или около 10154) каждое, что требует больших вычислительных затрат, превышающих на 20…30%
вычислительные затраты других алгоритмов циф-ровой подписи при сохранении того же уровня крип-
тостойкости.
3. Цифровая подпись RSA уязвима к так называемой мультипликативной атаке. Иначе говоря,
алгоритм цифровой подписи RSA позволяет злоумышленнику без знания секретного ключа D сфор-
мировать подписи под теми документами, у которых результат хэширования можно вычислить как
произведение результатов хэширования уже подписанных документов.
Пример. Допустим, что злоумышленник может сконструировать три сообщения M1, M2 и M3, у которых хэш-значения
m1 = h(M1), m2 = h(M2), m3 = h(M3),
m3 = m1 ? m2 (mod N).
причем
Допустим также, что для двух сообщений M1 и M2 получены законные подписи
D D
S1 = m1 (mod N) и S2 = m2 (mod N).

<< Предыдущая

стр. 21
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>