Асимметричный криптографический алгоритм на базе Конечно-Автоматной Модели




Ну, и … что?


Мы показали, что  на базе КАМСИ можно построить однонаправленную функцию без секрета.

Это   объясняет, почему КАМСИ до сих пор не нашли применения в криптографии.

Ну, и что?

Существует ли возможность построить на базе КАМСИ однонаправленную функцию с секретом?

Рассмотрим, обладает ли КАМСИ-композиция свойствами, которые позволяют построить однонаправленную функцию с секретом? ([35])

Обсудим   два способа построения инвертора КАМСИ-композиции:

1.      Первый способ, описан в 14 разделе работы Цви Кохави «Ошибка! Источник ссылки не найден.» (см. здесь, стр.Ошибка! Закладка не определена.), назовем его непосредственный способ инвертирования. В соответствии с «Утверждение 2» (стр. 49) и Ошибка! Источник ссылки не найден. (см. стр. Ошибка! Закладка не определена.), сложность инвертирования такой КАМСИ-коипозиции может быть вычислена по формуле:

,

где m – число КАМСИ-компонент,

 - µ-порядок  i-ой КАМСИ-компоненты.

Если принять, что у всех компонентов µ-порядки одинаковые, то сложность непосредственного инвертирования равна

.

Эта формула получена на основании оценок, сделанных в разделе «Ошибка! Источник ссылки не найден.» (см. стр. Ошибка! Закладка не определена.)

Таким образом, сложность построения КАМСИ-композиции (кодера, в соответствии с «Утверждение 2», стр. 49) зависит от числа состояний

, в то время, как сложность инвертирования КАМСИ-композиции (то есть, построение инвертора) равна

не трудно показать, что это возможно только при

.

Если принять, что все компоненты имеют одинаковые параметры, то

и сложность решения обратной задачи (инвертирование КАМСИ-композиции) больше сложности решения  прямой задачи (создание КАМСИ-композиции) в

 раз.

Если принять, что

, то

 раз.

Мы  показали, что непосредственный способ инвертирования КАМСИ-композиции, как и любой КАМСИ, позволяет построить однонаправленную функцию, но так как сложность инвертирования одинаковая для всех, эта однонаправленная функция без «секрета».




Содержание  Назад  Вперед