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

       

КАМСИ-композиция и КАМСИ-примитив


Введем несколько определений.

Допустим, существует два примитива ?(i) и ?(j) (i,j:=1,[?]), где ?(i)

и  ?(j)  – примитивы   i

-го и j

–го  типов, а  [?] - мощность множества ?

примитивов.

Было  уже показано, что если две КАМСИ-композиции, каждая из которых состоит из примитивов ?(i) и ?(j), и отличается только порядком расположения примитивов, то они  имеют разные таблицы переходов (то есть, реализуют разные алгоритмы).

Если одну из этих КАМСИ-композиций обозначим, как кортеж

  то  другую можно обозначить:  
, где нижний индекс у ? соответствуют позиции примитива в КАМСИ-композиции.

В общем виде, m-позиционные кортежи КАМСИ-композиции можно записать в виде:

Форм. 3                                            

где:

- примитив или его инверсия типа q, который расположен в i-ой позиции кортежа;

 q - один из множества ?



примитивов типа q.([23])

Рассмотрим некоторые свойства КАМСИ, которые позволят нам оценить возможное количество кортежей.

Утверждение 8:  «Перестановка переходов в любой строке таблицы переходов КАМСИ сохраняет свойство КАМСИ и его тип (?-порядок и  число состояний)».

Например, в Table 21  таблицы переходов (a) и (b) получены перестановкой в строке А.  Как следует из способа построения  тестирующей таблицы (с) (см. «Минимальная инверсная машина», стр. 17), каждому из них  соответствует одна и та же тестирующая  таблица Table 21(с).

P,E1

P=0

P=1

A

B,0

A,0

B

A,1

B,1

(a)

P,E1

P=0

P=1

A

A,0

B,0

B

A,1

B,1

(b)

Е1,Р

Е1=0

У1=1

A

AB

B

AB

AB

-

-

(c)

?=2

Table 21

Столбец А

Столбец В

P,E1

P=0

P=1

A

B,0

A,0

B

A,1

B,1

P,E1

P=0

P=1

A

B,1

A,1

B

A,0

B,0

000

100



P,E1

P=0

P=1

A

A,0

B,0

B

A,1

B,1

P,E1




P=0



P=1



A



A,1



B,1



B



A,0



B,0



001





101















P,E1



P=0



P=1



A



B,0



A,0



B



B,1



A,1











P,E1



P=0



P=1



A



B,1



A,1



B



B,0



A,0



010





110









Table 22

Утверждение 9 : « Инвертирование всех значений выходов автомата в таблице переходов КАМСИ сохраняет свойство КАМСИ и его тип».

Например, в Table 22 в столбцах (А) и (В) в строках 000 и 100 расположены таблицы переходов, полученные инвертированием значений выходов, соответственно. Другие  строки таблицы получены последовательным применением операций, описанных в «Утверждение 8» и «Утверждение 9».

Таким образом, в Table 22 (в столбце А) приведены все варианты таблицы переходов 000, к которой применена операция, описанная в «Утверждение 8», а столбец В

получен применением к соответствующей таблице переходов столбца А  «Утверждение 9».

Если обозначить через n? число состояний примитива, то  не трудно показать, что общее число примитивов будет равно


Допустим, Библиотека Примитивов состоит только из примитивов, приведенных в Table 22 и их инверсий. Из этого следует, что общее число элементов Библиотеки равно  
 и это число равно числу вариантов заполнения каждого разряда m-позиционного кортежа.

Не трудно показать, что число  m-позиционных кортежей, которые могут быть получены перестановкой с повторением равно
.

Так, для m=10 ,
 кортежей, каждый из которых соответствует КАМСИ с ?=2Чm=20, и N=211=2048.

Для примитива, анализируемого в Table 12 (см. стр.23), у которого n?=5 и ?(?)=6, для m=10
 кортежей. Если обратиться к Table 23 (см. стр. 41), то можно увидеть, что это число в 1013

раз больше возраста Вселенной.

Полученные цифры показывают, что даже если использовать только примитив с параметрами n?=5, ?(?)=6, то и этого достаточно, чтобы обеспечить всех желающих  сгенерировать пару разных ключей любое количество раз в течение всего времени существования нашей цивилизации без опасности, что результаты генерации когда либо повторятся. Сравнение
 с
 показывает, что функция
 монотонно возрастает с ростом x и  y, то есть, полученные оценки можно считать нижней границей при оценке количества кортежей при использовании разных типов примитивов.



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

  • Отпадает необходимость строить КАМСИ, применяя описанные выше тестирующие процедуры;


  • Отпадает необходимость обеспечивать секретность Библиотеки Примитивов.


  • Рассмотрим далее процесс формирования кортежей.

    Двоичная  запись чисел, поставленных в соответствие примитиву в Table 22, представляет собой шаблон, который показывает, как из примитива с номером 000 (назовем ее базовой ([24])) получить примитив, соответствующий заданному числу.

    На это указывает взаимное расположение в этом числе единиц и нулей:

    a)      Единица в первом (слева) разряде показывает, что в базовой модели следует инвертировать значения выходов во всех состояниях (то есть, применить операцию из «Утверждение 9»);

    b)      Для остальных разрядов заданного двоичного числа выполнить операцию, описанную в «Утверждение 8» для всех состояний базовой модели, номера которых совпадают с номерами позиций, в которых располагаются единицы.

    Например, для компонентов типа (n?=2, ??=2) кортеж 101, 011, 111, 000, 000, 110, 001 (см. Table 22, стр. 37), который можно представить в виде: 5370061 (восьмеричная запись). Этот кортеж соответствует КАМСИ-композиции (m=7,  µ=14), в которой примитивы расположены в порядке, описанном выше.

    Таким образом, приведенные «Утверждение 8» (стр. 36) и «Утверждение 9» (стр. 37) позволяют построить кортеж
      для КАМСИ-композиции. Для этого достаточно выбрать (можно с повторениями) m

    компонентов из таблицы, подобной Table 22.


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












    P,E1



    P=0



    P=1



    A



    A,0



    B,0



    B



    B,1



    A,1











    P,E1



    P=0



    P=1



    A



    A,1



    B,1



    B



    B,0



    A,0



    011





    111