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

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

Допустим, существует два примитива ?(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

(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

B,1

A,1

A,0

B,0

000

100

P,E1

P=0

P=1

A,0

B,0

A,1

B,1

P,E1

P=0

P=1

A,1

B,1

A,0

B,0

001

101

P,E1

P=0

P=1

B,0

A,0

B,1

A,1

P,E1

P=0

P=1

B,1

A,1

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) позволяют построить кортеж