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