Электронная цифровая подпись Лекция по с/к «Методы защиты информации» Ливак Е.Н.

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

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

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

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

Напоминание В асимметричных криптосистемах (системах с открытым ключом) используется: 1) открытый ключ – для шифрования 2) соответствующий ему секретный – для расшифрования: E k1 (P) = C D k2 (C) = P, где k 1 – открытый ключ, k 2 – секретный ключ. E PC K1K1 D CP K2K2

Применение криптографии с открытым ключом для создания ЭЦП основано на шифровании сообщения секретным (закрытым) ключом, и расшифровании – открытым. E k1 (P) = C D k2 (C) = P где k 1 – секретный, k 2 – открытый ключ.

Протокол подписания документа 1. Алиса шифрует документ своим закрытым ключом (подписывает его) 2. Алиса посылает Бобу подписанный документ 3. Боб расшифровывает документ, используя открытый ключ Алисы (проверяя тем самым достоверность подписи)

Наиболее известны е схем ы создания ЭЦП DSA RSA Эль-Гамаля (ElGamal) Рабина Шнорра Диффи-Лампорта

Стойкость схем ЭЦП Стойкость распространенных схем ЭЦП основана на сложности решения частной задачи дискретного логарифмирования в простом поле GF(p). Задача эта формулируется следующим образом: заданы простые числа p, q и натуральное число g < p порядка q, то есть g q 1 (mod p); зная значение y = g x (mod p), – необходимо найти x Z.

DSA – алгоритм цифровых сигнатур Алгоритм с открытым ключом. Размер ключа – от 512 до 1024 бит. При проверке достоверности сигнатуры DSA работает в раз медленнее RSA. Используется только для ЭЦП, не для шифрования. DSS – стандарт США (1994) на основе DSA и алгоритме хэширования SHA-1.

Алгоритм DSA. Параметры Открытый ключ ( (p, q, g, y) p – простое число длиной от 512 до 1024 битов q – 160-битовый простой множитель p-1 g – = h (p-1)/q mod p, где h – любое число 1 y - = g x mod p (p-битовое число) Закрытый ключ (x) X - < q (160-битовое число)

Алгоритм DSA. Подпись сообщения 1. Алиса генерирует случайное число k, меньшее q 2. Алиса генерирует r = (g k mod p) mod q s = (k -1 (H(m) + x r )) mod q H(m) – хэш-функция 3. Алиса посылает Бобу свою подпись - (r, s)

Алгоритм DSA. Проверка подписи 1. Боб проверяет подпись Вычисляет w = s -1 mod q u 1 = (H(m) * w) mod q u 2 = (r w) mod q v = ((g u1 * y u2 ) mod p ) mod q 2. Если v = r, то подпись верна

Схема Эль-Гамаля Подписью к сообщению m является решение (r, s) уравнения g m y r r s (mod p), где p – простое число, g – первообразный корень y = g x mod p, x Z p-1. Открытым ключом является тройка (p, q, y), секретным ключом – x.

Алгоритм Эль-Гамаля Подпись создается по следующему алгоритму: 1) выбирается случайное k Z * p-1 ; 2) вычисляется r = g k mod p; 3) вычисляется s = k -1 (m – x r) mod (p-1).

Национальные стандарты ( реализовывают ЭЦП в простом поле) Стандарт США - Digital Signature Standard (принят в 1991 г. с последующими изменениями в 1993, 1996 г.) Российский стандарт цифровой подписи ГОСТ Р Стандарт Республики Беларусь – СТБ (1999 г.)

Недостатки существующих схем формирования ЭЦП 1) медленная работа алгоритмов формирования и проверки подписи; 2) ограничения на длину подписываемого сообщения.

Решение проблемы, связанной с ограничениями на длину – разбиение сообщения на фрагменты и подпись каждого фрагмента. Однако увеличение объема сообщения и времени выполнения процедур создания и проверки ЭЦП.

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

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

Построение функций хэширования Требуется, чтобы вычислительно трудным являлось решение следующих криптоаналитических задач: 1) по заданному y = h(x) определить x (односторонняя функция h); 2) для заданного x найти другое x, такое, что h(x) = h(x ) (свободная от коллизий функция h); 3) найти пару x, x (x x ), такую, что h(x) = h(x ) (строго свободная от коллизий функция h).

Значение хэш-функции также называют Хэш-код Функция (значение) свертки Профиль сообщения Дайджест сообщения Криптографическая контрольная сумма Цифровой отпечаток Код аутентичности сообщения Код обнаружения манипуляций

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

1. Функции хэширования (Алгоритмы создания дайджестов сообщений) Разработаны Рональдом Ривестом MD2 - Message Digest #2 Низкоскоростной, но очень надежный алгоритм, создающий 128-разрядные дайджесты данных любого объема. MD4 - Message Digest #4 (1990) Более скоростной, но менее надежный алгоритм, создающий 128-разрядные дайджесты данных любого объема. 512-битовые блоки. Есть дефекты. MD5 Message Digest #5 (1992) Версия MD4 с повышенной надежностью, преимущества также и в скорости. 128-разрядные дайджесты данных любого объема. Не устойчив к коллизиям!!! Не используется для долговременных ЭЦП

2. Функции хэширования (Алгоритмы создания дайджестов сообщений) SHA - Secure Hash Algorithm (1992) 160-разрядные хэш-код (дайджест). НЕ устойчив к коллизиям. 512-битовые блоки. SHA-1 - Secure Hash Algorithm 1 (1995) Модификация SHA. Исправлены недостатки. Решает проблему коллизий. MAC - Message Authentication Code HMAC При создании хэша (дайджеста) используется также секретный ключ. Использует 128-битную хэш-функцию.

Защищенная функция хэширования SHA–1 (Secure Hash Algorithm) каждый бит хэш-кода зависит от всех битов хэшируемых данных (практически невероятно, чтобы два набора входных данных породили один и тот же хэш-код) «сведения об успешных криптографических атаках на алгоритм SHA отсутствуют» Б. Шнайер

Защищенная функция хэширования SHA–1 (Secure Hash Algorithm) Основное отличие алгоритма SHA от других защищенных функций хэширования (MD2, MD4, MD5) – генерирование 160-битового хэш-кода (против 128-битового). Современные технологии распределенных вычислений и многопроцессорные компьютеры демонстрируют недостаточную защищенность 128-битовых хэш-кодов. «Кроме того, были разработаны сценарии целого ряда атак, демонстрирующих уязвимость MD5 в отношении современных методов криптоанализа» Задача поиска двух наборов входных данных с одинаковым значением хэш- функции имеет сложность O(2 80 ) Задача нахождения набора входных данных с заданным значением имеет сложность O(2 160 )

Основные характеристики SHA Длина хэш-кода бит Длина обрабатываемых блоков бит Число шагов алгоритма - 80 (4 раунда по 20 шагов) Максимальная длина хэшируемых данных Число базовых функций - 4 Число аддитивных констант - 4

Алгоритм SHA–1 1. На вход поступает k-битовый блок данных, где k < k-битовый блок дополняется так, чтобы его длина стала кратной 512 разрядам (данные обрабатываются 512-битовыми блоками). Структура дополнения следующая: (от 1 до 512 бит). 3. К полученному результату добавляется 64-битовое представление длины исходного блока данных. 4. Инициализируются пять 32-разрядных переменных: A = 0x B = 0xefcdab89 C = 0x98badcfe D = 0x E = 0xc3d2e1f0 5. Производится обработка 512-битовых блоков данных в 4 раунда по 20 операций каждый.

Схема одной операции SHA–1 eiei c i-1 b i-1 a i-1 d i-1 e i-1 didi cici bibi aiai

W t = (W t-3 W t-8 W t-14 W t-16 ) « 1 (16 t 79). Соответствие аддитивных констант K t и нелинейных функций F t номеру операции 80 операций = 4 раунда по 20 шагов Номер шага (t) Нелинейная функция (F t ) Аддитивная константа (K t ) 0 t 19(X Y) (( X) Z)0x5a = /2 20 t 39X Y Z0x6ed9eba1 = /2 40 t 59 ( X Y) (X Z) (Y Z) 0x8f1bbcdc = /2 60 t 79 X Y Z 0xca62c1d6 = /2

Алгоритм SHA–1 (продолжение) 6. Значения переменных a, b, c, d, e добавляются, соответственно, к A, B, C, D, E. 7. Обрабатывается следующий блок данных. 8. Окончательный результат получается конкатенацией значений A, B, C, D, E (32- битовые). На выходе получается 160-битовый хэш-код.

Создание ЭЦП СООБЩЕНИЕСООБЩЕНИЕ H E СООБЩЕНИЕСООБЩЕНИЕ К секретный

Проверка целостности СООБЩЕНИЕСООБЩЕНИЕ H D К открытый СравнениеВывод

Основные причины уязвимости ЭЦП 1) уязвимость алгоритма шифрования с открытым ключом, лежащего в основе технологии электронной подписи; 2) механизм генерации и распределения ключей; 3) ошибки реализации систем ЭЦП; 4) передача открытого ключа в одном конверте с электронной подписью ( в структуру ЭЦП, согласно международному стандарту CCITT X.509, входит не только открытый ключ отправителя, но и его имя, серийный номер ЭЦП, название и собственная ЭЦП уполномоченной организации, выдавшей набор секретного и открытого ключа).

Компрометация схем ЭЦП В настоящее время реализованы и опубликованы схемы механизмов взлома ЭЦП, основанные на генерации новой пары (открытый, секретный) ключей и включении нового открытого ключа в конверт ЭЦП

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

Задача дискретного логарифмирования в группе точек эллиптической кривой Задача формулируется следующим образом: – задана эллиптическая кривая E над полем GF(p), где p - простое число; – выбрана точка G, имеющая простой порядок q в группе точек кривой E; – зная точку kG необходимо восстановить натуральное число k.

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

На технике эллиптических кривых основаны Международная серия стандартов OSO/IEC Стандарт IEEE P1363 Новый стандарт РФ – – ГОСТ Р

Механизм генерации и распределения ключей распределение осуществляется двумя способами: 1) созданием центра генерации и распределения ключей; 2) прямым обменом ключами между абонентами. В первом случае компрометация центра приводит к компрометации всей передаваемой информации. Во втором случае – необходимо обеспечить подлинность каждого абонента.

Ненадежность практических реализаций алгоритмов ЭЦП Анализ уязвимостей существующих схем ЭЦП позволяет утверждать, что «число уязвимых точек ЭЦП, базирующейся на шифровании с открытым ключом, настолько велико, что целесообразность использования подобного метода вызывает большие сомнения» [Ивт И., Богданов В. Надежна ли цифровая подпись?].

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

Случайные числа Истинные случайные числа не должны быть предсказуемы. Генераторы случайных чисел выдают псевдослучайные числа (при каждом выполнении алгоритма генерации случайных чисел получим тот же самый список случайных чисел). Используют специальную аппаратуру. Unix (Linux) имеют специальный код в составе драйверов устройств нижнего уровня, который непрерывно собирает случайные сигналы клавиатурных вводов и других аппаратных устройств и предоставляет их приложениям в качестве источника случайных чисел.

РЕЗЮМЕ Алгоритмы формирования ЭЦП, базирующиеся на шифровании с открытым ключом, принципиально уязвимы. Эффективность используемых на практике схем формирования ЭЦП, основанных на криптографии с открытым ключом, с точки зрения быстродействия, является достаточно низкой. Современные практические реализации схем ЭЦП являются уязвимыми. «Будущего у электронных цифровых подписей пока нет» ?