Копыленко В. - Асимметричный криптографический алгоритм на базе Конечно-Автоматной Модели
Если Вы хотите сохранить секрет, не доверяйте его никому.
Сенека (5 до н.э. - 65 н.э.),
Как следует из эпиграфа, проблема сохранения секретов волновала людей со времени появления секретов. Сенека до сих пор прав, и истина, знают двое - знает свинья, как говаривал папаша Мюллер, всегда будет актуальна.
Иллюстрацией этого в криптографии может служить наличие двух типов алгоритмов: симметричного и асимметричного.
Первый, как это существует до сих пор, обладает высоким быстродействием, но предполагает наличие секретного ключа, который должен быть известен минимум двум участникам процесса обмена информацией (знает свинья).
Второй тип алгоритма, асимметричный, до настоящего времени имеет малое быстродействие, сложную реализацию, но он имеет два ключа:
- один, который известен всем участникам обмена информацией, и
- второй - известный только одному участнику обмена информацией - тому, кому эта информация предназначается (см. рекомендацию Сенеки).
Это обстоятельство настолько существенно, что, несмотря на ряд преимуществ симметричных алгоритмов, они используются в криптографических протоколах только совместно с асимметричными алгоритмами.
Следует добавить, что, как мы покажем далее, асимметричные алгоритмы - это самое удивительное и, парадоксальное явление, и не только в криптографии. Действительно, в обыденной жизни всем понятно, что если все знают, как спрятан предмет, то нет большого секрета в том, как его найти. И вдруг в криптографии появляется способ, при котором все могут знать, как спрятан предмет.
Более того, любой может спрятать предмет. Но найти его может только тот, кто придумал, как его спрятать, а не тот, кто его спрятал. Конечно, это не очень строгая аналогия с асимметричным криптографическим алгоритмом, но вызывает те же ощущения.
Действительно, что может быть привлекательнее для защиты информации, передаваемой по незащищенному каналу, чем способ кодирования, при котором все знают ключ шифрования и могут им воспользоваться для кодирования информации, в том числе и недобросовестные участники информационного обмена. Но раскодировать ее может только единственный участник, который разработал алгоритм кодирования.
Как всегда, воплощение мечты решает меньше проблем, чем создает новых.
Тем не менее, в нашей работе мы сосредоточим внимание только на решении проблемы низкой производительности существующих асимметричных алгоритмов, которая не позволяет достаточно эффективно применить их в криптографии. Другими словами, предлагаемая работа будет посвящена решению проблемы создания асимметричного быстродействующего алгоритма.
Какие соображения используются при этом?
Причина низкой производительности существующих асимметричных алгоритмов заключается в том, что применяемые на практике алгоритмы используют, так называемую, длинную арифметику, то есть арифметику, предназначенную для работы с числами размером от сотни и более цифр. Вследствие этого быстродействие асимметричных алгоритмов на несколько порядков меньше симметричных алгоритмов.
Надежды на то, что с ростом быстродействия технических средств разрыв между быстродействием асимметричных и симметричных алгоритмов будет сокращаться, безосновательны. Это происходит потому, что с ростом быстродействия технических средств, при сохранении размера чисел, снижается степень защищенности алгоритма, а это, в свою очередь, приводит к необходимости увеличить размерность арифметики ().
Возникло целое направление в криптографии, так называемые теоретико-числовые алгоритмы (например, RSA), которое за последние двадцать лет привело к появлению большого числа оригинальных асимметричных алгоритмов и это создало иллюзию, что термины асимметричный алгоритм и длинная арифметика - синонимы.
Так ли это?
Для того, чтобы опровергнуть это утверждение, далее будет рассмотрен асимметричный алгоритм кодирования на базе конечно-автоматной модели.
- Будет показано, что, если трудность взлома RSA определяется сложностью выполнения операции разложения числа на простые сомножители (это и приводит к необходимости использования длинной арифметики), то для конечно-автоматной модели аналогичной операцией является декомпозиция кодера на простые компоненты.
- Будет показано, что сложность декомпозиции конечного автомата возрастает экспоненциально, в то время, как его быстродействие не зависит от размера его таблицы переходов .
По аналогии с понятиями сложного и простого числа в теории чисел, далее будут введены понятия композиции конечных автоматов и примитивов.
Особенность этих понятий заключается в том, что, сложное число в теории чисел представляет собой произведение простых чисел и это произведение не зависит от порядка расположения в нем сомножителей. Для конечного же автомата, эквивалентного композиции примитивов, имеют значение, как их набор, так и порядок их взаимного расположения в композиции, то есть, композиция автоматов не обладает свойством коммутативности.
Структура предлагаемой работы определялась тем обстоятельством, что до настоящего времени Теория Конечных Автоматов и Криптология развиваются параллельно и независимо. Каждая из них имеет специфический язык, объекты изучения, область применения и своих специалистов.
Это создает трудности при изложении материала:
- С одной стороны, для понимания сути проблемы, изложение должно предполагать знакомство читателя с Теорией Конечных Автоматов, хотя бы в объеме работы Zvi Kohavi "Switching and Finite Automata Theory".
- С другой стороны, изложение должно предполагать знакомство читателя с Криптологией, хотя бы в объеме работы Bruce Schneier "Applied Cryptography".
Понимая, что одновременное совмещение задачи просвещения и обсуждения предлагаемого способа решения проблемы создания асимметричного криптографического алгоритма, может привести к ситуации, когда ни та, ни другая задача не будет достаточно эффективно решена, автор выбрал компромиссный вариант.
В основу его положены соображения, что, принятый способ изложения может быть рассчитан хотя бы на одну из трех категорий читателей:
1. Читатель, который слабо знаком с Криптографией и Теорией Конечных Автоматов, но обладает достаточной математической культурой. Его интересует логика изложения и корректность проводимых расчетов, которые используются для оценки параметров предлагаемого асимметричного алгоритма.
Такой читатель может ограничиться Частью 1 (см. стр) и составить собственное мнение, насколько можно доверять выводам, сделанным в работе.
2. Читатель, который знаком с проблематикой предлагаемой работы. Такому читателю можно предложить предварительно познакомиться с работой Лунина А.В., Сальникова А.А Перспективы развития и использования асимметричных алгоритмов в криптографии (см. стр. и четырнадцатой главой работы Цви Кохави Память, определенность и конечные автоматы, сохраняющие информацию (см. стр. . Эти работы позволяют оценить существующее положение асимметричных алгоритмов в криптографии, и, после перехода к Части 1, оценить правильность выводов, сделанных в ней.
3. И, наконец, наиболее приятная автору третья категория читателей - это те, которые не обладают необходимой математической культурой и при этом не знакомы с проблематикой Криптографии и Теории Конечных Автоматов. Но ими движет здоровая природная любознательность. Таким читателям автор рекомендует поверить на слово, что все, о чем далее пойдет речь - очень интересно.
Если автор уже убедил Вас в этом, то ему остается порекомендовать, не теряя времени, как можно скорее перейти в одну из первых двух категорий читателей.
Мы ставим здесь перед собой задачу исследования множества объектов нашей любознательности, причем мы будем исследовать их с тем недоверием, с каким надо относиться к любой системе до тех пор, пока она не продемонстрирована нашим глазам или не доказана нашему разуму. Вольтер, О феноменах природы
Введение
Предлагаемая работа предполагает знания, хотя бы в объеме следующих работ:
- Лунин А.В. и Сальников А.А. Перспективы развития и использования асимметричных алгоритмов в криптографии. В ней перечислены преимущества асимметричных алгоритмов перед симметричными алгоритмами.
Там же показано, что главный недостаток существующих асимметричных алгоритмов - малая скорость кодирования, связанная с выполнением трудоемких математических преобразований. Это привело к тому, что существующие асимметричные алгоритмы применяются только для выполнения вспомогательных (относительно процесса обеспечения секретности) функций, таких, как кодирование ключей применяемых симметрических алгоритмов и тому подобное.
- Zvi Kohavi "Switching and finite automata theory". Книга была издана в 1978 году.
Zvi Kohavi, ссылаясь на работы других авторов сделал достаточно полное описание КАМСИ (Конечно-Автоматная Модель, Сохраняющая Информацию). (гл. 14).
В нашей работе мы построим криптографический алгоритм на базе КАМСИ. Наиболее ранняя работа о КАМСИ была опубликована во второй половине пятидесятых годов двадцатого столетия.
Более того, сегодня можно утверждать, что это были первые предложения асимметричного алгоритма ().
Способ применения КАМСИ для кодирования был описан Huffman D.A. за двадцать лет (см., стр.) до того, как Уитвелд Диффи и Мартин Хеллман сформулировали общую концепцию асимметричных алгоритмов. Почему же описанная Huffman D.A.
КАМСИ до сих пор не нашла применения в криптографии?
Для того, чтобы ответить на этот вопрос, следует обратиться к работам Уитвелда Диффи и Мартина Хеллмана.
Главная заслуга Уитвелда Диффи и Мартина Хеллмана заключалась в том, что они ввели понятие однонаправленной функции.
Упрощенно, идею однонаправленной функции можно представить на примере трафика движения по городским улицам с односторонним движением.
Допустим, водитель прибыл в пункт Б из пункта А (решил прямую задачу). Спрашивается
- Каким путем он должен воспользоваться, чтобы вернуться в пункт А (обратная задача)?
- Можно ли, двигаясь из А в Б, одновременно получить информацию о пути движения из Б в А? (чтобы упростить решение обратной задачи)
Не трудно видеть, что в рассмотренной ситуации, для любого водителя, участвующего в этом процессе, есть единственный способ поиска решения обратной задачи (то есть, возвращение из пункта Б в пункт А) - это полный перебор возможных вариантов.
Характерная особенность рассмотренного процесса заключается в том, что сложность решения прямой задачи (движение из А в Б) намного проще решения обратной задачи, которая может даже не иметь решения. Именно по этой причине, функция, описывающая рассмотренную выше ситуацию, называетсяоднонаправленной.
Положение может измениться, если кто-либо из участников процесса движения секретно обзаведется, например, вертолетом (или воздушным шаром, или чем-либо, позволяющим ему изменить механизм движения). Понятно, что для него решение прямой задачи (движение из А в Б), и обратной (движение из Б в А), обладают одинаковой сложностью.
Такую задачу называют однонаправленной задачей с секретом. В рассмотренном случае секретом является наличие вертолета у одного из участников ().
Таким образом, для обладателей секрета, решение обратной задачи имеет сложность, такую же, как и для прямой задачи, в то время как для всех остальных участников движения, обратная задача может даже не иметь решения.
Уитвелд Диффи и Мартин Хеллман показали, что
- Асимметричный криптографический алгоритм может быть построен только на базе однонаправленной функции; Например, асимметричный алгоритм RSA основан на том, что сложность вычисления произведения двух простых чисел неизмеримо проще разложения этого произведения на простые сомножители. До настоящего времени все усовершенствования мало упростили операцию разложения на простые сомножители.
То есть, при достаточно большом размере сомножителей (500 и более бит), обратная задача практически не разрешима.
- Однонаправленная функция, на базе которой создан асимметричный криптографический алгоритм, должна обладать секретом. Именно это обстоятельство позволяет обладателю секрета, в отличие от остальных, выполнить обратную операцию (декодирование) за приемлемое время и с достаточными для этого вычислительными ресурсами.
Например, в RSA прямая задача (кодирование), выполняется с применением упомянутого выше произведения двух простых чисел. Произведение этих простых чисел известно всем, желающим закодировать информацию, и называется открытым ключем.
Однако, легко раскодировать информацию может только обладатель секрета -знания сомножителей - двух простых чисел, которые образуют произведение (открытый ключ) и называются секретным ключем.
Особенность такого процесса заключается в том, что открытый ключ не может использоваться для декодирования и по этому его допустимо передавать по незащищенным каналам, с тем, чтобы им мог воспользоваться любой, желающий передать конфиденциальную информацию, в то время, как секретный ключ хранится только у хозяина сгенерированных ключей.
Вернемся к КАМСИ (Конечно-Автоматной Модели, Сохраняющей Информацию). Как это будет показано ниже, применение КАМСИ в криптографии предполагает существование пары конечных автоматов, один из которых выполняет функцию кодера, и другой, инверсный кодеру, функцию декодера.
В работах, список которых приведен на стр., показан способ построения инверсных КАМСИ (необходимых для декодирования).
Ниже будет показано, что уже при числе состояний таблицы переходов кодера, равном 1250, сложность построения инвертора (декодера) требует около 260 ~ 1018 операций (В(см. стр.) приведены значения Больших чисел). Такое количество операций показывает, что практически невозможно построить инвертор. Описанная в цитированных работах КАМСИ представляет собой однонаправленную функцию, у которой сложность построения таблицы переходов кодера линейно зависит от числа состояний, а сложность построения инвертора -приближается к экспоненциальной зависимости.
Сложность построения инвертора одинакова для всех участников процесса обмена информацией, то есть, в таком виде КАМСИ представляет собой однонаправленную функцию без секрета. Это объясняет, почему КАМСИ до сих пор не были использованы в криптографии.
Факт тем более огорчительный, что по всем остальным параметрам КАМСИ превосходят существующие асимметричные алгоритмы. КАМСИ обладают:
- Высоким быстродействием. Оно определяется временем перехода конечного автомата из одного состояния в другое и не зависит от числа состояний таблицы переходов.
- Легкой перестройкой оконечного устройства для реализации очередного криптографического алгоритма.
- Простотой реализации в виде аппаратного устройства, например на базе FPGA (настраиваемые матрицы). Кроме того,
- реализация алгоритмов на базе КАМСИ использует только логические (самые быстрые) операции.
Почему же, несмотря на то, что КАМСИ были достаточно полно исследованы более сорока лет назад, они не нашли до сих пор применения в криптографии, несмотря на то, что существующие, так называемые, паблик-кей технологии по производительности и сложности реализации оставляют желать лучшего?
Этому может быть несколько объяснений:
- Описанный в литературе способ применения КАМСИ представляет собой однонаправленную функцию без секрета.
Действительно, асимметрия здесь заключается в том, что алгоритмы кодирования отличаются от алгоритмов декодирования. Однако, сложность построения инвертора экспоненциально зависит от ц (одного из параметров КАМСИ, о котором будет сказано ниже).
Эта сложность в этом случае одинакова для всех участников процесса обмена информацией.
- Можно высказать различные предположения о том, почему эта проблема не была разрешена до сих пор. Но, учитывая высокий уровень ученых -специалистов в области Теории Конечных Автоматов, которые разрабатывали теорию КАМСИ (см. список литературы на стр.), можно выделить одно - Теория Конечных Автоматов изначально создавалась только для анализа и технической реализации алгоритмов управления технологическими процессами, которые разрабатывались в других областях науки.
То есть, Теория Конечных Автоматов изначально создавалась для анализа алгоритмов управления технологическими процессами, разрабатываемыми вне нее. В криптографии же возникает проблема генерации криптографических алгоритмов, которые должны обладать определенными свойствами.
Каковы же перспективы применения КАМСИ в криптографии?
В каком направлении следует исследовать проблему создания однонаправленной функции с секретом на базе КАМСИ?
Очень заманчиво, но бесполезно для применения в криптографии, попытаться усовершенствовать алгоритм инвертирования КАМСИ.
Как любое усовершенствование, оно представляет технический интерес. Однако, любое усовершенствование облегчит жизнь всем участникам процесса обмена информацией, в том числе, и недобросовестным. Так, рассмотренные Цви Кохави в разделе называются линейными потому, что сложность их преобразования линейно зависит от размера Машины.
Однако, это облегчает жизнь всем участникам процесса обмена информацией. То есть, оно не может привести к созданию секрета однонаправленной функции.
Кроме того, трудно рассчитывать, что любые усовершенствования удастся длительно держать в секрете, тем более, что понятие недобросовестный пользователь среди участников информационного процесса может изменяться в зависимости от характера защищаемой информации.
Все это показывает, что сама по себе, разработка теории КАМСИ не может привести к созданию однонаправленной функции с секретом.
Есть и еще одно обстоятельство, которое создавало проблему применения КАМСИ в криптографии. Это - необходимость автоматизации процесса генерации кодера.
Проблема генерации существует в любом криптографическом протоколе, но не существует в Теории Конечных Автоматов, так как к ней обращаются с готовым алгоритмом, который следует проанализировать.
Для симметричного алгоритма процесс решен достаточно успешно, но при этом возникает проблема защищенной доставки нового сгенерированного ключа по назначению.
В асимметричном алгоритме проблема защищенной доставки отсутствует, так как открытый ключ не от кого охранять, а секретный - некому посылать.
При этом следует учитывать, что секретность держится на трудности получения секретного ключа из открытого.
Например, в RSA, для взломщиков существует проблема разложения сложного числа (открытый ключ) большой размерности (сто цифр и больше) на простые сомножители (секретный ключ). Это действительно так, если не существует рациональный способ автоматической генерации простых чисел большого размера. Трудность связана с тем, что сам процесс генерации, с одной стороны, должен исключать повторяемость, то есть, должен быть случайным, (для того, чтобы его не мог повторить другой участник процесса обмена информацией), а, с другой стороны, должна быть гарантия генерации именно простого числа большого размера.
К сожалению (для науки) и к счастью (для создателей алгоритма), до сих пор процесс тестирования большого числа на простоту требует огромных затрат времени и технических ресурсов.
Это является одной из причин, по которой существующие асимметричные алгоритмы сложны для внедрения.
Коротко сложившуюся ситуацию можно назвать проблемой отсутствия правила. ()
Для RSA - это отсутствие правила проверки на простоту. На практике это приводит к тому, что часто используют псевдопростые числа.
Для КАМСИ в опубликованных исследованиях так же отсутствует простое правило проверки на КАМСИ-шность. Это еще одна причина, по которой КАМСИ до сих пор не получила применения в криптографии.
В предлагаемой работе проблема правила для КАМСИ решена неожиданным образом: предложена ситуация, в которой нет необходимости в правиле. Это возможно при условии, если к КАМСИ применяются преобразования, сохраняющие свойство КАМСИ (для простых чисел известно, что любые преобразования простых чисел дают сложные числа, но не наоборот).
Такие преобразования КАМСИ разработаны в прелагаемой работе.
Для этого введены понятия КАМСИ-примитива и КАМСИ-композиции, которые можно считать аналогами простого и сложного числа в теории чисел.
По аналогии с RSA, в предлагаемом алгоритме, секретом является декомпозиция КАМСИ-композиции на примитивы. Особенность секрета однонаправленной функции на базе КАМСИ, в отличие от RSA, является то, что, если для сложного числа существует, в виде секретного ключа, набор простых чисел - сомножителей, для которых безразличен порядок их использования для получения произведения (транзитивность), то для каждой КАМСИ-композиции существует, кроме набора примитивов, порядок расположения их в композиции (не транзитивность).
Нужны ли сегодня новые асимметричные алгоритмы?
Мы рассмотрели особенности асимметричных алгоритмов.
Коротко рассмотрели отличие применения асимметричных алгоритмов от симметричных.
Попытались понять причины, по которым КАМСИ в течение последних сорока лет не были применены в криптографии, несмотря на то, что существующие и применяемые асимметричные алгоритмы основаны на применении длинной арифметики, что делает невозможным использовать их самостоятельно из-за малой скорости обработки информации.
Тем не менее, криптография существует, развивается и нет ощущения, что малая скорость RSA и ему подобных не позволяет решить какие-либо проблемы защиты информации.
Более того, внимательный взгляд на пятитысячную историю криптографии показывает, что большую часть времени существования криптографии она благополучно обходилась только симметричными алгоритмами.
Нуждался ли Г ай Юлий Цезарь в асимметричных алгоритмах кодирования?
А сотрудники многочисленных разведок (разведчики и шпионы)?
Всевозможные дипломатические представительства?
Можно ответить однозначно: нет.
Более того, каждый, кто предложил бы Цезарю систему обмена информацией по схеме все - одному (все кодируют, но только Цезарь декодирует), рисковали бы своей жизнью.
Задумывались ли Вы, почему папаша Мюллер так возбудился, обнаружив пальчики Штирлица на чемодане радистки Кэт? Почему в этом случае его больше интересовал информационный канал, а не передаваемые по нему сообщения - к тому моменту у него скопилось много перехваченных шифровок.
Во всех упомянутых случаях секретной была не только закодированная информация, но и информационный процесс, который включал в себя информационный канал и причастных к этому процессу людей. Более того, обеспечение секретности информационного процесса зачастую ставилось на первое место.
Иногда это приводило к абсурду (). Известно, что в СССР работы, связанные с криптографией и люди, которые ею занимались, были засекречены. Нуждались ли подобные системы в криптографии с открытым ключем?
Конечно, нет.
Существовали ли в подобной криптографии такие проблемы, как контроль целостности документа, контроль подписи (истинности) и тому подобное? Защиты базы данных?
Существовали, но решения были больше административные, чем криптографические.
Параллельно с рассмотренной выше криптографией, которую можно назвать государственной, на первых порах не так интенсивно, но настойчиво развивалась другая криптография, которую можно назвать коммерческой (). В ней, на первом этапе, решались сходные задачи, но условия их решения были другими.
Главное отличие государственной криптографии от коммерческой заключается в качестве информационного канала. В первом случае информационный канал охраняется всей мощью государственного аппарата и поэтому кодирование информации, в первую очередь, предназначено для защиты шифруемой информации от представителей этого самого аппарата.
Во втором случае участники информационного процесса - кроме тех, для кого информация предназначается, это: а) люди, заинтересованные в не легитимном получении информации, б) люди, заинтересованные изменить или заменить передаваемую информацию и в) случайные люди.
