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

Эксперт в области криптографии и создания защищенного ПО Дэниэл Бернштейн (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 для защиты искусственного интеллекта.

Источник: OpenNET