Cryptanalytic invertibility with finite delay of finite automata.pdf Предлагаемые вниманию тезисы доклада являются расширенным рефератом работы автора [1], содержащей определение обратимости с конечной задержкой конечных автоматов с криптоаналитической точки зрения, по которой обращение автоматного преобразования осуществляется с целью восстановления входного слова автомата по его выходной последовательности при наличии некоторой частичной информации об этом преобразовании. Разные типы этой информации определяют разные типы и классы криптоаналитической обратимости автоматов и порождают многочисленные теоретико-автоматные и криптографические задачи, требующие математического решения. Обширный список этих задач включает в себя такие задачи, как, например, установление необходимых и достаточных условий автоматной обратимости каждого типа, построение конструктивных тестов принадлежности автоматов конкретным классам обратимости, алгоритмический синтез автоматов в заданных классах обратимости, характеризация обратимых автоматов, допускающих обратные автоматы, алгоритмический синтез обратных автоматов каждого типа, разработка эффективных алгоритмов восстановления входных последовательностей обратимых автоматов в конкретных классах обратимости, создание криптосистем с закрытым и открытым ключами на базе обратимых автоматов определённых классов обратимости, алгоритмический криптоанализ таких криптосистем с оценками его вычислительной сложности. Произвольный конечный автомат представляется как A - (X, Q,Y, где X, Q и Y суть его входной алфавит, множество состояний и выходной алфавит соответственно; " и ^ - его функции соответственно переходов и выходов, " : X х Q ^ Q и : X х Q ^ Y. Последние, будучи определёнными для пар xq G X х Q, распространяются на пары aq G X* xQ индукцией по длине |a| слова a G X*, а именно определяются функции " : X* х Q ^ Q и : X* х Q ^ Y* как "(A,q) - q, "(a^,q) - "(в, "(a, q)),

Скачать электронную версию публикации