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

Основная концепция алгоритма построения криптографической КАМСИ.


В предыдущих разделах было показано, что сложность непосредственного инвертирования КАМСИ соизмерима с

.

Было показано, что при достаточно больших значениях µ непосредственное инвертирование КАМСИ-композиции становится практически не выполнимым.

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

 (где
- максимально возможное значение µ-порядка, а R

– число дополнительных битов, такое, чтобы 

 имело размер порядка 100 или больше).

Значение 

 может быть известно всем.

Какую же информацию недобросовестный абонент может получить из таблицы  переходов кодера? ([36])

  • Во-первых, число состояний таблицы переходов, равное N.
  • Во-вторых, он может разложить N на сомножители, для того, чтобы определить предполагаемое значение m – количество КАМСИ-компонентов. Как  показывает Утверждение 2, m может удовлетворять формулам:
  • Форм. 9                                             

    ,

    где

     - число состояний i-ой компоненты и число компонент соответственно,

    и:

    Форм. 10                                  

     ,

    где

     - µ-порядок i-ой компоненты.

    • Форм. 9 и Форм. 10 представляют собой систему из двух диофантовых ([37]) уравнений от (2 х m) неизвестных (одно нелинейное уравнение от переменных

      , и другое – линейное от переменных
      ). Совместное  решение  этих уравнений дает один из вариантов набора компонентов КАМСИ-композиции. Проблема усложняется тем, что m не известно, так как представляет собой часть секретного ключа.

      Таким образом, КАМСИ-композиция дополнительно, в качестве альтернативы к описанной Цви Кохави (см. стр. Ошибка! Закладка не определена.) процедуре построения инвертора, позволяет применить процедуру, которая состоит из нескольких этапов:

      1.      совместное решение описанной выше системы диофантовых  уравнений, в результате которого будет получено значение  m и один из вариантов набора компонентов КАМСИ-композиции.

      2.      определение порядка расположения найденных компонентов при декодировании.

      3.      инвертирование компонентов КАМСИ-композиции.

      В следующих разделах будет оценена сложность выполнения операций декодирования  для недобросовестного([38]) участника процесса обмена информацией и сравнение ее с легитимным декодированием.



      Содержание раздела