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

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

Допустим, существует два примитива

, где i и j – i

-ый и j –ый примитивы типа

, а

- мощность множества

примитивов к-го типа.

Не трудно показать, что две КАМСИ-композиции, каждая из которых состоит из одинаковых примитивов

, и отличаются только порядком расположения примитивов – имеют разные таблицы переходов. Одну из этих КАМСИ-композиций можно обозначить, например,

и другую -

, где нижние индексы показывают позицию в КАМСИ-композиции. В математике такие последовательности называются кортежами.

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

Форм. 16

где:

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

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

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

Общее число m-позиционных кортежей, которые имеют одни и те же примитивы и отличаются только порядком их расположения равно ([45]):

Форм. 17

где:

- множество примитивов типа w, один из которых расположен в t-ой позиции кортежа.

Приступим к определению мощности множества примитивов.

Введем определение.

Два состояния А и В таблицы переходов, которые имеют вид

где C и D – любые состояния таблицы переходов,

будем называть взаимообратимыми. Взаимообратимые состояния имеют одинаковое заполнение в тестирующей таблице.

Предварительно сформулируем несколько утверждений.

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

Это утверждение вытекает из Theorem 14-1 цитированной выше книги Zvi Kohavi (стр. 510).

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

Доказательство.

Первая часть Утверждения вытекает из способа построения тестирующей таблицы (см. «Switching and Finite Automata Theory», Zvi Kohavi), в которой каждой строке верхней половины тестирующей таблицы ставится упорядоченное сочетание названий состояний переходов в соответствующей строке таблицы переходов. Из этого следует, что перестановка переходов сохраняет свойство КАМСИ.

Вторая часть Утверждения вытекает из того факта, что если верхняя часть тестирующей таблицы при перестановке переходов в одной строке таблицы не изменяется, то нижняя часть тестирующей таблицы также не изменяется, то есть, величина µ-задержки при перестановке переходов не изменяется.

Например, в Ошибка! Источник ссылки не найден.

таблицы переходов (a) и (b) получены перестановкой в строке А. Как следует из способа построения тестирующей таблицы (с) (см. «Switching and Finite Automata Theory», Zvi Kohavi), каждому из них соответствует одна и та же тестирующая таблица Ошибка! Источник ссылки не найден.(с).

	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 12

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

Доказательство следует из того, что инвертирование всех значений равносильно перестановке столбцов P=0 и P=1 в тестирующей таблице, что не может изменить характеристики автомата.

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

Таким образом, в Ошибка! Источник ссылки не найден.

(столбце А) приведены все варианты таблицы переходов 000, к которой применена операция «Ошибка! Источник ссылки не найден.», а в столбце В – операция «Ошибка! Источник ссылки не найден.».

Столбец А		Столбец В

	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,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 13

Не трудно показать, что общее число примитивов при этом равно

Форм. 18

.

где

- число состояний таблицы переходов примитива.

Полученная оценка справедлива только для примитивов. Действительно, если в таблице переходов есть взамнообратимые состояния А и В такие, что

, то после перестановки переходов, например, в состоянии А мы получим эквивалентные состояния А и В. После «объединения» эквивалентных состояний, мы получим таблицу переходов с числом состояний, равным

. Не трудно видеть, что

- не простое число, то есть полученная таблица переходов - не примитив. Если это все еще КАМСИ – то скорее всего – композиция примитивов (а может быть – и нет). В любом случае – применение такой таблицы переходов требует трудоемких проверок, что уничтожает эффект применения примитивов.

Форм. 18 позволяет преобразовать Ошибка! Источник ссылки не найден. к виду:

Форм. 19

если принять, что m-кортеж состоит из примитивов одинакового типа, то эта формула примет вид:

Форм. 20

Так, для кортежа с числом позиций m=12, и
общее число кортежей равно

, а для m=4 и

(обратите внимание что обе эти цифры соизмеримы с возрастом Вселенной).

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

Докажем еще одно не тривиальное утверждение.

Утверждение 7. Если существует две композиции

где:

- четыре разных примитива,

- композиция примитивов

, которая выполняет операцию

,

– множество примитивов y-го типа, то есть с одинаковым числом состояний и величиной µ,

и

(где

- закодированный композициями
, соответственно,

текст Р), то
и
.

Доказательство. Допустим, что

, то есть
. Примем, что в таблицах переходов примитивов
и
:

Форм. 21

где

фрагмент
соответствует переходу примитива из состояния S в состояние Q, если на его входе P=0. При этом на выходе устанавливается значение t (ноль или единица).

Принятое выше допущение

является условием эквивалентности композиций
и
. Другими словами, при обходе всех состояний таблиц переходов
и
на их выходах появляется одинаковая последовательность битов.

Допустим, что
и
эквивалентны, а для
и
существует состояние S, которое имеет вид Форм. 21 (см. Ошибка! Источник ссылки не найден., стр. 61).

Допустим, на входы
и
подан поток битов, который перевел оба автомата в состояние S. Из Форм. 21 следует, что при очередном изменении на входах
и
один из автоматов перейдет в состояние Q, а другой – в F (это зависит от значения Р). Но так как Q не эквивалентно F, то при продолжении эксперимента на выходах
и
появятся разные последовательности битов.

Не трудно показать, что ситуация не изменится, если операция, описанная в «Ошибка! Источник ссылки не найден.» будет применена к разному числу примитивов композиций
и
.

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

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

Отпадает необходимость обеспечивать секретность принятому набору типов примитивов.

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

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

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

Единица в первом (слева) разряде показывает, что в базовой модели следует инвертировать значения выходов во всех состояниях (то есть, применить операцию из «Ошибка! Источник ссылки не найден.»);

Для остальных разрядов заданного двоичного числа выполнить операцию, описанную в «Ошибка! Источник ссылки не найден.» для всех состояний базовой модели, номера которых совпадают с номерами позиций, в которых располагаются единицы.

Ошибка! Источник ссылки не найден.

утверждения

Ошибка! Источник ссылки не найден.