Плоскость пользователя сети АТМ использует алгоритмы защиты информации, отражённые в таблицах 3.4.1-3.4.5.

Таблица 3.4.1 - Профили алгоритмов аутентификации плоскости пользователя

Примечание 1: Требуется поддержка обмена сообщениями безопасности.

Примечание 2: В данном профиле функция хэширования не используется.

Таблица 3.4.2 - Профили алгоритмов конфиденциальности плоскости пользователя

Примечание 1: Требуется поддержка обмена сообщениями безопасности.

Таблица 3.4.3 - Профили алгоритмов целостности информации плоскости пользователя и контроля

Примечание 1: Требуется поддержка обмена сообщениями безопасности.

Примечание 2: Требуется поддержка двух версий целостности с защитой от перезаписи и без неё.

Таблица 3.4.4 - Профили меток контроля доступа плоскости пользователя

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

Таблица 3.4 5 - Профили алгоритмов аутентификации плоскости контроля

Примечание 1: Так как сообщения аутентификации плоскости контроля независимо обрабатываются в каждом агенте безопасности то поддержки обмена сообщениями безопасности не требуется.

3.4.1 Алгоритм DES

Американский стандарт криптографического закрытия данных DES (Data Encryption Standard) является типичным представителем семейства блочных шифров. Этот шифр допускает эффективную аппаратную и программную реализацию, причём возможно достижение скоростей шифрования до нескольких мегабайт в секунду. Шифр DES представляет собой результат 33 отображений:

,(3.4.1.1)

где: IP (Initial Permutation - исходная перестановка) представляет собой проволочную коммутацию с инверсией IP^-1;

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

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

- на i-м цикле входной блок длиной 64 символа делится на два блока по 32 символа и , правый блок Х' разбивается на восемь блоков по четыре символа:

,

Эти восемь блоков путём копирования крайних элементов преобразуются в восемь блоков из шести символов:

;

- на i-циклической итерации 48 разрядов ключа поразрядно суммируются (по модулю 2) с полученными выше 48 разрядами данных;

- j-й блок из шести символов подаётся на вход блока подстановки (S-бокс) имеет шестиразрядный вход и четырёхразрядный выход и представляет собой четыре преобразования из в : два крайних разряда входного блока служат для выборки одного из этих преобразований. Каждая из восьми подстановок осуществляется с использованием четырёх строк и 16 столбцов матрицы с элементами . Каждый из массивов размерностью 4Ч16 определяет подстановку на множестве следующим образом. Если входом является блок из шести символов , то две крайние позиции интерпретируются как двоичное представление целых чисел из набора .

Эти целые определяют номер строки (от 0 до 3). Оставшиеся четыре символа интерпретируются как двоичное представление целых чисел из набора и служат для определения столбца в массиве (от 0 до 15). Таким образом, входной блок (0,0,1,0,1,1) соответствует строке 1 и столбцу 5;

- 32 разряда, составляющие выход S-бокса, подаются на вход блока проволочной коммутации (Р-бокс);

- компоненты правого входного 32-разрядного блока Х', преобразованного в Т(Х'), поразрядно суммируются по модулю 2 с компонентами левого входного 32-разрядного блока Х.

На каждой итерации используется 48-разрядный ключ . Поскольку входным ключом DES является 56-разрядный блок , то каждый его разряд используется многократно.

Какой именно из ключей используется на i-циклической итерации, определяется списком ключей. Для описания списка ключей введены дополнительные элементы.

Ключ определяется по следующему алгоритму:

- производиться начальная перестановка РС-1 56-разрядного ключа пользователя . Получаемый в результате 56-разрядный блок рассматривается как два 28-разрядных блока: левый - и правый - ;

- производится левый циклический сдвиг блоков и раз для получения блоков и ;

- из сцепления блоков (,) выбираются 48 разрядов с помощью перестановки РС-2. Эти разряды используются на первой итерации;

- используемые на i-й циклической итерации разряды ключа определяются методом индукции. Для получения блоков и производим левый циклический сдвиг раз блоков и .

Инверсией DES (обеспечивающей расшифрование зашифрованных посредством DES данных) является:

. (3.4.1.2)

Расшифрование зашифрованного посредством DES текста осуществляется с использованием тех же блоков благодаря обратимости преобразования.

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

Было выдвинуто большое количество предложений по усовершенствованию DES, которые отчасти компенсируют указанные недостатки. Наиболее широко известным предложением по усилению DES является так называемый «тройной» DES (Triple-DES), одна из версий которого определяется формулой:

. (3.4.1.3)

То есть, ключ для EDE3 имеет длину 56Ч3=168 бит, и шифрование 64-битового блока осуществляется шифрованием с одним подключом, расшифрованием с другим и затем шифрованием с третьим. Причина, по которой вторым шагом является , а не , является совместимость с DES: если выбрать , то . Причина использования DES три раза вместо двух заключается в существовании атаки «человек в середине» на двойной DES.

Проблема с тройным DES состоит в том, что он гораздо медленнее, чем сам DES - его скорость составляет ровно одну треть исходной. При использовании EDE3 в режиме сцепления блоков (СВС - Cipher Block Chaining) замедление снижается как на аппаратном, так и на программном (даже если попытаться компенсировать его дополнительной аппаратной частью) уровнях. Во многих случаях такое падение производительности неприемлемо.

DES - блочный шифр и при шифровании он может использоваться в нескольких режимах. В сетях АТМ используется режим сцепления блоков шифрованного текста (CBC - Cipher Block Chaining).

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

. (3.4.1.4)

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 3.4.1.1 - Режим сцепления блоков шифрованного текста

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

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

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

3.4.2 Алгоритм RSA

Криптосистема Ривеста-Шамира-Эйделмана (RSA - Rivest-Shamir-Adleman) представляет собой систему, стойкость которой основана на сложности решения задачи разложения числа на простые сомножители. Кратко алгоритм можно описать следующим образом:

Пользователь A выбирает пару различных простых чисел и , вычисляет и выбирает число , такое что

, (3.4.2.1)

где - функция Эйлера (количество чисел, меньших n и взаимно простых с n). Если , где p и q - простые числа, то

. (3.4.2.2)

Затем он вычисляет величину , такую, что

, (3.4.2.3)

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

Теперь пользователь В, желая передать сообщение пользователю А, представляет исходный текст: , по основанию :

. (3.4.2.4)

Пользователь В зашифровывает текст при передаче его пользователю А, применяя к коэффициентам отображение:

, (3.4.2.5)

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

. (3.4.2.6)

Пользователь А производит расшифрование полученного сообщения , применяя .

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

Кроме того, криптосистема Ривеста-Шамира-Эйделмана может использоваться для формирования электронной цифровой подписи.

Пользователь А вырабатывает цифровую подпись предназначенного для пользователя В сообщения М с помощью следующего преобразования

SIG(M)=E_eB·nB(E_dA·nA(M)). (3.4.2.7)

При этом он использует:

- своё секретное преобразование E_dA·nA;

- открытое преобразование E_eB·nB пользователя В.

Затем он передаёт пользователю В пару <М, SIG(М)>.

Пользователь В может верифицировать это подписанное сообщение сначала при помощи своего секретного преобразования E_dB·nB с целью получения

E_dA·nA(М)= E_dB·nB(SIG(M))=E_dB·nB(E_eB·nB(E_dA·nA(М))) (3.4.2.8)

и затем открытого преобразования E_еA·nA пользователя А для получения сообщения М:

М=E_еA·nA(E_dA·nA(М)). (3.4.2.9)

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

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

SIG(M)=E_dA·nA(M), (3.4.2.10)

а пользователи осуществляют верификацию с использованием открытого преобразования отправителя (пользователя А):

М=E_еА·nА(SIG(M))=E_еА·nА(E_dA·nA(М)). (3.4.2.11)

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

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

3.4.3 Алгоритм, основанный на эллиптических кривых

В 1985 году Коблиц и Миллер независимо друг от друга предложили использовать для построения криптосистем алгебраические структуры, определённые на множестве точек на эллиптических кривых. Рассмотрим случаи определения эллиптических кривых над простыми конечными полями произвольной характеристики и над полями Галуа характеристики 2.

Пусть - простое число. Пусть такие, что . Эллиптической кривой над полем называется множество решений уравнения

(3.4.3.1)

над полем вместе с дополнительной точкой , называемой точкой в бесконечности.

Представление эллиптической кривой в виде уравнения (3.4.3.1) носит название эллиптической кривой в форме Вейерштрасса.

Обозначим количество точек на эллиптической кривой через . Верхняя и нижняя границы для определяются теоремой Хассе:

. (3.4.3.2)

Зададим бинарную операцию на (в аддитивной записи) следующими правилами:

;

;

;

, где: (3.4.3.3)

и ;

, где:

и .

Множество точек эллиптической кривой с заданной таким образом операцией образует абелеву группу.

Если , то кривая называется суперсингулярной.

Эллиптическая не являющаяся суперсингулярной кривая над полем характеристики 2 задаётся следующим образом:

Пусть - целое число. Пусть . Эллиптической кривой над полем называется множество решений уравнения

(3.4.3.4)

над полем вместе с дополнительной точкой , называемой точкой в бесконечности.

Количество точек на кривой также определяется теоремой Хассе:

, (3.4.3.5)

где . Более того, чётно.

Операция сложения на в этом случае задаётся следующими правилами:

;

;

;

, где: (3.4.3.6)

и ;

, где:

и .

В этом случае множество точек эллиптической кривой с заданной таким образом операцией также образует абелеву группу.

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

Построим одностороннюю функцию, на основе которой можно будет создать криптографическую систему.

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

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

3.4.4 Алгоритм цифровой подписи диффи-хеллмана

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

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

k_S=(k₀, k₁). (3.4.4.1)

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

|k_S|=2|K|=2n_K. (3.4.4.2)

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

k_V=(C₀, C₁)=(E_k0(X₀), E_k1(X₁)) (3.4.4.3)

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

|k_V|=2|Х|=2n. (3.4.4.4)

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

s=S(t)=k_t. (3.4.4.5)

Алгоритм Ver проверки подписи состоит в проверке уравнения

E_kt(X_t)=C_t, (3.4.4.6)

которое, очевидно, должно выполняться для t. Получателю известны все используемые при этом величины.

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

. (3.4.4.7)

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

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

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

. (3.4.4.8)

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

Первый недостаток заключается в том, что данная схема позволяет подписать лишь один бит информации. В блоке большего размера придётся отдельно подписывать каждый бит, поэтому даже с учётом хэширования сообщения все компоненты подписи - секретный ключ, проверочная комбинация и собственно подпись получаются довольно большими по размеру и более чем на два порядка превосходят размер подписываемого блока. Предположим, что в схеме используется криптографический алгоритм Е_К с размером блока и ключа, соответственно n и n_К. Предположим также, что используется функция хэширования с размером выходного блока n_Н. Тогда размеры основных рабочих блоков будут следующими:

- размер ключа подписи - n_kS=2n_Hn_K;

- размер ключа проверки подписи - ;

- размер подписи - .

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

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

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

Пусть в нашем распоряжении также имеется некоторая функция отображения n-битовых блоков данных в n_K-битовые . Определим рекурсивную функцию «односторонней прокрутки» блока данных размером n бит k раз при помощи следующей формулы:

, (3.4.4.9)

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

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

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

; (3.4.4.10)

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

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

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

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

. (3.4.4.11)

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

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

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

; (3.4.4.12)

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

 (3.4.4.13)

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

. (3.4.4.14)

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

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

. (3.4.4.15)

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

(a) если T<T', то ,

(b) если T>T', то .

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

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

, (3.4.4.16)

, (3.4.4.17)

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

и . (3.4.4.18)

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

, где . (3.4.4.19)

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

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

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

бит, (3.4.4.20)

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

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

, (3.4.4.21)

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

. (3.4.4.22)

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

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

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

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

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

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

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

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

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

, (3.4.4.23)

где через обозначен результат конкатенации двух блоков данных А и В, а через Н(Х) - процедура вычисления хэш-функции блока данных Х.

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

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

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

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

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

4. РАЗРАБОТКА АЛГОРИТМА ЗАЩИТЫ ИНФОРМАЦИИ В СЕТИ АТМ

4.1 Постановка задачи