Исследователь из МГУ разработал алгоритм, повышающий эффективность средств защиты информации

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

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

 

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

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

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

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

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

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

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

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

Фото: Иллюстрации эллиптических кривых. Источник: Денис Хлебородов