Обсуждение возможности построения однонаправленной функции с «секретом».
Рассмотрим пример.
В Table 12 в строке 1 приведена сложность инвертирования КАМСИ-примитива с n=5, а в строке 2 – сложность инвертирования композиции двух примитивов, каждый из которых имеет n=5 состояний. Как следует из таблицы, сложность инвертирования этой композиции (таблицы переходов с 25 состояниями) составляет ?224
операций.
Если же мы вначале инвертируем два КАМСИ-примитива, а затем выполним композицию их инверсий (сложность инвертирования каждого примитива ?212), то сложность построения инверсной КАМСИ будет равна 2•212= ?
213 (проще в
211 раз).
224 и 213 разница ощутимая, но - в пределах технических возможностей компьютера. Но вот, если обратиться к 5 строке Table 12 (композиция пяти примитивов – таблица переходов состоит из 1250 состояний), то здесь сложность инвертирования композиции пяти КАМСИ-примитивов будет равна ?260, в то время, как инвертирование пяти примитивов будет равно 5•212=1.25•214. то есть, сложность инвертирования композиции пяти КАМСИ-примитивов в ?246 раз больше раздельного инвертирования пяти КАМСИ-примитивов.
Оценим, как изменяется отношение сложности инвертирования КАМСИ-композиции m примитивов к сложности последовательности примитивов, каждый из которых имеет ?(m)-порядок. Обозначим его - ?(m,?(m)),.
Ранее было показано, что сложность инвертирования КАМСИ, с порядком, равным ?, равна
Если примем, что все ?(i)-порядки одинаковые и равны ?(m), то
При последовательном инвертировании примитивов
В этом случае сложность инвертирования КАМСИ-композиции превышает сложность последовательного инвертирования m примитивов в:
Таким образом, если воспользоваться для инвертирования композицией наборов из m компонентов, то удастся упростить процесс инвертирования в
Это дает возможность построить на базе КАМСИ-композиции однонаправленную функцию с «секретом».
«Секрет» заключается в том, что тот, кто выбрал КАМСИ-компоненты и построил КАМСИ-композицию, получает возможность упростить в
Теперь любой участник информационного процесса, имея инверсию композиции КАМСИ-примитивов, может закодировать информацию, а раскодировать ее сможет только единственный обладатель композиции КАМСИ-примитивов (вот он «секрет» однонаправленной функции!), то есть, обладатель кода. В это же время, любой, кто пожелает раскодировать информацию, должен будет инвертировать открытый ключ, выполнив (для рассмотренного примера) ?260?1018
операций, так как ему не известен порядок, в котором примитивы входят в композицию закрытого кода ([18]).
Для того, чтобы представить себе величину 1018, достаточно вспомнить (см. Table 23, см. Дополнение, стр. 41 ), что возраст Вселенной составляет всего 1010
лет.
Table 12 показывает, что сложность инвертирования резко возрастает при линейном росте m – кратности (то есть, количества) КАМСИ-примитивов в композиции.
Таким образом, «секретом» однонаправленной функции является набор и порядок следования примитивов в композиции - закрытом ключе.
В Table 21 приводятся значения ?(m,?(m)) в зависимости от m,
изменяющегося в диапазоне 1 .. 7, и ?(m) - в диапазоне 2 .. 5. Из этой таблицы видно, что уже при ?(10)=5 сложность инвертирования КАМСИ-композиции при покомпонентном инвертировании может быть уменьшена в ?(7,5)?1018 раз.
В этом случае: ?=m?(7)=7•5=35, и, в то время, как сложность непосредственного инвертирования равна 270?1021 (сравните с числами в Table 23, строка 4), покомпонентное инвертирование имеет сложность 7•210=71680. Другими словами, обладатель «секрета» (знание структуры декомпозиции кодера) получает возможность упростить процесс построения инвертора в ?1021 раз.
Приведенный пример еще раз показывает, что на базе КАМСИ-композиции можно построить однонаправленную функцию с «секретом».
 |
||||
|
m |
?(m,2) |
?(m,3) |
?(m,4) |
?(m,5) |
|
1 |
1 |
1 |
1 |
1 |
|
2 |
8 |
32 |
128 |
512 |
|
3 |
85.3 |
1395.3 |
21845.3 |
349525.3 |
|
4 |
1024 |
65536 |
4194304 |
268435456 |
|
5 |
13107.2 |
3355443.2 |
858993459.2 |
219902325555.2 |
|
6 |
174762.6 |
178956970 |
183251937962 |
187649984473770 |
|
7 |
?107 |
?1011 |
?1014 |
?1018 |
Table 20
Известно, что проблема «взлома» криптографической системы с открытым ключем сводится к «взлому» открытого ключа, то есть построение по нему закрытого, секретного ключа. В роли открытого ключа для криптографической системы на базе КАМСИ выступает инверсия композиции примитивов, образующих кодер.
Перед нелегитимным участником информационного процесса встает проблема дешифрования закодированного сообщения. Этого можно достигнуть одним из способов: либо
1. Инвертировать открытый ключ, или
2. разложить открытый ключ на примитивы, а затем построить композицию секретного ключа, инвертировав полученные компоненты.
Мы уже обсуждали оценку сложности инвертирования (см. Форм. 1, стр. 23) из которой видно, что она зависит от ?-порядка, и, практически, не зависит от числа состояний таблицы переходов инвертируемой КАМСИ.
Для того, чтобы обсуждить проблемы, связанные с декомпозицией открытого ключа, рассмотрим основные этапы построения асимметрического криптографического алгоритма на базе КАМСИ.
Примем, что:
a. Существует абонент А, который строит: а) открытый ключ, с помощью которого абонент В
сможет кодировать сообщения для абонента А, и б) закрытый (секретный) ключ, который будет известен только А, и, с помощью которого абонент А
сможет декодировать сообщение абонента В. «Открытость» системы заключается в том, что в качестве абонента В могут выступать любые абоненты информационной системы, желающие послать сообщение абоненту А, а в качестве абонента А
выступает единственный абонент, «хозяин», который имеет закрытый (секретный) ключ.
b. Всех абоненты информационной сети имеют Библиотеку Примитивов, из которых любой абонент может создать собственный открытый и закрытый ключ.
c. Библиотека Примитивов содержит таблицы переходов примитивов и их инверсий.
С учетом принятого, процесс формирования асимметрического алгоритма можно представить в виде последовательности следующих операций:
1. Выбрать m - количество компонентов КАМСИ-композиции.
2. Выбрать типы КАМСИ-примитивов и порядок их размещения в КАМСИ-композиции секретного ключа. Допускается применение нормальных и инверсных форм примитивов, а так же повторение типов. Единственное ограничение – один и тот же тип не должен входить в набор нормально и инверсно.
3. Построить композицию выбранных компонентов, которая образует секретный ключ. Это секретный ключ ?(m) абонента, который хранится у получателя информации абонента А.
4. Образовать кортеж из инверсий, выбранных в п.2 примитивов, и разместить их в порядке, обратном размещению их в кортеже п.2.
5. Построить композицию из выбранных в п.4 примитивов, образовав КАМСИ-композицию ?(m). ?(m) является открытым ключем;
6. Разослать всем абонентам сети В
открытый ключ ?(m) по незащищенному информационному каналу.
Обратим внимание, что если открытый ключ ?(m),
может распространяться любым способом, в том числе, по незащищенным информационным каналам, то для ?(m),
за все время существования построенного криптографического алгоритма, не возникает необходимость передавать его, либо сообщать его кому бы то ни было.
Проанализируем, возможности «взлома» подобного алгоритма.
Для этого перечислим данные, которыми располагает любой, легитимный и нелегитимный участник информационного процесса:
- Количество состояний N таблицы переходов КАМСИ ?(m).
- ?-порядок ?(m). Эту информацию он может получить, экспериментируя с ?(m).
- Библиотеку Примитивов и их инверсий.
- порядок следования компонентов, и
- форма примитива (нормальная или инверсная) выбраная при формировании ?(m) ([20]).
Перед «взломщиком» стоит задача определить ?(m).
«Взломщик» может выбрать одну из двух стратегий «взлома»:
1. Инвертировать ?(m), для которой известен ?-порядок ([19]). Эта ситуация рассматривалась нами выше и для нее получена оценка числа операций, равная ? ? 22? (см.Форм. 1, стр. 23 ). Эту стратегию «взлома» взломщик выбирает с учетом своих технических ресурсов.
2. В соответствии с «Утверждение 6» (см. стр. 30) набор примитивов, теоретически, можно определить, решив диофантовы уравнения:
значения N и ? – можно считать известными, кроме того, возможные значения ni
и ?(i) можно определить из Библиотеки Примитивов (способ построения Библиотеки будет определен ниже)
Несмотря на сложность решения этих уравнений, проблема будет решена частично, так как после этого остаются неизвестными:
Что же такое примитивы?
Достаточно ли их количество, чтобы строить на их основе секретные криптографические ключи ([21])?
Это обстоятельство очень важно.
Действительно, если окажется, что примитивы существуют в малом количестве, то при определении кортежа ([22]) композиции (числа и порядка расположения примитивов в композиции) пространство перебора будет настолько ограниченным, то есть пространство перебора будет малым.
