Пример КАМСИ

Пример 1.

На Рис. 3 показано взаимодействие двух конечных  автоматов А1 и SS1.

Первый  из них, А1 принимает на вход поток битов Р (назовем его исходным текстом), и на выходе его  появляется поток битов Е (назовем его кодом, а сам автомат -  кодером).

Второй из этих автоматов SS1 принимает на вход поток битов Е, а на выходе при этом появляется поток битов Р (такой же, какой был подан на вход А1) поэтому SS1 будем называть декодером.

Рис. 3 Структура процесса кодирования-декодирования

Казалось бы, эта пара автоматов ничего не сделала: на вход А1 подан поток битов Р, и этот поток битов  появляется на выходе SS1, то есть, эта пара автоматов вместе выполняет функцию повторителя. Но это только на первый взгляд.

Конечные автоматы А1 и SS1 могут находиться на любом расстоянии друг от друга и в этом случае говорят, что их соединяет информационный канал. По  информационному каналу передается поток  битов Е. Если информационный канал не защищен, то информация, передаваемая по нему доступна любому, кто имеет доступ к каналу. В этом случае защищенность информации полностью зависит от того, насколько код Е содержит информацию об исходном тексте Р. Это  значит, что качество защиты информации зависит от алгоритма функционирования конечного автомата А1. Конечный автомат А1 может обладать одним из следующих свойств:

Алгоритм автомата А1 может быть настолько примитивным, что по потоку битов Е не трудно восстановить Р. В этом случае теряет смысл применение А1 и, соответственно, SS1.

Алгоритм автомата А1 может быть таким, что по Е,  никто и никогда не сможет  восстановить Р. В этом случае отпадает необходимость не только в применении А1 и SS1, но и самого информационного канала.

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

Конечные автоматы А1 и  SS1 реализуют алгоритмы, которые могут быть заданы с помощью таблиц переходов.
Рассмотрим Table 1,  в которой приведены таблицы переходов конечных автоматов А1 и SS1.

А1	P,E
P=0	P=1
A	B,0	A,0
B	A,1	B,1

(A)

SS1
E,P
E=0
E=1
S0
S1,1
S2,1
S1
S1,1
S2,1
S2
S3,0
S4,0
S3
S1,0
S2,0
S4
S3,1
S4,1
(B)
Table 1
Само название таблицы переходов показывает, что она описывает изменения, которые произойдут в состоянии автомата при изменении сигнала на его входе.
Таблица переходов имеет три столбца:

в первом столбце приведены состояния конечного автомата. В рассматриваемом примере это два состояния: А и В ([29]);

во втором столбце – записано имя состояния, в которое будет переход, при подаче на вход Р значения 0. Через  запятую записано значение, которое появится на выходе Е.

Например, если автомат А1 находится в состоянии А (строка А), и на его вход Р подается 0 (Р=0), то автомат А1 перейдет в состояние В (строка В) и на его выходе  Е установится значение 0 (это записано в виде В,0). Аналогично интерпретируется содержимое третьего столбца.
На   Рис. 3 (стр 38) показаны:
1.     Кодер и декодер:

• кодер А1 (Table 1A); он задан таблицей переходов конечного автомата, на вход которого подаются входные биты, а на выходе устанавливаются значения выходных битов. Например, пусть автомат А1 находится в состоянии А (первая строка таблицы переходов). Если на его вход Р подать 1, то он останется в состоянии А, а на выходе появится 0. Если опять подать на вход 1,  то автомат останется в состоянии А, а на выходе появится 0. Обратите внимание: подали на вход  последовательность 11, а на выходе появилась последовательность 00. значит ли это, что автомат А1 инвертирует входные биты? Продолжим эксперимент и подадим на вход 0, автомат перейдет в состояние В, и на выходе появится значение 0. На Рис. 4 в строках (a), (b) и (c) показан весь процесс кодирования.




• декодер  SS1 (Table 1B) – инвертор кодера А1. Он задан таблицей переходов конечного автомата, на вход которого подаются биты, полученные с выхода кодера Е. Так как SS1 – инвертор кодера, то на выходе декодера появляются значения Р (см. Рис. 3). Строки (d) и (e) Рис. 4 показывают процесс декодирования.










Процесс кодирования-декодирования
A1	1	1	0	1	0	0	1	1	0	0	1	0	0	1			(a)
	A	A	A	B	B	A	B	B	B	A	B	B	A	B	B		(b)
		0	0	0	1	1	0	1	1	1	0	1	1	0	1		(c)
SS1		S0	S1	S1	S1	S2	S4	S3	S2	S4	S4	S3	S2	S4	S3	S2	(d)
			1	1	1	1	0	1	0	0	1	1	0	0	1	0	(e)


Рис. 4
Особенность кодера (КАМСИ) заключается в том, что

• в его таблице переходов (см. Table 1А) есть состояния, переход из которых формирует одинаковые значения на выходе, независимо от сигнала на входе. Например, при переходе из состояния А и при Р=0 и при Р=1 на входе, значение на выходе Е равно 0. Это  обстоятельство затрудняет восстановление входного сигнала по значению на выходе (reverse engineering). Инвертор  (В) так же представляет собой КАМСИ.


• В  строке  (e) таблицы (Рис. 4), исходный текст начинается с третьего  бита. Это равносильно тому, что закодированная входная последовательность появляется на выходе SS1 с задержкой, равной 2. Это означает, что для получения раскодированного текста целиком, в конце его следует дополнительно добавить, минимум, два бита, значения которых могут выбираться произвольно.

Следует  заметить, что не всякая таблица, похожая на рассмотренную таблицу переходов, является КАМСИ.
Формализуем   понятия, которые были использованы в рассмотренном  примере.
В работе [8]  (см. стр Ошибка! Закладка не определена.) приведено определение  конечно-автоматной модели  с памятью: «Машина М называется машиной с конечной памятью порядка µ, если µ
есть наименьшее целое, такое что текущее состояние М (а значит, и значение на выходе) может быть определено однозначно из предшествующих µ значений выходов».


В  рассмотренном выше примере КАМСИ имеет µ=2 (см Рис. 4, стр. 41).
Следует обратить внимание, что приведенное определение машины с памятью не является конструктивным, то есть, оно не содержит признаков, по которым можно непосредственно, без тестирования определить, обладает ли конкретный конечный автомат конечной памятью. Для этого существует единственный способ – проделать определенные тестирующие проверки.
Аналогичная ситуация существует в Теории Чисел, где, со времен Эратосфена, определение основного объекта теории – простого числа, предполагает тривиальную. проверку, имеет ли оно, в качестве  делителя, простые числа. Кстати, именно это обстоятельство легло в основу однонаправленной функции с секретом, что позволило создать асимметричный алгоритм RSA.
Разумеется, подобное сравнение не предполагает применения суждения по аналогии, и требует дополнительной аргументации.
Для  применения КАМСИ в криптографическом протоколе необходимо создать алгоритм генерации открытого и секретного ключей, в состав которого не входили бы достаточно трудоемкие операции тестирования на информационную сохраняемость. Более того, алгоритм генерации должен позволять генерировать КАМСИ с заданными значениями параметров. Эти обстоятельства выгодно отличают алгоритм на базе КАМСИ от RSA, в котором часто вынуждены применять псевдопростые числа из-за большой трудоемкости генерации простых чисел.
В работе [8]  (см. стр Ошибка! Закладка не определена.) показано, что существует класс конечно-автоматных моделей, для которых наличие таблицы переходов позволяет закодировать исходный текст, и, при этом, знание  µ - декодировать его. Там же обсуждается  способ тестирования конечно-автоматной модели на информационную сохраняемость (КАМСИ), и приводится  способ построения обратного автомата – декодера.
Введем некоторые определения и преобразования КАМСИ, которые позволят нам построить однонаправленную функцию с секретом на базе КАМСИ.

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



---







---