КЭК. Криптография с помощью эллиптических кривых
 Скачать 1.4 Mb.
|
Криптография с помощью эллиптических кривыхВыполнила: Яганина Ольга, студентка 231 группы Эллиптическая криптография - раздел криптографии, который изучает асимметричные криптосистемы, основанные на эллиптических кривых над конечными полями В общем случае уравнение эллиптической кривой E имеет вид: или (путём замены переменных) В качестве примера рассмотрим эллиптическую кривую E, уравнение которой имеет вид:y2 + y = x3 - x2 На кривой лежат четыре точки, координаты которых являются целыми числами. Это точки А (0, 0), В (1, -1), С (1, 0) и D (0, -1) Формы эллиптических кривых:Формы эллиптических кривых:Формы эллиптических кривых:Для определения операции сложения для точек на эллиптической кривой сделаем следующие предположения:• На плоскости существует бесконечно удаленная точка 0 ∈ E, в которой сходятся все вертикальные прямые • Будем считать, что касательная к кривой пересекает точку касания два раза • Если три точки эллиптической кривой лежат на прямой линии, то их сумма есть 0 Сложение точек на эллиптической кривойТочка О – бесконечность Р+(-Р)=О Точка «касания» - берется дважды (сложить с собой) Сложить 2 точки Р и Q Провести через них прямую Пересечение в 3-й точке R : P + Q + R = O Отобразить 3-ю точку относительно оси Х (обратный элемент) : P + Q = -R В криптографии с использованием эллиптических кривых все значения вычисляются по модулю p, где p является простым числом. Элементами являются пары неотрицательных целых чисел, которые меньше р (простое число) и удовлетворяют частному виду эллиптической кривой: y2 x3 + ax + b (mod p) Эллиптическая кривая: y2 x3 + ax + b (mod p) Такую кривую будем обозначать Ep (a,b) Числа а и b должны быть меньше р и должны удовлетворять условию 4a3 + 27b2 (mod p) ≠ 0 Вычисление точек на эллиптической кривой:1) Для каждого х ( 0 ≤ х ≤ р) вычисляется x3 + ax + b (mod p) 2) Выясняется: имеет ли это значение квадратный корень 3) Если корень – есть, то эти два значения (х,у) являются точками Ep (a,b) Свойства множества точек Ep (a,b) Р + 0 = Р 2) Если Р = (x,y), то Р + (x,-y) = 0 Точка (x,-y) является отрицательным значением точки Р и обозначается -Р 3)Если Р = (x1,y1) и Q = (x2,y2), где P ≠ Q, то P + Q = (x3,y3) определяется по следующим формулам: x3 λ2 - x1 - x2 (mod p) y3 λ (x1 - x3) - y1 (mod p) где, Свойства множества точек Ep (a,b) (y2 - y1)/(x2 - x1) , если P ≠ Q λ = { (3x12 + a)/2y1 , если P = Q Число λ есть угловой коэффициент секущей, проведенной через точки P = (x1, y1) и Q = (x2, y2). При P = Q секущая превращается в касательную. Задача, которую должен решить атакующий, есть задача "дискретного логарифмирования на эллиптической кривой». Даны точки P и Q на эллиптической кривой Ep (a,b). Необходимо найти коэффициент k < p такой, что P = k × Q Относительно легко вычислить P по данным k и Q, но довольно трудно вычислить k, зная P и Q. Способы использования эллиптических кривых. (Задача обмена ключами). Подготовительный этап.Выбирается простое число р ≈ 2180 и параметры a и b для уравнения эллиптической кривой. Это задает множество точек Ep (a,b). В Ep (a,b) выбирается генерирующая точка G = (x1,y1). При выборе G важно, чтобы наименьшее значение n, при котором n × G = 0, оказалось очень большим простым числом. Параметры Ep (a,b) и G криптосистемы являются параметрами, известными всем участникам. Расчет открытого ключа1) Участник А выбирает целое число nA, меньшее n. Это число является закрытым ключом участника А. 2) Участник А вычисляет открытый ключ PA = nA × G (это - точка на Ep (a,b)). 3) Участник В выбирает закрытый ключ nB и вычисляет открытый ключ PB. 4) Участники обмениваются открытыми ключами, и вычисляют общий секретный ключ K Расчет общего секретного ключаУчастник А: K = nA × PB Участник В: K = nВ × PА Общий секретный ключ – это пара чисел. Если ключ предполагается использовать в качестве сеансового ключа для алгоритма симметричного шифрования, то из этой пары необходимо создать одно значение. Алгоритм цифровой подписи на основе эллиптических кривых ECDSA (Elliptic Curve Digest Signature Algorithm)Создание ключей: 1) Выбирается эллиптическая кривая Ep (a,b). Число точек на ней должно делиться на большое целое n. 2) Выбирается точка Р Ep (a,b). 3) Выбирается случайное число d [1, n-1] 4) Вычисляется Q = d × P. 5) Закрытым ключом является d, открытым ключом - (E, P, n, Q). Создание подписи: 1) Выбирается случайное число k [1, n-1]. 2) Вычисляется k × P = (x1, y1) и r = x1 (mod n) Проверяется, чтобы r не было равно нулю, так как в этом случае подпись не будет зависеть от закрытого ключа. Если r = 0, то выбирается другое случайное число k. 3) Вычисляется k-1 mod n 4) Вычисляется s = k-1 (Н(M) + dr) (mod n) Проверяется, чтобы s не было равно нулю, так как в этом случае необходимого для проверки подписи числа s-1 mod n не существует. Если s = 0, то выбирается другое случайное число k. 5) Подписью для сообщения М является пара чисел (r,s). Шифрование/дешифрование с использованием эллиптических кривыхЗадача состоит в том, чтобы зашифровать сообщение M , которое может быть представлено в виде точки на эллиптической кривой .Участник B выбирает закрытый ключ и вычисляет открытый ключ .Чтобы зашифровать сообщение используется открытый ключ получателя Участник A выбирает случайное целое положительное число k и вычисляет зашифрованное сообщение , являющееся точкой на эллиптической кривой. Чтобы дешифровать сообщение, участник В умножает первую координату точки на свой закрытый ключ и вычитает результат из второй координаты: Pm + k × PB - nB × (k × G) = Pm + k × (nB × G) - nB × (k × G) = Pm Участник А зашифровал сообщение Pm добавлением к нему kxPB. Никто не знает значения k, поэтому, хотя PB и является открытым ключом, никто не знает k × PB. Противнику для восстановления сообщения придется вычислить k, зная G и k × G. Сделать это будет нелегко. Получатель также не знает k, но ему в качестве подсказки посылается k × G. Умножив k × G на свой закрытый ключ, получатель получит значение, которое было добавлено отправителем к незашифрованному сообщению. Тем самым получатель, не зная k, но имея свой закрытый ключ, может восстановить незашифрованное сообщение. Основные плюсы:Гораздо меньшая длина ключа по сравнению к «классической» асимметричной криптографией Скорость работы эллиптических алгоритмов гораздо выше, чем у классических. Это объясняется как размерами поля, так и применением более близкой для компьютеров структуры бинарного конечного поля Из-за маленькой длины ключа и высокой скорости работы, алгоритмы асимметричной криптографии на эллиптических кривых могут использоваться в смарт-картах и других устройствах с ограниченными вычислительными ресурсами Минусы:Все плюсы эллиптической криптографии вытекают из одного конкретного факта: для задачи дискретного логарифмирования на эллиптических кривых не существует субэкспоненциальных алгоритмов решения. Это позволяет уменьшить длину ключа и увеличить производительность. Однако если такие алгоритмы появятся, то это будет означать крах эллиптической криптографии Эллиптическая криптография — это очень сложно. Начиная с выбора эллиптической кривой и заканчивая генерацией ключей. При массовом переходе на эллиптику скорее всего обязательно будет большое количество ошибок и уязвимостей, которые уже отработаны для более привычных методов |