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

Пример КАМСИ


Пример 1.

На Рис. 3 показано взаимодействие двух конечных  автоматов А1 и SS1.

Первый  из них, А1 принимает на вход поток битов Р (назовем его исходным текстом), и на выходе его  появляется поток битов Е (назовем его кодом, а сам автомат -  кодером).

Второй из этих автоматов SS1 принимает на вход поток битов Е, а на выходе при этом появляется поток битов Р (такой же, какой был подан на вход А1) поэтому SS1 будем называть декодером.



Рис. 3 Структура процесса кодирования-декодирования

Казалось бы, эта пара автоматов ничего не сделала: на вход А1 подан поток битов Р, и этот поток битов  появляется на выходе SS1, то есть, эта пара автоматов вместе выполняет функцию повторителя. Но это только на первый взгляд.

Конечные автоматы А1 и SS1 могут находиться на любом расстоянии друг от друга и в этом случае говорят, что их соединяет информационный канал. По  информационному каналу передается поток  битов Е. Если информационный канал не защищен, то информация, передаваемая по нему доступна любому, кто имеет доступ к каналу. В этом случае защищенность информации полностью зависит от того, насколько код Е содержит информацию об исходном тексте Р. Это  значит, что качество защиты информации зависит от алгоритма функционирования конечного автомата А1. Конечный автомат А1 может обладать одним из следующих свойств:

  • Алгоритм автомата А1 может быть настолько примитивным, что по потоку битов Е не трудно восстановить Р. В этом случае теряет смысл применение А1 и, соответственно, SS1.
  • Алгоритм автомата А1 может быть таким, что по Е,  никто и никогда не сможет  восстановить Р. В этом случае отпадает необходимость не только в применении А1 и SS1, но и самого информационного канала.
  • Алгоритм автомата А1 может быть таким, что исходный текст Р может быть восстановлен по Е только с помощью конечного автомата SS1. Это значит, что если засекретить конечный автомат SS1, то доступ к информации Р будет иметь только тот, кто обладает этим автоматом. Конечные автоматы А1 и SS1 могут реализовать такие алгоритмы кодирования и декодирования, что обладатель конечного автомата А1 не сможет по полученному им  потоку Е, восстановить Р.

  • Конечные автоматы А1 и  SS1 реализуют алгоритмы, которые могут быть заданы с помощью таблиц переходов.
    Рассмотрим Table 1,  в которой приведены таблицы переходов конечных автоматов А1 и SS1.





    А1
    P,E
    P=0
    P=1
    A
    B,0
    A,0
    B
    A,1
    B,1

    (A)

    SS1
    E,P
    E=0
    E=1
    S0
    S1,1
    S2,1
    S1
    S1,1
    S2,1
    S2
    S3,0
    S4,0
    S3
    S1,0
    S2,0
    S4
    S3,1
    S4,1
    (B)
    Table 1
    Само название таблицы переходов показывает, что она описывает изменения, которые произойдут в состоянии автомата при изменении сигнала на его входе.
    Таблица переходов имеет три столбца:
  • в первом столбце приведены состояния конечного автомата. В рассматриваемом примере это два состояния: А и В ([29]);

  • во втором столбце – записано имя состояния, в которое будет переход, при подаче на вход Р значения 0. Через  запятую записано значение, которое появится на выходе Е.

  • Например, если автомат А1 находится в состоянии А (строка А), и на его вход Р подается 0 (Р=0), то автомат А1 перейдет в состояние В (строка В) и на его выходе  Е установится значение 0 (это записано в виде В,0). Аналогично интерпретируется содержимое третьего столбца.
    На   Рис. 3 (стр 38) показаны:
    1.     Кодер и декодер:
    • кодер А1 (Table 1A); он задан таблицей переходов конечного автомата, на вход которого подаются входные биты, а на выходе устанавливаются значения выходных битов. Например, пусть автомат А1 находится в состоянии А (первая строка таблицы переходов). Если на его вход Р подать 1, то он останется в состоянии А, а на выходе появится 0. Если опять подать на вход 1,  то автомат останется в состоянии А, а на выходе появится 0. Обратите внимание: подали на вход  последовательность 11, а на выходе появилась последовательность 00. значит ли это, что автомат А1 инвертирует входные биты? Продолжим эксперимент и подадим на вход 0, автомат перейдет в состояние В, и на выходе появится значение 0. На Рис. 4 в строках (a), (b) и (c) показан весь процесс кодирования.



    • декодер  SS1 (Table 1B) – инвертор кодера А1. Он задан таблицей переходов конечного автомата, на вход которого подаются биты, полученные с выхода кодера Е. Так как SS1 – инвертор кодера, то на выходе декодера появляются значения Р (см. Рис. 3). Строки (d) и (e) Рис. 4 показывают процесс декодирования.









    • Процесс кодирования-декодирования

      A1

      1

      1

      0

      1

      0

      0

      1

      1

      0

      0

      1

      0

      0

      1



      (a)


      A

      A

      A

      B

      B

      A

      B

      B

      B

      A

      B

      B

      A

      B

      B


      (b)



      0

      0

      0

      1

      1

      0

      1

      1

      1

      0

      1

      1

      0

      1


      (c)

      SS1


      S0

      S1

      S1

      S1

      S2

      S4

      S3

      S2

      S4

      S4

      S3

      S2

      S4

      S3

      S2

      (d)




      1

      1

      1

      1

      0

      1

      0

      0

      1

      1

      0

      0

      1

      0

      (e)

      Рис. 4
      Особенность кодера (КАМСИ) заключается в том, что
      • в его таблице переходов (см. Table 1А) есть состояния, переход из которых формирует одинаковые значения на выходе, независимо от сигнала на входе. Например, при переходе из состояния А и при Р=0 и при Р=1 на входе, значение на выходе Е равно 0. Это  обстоятельство затрудняет восстановление входного сигнала по значению на выходе (reverse engineering). Инвертор  (В) так же представляет собой КАМСИ.

      • В  строке  (e) таблицы (Рис. 4), исходный текст начинается с третьего  бита. Это равносильно тому, что закодированная входная последовательность появляется на выходе SS1 с задержкой, равной 2. Это означает, что для получения раскодированного текста целиком, в конце его следует дополнительно добавить, минимум, два бита, значения которых могут выбираться произвольно.

      • Следует  заметить, что не всякая таблица, похожая на рассмотренную таблицу переходов, является КАМСИ.
        Формализуем   понятия, которые были использованы в рассмотренном  примере.
        В работе [8]  (см. стр Ошибка! Закладка не определена.) приведено определение  конечно-автоматной модели  с памятью: «Машина М называется машиной с конечной памятью порядка µ, если µ
        есть наименьшее целое, такое что текущее состояние М (а значит, и значение на выходе) может быть определено однозначно из предшествующих µ значений выходов».


        В  рассмотренном выше примере КАМСИ имеет µ=2 (см Рис. 4, стр. 41).
        Следует обратить внимание, что приведенное определение машины с памятью не является конструктивным, то есть, оно не содержит признаков, по которым можно непосредственно, без тестирования определить, обладает ли конкретный конечный автомат конечной памятью. Для этого существует единственный способ – проделать определенные тестирующие проверки.
        Аналогичная ситуация существует в Теории Чисел, где, со времен Эратосфена, определение основного объекта теории – простого числа, предполагает тривиальную. проверку, имеет ли оно, в качестве  делителя, простые числа. Кстати, именно это обстоятельство легло в основу однонаправленной функции с секретом, что позволило создать асимметричный алгоритм RSA.
        Разумеется, подобное сравнение не предполагает применения суждения по аналогии, и требует дополнительной аргументации.
        Для  применения КАМСИ в криптографическом протоколе необходимо создать алгоритм генерации открытого и секретного ключей, в состав которого не входили бы достаточно трудоемкие операции тестирования на информационную сохраняемость. Более того, алгоритм генерации должен позволять генерировать КАМСИ с заданными значениями параметров. Эти обстоятельства выгодно отличают алгоритм на базе КАМСИ от RSA, в котором часто вынуждены применять псевдопростые числа из-за большой трудоемкости генерации простых чисел.
        В работе [8]  (см. стр Ошибка! Закладка не определена.) показано, что существует класс конечно-автоматных моделей, для которых наличие таблицы переходов позволяет закодировать исходный текст, и, при этом, знание  µ - декодировать его. Там же обсуждается  способ тестирования конечно-автоматной модели на информационную сохраняемость (КАМСИ), и приводится  способ построения обратного автомата – декодера.
        Введем некоторые определения и преобразования КАМСИ, которые позволят нам построить однонаправленную функцию с секретом на базе КАМСИ.

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