Причина низкой производительности существующих асимметричных
Причина низкой производительности существующих асимметричных алгоритмов заключается в том, что применяемые на практике асимметричные алгоритмы используют, так называемую, «длинную» арифметику, то есть арифметику, предназначенную для работы с числами размером от сотни и более цифр. Вследствие этого быстродействие асимметричных алгоритмов на несколько порядков меньше симметричных алгоритмов.
Надежды на то, что с ростом быстродействия технических средств разрыв между быстродействием асимметричных и симметричных алгоритмов будет сокращаться, безосновательны. Следует понять, что с ростом быстродействия технических средств, при сохранении размера чисел, снижается степень защищенности алгоритма, а это, в свою очередь, приводит к необходимости увеличить размерность «арифметики» ([1]).
Возникло целое направление в криптографии, так называемые теоретико-числовые алгоритмы (например, RSA), которое за последние двадцать лет привело к появлению большого числа оригинальных асимметричных алгоритмов и это создало иллюзию, что термины «асимметричный алгоритм» и «длинная арифметика» - синонимы.
Так ли это?
Для доказательства ошибочности этих представлений, далее будет рассмотрен асимметричный алгоритм кодирования на базе конечно-автоматной модели.
Будет показано, что, если трудность взлома RSA связана со сложностью выполнения операции разложения числа на простые сомножители (это и приводит к необходимости использования «длинной арифметики»), то для конечно-автоматной модели аналогичной операцией является декомпозиция кодера на простые компоненты.
Далее будет показано, что сложность декомпозиции конечного автомата возрастает экспоненциально, в то время, как его быстродействие не зависит от размера его таблицы переходов.
По аналогии с понятиями сложного и простого числа в теории чисел, далее будут введены понятия композиции конечных автоматов и примитивов. Особенность заключается в том, что если сложное число в теории чисел всегда может быть разложено на простые числа, для которых отсутствует понятие порядка их взаимного расположения в произведении (коммутативность перестановок сомножителей в произведении), то для конечного автомата, эквивалентного композиции примитивов, имеют значение, как их набор, так и порядок их взаимного расположения в композиции. Другими словами, композиция автоматов из примитивов не обладает свойством коммутативности.
КАМСИ (Конечно- Автоматная Модель, Сохраняющая Информацию) были достаточно полно исследованы более сорока лет назад, и, все-таки, они не нашли до сих пор применения в криптографии. Почему же это - так, несмотря на то, что существующие, так называемые, паблик-кей технологии (технологии с открытым ключом) по производительности и сложности реализации оставляют желать лучшего?
Этому может быть несколько причин.
Описанный в литературе способ применения КАМСИ представляет собой однонаправленную функцию без секрета.
Действительно, асимметричность здесь объясняется тем, что алгоритмы кодирования отличаются от алгоритмов декодирования. Однако, сложность построения инвертора (декодера) экспоненциально зависит от µ (одного из параметров КАМСИ, о котором будет сказано ниже) и эта сложность одинакова для всех участников процесса обмена информацией (как для отправителя, так и для всех участников информационного процесса).
Можно высказать различные предположения о том, почему эта проблема не была разрешена до сих пор. Но, учитывая высокий уровень ученых – специалистов в области Теории Конечных Автоматов, которые разрабатывали теорию КАМСИ (см. список литературы на стр. 46), можно привести одно - Теория Конечных Автоматов изначально создавалась только
для анализа и реализации алгоритмов управления технологическими процессами, которые разрабатывались другими и в других областях науки. В криптографии же возникает проблема генерации криптографических алгоритмов, которые должны обладать определенными свойствами.
Каковы же перспективы применения КАМСИ в криптографии?
Очень заманчиво, но бесполезно для применения в криптографии, попытаться усовершенствовать алгоритм инвертирования КАМСИ. Разумеется, что как любое усовершенствование, оно интересно.
Однако, любое усовершенствование «облегчает жизнь» всем участникам процесса обмена информацией, в том числе, и недобросовестным. Так, рассмотренные Цви Кохави (см. Список литературы, стр. 46) описываются последовательные линейные Машины, которые называются линейными потому, что сложность их преобразования линейно зависит от размера Машины, однако, это «облегчает жизнь» всем
участникам процесса обмена информацией. То есть, оно не может привести к созданию «секрета» однонаправленной функции. Более того, трудно рассчитывать, что любые усовершенствования удастся длительно держать в секрете, тем более, что понятие «недобросовестный пользователь» среди участников информационного процесса может изменяться в зависимости от характера защищаемой информации.
Из этого следует, что сама по себе разработка теории КАМСИ не может привести к созданию однонаправленной функции с секретом.
Есть и еще одно обстоятельство, которое создавало проблему применения КАМСИ в криптографии: это - необходимость автоматизации процесса генерации кодера ([2]).
Хотя для симметричного алгоритма этот процесс решен достаточно успешно, но при этом возникает проблема «защищенной» доставки нового сгенерированного ключа участнику процесса обмена информацией. В асимметричном алгоритме проблема «защищенной» доставки отсутствует, так как открытый ключ нет необходимости охранять, а секретный – некому посылать. В этом случае «секретность» держится на «трудности» получения закрытого ключа из открытого.
Например, в RSA, для «взломщиков» существует проблема разложения сложного числа (открытый ключ) большой размерности (сто цифр и больше) на простые сомножители (секретный ключ). Это держится на том, что не существует рациональный способ автоматической генерации простых чисел большого размера. К сожалению (для науки) и к счастью (для создателей алгоритма), до сих пор процесс тестирования большого числа на «простоту» требует огромных затрат времени и технических ресурсов (в этом и заключается «секрет» однонаправленной функции для RSA).
Это одна из причин, по которой существующие асимметричные алгоритмы сложны для внедрения.
Коротко сложившуюся ситуацию можно назвать проблемой отсутствия правила.([3])
Для RSA – это отсутствие правила проверки «на простоту». На практике это приводит к тому, что часто используют псевдопростые числа.
Для КАМСИ в опубликованных исследованиях так же отсутствует простое правило
проверки на «КАМСИ-шность».
Это главная причина, по которой КАМСИ до сих пор не получила применения в криптографии.
В предлагаемой работе проблема «правила» для КАМСИ решена неожиданным образом: предложена ситуация, в которой нет необходимости
проверки на «КАМСИ-шность». Это стало возможным потому, что разработаны операции преобразования КАМСИ, сохраняющие свойство КАМСИ (в отличие от простых чисел, о которых известно, что любые преобразования простых чисел дают сложные числа, но не наоборот).
В предлагаемой работе введены понятия КАМСИ-примитива
и КАМСИ-композиции, которые можно считать аналогами простого и сложного числа в теории чисел.
В предлагаемом алгоритме, «секретом» является разложение КАМСИ-композиции на примитивы.
Особенность «секрета» однонаправленной функции на базе КАМСИ, в отличие от RSA, является то, что, если для сложного числа существует, в виде секретного ключа, набор
простых чисел – сомножителей, для которых безразличен порядок их использования для получения произведения (коммутативность), то для каждой КАМСИ-композиции, кроме набора
примитивов, существенным является порядок
расположения их в композиции.
В работе «Асимметричный криптографический алгоритм на базе Конечно-Автоматной Модели, Сохраняющей Информацию (КАМСИ)» ([4]) мы рассмотрели свойства КАМСИ и возможности реализации на их основе различных криптографических протоколов.
В предлагаемой работе мы рассмотрим основные свойства КАМСИ, которые позволят применить их для реализации асимметричных криптографических алгоритмов.
Для этого мы рассмотрим следующие вопросы:
Начнем с определения понятия однонаправленной функции.
