Мінімізація BITSLICED-представлення 4×4 S-Boxes на базі тернарної логічної інструкції

Abstract

Розглянуто методи і засоби для генерації програмно-орієнтованих bitsliced-описів бієктивних 4×4 S-Boxes зі зменшеною кількістю інструкцій на базі тернарної логічної інструкції. Згенеровані запропонованим методом bitsliced-описи дають змогу підвищити продуктивність та безпеку програмних імплементацій криптоалгоритмів, що використовують 4×4 S-Boxes на різноманітних процесорних архітектурах та під час проєктування апаратних засобів шифрування. Розроблено евристичний метод мінімізації, що використовує тернарну логічну інструкцію, яка доступна в х86-64 процесорах із підтримкою розширення системи команд AVX-512 та деяких GPU-процесорах. Завдяки поєднанню у методі різних евристичних технік (попередніх обчислень, вичерпному пошуку на певну глибину, уточнювальному пошуку) вдалося зменшити кількість вентилів у bitsliced-описах S-Boxes, порівняно з іншими відомими методами. Розроблено відповідне програмне забезпечення у вигляді утиліти мовою Python і протестовано її роботу на 225 S-Boxes різноманітних криптоалгоритмів. Встановлено, що розроблений метод у 91,1% випадках генерує bitsliced-опис із меншою кількістю тернарних інструкцій, порівняно із найкращим відомим сьогодні методом, реалізованим в утиліті sboxgates.The article is devoted to methods and tools for generating software-oriented bitsliced descriptions of bijective 4×4 S-Boxes with a reduced number of instructions based on a ternary logical instruction. Bitsliced descriptions generated by the proposed method make it possible to improve the performance and security of software implementations of crypto-algorithms using 4×4 S-Boxes on various processor architectures and when designing encryption hardware. The paper develops a heuristic method of minimization using a ternary logical instruction, which is available in x86-64 processors with support AVX-512 instruction system extension and some GPU processors. Thanks to the combination of various heuristic techniques (preliminary calculations, exhaustive search to a certain depth, refining search) in the method, it was possible to reduce the number of gates in bitsliced descriptions of S-Boxes compared to other known methods. The corresponding software in the form of a utility in the Python language was developed and its operation was tested on 225 S-Boxes of various crypto-algorithms. It was found that the developed method generates a bitsliced description with fewer ternary instructions in 91.1% of cases, compared to the best known method implemented in the sboxgates utility.