Оценки стойкости шифров семейства Trivium к криптоанализу на основе алгоритмов решения проблемы булевой выполнимости

Представлены результаты криптоанализа трёх поточных шифров семейства Trivium (Bivium, Trivium toy, Bivium toy). Криптоанализ осуществляется за счёт сведения обращения соответствующих дискретных функций к задаче о булевой выполнимости (SAT). Криптоанализ неослабленного шифра Bivium toy удалось осуществить на персональном компьютере. Задачи криптоанализа шифров Bivium и Trivium toy оказались более сложными, в связи с чем исследованы их ослабленные варианты. Соответствующие SAT-задачи были решены на вычислительном кластере и проекте добровольных распределённых вычислений SAT@home. При этом использована предложенная ранее техника распараллеливания по данным, согласно которой из множества переменных пропозициональной кодировки рассматриваемой задачи специальным образом выбирается некоторое подмножество, по которому исходная задача разбивается на независимые подзадачи.