Разработка алгоритмов защиты информации в сетях АТМ
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?ывается по той же схеме, но при этом используется не само сообщение, а значение хэш-функции от него. Это существенным образом ускоряет выработку и верификацию ЭЦП.
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 и использующий ключ размером nK: |Х|=n, |K|=nK. Структура ключевой информации в схеме следующая: секретный ключ подписи kS выбирается как произвольная (случайная) пара ключей k0, k1 используемого блочного шифра:
kS=(k0, k1). (3.4.4.1)
Таким образом, размер ключа подписи равен удвоенному размеру ключа использованного блочного шифра:
|kS|=2|K|=2nK. (3.4.4.2)
Ключ проверки представляет собой результат шифрования двух блоков текста Х0 и Х1 с ключами k0 и k1 соответственно:
kV=(C0, C1)=(Ek0(X0), Ek1(X1)) (3.4.4.3)
где являющиеся параметром схемы блоки данных не секретны и известны проверяющей подпись стороне. Таким образом, размер ключа проверки подписи равен удвоенному размеру блока использованного блочного шифра:
|kV|=2|Х|=2n. (3.4.4.4)
Алгоритм Sig выработки цифровой подписи для бита t (t{0, 1}) заключается просто в выборе соответствующей половины из пары, составляющей секретный ключ подписи:
s=S(t)=kt. (3.4.4.5)
Алгоритм Ver проверки подписи состоит в проверке уравнения
Ekt(Xt)=Ct, (3.4.4.6)
которое, очевидно, дол