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



         

Минимальная инверсная машина


Мы продемонстрируем процедуру построения минимальной инверсии на примере М показанной в Table 7а. Эта машина третьего ?-порядка (µ=3), поэтому, если мы знаем исходное состояние и значения трех

соответствующих выходных символов при переходах из начального состояния, мы можем определить первый входной символ. Определим множество триплов, обозначая их:  S(t)zt+1,zt+2

Первый компонент каждого трипла (S(t)) есть любое из  исходных состояний машины М, второй (zt+1) – один из выходных символов, который может быть продуцирован при одном из переходов из этого состояния и третий (zt+2) –выходной символ, который может быть продуцирован при переходе из этого состояния.  Трипл  определяется для каждого возможного исходного состояния  и для всех возможных последовательностей длиной 2. Для машины М

полученные триплы показаны в Table 7c.  Из этой таблицы видно, что, например, трипл  (А,0,1) - не определен, потому, что, если исходное состояние А, то после нулевого значения на выходе (переход А=>C), следующим значением не может быть единица.

Множество так сгенерированных триплов содержит все возможные варианты начальных состояний и соответствующих им выходных последовательностей длиной 2. Чтобы определить входной символ, который явился причиной перехода из этого начального состояния, при котором вырабатывается на выходе символ, определенный вторым

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

Перейдем к построению таблицы переходов инверсной машины. Для этого обозначим инверсную машину через , которая, в соответствии с примером  имеет 8 состояний, соответствующих восьми триплам (см. Table 7c).

Начнем построение таблицы переходов машины *М.

Она соответствует автомату, на входы которого подаются биты z, а на выходе формируются сигналы x.




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