Криптографические протоколы на эллиптических кривых
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?дит следующим образом:
Вход: Параметры кривой (p, E, P,n), секретный ключ d, криптограмма (C1,C2).
Выход: Исходный текст m.
Алгоритм: 1. Вычислить M = C2 ? dC1, и вычислить m из M.
Вернуть: (m).
Данные, которые размещаются в некоторой точке эллиптической кривой, должны состоять из несколько меньшего числа бит, чем элемент конечного поля, над которым строится кривая. Несколько бит должны оставаться неопределенными, чтобы обеспечить возможность попадания на кривую.
Алгоритм цифровой подписи на основе эллиптических кривых
Схема цифровой подписи ECDSA состоит из четырех алгоритмов:
. Алгоритм генерации параметров эллиптической кривой.
. Алгоритм генерации пары ключей.
. Алгоритм генерации цифровой подписи, на вход которого подаются параметры эллиптической кривой, секретный ключ и сообщение для подписи.
. Алгоритм заверения подписи, на вход которого подаются параметры кривой, открытый ключ, сообщение и подпись.
Алгоритм генерации пары ключей аналогичен генерации пары ключей в шифре Эль-Гамаля. Однако для повышения криптостойкости схемы в нее следует добавить алгоритм заверения открытого ключа. Данный алгоритм проверяет, обладает ли открытый ключ некоторыми арифметическими свойствами, которые может использовать злоумышленник. Успешное выполнение этого алгоритма доказывает, что на его вход подан действительно публичный ключ данной схемы шифрования.
Заверение открытого ключа особенно важно в алгоритмах, основанных на алгоритме Диффи-Хеллмана, в которых сторона A создает общий секрет k, складывая свой секретный ключ d с открытым ключом стороны B, и затем использует k в некотором протоколе с симметричном ключом. Если B окажется злоумышленником, то он может выбрать открытый ключ таим образом, что использование этого ключ стороной А может помочь ему узнать некоторую информацию о секретном ключу A.
Вход: Параметры кривой D, открытый ключ Q.
Выход: Принятие или отвержение ключа Q.
Алгоритм: 1. Установить, что Q O.
. Убедиться, что x0 и y0 являются элементами поля GF(q) (то есть являются целыми числами из интервала [0,q ?1] если кривая задана над полем большой характеристики или последовательностями битов длины m, если кривая задана над расширением полем характеристики два GF(q=2m)).
. Убедиться, что подстановка координат Q в уравнение эллиптической кривой обращает его в верное равенство.
. Убедиться, что nQ O.
. Если хотя бы одна из проверок прошла неудачно, то вернуть (Invalid); иначе вернуть (Valid).
Алгоритм цифровой подписи на эллиптических кривых является аналогом алгоритма цифровой подписи DSA. Он является самым стандартизированным алгоритмом, использующим эллиптические кривые, и занесен в такие стандарты, как ANSI X9.62, FIPS 186-2, IEEE 1363-2000 и ISO/IEC 15946-2. В последующем описании алгоритма через H обозначается криптографическая хэш-функция, выходное значение которой не превышает числа n (если это условие не выполняется, то значения хэш-функции могут быть усечены).
Алгоритм генерации цифровой подписи:
Вход: Параметры эллиптической кривой D = (a, b, p), секретный ключ d, сообщение m, порождающая точка G и ее порядок q.
Выход: Подпись (r, s).
Алгоритм: 1. Выбрать k ? R [1,q?1].
. Вычислить kG = (x1, y1).
. Вычислить r = x1 mod q. Если r = 0 вернуться к шагу 1.
. Вычислить h = H(m).
. Вычислить s = k?1(h+d*r) mod q. Если s = 0 вернуться к шагу 1.
Вернуть: (r, s).
Алгоритм заверения цифровой подписи:
Вход: Параметры кривой D = (a, b, p), открытый ключ Q, сообщение m, подпись (r, s), порождающая точка G и ее порядок q.
Выход: Заверение или отвержение подписи.
Алгоритм: 1. Вычислить h = H(m).
. Вычислить w = s?1 mod q.
. Вычислить u1 = hw mod q и u2 = rw mod q.
. Вычислить Pver = (x1, y1) = u1*G +u2*Q.
5. Если Pver =О то вернуть (Reject the signature);
6. Вычислить v= x1 mod q.
7. Если v = r то вернуть (Accept the signature);
Иначе вернуть (Reject the signature).
Можно легко показать, что данный алгоритм действительно успешно заверяет цифровую подпись. Если подпись (r, s) сообщения m была действительно сгенерирована с использованием секретного ключа, то s ? k?1(h+dr) (mod q). Раскрывая скобки получим:
k ? s?1(h + dr) ? s?1h + s?1rd ? wh + wrd ? u1 + u2d (mod q).
Тогда Pver = u1*G +u2*Q = (u1 +u2d)*G = kG и значит v = r, что и требуется для заверения подписи.
Преимущества использования схем эллиптической криптографии
При сравнении асимметричных схем шифрования наиболее существенными являются следующие критерии:
. Функциональность. Предоставляет ли данная схема шифрования все необходимые возможности?
. Безопасность. Какие гарантии того, что данная схема шифрования является безопасной?
. Производительность. Работает ли данная схема шифрования за допустимое время?
Все три основных схемы шифрования RSA, DL и EC предоставляют базовый набор функций криптографии с открытым ключом - шифрование, ЭЦП и использование общего ключа. Безопасность данных алгоритмов в основном определяется трудностью математической проблемы, лежащей в их основе. Для алгоритма RSA это проблема факторизации целых чисел, для DL - проблема дискретного логарифмирования, а для EC - проблема дискретного логарифмирования для эллиптических кривых. Сложность этих задач непосредственно сказывается на прои