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

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

Эллиптические кривые являются надёжным инструментом, при помощи которого можно построить криптосистему с открытым ключом [2].

Определение

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

<math>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\}</math>

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

<math>E(F_p)=\{(X : Y : Z):\; ZY^2 = X^3 + AZ^2X + Z^3B;\; 4A^3 + 27B^2 \neq 0,\; \forall A, B \in F_p,\; Z \neq 0\} \cup \{O\}</math>

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

Сложение двух точек <math>P</math> и <math>Q</math> на эллиптической кривой легче всего понять при помощи геометрической иллюстрации.

ECClines.svg

В простейшем случае (1), когда <math>P \ne Q</math> сложение производится путём проведения прямой через суммируемые точки [6]. Данная прямая пересечёт эллиптическую кривую в третьей точке <math>R</math>. Тогда симметричную эй точку <math>-R</math> и называют суммой двух точек <math>P</math> и <math>Q</math> на эллиптической кривой.

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

Случай (2) отражает ситуацию, в которой прямая, проходящая через суммируемые точки оказалась касательной к эллиптической кривой. Здесь полагают, что в точке Q прямая не касается эллиптической кривой, а пересекает её в двух очень близких [7] точках так, что обе можно считать равными <math>Q</math>. Тогда можно сказать, что <math>Q + Q = -P</math>, другими словами <math>P + Q = -Q</math>

Особенность (3) в том, что получившаяся прямая параллельна оси ординат, вследствие чего третьей точки, которая бы принадлежала и прямой и эллиптической кривой не существует. Но, поскольку <math>Q = -P</math> получается, что <math>P + Q = O</math>

Последний случай (4) — комбинация (2) и (3). Получаем, что <math>P + P = O</math>[8].


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

Далее определим операцию умножения точек эллиптической кривой на число[9][10]. Пускай выбрана точка <math>P</math> на эллиптической кривой и целое число <math>k</math> длиной <math>n</math> бит. Затем путём <math>k</math>-кратного сложения точки <math>P</math> самой с собой получается точка <math>kP</math>, лежащая на той же эллиптической кривой, в силу свойств поля, в котором производится операция многократного сложения.

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

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

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

В 2008 году в статье Пьера-Алана Форке [11] была обнаружена уязвимость алгоритма Монтгомери.

Авторы отметили, что недостаток алгоритма Монтгомери заключается в том, что вычисление значения точки на кривой производится лишь на последней итерации цикла, а во время промежуточных шагов принадлежность полученной точки эллиптической кривой не подтверждается [11]. Отсюда возникает возможность для атаки по ошибке вычислений[12].

В статье[11] предлагается использовать вспомогательную кривую <math>E'</math>. Вводимая кривой является изоморфной основной кривой <math>E</math> в поле <math>F_{p^2}</math>, но не в <math>F_{p}</math>. Таким образом [11]:

<math>\forall x \in F_p: g(x) \equiv x^3 + ax + b \neq 0</math>,

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

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

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

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

В своем оригинальном варианте алгоритм Монтгомери не проводил проверку принадлежности результата исходной эллиптической кривой, вследствие чего злоумышленнику необходимо было вносить ошибку лишь в самом начале вычислений. Авторы статьи про атаку предложили простое решение данной проблемы, а именно проверку того, что результат принадлежит исходной кривой[11]. Таким образом алгоритм выглядит следующим образом: 

Input: k, P
Output: kP

1: compute kP
2: if kP is on the curve, i.e. <math>x^3 + ax + b</math> is a square:
3:     return kP
4: else:
5:     return Error

.

Эта мера оказалась недостаточной, поскольку далее авторы приводят способ преодоления данной проверки.[13]. Идея основана на изменении результата вычислений прямо перед проведением проверки. Абсцисса <math>x</math> результата вычислений <math>kP</math> может быть изменена злоумышленником при помощи побитового сложения <math>x\oplus\epsilon</math>, обозначаемая <math>kP\oplus\epsilon</math>, с вероятностью <math>1/2</math> принадлежащая кривой. Само значение <math>\epsilon</math> злоумышленнику неизвестно, но может быть определено из соображений, что вносимая ошибка изменяет только первые <math>s</math> регистров из <math>n</math>. За <math>2^s n/s</math> можно подобрать <math>\epsilon</math>, что довольно долго для больших значений <math>n</math>.

Но существует гораздо быстрый способом, который и предлагают использовать авторы[13]. Злоумышленнику достаточно двух шагов атаки по ошибкам вычислений[12]. Внеся в один и тот же результат различные ошибки <math>\epsilon</math> <math>\epsilon'</math> можно понять какие именно регистры были изменены, таким образом получив возможность обойти проверку, а далее решить задачу дискретного логарифмирования [14] для нахождения секретного ключа <math>k</math>.

А прямо перед окончанием вычислений вносится ещё одна ошибка, для перемещения точки обратно на основную кривую[13].

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

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

Простейшей идеей является проверка промежуточных значений <math>Q_0</math>[13]. Но поскольку все операции производятся в проективных координатах, непосредственное нахождение значения в точке на каждой итерации цикла будет вычислительно сложной задачей, что значительно снизит эффективность алгоритма, полученную за счёт отказа от <math>y</math>-координаты. Поэтому необходимы другие способы отражения атаки [10].

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

Для избавления от дорогостоящих вычислений, предлагается[16] оценивать значение точки <math>Q_0 = (x_0, y_0) = (X_0 : Y_0 : Z_0)</math> в проективных координатах, а именно <math>Y_0</math>. После этого с помощью всего одной операции инверсии получится нужное для проверки <math>y_0</math>. Для начала, формулу для вычисления значения <math>y_0</math> приводится к следующему виду[17], путём подстановки проективных координат точек <math>Q_0 = (X_0 : \;.\; : Z_0)</math> и <math>Q_1 = (X_1 : \;.\; : Z_1)</math>:

<math>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}</math>, где <math>(x, y)</math> — координаты точки <math>(Q_1 - Q_0)</math>
<math>y_0 = \dfrac{2BZ_1Z_0^2 + Z_1(AZ_0 + xX_0)(xZ_0 + X_0) - X_1(xZ_0 - X_0)^2}{2yZ_1Z_0^2} = \dfrac{Y_0'}{Z_0'}</math>

Далее с помощью одной операции инверсии получается искомое проверочное значение для <math>y_0</math>.

Дополнительно можно вычислить, <math>X_0' = 2yX_0Z_1Z_0</math> и произвести подстановку в уравнение кривой, получив проверочное соотношение:

<math>Z'(Y'^2 - BZ'^2) = X'(X'^2 + AZ')</math>

Алгоритм LOEDAR

Более эффективным способом отражения описанной выше атаки является алгоритм LOEDAR[18]. Авторы заявляют, что простейшей идеей являлась бы проверка того, что на каждом шаге выполнено равенство <math>Q_0 + P \equiv Q_1</math>. Однако проведение такой проверки в исходных координатах затруднительно, поскольку требует непосредственного вычисления <math>y</math>-координат всех трёх точек. В проективных координатах необходимо знать <math>Q_1 - P = (X_{Q_1 - P} : \;.\; : Z_{Q_1 - P})</math>, что также требует дополнительных вычислений

Предлагается использовать[18] «верификационную точку» <math>Q_v</math>. Особенность заключается в том, что все вычисления и проверки будут по-прежнему осуществляться в проективных координатах <math>(X : \;.\; : Z)</math>, поскольку на любом шаге алгоритма выполняется соотношение <math>Q_1 + Q_v = 2Q_0</math>. Таким образом алгоритм будет выглядеть следующим образом: 

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]

Примечания

Шаблон:Примечания

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Статья
  2. ↑ 2,0 2,1 Шаблон:Статья
  3. ↑ Шаблон:Книга
  4. ↑ Шаблон:Книга
  5. ↑ Шаблон:Статья
  6. ↑ Шаблон:Книга
  7. ↑ Шаблон:Книга
  8. ↑ Шаблон:Статья
  9. ↑ Шаблон:Статья
  10. ↑ 10,0 10,1 Шаблон:Статья
  11. ↑ 11,0 11,1 11,2 11,3 11,4 Шаблон:Статья
  12. ↑ 12,0 12,1 Шаблон:Статья
  13. ↑ 13,0 13,1 13,2 13,3 Шаблон:Статья
  14. ↑ Шаблон:Статья
  15. ↑ Шаблон:Статья
  16. ↑ Шаблон:Статья
  17. ↑ Шаблон:Статья
  18. ↑ 18,0 18,1 Шаблон:Статья
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Атака_по_ошибкам_вычислений_на_эллиптические_кривые,_использующие_алгоритм_Монтгомери&oldid=9048553