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