Защита криптосистем, основанных на свойствах эллиптических кривых (ECCS), от временного анализа (ВА)

А. В. КОВАЛЕВ

Московский инженерно-физический институт (государственный университет)

ЗАЩИТА КРИПТОСИСТЕМ,
ОСНОВАННЫХ НА СВОЙСТВАХ ЭЛЛИПТИЧЕСКИХ КРИВЫХ (ECCS), ОТ ВРЕМЕННОГО АНАЛИЗА (ВА)

Рассматриваются методы противодействия временным атакам на реализацию эллиптических алгоритмов.

Суть временных атак на криптографические алгоритмы (КА) заключается в получении информации о ключе шифрования путем анализа времени выполнения тех или иных операций шифрования. Для асимметричных КА интерес представляет операция расшифрования, в которой используется секретный ключ. Если говорить об ECCS, то наибольшую опасность представляют операции умножения и инверсии в конечных полях. Надо заметить, что даже если злоумышленник не сможет определить весь ключ (например, если количество сообщений, которые он посылает жертве сильно ограничено), то полученная информация может быть эффективно использована для ускорения процедуры поиска ключа методом грубой силы, т. е. перебором.

Наиболее очевидный путь предотвращения ВА состоит в том, чтобы все действия занимали одно и то же время. Однако реализация этого принципа не так проста, как кажется на первый взгляд. Во-первых, это приведет к существенному (в несколько раз) падению производительности, а во-вторых, может сильно упростить так называемый мощностной криптоанализ. Другим универсальным средством, позволяющим усложнить проведение такой атаки, является введение «шума». Очевидно, в данном случае, речь идёт о временном шуме. Достаточно ввести в процедуру умножения (для ECCS) дополнительную операцию, занимающую случайное время от 0 до К единиц. Чем больше мы выберем величину К, тем больше понадобится сообщений для получения единицы информации о ключе. К сожалению, этот метод также может привести к упрощению мощностного анализа. Отметим также, что при реализации КА, устойчивых к ВА, следует избегать операций условного перехода, особенно если переход осуществляется в зависимости от каких-либо характеристик секретного ключа или открытого текста. Если отсутствует возможность избежать использования условного перехода, то в секции else желательно выполнить операцию, которая займёт примерно такое же время, как и операция в секции if. Следует особо отметить, что не следует применять циклы, число итераций в которых зависит от ключа или открытого текста. В ECCS есть две операции, которые легко могут быть подвержены ВА – умножение и инверсия. Выполнение этих операций занимает наибольшее количество времени при умножении точек на кривой. Умножение обычно реализуют с использованием табличного алгоритма, что позволяет не только исключить временные атаки на данную операцию, но и существенно увеличить производительность. ECCS часто строится по аналогии с криптосистемой Эль-Гамаля, только с использованием операции умножения точек кривой вместо модульного возведения в степень. Таким образом, расшифрование включает две операции: G’ = ya и m’ = b - G’ = m. Операция вычитания точек кривой относительно проста и легко может быть безопасно реализована. А операция G’ = ya представляет собой последовательность операций умножения точки кривой на два и сложения точек. Реализация умножения точек P и k может выглядеть так [1]:

bit_count--;

copy_point(p, r); /* first bit always set */

while (bit_count > 0)

{ edbl(r, &temp, curv);

bit_count--;

switch (blncd[bit_count])

{ case 1: esum (p, &temp, r, curv);

break;

case -1: esub (&temp, p, r, curv);

break;

case 0: copy_point (&temp, r);

}

}

Здесь используется так называемое «сбалансированное» представление P, то есть в троичной записи P присутствуют символы 0, -1, 1. Такое представление позволяет ускорить операции умножения точки на два и сложение точек за счёт того, что в записи числа становится больше нулей [1]. Анализ этого кода позволяет сделать вывод, что время выполнения умножения будет зависеть от веса k по Хеммингу, однако узнать ключ не представляется возможным, ведь при расшифровании различных сообщений время выполнения не будет меняться, а значит злоумышленник не получит какой-либо информации, кроме общего времени выполнения. Информация о ключе расшифрования может быть получена при помощи ВА только в том случае, если время выполнения функций edbl, esum или esub будет зависеть от k, однако выше мы показали, что табличная реализация умножения позволяет сделать время выполнения независимым от значений операндов. И действительно, в [2] показано, что реализация ECCS, предложенная в [1], практически не подвержена ВА. Однако небольшие временные отклонения всё же имеют место и связаны, скорее всего, с реализацией других функций. Для минимизации этого эффекта следует просто привести весь код в соответствие с вышеуказанными рекомендациями. Это не сильно скажется на производительности. Другим кардинальным решением является «маскирование». Например, умножение может производиться следующим образом: dy1 = (d + x)y1 – xy1, где x – случайное число. Если каждый раз при расшифровании будет выбрано новое значение x, то временная атака на операцию умножения будет невозможна.

Список литературы

1.  M. Rosing. Implementing Elliptic Curve Cryptography. Manning Publications Co. 1998.

2.  M. Mah, M. Neve, E. Peeters, Z. Lu. Timing attack on elliptic curve cryptography. 2001.