Введение 5
Глава 1. Линейная сложность 6
1.1. Определения и примеры 6
1.2. Обобщение линейной сложности 9
Глава 2. Задача нахождения к-error линейной сложности 11
2.1. Математическая постановка задачи 11
2.2. Вычисление к-error линейной сложности 13
Глава 3. Генетический алгоритм для вычисления к-error линейной сложности последовательности 14
3.1. Хромосомы 14
3.2. Целевая функция 15
3.3. Генетические операторах 16
3.3.1. Отбор родителей 16
3.3.2. Кроссовер 18
3.3.3. Мутация 22
Глава 4. Численные эксперименты и результаты 25
4.1. Тесты с последовательностями длины 2п 25
4.2. Сравнение типов отбора родителей 27
4.3. Сравнение типов кроссовера и мутации 28
4.4. Тестирование с различными параметрами алгоритма 31
4.4.1. Размер популяций и их количество 33
4.4.2. Вероятность мутации 35
Заключение 37
Список литературы 39
Приложение А. Алгоритм Берлекэмпа—Мэсси 40
Приложение Б. Алгоритм Stamp, Martin 41
В поточном шифре бинарное сообщение шифруется путем добавления поэлементно по модулю 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).
1. Massey J.L., Serconek S. Linear Complexity of Periodic Sequences // Lecture Notes in Computer Science. New York: Springer, 1996. V. 1109, P. 358-371.
2. Stamp M., Clyde F.M. An Algorithm for the fc-Error Linear Complexity of Binary Sequences with Period 2n // IEEE Transactions on Information Theory. 1993. V. 39, № 4, P. 1398-1401.
3. Xiao G., Wei S., Lam K.Y., Imamura K. A fast algorithms for determining the linear complexity of a sequence with period 2n over GF(q)// IEEE Transactions on Information Theory. 2000, V. 46, A2 6, P. 2203-2206.
4. Rueppel R.A. Analysis and Design of Stream Ciphers. Berlin: Springer-Verlag. 1986.
5. Menezes P., van Oorshot P., Vanstone S. Stream Ciphers// Handbook of Applied Cryptography. CRC Press. 1996. P. 191-221.
6. Ding C., Xiao C., Shan W. The Stability Theory of Stream Ciphers // Lecture Notes in Computer Science. Heidelberg: Springer-Verlag. 1992.
7. Alecu A., Salagean A.M. A genetic algorithm for computing the fc-error linear complexity of cryptographic sequences // IEEE Congress on Evolutionary Computation. 2007. P. 3569-3576.
8. Games R.A., Chan A.H. A Fast Algorithm for Determining the Complexity of a Binary Sequence with Period 2n // IEEE Transactions on Information Theory. 1983. V. 29, № 1, P. 144-146.
9. Нгуен M.X. Применение генетического алгоритма для задачи нахождения покрытия множества // Динамика неоднородных систем. М.:Изд-вл ЛКИ. 2008. Т. 33. Вып. 12. С. 206-219.