Сотрудник МГУ имени М.В. Ломоносова разработал алгоритм, который позволит повысить скорость вычисления криптографических преобразований на основе эллиптических кривых. Особенность алгоритма в том, что при этом он будет потреблять мало вычислительных ресурсов. Результаты исследований были опубликованы в журнале Applied Mathematics and Computation.

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

«В результате исследования был найден алгоритм и установлены различные параметры его работы, при которых, в зависимости от объема доступной памяти и величины скаляра, он позволяет с наименьшими вычислительными затратами выполнять основную операцию на эллиптической кривой — скалярное умножения точки», — рассказал автор статьи, кандидат физико-математических наук Денис Хлебородов.

Новый алгоритм основан на методе несовместного представления скаляра с окном, который относится к классу алгоритмов с предвычислениями. Предвычисления — это вычисления, которые выполняются однократно до основной части работы, и их результаты при этом сохраняются в памяти. Основное преимущество алгоритмов с предвычислениями — это возможность разделить вычисления на две части. Первая часть — это сами предвычисления, а во второй части — многократно проводимые новые вычисления, для которых используются уже полученные результаты.

Денис Хлебородов также сравнил свою разработку с другим эффективным алгоритмом, который основан на том же методе. Среднюю вычислительную сложность этапа предвычислений он смог снизить на 5-46 %, а основного этапа — на 4-22 % в зависимости от входа.

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

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