АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Математические понятия

Читайте также:
  1. I. ОСНОВНЫЕ ПОНЯТИЯ (ТЕРМИНЫ) ЭКОЛОГИИ. ЕЕ СИСТЕМНОСТЬ
  2. III.I. ПОНЯТИЯ «КАРТИНА МИРА» И «ПАРАДИГМА». ЕСТЕСТВЕННОНАУЧНАЯ И ФИЛОСОФСКАЯ КАРТИНЫ МИРА.
  3. VIII.1. Общие понятия обязательственного права
  4. Абстрактное речевое мышление, понятия, умозаключения.
  5. Базовые понятия предметного поля социальной информатики
  6. Базовые понятия языка Пролог
  7. Бальнеология. Понятия и определения
  8. Бухгалтерский учет: понятия, объекты учета, принципы, основные задачи и организация
  9. В защиту понятия мотивации
  10. Важнейшие понятия в системе денежного обращения
  11. ВАЖНЕЙШИЕ ТЕРМИНЫ И ПОНЯТИЯ
  12. Вопрос 6. Какое определение понятия «охрана труда» будет верным?

Преимущество подхода на основе эллиптических кривых в сравнении с задачей факторизации числа, используемой в RSA, или задачей целочисленного логарифмирования, применяемой в алгоритме Диффи-Хеллмана и в DSS, заключается в том, что в данном случае обеспечивается эквивалентная защита при меньшей длине ключа.

В общем случае уравнение эллиптической кривой Е имеет вид:

y2 + axy + by = x3 + cx2 + dx + e

В качестве примера рассмотрим эллиптическую кривую Е, уравнение которой имеет вид:

y2 + y = x3 - x2

На этой кривой лежат только четыре точки, координаты которых являются целыми числами. Это точки

А (0, 0), В (1, -1), С (1, 0) и D (0, -1)


Рис. 1. Пример эллиптической кривой с четырьмя точками

 

Для определения операции сложения для точек на эллиптической кривой сделаем следующие предположения:

  • На плоскости существует бесконечно удаленная точка 0 Е, в которой сходятся все вертикальные прямые.
  • Будем считать, что касательная к кривой пересекает точку касания два раза.
  • Если три точки эллиптической кривой лежат на прямой линии, то их сумма есть 0.


Рис. 2. Сложение точек на эллиптической кривой

 

Введем следующие правила сложения точек на эллиптической кривой:

  • Точка 0 выступает в роли нулевого элемента. Так, 0 = -0 и для любой точки Р на эллиптической кривой Р + 0 = Р.
  • Вертикальная линия пересекает кривую в двух точках с одной и той же координатой х - скажем, S = (x, y) и T = (x, -y). Эта прямая пересекает кривую и в бесконечно удаленной точке. Поэтому Р1 + Р2 + 0 = 0 и Р1 = -Р2.
  • Чтобы сложить две точки P и Q (см. рисунок 11.2) с разными координатами х, следует провести через эти точки прямую и найти точку пересечения ее с эллиптической кривой. Если прямая не является касательной к кривой в точках P или Q, то существует только одна такая точка, обозначим ее S. Согласно нашему предположению

P + Q + S = О

Следовательно,

P + Q = -SилиP + Q = T

Если прямая является касательной к кривой в какой-либо из точек P или Q, то в этом случае следует положить S = P или S = Q соответственно.

  • Чтобы удвоить точку Q, следует провести касательную в точке Q и найти другую точку пересечения S с эллиптической кривой. Тогда Q + Q = 2 × Q = -S.

Введенная таким образом операция сложения подчиняется всем обычным правилам сложения, в частности коммутативному и ассоциативному законам. Умножение точки Р эллиптической кривой на положительное число k определяется как сумма k точек Р.

В криптографии с использованием эллиптических кривых все значения вычисляются по модулю р, где р является простым числом. Элементами данной эллиптической кривой являются пары неотрицательных целых чисел, которые меньше р и удовлетворяют частному виду эллиптической кривой:

y2 x3 + ax + b (mod p)

Такую кривую будем обозначать Ep (a,b). При этом числа а и b должны быть меньше р и должны удовлетворять условию 4a3 + 27b2 (mod p) 0. Множество точек на эллиптической кривой вычисляется следующим образом.

  1. Для каждого такого значения х, что 0 х р, вычисляется x3 + ax + b (mod p).
  2. Для каждого из полученных на предыдущем шаге значений выясняется, имеет ли это значение квадратный корень по модулю р. Если нет, то в Ep (a,b) нет точек с этим значением х. Если корень существует, имеется два значения y, соответствующих операции извлечения квадратного корня (исключением является случай, когда единственным значением оказывается y = 0). Эти значения (x,y) и будут точками Ep (a,b).

Множество точек Ep (a,b) обладает следующими свойствами:

  1. Р + 0 = Р
  2. Если Р = (x,y), то Р + (x,-y) = 0. Точка (x,-y) является отрицательным значением точки Р и обозначается -Р. Заметим, что (x,-y) лежит на эллиптической кривой и принадлежит Ep (a,b).
  3. Если Р = (x1,y1) и Q = (x2,y2), где P Q, то P + Q = (x3,y3) определяется по следующим формулам:
4. x3 λ2 - x1 - x2 (mod p)5. y3 λ (x1 - x3) - y1 (mod p)

где

(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.

Рассмотрим три способа использования эллиптических кривых в криптографии.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)