Криптографические протоколы на эллиптических кривых
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?ой и не требуется проводить предвычислений.
Эллиптическая криптография
В этом разделе будут рассмотрены реализации криптосистем с открытым ключом на основе эллиптических кривых.
Криптосистема с открытым ключом
Криптографическая система с открытым ключом (или асимметричный шифр) - система шифрования или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (незащищённому) каналу, и используется для проверки ЭЦП и для шифрования сообщения. Для шифрования или генерации подписи сообщения используется секретный (private) ключ, который известен только пользователю. А для проверки подписи и для дешифровки используется открытый (public) ключ, который генерируется на основе секретного ключа при помощи некоторой односторонней функции. То есть по значению открытого ключа вычислить секретный практически невозможно (используя современные вычислительные средства, за обозримый интервал времени), чем сгенерировать открытый ключ из секретного. Таким образом, открытый ключ можно сообщать кому угодно и даже публиковать его.
Рассмотрим общую схему работы системы шифрования с открытым ключом. Пусть сторона А хочет послать конфиденциальное сообщение m стороне B. А получает копию открытого ключа В - eB, и использует функцию шифрования Enc некоторого алгоритма шифрования для вычисления криптограммы c = Enc eB (m). Затем А передает криптограмму с стороне В, которая использует функцию дешифровки Dec со своим секретным ключом db для получения исходного сообщения m = Dec dB (c). Предполагается, что злоумышленник, зная только eb , не сможет расшифровать криптограмму c, т.е. eb может передаваться по незащищенному каналу. Важно лишь, чтобы сторона А получила неиспорченную копию ключа eВ, иначе сообщение будет зашифровано на неверном ключе и расшифровать его будет уже невозможно.
Теперь рассмотрим общую схему работы алгоритма цифровой подписи с открытым ключом. Пусть сторона А использует алгоритм генерации цифровой подписи Sign и ее секретный ключ dA для вычисления подписи сообщения s = Sing dA (m). При получении m и s, сторона В, которая имеет копию публичного ключа eA использует алгоритм заверения подписи для подтверждения того, что подпись s была действительно получена из сообщения m и секретного ключа dA. Так как dA - секретный ключ, который известен только стороне А, сторона В может быть уверена в том, что сообщение действительно получено от А. Более того, так как заверение требует только не подлежащих засекречиванию данных m и eA, то подпись s для сообщения m также может быть заверена третьей стороной для разрешения спора в том случае, если А отрицает акт подписи сообщения m. В отличие от обычной подписи документа, цифровая подпись s зависит от сообщения m, а значит, злоумышленник не сможет подделать подпись, просто приложив ее к другому сообщению m. Несмотря на то, что на открытый ключ eA не накладывается никаких ограничений секретности, необходимо чтобы заверяющая сторона В получила подлинную копию eA при заверении сообщения, предположительно подписанного стороной А.
Таким образом, криптография с открытым ключом решает три проблемы симметричной криптографии, а точнее проблемы распределения ключей, работы с ключами и проблему безотказности. Однако следует отметить, что реализация систем с открытым ключом несколько сложнее реализации систем симметричной криптографии. Также, операции с открытыми ключами занимают больше времени, чем операции в симметричном шифровании.
Шифр Эль-Гамаля на основе эллиптических кривых
Генерация ключа. Пусть P - точка эллиптической кривой E над полем G(p), имеющая порядок n. Тогда циклическая подгруппа E порожденная точкой P будет состоять из точек {O, P,2P,3P, . . .,(n?1)P}. Характеристика поля p, уравнение эллиптической кривой E, точка P и ее порядок n являются параметрами кривой. Секретным ключом является число d, которое выбирается случайно из интервала [1, n-1], а открытым ключом является точка Q = dP. Задача вычисления d по известным параметрам кривой и точке Q называется проблемой дискретного логарифма в группе точек эллиптической кривой (ECDLP). Ниже предоставлен алгоритм генерации ключевой пары ECC.
Вход: Параметры кривой (p, E, P, n).
Выход: Открытый ключ Q и секретный ключ d.
Алгоритм: 1. Выбрать d ? R [1,n?1].
. Вычислить Q = dP.
Вернуть: (Q,d)
Шифрование.
Открытый текст m представляется в виде точки M, а затем шифруется путем сложения с точкой kQ. Отправитель передает точку C1 = kP и C2 = M + kQ получателю, который использует свой секретный ключ d для вычисления dC1 = d(kP) = kQ и затем восстанавливает M = C2 - kq. Злоумышленник, желающий восстановить M, должен вычислить kQ. Проблема вычисления kQ при знании параметров кривой, Q и C1 = kP, является аналогом проблемы Диффи-Хеллмана для эллиптических кривых. Ниже предоставлен алгоритм шифрования.
Вход: Параметры кривой (p, E, P,n), открытый ключ Q, текст m.
Вывод: Криптограмма (C1,C2).
Алгоритм: 1. Представить сообщение m в виде точки M кривой E(Fp).
. Выбрать k ? R [1,n?1].
. Вычислить C1 = kP.
. Вычислить C2 = M +kQ.
Вернуть: (C1,C2).
А алгоритм дешифрования выгл?/p>