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

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

Определение Предполагается, что существует конечное поле нечётной характеристики , обозначаемое . Тогда в поле может быть задана ЭК в форме Вейерштрасса:

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

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

В простейшем случае (1), когда сложение производится путём проведения прямой через суммируемые точки . Данная прямая пересечёт эллиптическую кривую в третьей точке . Тогда симметричную эй точку и называют суммой двух точек и на эллиптической кривой.

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

Случай (2) отражает ситуацию, в которой прямая, проходящая через суммируемые точки оказалась касательной к эллиптической кривой. Здесь полагают, что в точке Q прямая не касается эллиптической кривой, а пересекает её в двух очень близких

точках так, что обе можно считать равными . Тогда можно сказать, что , другими словами

Особенность (3) в том, что получившаяся прямая параллельна оси ординат, вследствие чего третьей точки, которая бы принадлежала и прямой и эллиптической кривой не существует. Но, поскольку получается, что

Последний случай (4) — комбинация (2) и (3). Получаем, что .

Скалярное умножение Далее определим операцию умножения точек эллиптической кривой на число. Пускай выбрана точка на эллиптической кривой и целое число длиной бит. Затем путём -кратного сложения точки самой с собой получается точка , лежащая на той же эллиптической кривой, в силу свойств поля, в котором производится операция многократного сложения.

Пример простейшего алгоритма скалярного умножения: 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 году в статье Пьера-Алана Форке

была обнаружена уязвимость алгоритма Монтгомери.

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

В статье предлагается использовать вспомогательную кривую . Вводимая кривой является изоморфной основной кривой в поле , но не в . Таким образом :

, если является квадратичным остатком, то будет являться абсциссой точки на .

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

Рассмотреть новую группу точек на таких что Использовать абсциссу точки на кривой , получая то же самое значение

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

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

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.

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

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

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

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

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

Защита Эбейд-Ламберта Для избавления от дорогостоящих вычислений, предлагается оценивать значение точки в проективных координатах, а именно . После этого с помощью всего одной операции инверсии получится нужное для проверки . Для начала, формулу для вычисления значения приводится к следующему виду, путём подстановки проективных координат точек и :

, где  — координаты точки

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

Дополнительно можно вычислить, и произвести подстановку в уравнение кривой, получив проверочное соотношение:

Алгоритм LOEDAR Более эффективным способом отражения описанной выше атаки является алгоритм LOEDAR. Авторы заявляют, что простейшей идеей являлась бы проверка того, что на каждом шаге выполнено равенство . Однако проведение такой проверки в исходных координатах затруднительно, поскольку требует непосредственного вычисления -координат всех трёх точек. В проективных координатах необходимо знать , что также требует дополнительных вычислений

Предлагается использовать «верификационную точку» . Особенность заключается в том, что все вычисления и проверки будут по-прежнему осуществляться в проективных координатах , поскольку на любом шаге алгоритма выполняется соотношение . Таким образом алгоритм будет выглядеть следующим образом: Input: k, P Output: kP Commentary: Q := Q_v

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

Примечания

Категория:Криптографические атаки