Атака по ошибкам вычислений на эллиптические кривые, использующие алгоритм Монтгомери

Атака по ошибкам вычислений на эллиптические кривые, использующие алгоритм Монтгомери — это один из способов атаки по сторонним каналам , направленный на конкретный алгоритм скалярного умножения (алгоритм Монтгомери), использующийся в криптосистемах построенных на эллиптических кривых.

Краткие сведения об эллиптических кривых

Эллиптические кривые (ЭК) являются надежным инструментом, при помощи которого можно построить криптосистему с открытым ключом .

Определение

Предполагается, что существует конечное поле нечетной характеристики $p>3$, обозначаемое $F_{p}$. Тогда в поле $F_{p}\cup \{O\}$ может быть задана ЭК в форме Вейерштрасса:

$E(F_{p})=\{(x,y):\;y^{2}=x^{3}+Ax+B;\;4A^{3}+27B^{2}\neq 0,\;\forall A,B\in F_{p}\}\cup \{O\}$

Для удобства вычислений данный вид может быть преобразован переходом к проективным координатам Якоби. В таком случае ЭК будет иметь вид:

$E(F_{p})=\{(X:Y:Z):\;ZY^{2}=X^{3}+AZ^{2}X+Z^{3}B;\;4A^{3}+27B^{2}\neq 0,\;\forall A,B\in F_{p},\;Z\neq 0\}\cup \{O\}$

Сложение двух точек эллиптической кривой

Сложение двух точек $P$ и $Q$ на ЭК легче всего понять при помощи геометрической иллюстрации.

В простейшем случае (1), когда $P\neq Q$ сложение производится путем проведения прямой через суммируемые точки. Данная прямая пересечет ЭК в третьей точке $R$. Тогда симметричную эй точку $-R$ и называют суммой двух точек $P$ и $Q$ на ЭК.

Существуют и другие "специальные ситуации" (2–4), определение сложения в которых требует особого рассмотрения.

Скалярное умножение

Далее определим операцию умножения точек ЭК на число. Пускай выбрана точка $P$ на ЭК и целое число $k$ длиной $n$ бит. Затем путем $k$-кратного сложения точки $P$ самой с собой получается точка $kP$, лежащая на той же ЭК, в силу свойств поля, в котором производится операция многократного сложения.

Пример простейшего алгоритма скалярного умножения:

Input: k, P
Output: kP

1: Q = P
2: for i = n-2 down to 0:
3:     Q = 2Q
4:     if k[i] == 1:
5:         Q = Q + P
6: return Q

Алгоритм Монтгомери

Недостатки предыдущих алгоритмов

Описанный выше алгоритм скалярного умножения не рекомендуется использовать при просторении криптосистем на ЭК, поскольку он подвержен атаке по энергопотреблению . Шаги 3: и 5: позволяют злоумышленнику, перехватывающему значения $Q$ на очередной итерации цикла, побитово восстановить значение секретного ключа $k$.

Аналогичным проблемам подвержены более сложные алгоритмы скалярного умножения, использующие $y$-координату. Существует множество вариантов атак по ошибкам вычисления. Например можно применять атаку смены знака .

Описание алгоритма Монтгомери

Монтгомери предложил алгоритм , в котором не требуется использование $y$-координаты, что позволило значительно ускорить создание открытого ключа, а также полностью защититься от атак по энергопотреблению:

Input: k, P
Output: kP

1: Q[0] = P, Q[1] = 2P
2: for i = k-2 down to 0:
3:     Q[1 - k[i]] = Q[0] + Q[1]
4:     Q[k[i]] = 2Q[k[i]]
5: return Q[0]

Предлагается в самом начале помимо точки $Q_{0}=P$ рассчитывалать также точку $Q_{1}=2P$. Основная идея заключается в том, что во время очередной итерации цикла разница между точками $Q_{0}$ и $Q_{1}$ остается неизменно равной $P$. Это позволяет при помощи проективынх координат быстро вычислять значение в точках $(X_{Q_{0}+Q_{1}}:\;.\;:Z_{Q_{0}+Q_{1}})$ и $(X_{2Q_{0}}:\;.\;:Z_{2Q_{0}})$, с помощью которых подновляются значения $Q_{0}$ и $Q_{1}$. В самом же конце используя $(X_{kP}:\;.\;:Z_{kP})$ вычисляется значение открытого ключа $kP$.

В дальнейшем будет показано, что главная особенность алгоритма оказалась слабым местом, дающим возможность для атаки и расшифровки секретного ключа.

Особенность реализации

Подсчет $Q_{0}$ и $Q_{1}$ на очередном шаге алгоритма заслуживает отдельного внимания. Поскольку Монтгомери отказывается от использования $y$-координаты необходимо иметь точный порядок действий для вычисления проективных координат на очередной итерации.

В статье приводится полное подробное описание вычисления проективных координат, получающихся удвоением и суммированием соответствующих значений. Всего требуется 18 операций сложения, 13 суммирования и 4 возведения в квадрат для случая $A\neq -3$, и, соответственно, 23 сложения, 11 суммирования и 4 возведения в квадрат иначе.

Области применения

Алгоритм Монтгомери применяется как в протоколе Диффи-Хэлмана, так и в алгоритмах электронной подписи, в случае, когда оба строятся на эллиптических кривых (ECDH и ECDSA соответственно). В обоих случаях –– это вычисление открытых ключей агентов, собирающихся обмениваться информацией по незащищенному каналу.

Основным преимуществом криптосистемы, использующей ЭК, является относительно небольшая длина закрытого ключа (минимум 163 бита). Для примера в алгоритме RSA минимальная длина секретного ключа составляет 1024 бит. Данная возможность появляется благодаря особенности вычисления открытого ключа, задача дискретного логарифмирования для которого решается намного сложнее, чем для алгоритмов, построенных на целых числах.

Предложенная атака

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

В статье предлагается использовать вспомогательную ЭК $E'$. Вводимая кривая является изоморфной основной ЭК $E$ в поле $F_{p^{2}}$, но не в $F_{p}$. Таким образом:

$\forall x\in F_{p}:g(x)\equiv x^{3}+ax+b\neq 0$,

если $g(x)$ является квадратичным остатком, то $x$ будет являться абсциссой точки на $E$.

В противном случае существует две возможности:

1. Рассмотреть новую группу точек на $E$ таких что $y\in F_{p^{2}}$
2. Использовать абсциссу точки на кривой $E'$, получая то же самое значение $y$

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

Учитывая особенности алгоритма Монтгомери такой перенос будет незаметным с точки зрения вычислений. Дополнительно будет пройдена одна из самых часто встречающихся проверок: принадлежность итоговой точки исходной ЭК.

Способы отражения атаки

Простейшей идеей является проверка промежуточных значений $Q_{0}$. Но поскольку все операции производятся в проективных координатах, непосредственное нахождение значения в точке на каждой итерации цикла будет вычислительно сложной задачей, что значительно снизит эффективность алгоритма, полученную за счет отказа от $y$-координаты. Поэтому необходимы другие способы отражения атаки.

Защита Эбейд-Ламберта

Для избавления от дорогостоящих вычислений, предлагается оценивать значение точки $Q_{0}=(x_{0},y_{0})=(X_{0}:Y_{0}:Z_{0})$ в проективных координатах, а именно $Y_{0}$. После этого с помощью всего одной операции инверсии получится нужное для проверки $y_{0}$. Для начала, формулу для вычисления значения $y_{0}$ приводится к следующему виду , путем подстановки проективных координат точек $Q_{0}=(X_{0}:\;.\;:Z_{0})$ и $Q_{1}=(X_{1}:\;.\;:Z_{1})$:

$y_{0}={\dfrac {2B+(A+x{\dfrac {X_{0}}{Z_{0}}})(x+{\dfrac {X_{0}}{Z_{0}}})-{\dfrac {X_{1}}{Z_{1}}}(x-{\dfrac {X_{0}}{Z_{0}}})^{2}}{2y}}$, где $(x,y)$ -- координаты точки $(Q_{1}-Q_{0})$

$y_{0}={\dfrac {2BZ_{1}Z_{0}^{2}+Z_{1}(AZ_{0}+xX_{0})(xZ_{0}+X_{0})-X_{1}(xZ_{0}-X_{0})^{2}}{2yZ_{1}Z_{0}^{2}}}={\dfrac {Y_{0}'}{Z_{0}'}}$

Далее с помощью одной операции инверсии получается искомое проверочное значение для $y_{0}$.

Дополнительно можно вычислить, $X_{0}'=2yX_{0}Z_{1}Z_{0}$ и произвести подстановку в уравнение ЭК, получив проверочное соотношение:

$Z'(Y'^{2}-BZ'^{2})=X'(X'^{2}+AZ')$

Алгоритм LOEDAR

Более эффективным способом отражения описанной выше атаки является алгоритм LOEDAR . Авторы заявляют, что простейшей идеей являлась бы проверка того, что на каждом шаге выполнено равенство $Q_{0}+P\equiv Q_{1}$. Однако проведение такой проверки в исходных координатах затруднительно, поскольку требует непосредственного вычисления $y$-координат всех трех точек. В проективных же координатах необходимо знать $Q_{1}-P=(X_{Q_{1}-P}:\;.\;:Z_{Q_{1}-P})$, что также требует дополнительных вычислений

Предлагается использовать "верификационную точку" $Q_{v}$. Особенность заключается в том, что все вычисления и проверки будут по-прежнему осуществляться в проективных координатах $(X:\;.\;:Z)$, поскольку на любом шаге алгоритма выполняется соотношение $Q_{1}+Q_{v}=2Q_{0}$. Таким образом алгоритм будет выглядеть следующим образом:

Input: k, P
Output: kP
Commentary: Q[2] := Q_v

1: Q[0] = P, Q[1] = 2P, Q[2] = 0
2: for i = k-2 down to 0:
3:     Q[1 - k[i]] = Q[0] + Q[1]
4:     Q[k[i]] = 2Q[k[i]]
5:     Q[2] = Q[2] + Q[k[i]]
6:     # verification part
7:     (Q[2] + Q[1] == 2Q[0]) ? continue : break     
8: return Q[0]