Оптимізація цільових функції у евристичних алгоритмів пошуку високонелінійних S-блоків

Abstract

У роботі проведено аналіз існуючих досліджень та алгоритмів формування S-боксів з використанням різних цінових функцій — GA генетичний алгоритм, цінова функція WHT, цінова функція DDT, цінова функція WCF, цінова функція WHS, цінова функція PCF. Виконано їх порівняння з погляду пошуку S-боксу з нелінійністю 104, за критерієм швидкодії пошуку та меншої кількості порахованих S-боксів. Для розв’язання задачі в роботі вибрано рішення генетичного алгоритму (GA) з різними комбінаціями цінових функцій. Для обраного рішення побудована модель поетапного проведення дослідження. Розроблено програмне забезпечення, що реалізує обраний метод. Виконано практичне дослідження розробленого алгоритму з безліччю варіантів параметрів та приведено порівняльний результат. Досліджено можливість використання двох кросоверів, а саме циклічний кросовер та кросовер PMX, у парі з генетичним алгоритмом та обраними оптимальними ціновими функціями. Проведено порівняння отриманих результатів роботи алгоритму без кросовера, та з двома вказаними кросоверами. Всі результати наведені у вигляді порівняльних таблиць, рисунків та гістограм. Проведені спроби досягти нелінійності у значенні 106, використовуючи найоптимальніші цінові функції х досліджень.

The paper analyzes existing research and algorithms for the formation of S-boxes using various price functions – GA genetic algorithm, WHT cost function, DDT cost function, WCF cost function, WHS cost function, PCF cost function. They were compared from the point of view of S-box search with nonlinearity 104, according to the criterion of search speed and a smaller number of counted S-boxes. To solve the problem, the solution of the genetic algorithm (GA) with various combinations of price functions was chosen in the paper. For the chosen solution, a model of a phased research is built. The software that implements the selected method has been developed. A practical study of the developed algorithm with many options of parameters was performed and a comparative result was given. The possibility of using two crossovers, namely the cyclic crossover and the PMX crossover, in combination with a genetic algorithm and selected optimal price functions, was investigated. A comparison of the obtained results of the algorithm without a crossover and with the two specified crossovers was made.