Тема: Вычисление и оценки линейной сложности БИНАРНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

В поточном шифре бинарное сообщение шифруется путем добавле­ния поэлементно по модулю 2 псевдослучайной последователвности битов, в резулвтате чего битовая строка предположителвно трудно расшифровы­вается и, следователвно, может передаватвся по открытым каналам связи. Необходимо, чтобвх последователвности, полученнвхе таким образом, бвхли криптографически силвнвхми в том смвхсле, что их восстановление по из­вестному фрагменту последователвнвхх символов бвхло либо невозможно, либо требовало болвших ресурсов.
Известно, что такое свойство последователвности, как линейная слож­ности, значимо в определении криптографически сильных последователь­ностей.
Данная работа посвящена исследованию задачи нахождения к-error линейной сложности бинарной последовательности и методов ее решения. При этом написаны программы нахождения точного решения к-error ли­нейной сложности для следующих частных случаев:
1. к = 0 (Berlekamp-Massey Algorithm, [1]);
2. к = 2П, где п — целое число (Stamp,Martin, [2]).
Основной целью работы является применение к рассматриваемой за­даче одного из приближенных алгоритмов (а именно — генетического) и нахождение приближенного решения задачи при оптимальных значениях параметров.
Кроме того, проводится сравнение операторов генетического алгорит­ма, исследуется зависимость полученных результатов от выбранных опера­торов и параметров метода. Алгоритм реализован на языке Python 3.5.
Купить

В данной работе был предложен генетический алгоритм для вычисле­ния к-error линейной сложности последовательности произвольной длины над конечным полем GF(2). Кратко перечислим основные результаты.
Реализованы различные методы для каждого эволюционного операто­ра (отбор, кроссовер, мутация) и исследован наилучший выбор параметров для этой задачи.
В настоящей работе рассмотрены следующие типы операторов:
• отбор родителей:
• турнир;
• метод рулетки;
• кроссовер:
• специальный тип одноточечного кроссовера;
• специальный тип кроссовера, использующий целевую функцию;
• мутация:
• простая случайная мутация;
• мутация с переменной частотой.
Вычислительные эксперименты показали, что генетический алгоритм дает хорошие результаты для рассмотренной задачи. Например, для после­довательностей длины 28 следующая схема представляется оптимальной:
• среднее число популяций, 2000;
• среднее количество особей в популяции, 150;
• отбор родителей методом рулетки;
• специальный тип кроссовера, использующий целевую функцию, с ве­роятностью 0,7;
• специальный тип одноточечного кроссовера с вероятностью 0,3;
• мутация с переменной частотой с вероятностью 0,3.
С предложенными параметрами алгоритм выдает приближенное зна­чение fc-error линейной сложности, которая в большинстве построенных примерах всего на 14% выше точного значения.
Все результаты получены с помощью программы, с которой можно ознакомиться по ссылке https://yadi.Sk/d/pstEP6aB3JRUdY/2017.
В продолжение данной работы можно рассмотреть другие потенци­ально эффективные стратегии. Например, в работе [7] в качестве основно­го оператора отбора родителей выбран элитарный отбор 25%-го уровня. В нем 25% лучших особей текущей популяции автоматически переходят в следующую популяцию. В качестве кроссовера можно рассматривать, на­пример, специальный тип двухточечного кроссовера, работающий по тому же принципу, что и кроссовер SSPX (см. пункт 3.3.2).
Купить