На эллиптической кривой имеем
- добавление точки $С:=А+В$ определено для любых двух точек $А$ и $В$ кривой (часто со специальными правилами для $А=В$ или некоторые специальные точки, в зависимости от системы координат).
- нейтральный $\infty$ такой, что $A+\infty=\infty+A=A$ для всех $А$ на кривой (включая $\infty$)
- противоположный $-А$ любой $А$ на кривой такой, что $А+(-А)=(-А)+А=\infty$ (с $\infty$ это собственная противоположность).
Сложение точек ассоциативно и коммутативно.
Отсюда мы можем определить умножение точки на целое число $i\in\mathbb Z$ (также известный как скалярное умножение), как
$$i\times A\underset{\text{def}}=\begin{case}
\infty&\text{если}i=0\
((i-1)\times A)+A&\text{если}i>0\
(-i)\times (-A)&\text{если}i<0
\end{случаи}$$
Отсюда следует, что для всех $А$ и $В$ на кривой (включая $\infty$) и все целые числа $я$, $j$, он держит
$$\begin{выравнивание}
(i+j)\times A&=(i\times A)+(j\times A)\
я\раз(А+В)&=(я\раз А)+(я\раз В)\
(i\times j)\times A&=i\times (j\times A)\
\end{выравнивание}$$
где в приведенном выше, верхнем левом сложении и нижнем левом умножении находятся в $\mathbb Z$, а все остальные операции — это сложение точек или умножение точек на целое число.
Когда мы говорим об умножении в криптографии на основе эллиптических кривых, чаще всего это умножение на целое число.
Чтобы определить умножение точек, нам нужно обозначить конкретную точку $G$ и ограничиться точками $А$ который можно получить как $A=а\умножить на G$ для некоторого целого числа $a\in\mathbb Z$. Они образуют подгруппу кривой. Многие группы, используемые в криптографии на основе эллиптических кривых, являются циклическими, т. е. существуют $G$ таким образом, что любая точка группы может быть получена таким образом. Для некоторых кривых (с простым числом точек, включая $\infty$, например secp256k1 или secp384r1), любая точка $G$ Кроме как $\infty$ можно использовать, и все точки кривой имеют такую форму $A=а\умножить на G$.
Для эллиптических кривых на конечном поле, используемых в криптографии, существует некоторое минимальное строго положительное целое число. $n$ такой, что $n\раз G=\infty$ (получатель чего-то $G$), а также порядок (количество элементов) указанной подгруппы. Для любой $А$ в этой подгруппе однозначно определен $а\в[0,n)$ с $A=а\умножить на G$.
Затем мы можем определить произведение точек $A=а\умножить на G$ и $B=b\умножить на G$ с $а,б\in[0,n)$ как точка
$$A\times B\underset{\text{def}}=(a\times b\bmod n)\times G$$
Произведение точек эллиптической кривой наследует ассоциативность, коммутативность, нейтральность. $G$, из соответствующих свойств умножения в $\mathbb Z_n$. Распределяемость с.р.т. сложение точек выполняется. Также, $(я\раз А)\раз В=я\раз(А\раз В)$ выполняется для всех точек $А$, $В$ какой продукт определен, и все целые числа $я$.
Когда $n$ является простым (что верно для большинства кривых и образующих $G$ используется в ECC), любая точка $А$ кроме $\infty$ имеет обратный $А^{-1}$ такой, что $A\times A^{-1}=A^{-1}\times A=G$. Если $A=а\умножить на G$, тогда $A^{-1}=(a^{-1}\bmod n)\раз G$.
Обратите внимание, что это определение умножения зависит от выбора $G$, и для всей кривой только тогда, когда группа эллиптических кривых является циклической.
Также мы можем вычислить $C=A\раз B$ эффективно, если мы знаем $а$ с $A=а\умножить на G$ (как $C:=a\раз B$) или же знать $b$ с $B=b\умножить на G$ (как $C:=b\раз A$). Но в остальном самые известные алгоритмы стоили $\тета(\sqrt п)$ на стандартных компьютерах, таким образом, не полиномиальное время по сравнению с другими. битовый размер $n$.
