Применение метаэвристических алгоритмов псевдобулевой оптимизации к поиску линеаризующих множеств в криптоанализе криптографических генераторов

В статье рассматривается новый подход к построению атак типа «угадывай и определяй» на генераторы ключевого потока, основанный на понятии линеаризующего множества. Сложность атаки для конкретного линеаризующего множества оценивается как значение специально определённой псевдобулевой функции. Для решения задачи оптимизации псевдобулевой функции реализованы метаэвристические алгоритмы поиска: tabu search, генетический алгоритм, (1 + 1) эволюционный алгоритм, GBFS. Приведены оценки сложности атак указанного типа, которые были построены для поточных шифров A5/1 и ASG.