Шифрование текста на основе клеточных автоматов (правило 30)

В основе проекта лежит элементарный клеточный автомат с правилом 30, описанный Стивеном Вольфрамом в 1983 году. Поведение центрального столбца этой бинарной сетки демонстрирует выраженный детерминированный хаос при крайне простых начальных условиях. Проект связывает дискретную математику с практической криптографией через создание симметричного алгоритма шифрования.

Математическая модель правила 30

Для теоретической части проекта необходимо строго разобрать локальное правило перехода. Состояние клетки на следующем шаге вычисляется через побитовые операции над текущей клеткой и её соседями слева и справа. В булевой алгебре правило 30 выражается формулой: новое значение равно результату XOR между левым соседом и дизъюнкцией текущей клетки с правым соседом. В коде на Python или C++ это вычисляется как p ^ (q | r).

Опиши граничные условия для конечного массива клеток. На практике используют периодические границы, заворачивая вектор в кольцо, либо фиксированные нулевые границы. Выбор типа границы напрямую влияет на длину периода псевдослучайной последовательности, что обязательно нужно отразить в расчётах.

Архитектура поточного шифра

• Формирование начального вектора инициализации, который выступает секретным ключом шифрования и задаёт исходное состояние строки клеточного автомата.
• Генерация гаммы заданной длины путём съёма значений центральной клетки на каждой итерации автомата для получения битового потока.
• Посимвольное наложение битов гаммы на биты открытого текста через операцию XOR для получения шифротекста.
• Обратная процедура расшифрования с повторным запуском автомата из идентичного начального состояния.

Экспериментальная проверка и статистические тесты

Простой демонстрации шифрования и расшифрования фразы для защиты проекта недостаточно. Преподаватель ожидает численного подтверждения качества сгенерированной гаммы. Проведи частотный монобитный тест, подсчитав баланс нулей и единиц в последовательности длиной от десяти тысяч бит. В хорошем генераторе доля единиц колеблется около значения 0.5 с минимальным отклонением. Дополнительно можно построить график автокорреляционной функции центрального ряда, чтобы показать отсутствие выраженной периодичности на коротких дистанциях.

Где искать материалы и данные

• Книга Стивена Вольфрама A New Kind of Science, где подробно разобраны классификация клеточных автоматов и свойства правила 30.
• Специальная публикация NIST SP 800-22, откуда берутся формулы базовых статистических тестов для генераторов псевдослучайных чисел.
• Статьи по симметричной криптографии и поточным шифрам вроде конструкции Вернама, объясняющие математическую базу операции сложения по модулю 2.