Development and investigation of the key stream generators on the base of cellular automata

Abstract

EN: This paper presents the development and investigations of the binary key stream generators statistical characteristics. Developed generators based on the elementary rules of cells interaction: simple, modified and combined classical rules. We believe that elementary rules «30», «86», «135», «149» are most promising from statistical point of view. Modifications were consist of combining of array bits before outputting and combining various elementary rules of automaton cells interaction. It was developed a new simple interaction rule, based on the logical operation XOR. The investigation of statistical properties was performed using NIST STS v1.8. All designed generators showed good statistical characteristics, which indicates their satisfactory cryptoresistance. In addition we’ve investigated the developed generators linear complexity using Berlekamp-Massey algorithm. Obtained results shows the high values of linear complexity (about half of the cellular automaton length), which is typical for such structures type. On the base of the developed generator with own cells interaction rule has developed a system for secure communication of audio, text and file information. The statistical investigations of encrypted file showed that it satisfies all the NIST STS requirements. UK: В роботі подано результати розробки та дослідження статистичних характеристик генераторів бінарного ключового потоку на основі клітинних автоматів. Розроблені генератори використовують елементарні правила міжклітинної взаємодії, «30», «86», «135» и «149», як найбільш перспективні зі статистичної точки зору. Модифікації правил зводилися як до комбінування власне правил взаємодії, так і бітів масиву перед виводом чергового біта. Розроблено власне правило міжклітинної взаємодії на основі додавання за модулем два. Дослідження статистичних характеристик виконувалося за допомогою пакета NIST STS v1.8. Усі розроблені генератори продемонстрували хороші статистичні властивості, що підтверджує їх задовільну криптостійкість. Досліджено також лінійну складність з використанням алгоритму Берлекемпа-Мессі та отримано високі її значення (приблизно половину довжини клітинного автомата), що вважається традиційним для такого роду систем. На базі досліджених генераторів розроблено систему захищеного обміну аудіо-, текстовою та файловою інформацією в реальному часі, що свідчить про високу швидкодію системи захисту. Результати статистичних тестів демонструють, що система задовольняє усі вимоги NIST STS.