Наташа Маркова

Эксперт в области криптографии Дэниэл Бернштейн опубликовал новую библиотеку djbsort

Среди ее достоинств высокая скорость сортировки в памяти и использование простых арифметических инструкций без условного ветвления.

1293

Эксперт в области криптографии и создания защищенного ПО Дэниэл Бернштейн (Daniel J. Bernstein), создавший qmail, djbdns, NaCl, Ed25519, Curve25519 и ChaCha20-Poly1305, опубликовал новую библиотеку djbsort с высокопроизводительным алгоритмом сортировки массивов целых чисел.

Достоинства

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

  • djbsort опережает аналоги по скорости сортировки в памяти. Например, djbsort при сортировке 1024 32-разрядных знаковых целых чисел расходует 2,5 цикла CPU на байт данных независимо от содержимого массива, в то время как библиотека Intel IPP с оптимизациями на базе AVX расходует около 32 циклов на байт;
  • время сортировки не зависит от содержимого массива, что исключает методы анализа содержимого по сторонним каналам;
  • в djbsort используются только простые арифметические инструкции без условного ветвления;
  • в библиотеке есть инструменты для верификации корректности сортировки для всех возможных вариантов массивов заданного размера. Среди них — утилиты unroller для раскрутки программы сортировки массивов заданного размера, minmax для преобразования программы в набор операторов «min» и «max», а также decompose для подтверждения корректности программы min-max.

Ограничения

  • оптимизация только для CPU с поддержкой инструкций AVX2;
  • сортировка только знаковых 32-разрядных целых чисел с адаптацией для сортировки 16- и 64-разрядных целых, а также для чисел с плавающей запятой;
  • ограничение размера сортируемого массива размером памяти;
  • использование только одного ядра CPU при сортировке;
  • отсутствие проверки целостности данных в памяти при верификации;
  • запуск верификации отдельно для массивов разного размера;
  • уменьшение скорости верификации при увеличении размера массива.

Напомним, что в апреле 2018 года IBM Research запустила библиотеку Adversarial Robustness Toolbox для защиты искусственного интеллекта.

Следите за новыми постами по любимым темам

Подпишитесь на интересующие вас теги, чтобы следить за новыми постами и быть в курсе событий.

Инструменты
Криптография
1293
Что думаете?
0 комментариев
Сначала интересные