Предлагаемая работа предполагает знания, хотя
Предлагаемая работа предполагает знания, хотя бы в объеме следующих работ:
В нашей работе мы построим криптографический алгоритм на базе КАМСИ.
Наиболее ранняя работа о КАМСИ была опубликована во второй половине пятидесятых годов двадцатого столетия. Более того, сегодня можно утверждать, что это были первые предложения асимметричного алгоритма ([4]).
Способ применения КАМСИ для кодирования был описан Huffman D.A. за двадцать лет (см. Список литературы, стр. 78) до того, как Уитвелд Диффи и Мартин Хеллман сформулировали общую концепцию асимметричных алгоритмов.
Почему же описанная Huffman D.A. КАМСИ до сих пор не нашла применения в криптографии?
Для того, чтобы ответить на этот вопрос, следует обратиться к работам Уитвелда Диффи и Мартина Хеллмана.
Главная заслуга Уитвелда Диффи и Мартина Хеллмана заключалась
в том, что они ввели понятие однонаправленной функции.
Упрощенно, идею однонаправленной функции можно представить на примере трафика движения по городским улицам с односторонним движением.
Допустим, водитель прибыл в пункт Б из пункта А (решил прямую задачу). Спрашивается
Не трудно видеть, что в рассмотренной ситуации, для любого водителя, участвующего в этом процессе, есть единственный способ поиска решения обратной задачи (то есть, возвращение из пункта Б в пункт А) – это полный перебор возможных вариантов.
Характерная особенность рассмотренного процесса заключается в том, что сложность решения прямой задачи (движение из А в Б) намного проще решения обратной задачи, которая может даже не иметь решения. Именно по этой причине, функция, описывающая рассмотренную выше ситуацию, называется однонаправленной.
Положение может измениться, если кто-либо из участников процесса движения секретно обзаведется, например, вертолетом (или воздушным шаром, или чем-либо, позволяющим ему изменить механизм движения). Понятно, что для него решение прямой задачи (движение из А в Б), и обратной (движение из Б в А), обладают одинаковой сложностью. Такую задачу называют однонаправленной задачей с секретом. В рассмотренном случае «секретом» является наличие вертолета у одного из участников ([5]).
Таким образом, для обладателей секрета, решение обратной задачи имеет сложность, такую же, как и для прямой задачи, в то время как для всех остальных участников движения, обратная задача может даже не иметь решения.
Уитвелд Диффи и Мартин Хеллман показали, что
Например, в RSA прямая задача (кодирование), выполняется с применением упомянутого выше произведения двух простых чисел. Произведение этих простых чисел известно всем, желающим закодировать информацию, и называется открытым ключем.
Однако, легко раскодировать информацию может только обладатель секрета – знания сомножителей - двух простых чисел, которые образуют произведение (открытый ключ) и называются секретным ключем.
Особенность такого процесса заключается в том, что открытый ключ не может использоваться для декодирования и по этому его допустимо передавать по незащищенным каналам, с тем, чтобы им мог воспользоваться любой, желающий передать конфиденциальную информацию, в то время, как секретный ключ хранится только у «хозяина» сгенерированных ключей.
Вернемся к КАМСИ (Конечно-Автоматной Модели, Сохраняющей Информацию).
Как это будет показано ниже, применение КАМСИ в криптографии предполагает существование пары конечных автоматов, один из которых выполняет функцию кодера, и другой, инверсный кодеру, функцию декодера.
В работах, список которых приведен на стр. 78, показан способ построения инверсных КАМСИ (необходимых для декодирования).
Ниже будет показано, что уже при числе состояний таблицы переходов кодера, равном 1250, сложность построения инвертора (декодера) требует около 260 ? 1018 операций (В Table 9 (см. стр. 52) приведены значения «Больших чисел»). Такое количество операций показывает, что практически невозможно построить инвертор. Описанная в цитированных работах КАМСИ представляет собой однонаправленную функцию, у которой сложность построения таблицы переходов кодера линейно зависит от числа состояний, а сложность построения инвертора – приближается к экспоненциальной зависимости. Сложность построения инвертора одинакова для всех участников процесса обмена информацией, то есть, в таком виде КАМСИ представляет собой однонаправленную функцию без секрета.
Это объясняет, почему КАМСИ до сих пор не были использованы в криптографии. Факт тем более огорчительный, что по всем остальным параметрам КАМСИ превосходят существующие асимметричные алгоритмы.
КАМСИ обладают:
- реализация алгоритмов на базе КАМСИ использует только логические (самые быстрые) операции.
- Описанный в литературе способ применения КАМСИ представляет собой однонаправленную функцию без секрета.
- Можно высказать различные предположения о том, почему эта проблема не была разрешена до сих пор. Но, учитывая высокий уровень ученых – специалистов в области Теории Конечных Автоматов, которые разрабатывали теорию КАМСИ (см. список литературы на стр. 78), можно выделить одно - Теория Конечных Автоматов изначально создавалась только для анализа и технической реализации алгоритмов управления технологическими процессами, которые разрабатывались в других областях науки. То есть, Теория Конечных Автоматов изначально создавалась для анализа алгоритмов управления технологическими процессами, разрабатываемыми вне нее. В криптографии же возникает проблема генерации криптографических алгоритмов, которые должны обладать определенными свойствами.
Почему же, несмотря на то, что КАМСИ были достаточно полно исследованы более сорока лет назад, они не нашли до сих пор применения в криптографии, несмотря на то, что существующие, так называемые, паблик-кей технологии по производительности и сложности реализации оставляют желать лучшего?
Этому может быть несколько объяснений:
Действительно, асимметрия здесь заключается в том, что алгоритмы кодирования отличаются от алгоритмов декодирования. Однако, сложность построения инвертора экспоненциально зависит от µ (одного из параметров КАМСИ, о котором будет сказано ниже). Эта сложность в этом случае одинакова для всех участников процесса обмена информацией.
Каковы же перспективы применения КАМСИ в криптографии?
В каком направлении следует исследовать проблему создания однонаправленной функции с секретом на базе КАМСИ?
Очень заманчиво, но бесполезно для применения в криптографии, попытаться усовершенствовать алгоритм инвертирования КАМСИ.
Как любое усовершенствование, оно представляет технический интерес. Однако, любое усовершенствование «облегчит жизнь» всем участникам процесса обмена информацией, в том числе, и недобросовестным. Так, рассмотренные Цви Кохави в разделе «Ошибка! Источник ссылки не найден.» называются линейными потому, что сложность их преобразования линейно зависит от размера Машины. Однако, это «облегчает жизнь» всем участникам процесса обмена информацией. То есть, оно не может привести к созданию «секрета» однонаправленной функции. Кроме того, трудно рассчитывать, что любые усовершенствования удастся длительно держать в секрете, тем более, что понятие «недобросовестный пользователь» среди участников информационного процесса может изменяться в зависимости от характера защищаемой информации.
Все это показывает, что сама по себе, разработка теории КАМСИ не может привести к созданию однонаправленной функции с секретом.
Есть и еще одно обстоятельство, которое создавало проблему применения КАМСИ в криптографии. Это - необходимость автоматизации процесса генерации кодера. Проблема генерации существует в любом криптографическом протоколе, но не существует в Теории Конечных Автоматов, так как к ней обращаются с готовым алгоритмом, который следует проанализировать.
Для симметричного алгоритма процесс решен достаточно успешно, но при этом возникает проблема «защищенной» доставки нового сгенерированного ключа по назначению.
В асимметричном алгоритме проблема «защищенной» доставки отсутствует, так как открытый ключ не от кого охранять, а секретный – некому посылать. При этом следует учитывать, что «секретность» держится на «трудности» получения секретного ключа из открытого.
Например, в RSA, для «взломщиков» существует проблема разложения сложного числа (открытый ключ) большой размерности (сто цифр и больше) на простые сомножители (секретный ключ). Это действительно так, если не существует рациональный способ автоматической генерации простых чисел большого размера. Трудность связана с тем, что сам процесс генерации, с одной стороны, должен исключать повторяемость, то есть, должен быть случайным, (для того, чтобы его не мог повторить другой участник процесса обмена информацией), а, с другой стороны, должна быть гарантия генерации именно простого числа большого размера. К сожалению (для науки) и к счастью (для создателей алгоритма), до сих пор процесс тестирования большого числа на «простоту» требует огромных затрат времени и технических ресурсов.
Это является одной из причин, по которой существующие асимметричные алгоритмы сложны для внедрения.
Коротко сложившуюся ситуацию можно назвать проблемой отсутствия правила.([6])
Для RSA – это отсутствие правила проверки «на простоту». На практике это приводит к тому, что часто используют псевдопростые числа.
Для КАМСИ в опубликованных исследованиях так же отсутствует простое правило проверки на «КАМСИ-шность». Это еще одна причина, по которой КАМСИ до сих пор не получила применения в криптографии.
В предлагаемой работе проблема «правила» для КАМСИ решена неожиданным образом: предложена ситуация, в которой нет необходимости в «правиле». Это возможно при условии, если к КАМСИ применяются преобразования, сохраняющие свойство КАМСИ (для простых чисел известно, что любые преобразования простых чисел дают сложные числа, но не наоборот). Такие преобразования КАМСИ разработаны в прелагаемой работе.
Для этого введены понятия КАМСИ-примитива и КАМСИ-композиции, которые можно считать аналогами простого и сложного числа в теории чисел.
По аналогии с RSA, в предлагаемом алгоритме, «секретом» является декомпозиция КАМСИ-композиции на примитивы. Особенность «секрета» однонаправленной функции на базе КАМСИ, в отличие от RSA, является то, что, если для сложного числа существует, в виде секретного ключа, набор
простых чисел – сомножителей, для которых безразличен порядок их использования для получения произведения (транзитивность), то для каждой КАМСИ-композиции существует, кроме набора примитивов, порядок
расположения их в композиции (не транзитивность).
