Копыленко В. - Асимметричный криптографический алгоритм на базе Конечно-Автоматной Модели

Если Вы хотите сохранить секрет, не доверяйте его никому.
Сенека (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 и ему подобных не позволяет решить какие-либо проблемы защиты информации.
Более того, внимательный взгляд на пятитысячную историю криптографии показывает, что большую часть времени существования криптографии она благополучно обходилась только симметричными алгоритмами.
Нуждался ли Г ай Юлий Цезарь в асимметричных алгоритмах кодирования?
А сотрудники многочисленных разведок (разведчики и шпионы)?
Всевозможные дипломатические представительства?
Можно ответить однозначно: нет.
Более того, каждый, кто предложил бы Цезарю систему обмена информацией по схеме все - одному (все кодируют, но только Цезарь декодирует), рисковали бы своей жизнью.
Задумывались ли Вы, почему папаша Мюллер так возбудился, обнаружив пальчики Штирлица на чемодане радистки Кэт? Почему в этом случае его больше интересовал информационный канал, а не передаваемые по нему сообщения - к тому моменту у него скопилось много перехваченных шифровок.
Во всех упомянутых случаях секретной была не только закодированная информация, но и информационный процесс, который включал в себя информационный канал и причастных к этому процессу людей. Более того, обеспечение секретности информационного процесса зачастую ставилось на первое место.
Иногда это приводило к абсурду (). Известно, что в СССР работы, связанные с криптографией и люди, которые ею занимались, были засекречены. Нуждались ли подобные системы в криптографии с открытым ключем?
Конечно, нет.
Существовали ли в подобной криптографии такие проблемы, как контроль целостности документа, контроль подписи (истинности) и тому подобное? Защиты базы данных?
Существовали, но решения были больше административные, чем криптографические.
Параллельно с рассмотренной выше криптографией, которую можно назвать государственной, на первых порах не так интенсивно, но настойчиво развивалась другая криптография, которую можно назвать коммерческой (). В ней, на первом этапе, решались сходные задачи, но условия их решения были другими.
Главное отличие государственной криптографии от коммерческой заключается в качестве информационного канала. В первом случае информационный канал охраняется всей мощью государственного аппарата и поэтому кодирование информации, в первую очередь, предназначено для защиты шифруемой информации от представителей этого самого аппарата.
Во втором случае участники информационного процесса - кроме тех, для кого информация предназначается, это: а) люди, заинтересованные в не легитимном получении информации, б) люди, заинтересованные изменить или заменить передаваемую информацию и в) случайные люди.



Криптография - Алгоритмы

В этих условиях необходимость обмена ключами при симметричных алгоритмах создает трудности, которые иногда не преодолимы.
При применении асимметричных алгоритмов проблемы обмена ключами просто не существует: один из двух ключей может быть открыт для любого, желающего закодировать информацию. В то же время второй ключ, в качестве секретного, хранится у получателя информации, и при этом нет необходимости передавать этот ключ по информационному каналу.
Иные условия работы коммерческих криптографических систем породили такие задачи, как
- Защита базы данных;
- Контроль целостности документа;
- Электронная подпись;
- Электронные деньги и тому подобное.
Некоторые из этих задач могут быть решены только применением либо только асимметричных криптографических алгоритмов, либо комбинацией асимметричных и симметричных алгоритмов. Более того, появление асимметричных алгоритмов позволило решать такие задачи, которые с трудом можно отнести к области защиты информации.
Это упомянутые выше электронная подпись, электронные деньги и тому подобное.
Решение этих задач стало возможным только благодаря применению асимметричных криптографических алгоритмов, с одной стороны, а с другой стороны, сделало возможным решение многих задач взаимодействия абонентов без необходимости непосредственного контакта в сети. Другими словами, появление асимметричных алгоритмов позволило создать принципиально новый способ взаимодействия людей, при котором их географическое расположение не имеет значение.
Иногда быстрое внедрение в практику прогрессивных разработок приводит к трагикомическим, а для некоторых - катастрофическим, ситуациям.
В первой половине девяностых годов фирма DigiCash разработала технологию Электронных денег в Сети, а крупнейший банк Mark Twain Bank и 1995 году взялся опробовать разработанную систему.
Результаты оказались настолько впечатляющими, что в течение следующих трех лет последовало еще восемь сделок о лицензировании технологии с крупнейшими европейскими банками, австралийским банком, влиятельным финским провайдером Internet, японской корпорацией и, наконец, - верх признания - c консервативным швейцарским банком Cmdit Suisse.
И вдруг ..., сегодня фирма DigiCash объявила о своем банкротстве.
Причиной краха оказалось главное преимущество разработанных DigiCash платежных средств - анонимность, то есть, качество, которое делало разработанные фирмой электронные платежные средства похожими на наличные деньги.
Именно это качество первыми по достоинству оценили фирмы - производители порнографии. Анонимность при расчетах позволила резко увеличить доходы этих фирм.
Это вызвало энергичные протесты протестантских организаций США. Они призвали бойкотировать по всему миру банки, которые поддерживают разработки DigiCash и ... вот Вам результат.
Приведенный курьез показывает, что мало создать толковое техническое средство, следует затратить не меньше, а часто и больше интеллектуальных усилий на решение не только технических, но и социальных проблем.
В связи с решением технических проблем появилось понятие протокол, которое будет достаточно подробно рассмотрено в следующем разделе.
В нем будет показано, как наиболее эффективно можно использовать асимметричные алгоритмы на базе КАМСИ.

Особенности применения криптографического алгоритма с открытым ключем

Криптографическая система может быть сильна лишь настолько, насколько таковыми являются алгоритмы шифрования, алгоритмы цифровой подписи, односторонние хэш-функции и коды идентификации сообщений, на которые она опирается. Взломайте что-нибудь одно, и вы взломаете систему.
И как можно построить слабую структуру из крепких материалов, так и возможно построить слабую криптографическую систему из надежных алгоритмов и протоколов.
Брюс Шнайер Подводные камни безопасности в криптографии
Приведенные в эпиграфе слова Брюса Шнайера - это мнение человека, который стоял у истоков современной криптографии и продолжает сейчас активно развивать ее. В перечне алгоритмов, определяющих качество криптографической системы, присутствует криптографический алгоритм (из перечня Б.Шнайера -алгоритм шифрования) - одна из четырех составляющих системы, и, кроме того, определяет алгоритмы функционирования остальных компонентов системы, в том числе и их качество.
1. Например, в качестве алгоритма шифрования в существующихкриптографических системах применяются симметричные алгоритмы. Эти алгоритмы просты в реализации, обладают высоким быстродействием и устойчивы к взлому.
Пока информационные системы предназначались для обслуживания относительно небольшого числа абонентов, свойства симметричных алгоритмов обеспечивали все требования, предъявляемые к криптографическим системам. С увеличением сложности информационных систем стали проявляться проблемы, связанные с применением симметричных алгоритмов: а. Применение симметричного алгоритма в информационной системе, основано на существовании секрета для двоих - ключа для кодирования и декодирования конфиденциальной информации, которой могут обмениваться эти абоненты.
о Для информационной системы, обслуживающей n абонентов
общее число ключей N (всевозможных пар из П) можно вычислить по формуле. N= n( n-1)/2.
o Это значит, что для информационной системы, обслуживающей П=100 абонентов, следует сгенерировать и обеспечить секретность при обмене ключами не менее N =4900 ключей. о Информационная система, обслуживающая сто абонентов - это маленькая система, но уже при П=200 число ключей (число
сочетаний из 200 по 2) равно N19800. При П=1000 абонентов (количество абонентов локальной информационной системы) число ключей равно N=499000.
Понятно, что такое число ключей требует создания отдельной службы обслуживания в системе, которая обеспечивает генерацию, мониторинг и секретность распределения ключей.
b. Криптографический алгоритм в системе применяется не только для шифрования текста, но и для обеспечения его авторизации, идентификации и контроля целостности. Это приводит к тому, что при использовании симметричного алгоритма, вместе с текстом абонент должен хранить ключ кодирования - декодирования.
С. Учитывая, что каждый ключ известен, минимум, двум абонентам,
возникает необходимость периодически менять ключи. Это приводит к тому, что каждый абонент вынужден, наряду с действующими N ключами, сохранять другие ключи, которые использовались ранее для текстов из его архива (это необходимо в случае, когда сохраняются документы, для которых важна не только информация, но и признаки ее достоверности и сохранности).
Ситуация становится еще более сложной при необходимости обеспечить защиту информации в банковских системах (платежные системы, электронные деньги и тому подобное).
2. Как альтернативу применения симметричных алгоритмов, рассмотрим преимущества криптографических алгоритмов c открытым ключем:
a. Каждый абонент открытой криптографической системы, имеет два ключа - открытый, известный всем, и секретный, известный только одному абоненту - хозяину ключа. При этом в криптографической системе:
о открытый ключ может передаваться по незащищенным информационным каналам.
о секретный ключ известен только одному абоненту и для нормальной работы системы никогда не возникает необходимость передавать этот ключ кому бы то ни было.
b. Криптографическая система с открытым ключем, обслуживающая n абонентов имеет n открытых и n секретных ключей, то есть, N=2n.
С. Система требует генерации количества ключей в (n-1)/4 раз меньше, чем для симметричной системы.
И всё-таки, есть причина, по которой существующие криптографические алгоритмы с открытым ключем не получили достойного применения - это их малое быстродействие. Поэтому они выполняют в системах вспомогательные
11 Кроме того, в открытых системах нет необходимости организовать процесс распределения ключей. Забавно, но приведенное соотношение становится не в пользу систем с открытым ключемпри П 5. .
Такое условие соответствует системам, обслуживающим государственные организации. Это одно из обстоятельств, объясняющих причину, по которой во многовековой истории криптографии применялись симметричные алгоритмы.
Потребность систем с открытым ключем возникла с появлением негосударственных (научных, коммерческих и т.п. систем) только в 20 веке.
функции. Объясняется это тем, что все существующие алгоритмы с открытым ключем используют особые свойства простых чисел.
Эти свойства становятся определяющими для чисел, которые можно записать с применением 100 и более цифр, потому, что их преобразования требуют, так называемой, длинной арифметики. Быстродействие таких систем в тысячу раз меньше существующих симметричных алгоритмов.
Характерная особенность арифметических операций над числами заключается в том, что они коммутативны. Поэтому и существующие открытые алгоритмы коммутативны. Этот факт можно показать с помощью выражения, из которого видно, что перестановка операторов кодирования Ea () и декодирования Da () не изменяет результата декодирования:
Форм. 1
Db (Eb (Da (Ea (P))) = Db (Da (Eb (Ea (Р))))^Р
где:
- Ea (),Da 0 - операторы кодирования и декодирования абонента А. Соответственно, открытый и секретный ключи абонента А будем обозначать Ea., Da
- P- исходный текст.
- Ea (P) - процесс кодирования текста P открытым ключем абонента А. Как правило, это происходит при необходимости защитить содержание текста P, предназначенного для абонента А. Иногда, закодированный текст мы так же будем обозначать
Ea(P)^J
- Da (Ea (P)) ^P - процесс декодирования с помощью секретного ключа DA абонента А. Особенность этой записи заключается в том, что процесс, записанный таким способом, исполняется, справа налево, то есть: Ea (P) ^ Da (Ea (P)) ^P. В нашем случае, сначала выполняется операция EA (P) - кодирование открытым ключем, и после этого - декодирование.
В такой записи отсутствуют указания на время и место выполнения операций. Единственная информация, которую можно получить из подобной записи - это порядок (очередность) их исполнения.
- Левая часть приведенного выше выражения Db(Eb(Da(Ea(P))))^P описывает следующую последовательность операций:
о Один из абонентов сети (но не абонент А) кодирует текст
P (Ea(P)^J) и передает его через незащищенный канал абоненту А.
о Абонент А выполняет операцию Da(Ea(P)) ^Р и получает предназначенный ему текст P..
о Абонент А кодирует текст P : Eb(Da(Ea(P))) и передает его по незащищенному каналу абоненту В.
о Абонент В декодирует принятое сообщение:
Db(Eb(Da(Ea(P))))^P . .
- Правая частьDb (Da (Eb (Ea (P))))^P отличается от левой части положением операторов Ев 0 и Da 0, то есть порядком исполнения этих операторов. Знак тождества "=" между левыми и правыми частями показывает, что перестановка операторов Ев 0 и Da 0 не изменяет результата.
Определение. Алгоритм, который допускает перестановку операций в выражении виданазывается коммутативным.
Примером такого алгоритма являются такие арифметические операции, как умножение и сложение.
Известно, что любые комбинации этих операций также коммутативны, в том числе и существующие асимметричные криптографические алгоритмы.
Следствие. Так как перестановка операций в выражениине меняет тождества, то выражение имеет 24 эквивалентные формы (n!), так как любая из этих форм имеет один и тот же результат кодирования.
Отсюда следует, что коммутативность криптографического алгоритма уменьшает число различных способов кодирования, то есть снижает надежность алгоритма. Пример. Допустим, существует текст J, полученный после последовательности операций ,,.(...
Da (.Db(.Eb(P)).).)^J.
Тогда, если криптографический алгоритм коммутативен, то выполняется тождество:
Ea (Eb (...(...Da (.Db (.Eh (P)).).).)))=
= Eb (Ea (.(.Da (.Db (.Eh (1)).).).)))=
~.( .(EH (і)я ¦я)я ¦я)
которое показывает, что результаты применения операций Ea ()и Eb () одинаковы, независимо от порядка их применения.
Если алгоритм не коммутативен, то для последовательности ... (.(.Da (.Db (. Eh (P)).).)^J существует единственный порядок декодирования, обратный порядку кодирования и начинается он с Dh (Eh (P)). Как это будет показано ниже, некоммутативность криптографического алгоритма позволяет упростить некоторые функции системы и увеличить ее надежность.
Прежде, чем рассматривать различные аспекты применения асимметричных алгоритмов, рассмотрим понятие протокола.
Что же такое протокол?
В работе Леонида Левкович-Маслюка() приводится, на мой взгляд, самое корректное определение криптографического протокола:
.. .что такое протокол, сказать точно нельзя. Это такая вещь, которую можно на примерах пояснить, но не определить формально. Понятие протокола появилось в программировании.
Грубо говоря, это распределенный алгоритм (то есть алгоритм, выполняемый несколькими участниками) плюс соглашения о формате пересылаемых сообщений, о действиях в случае сбоев и т. д. Есть три задачи криптографии - обеспечить конфиденциальность, целостность и неотслеживаемость. Считается, что если протокол обеспечивает хотя бы одно из этих свойств, то это криптографический протокол.
Так как подавляющее число работ, вышедших после цитированной выше работы Брюса Шнайера - чаще всего, недобросовестное заимствование его текстов, то мне остается отослать любознательного читателя к его работе, которую можно найти в Интернете. Она представлена в двух вариантах: на языке оригинала () и неплохим переводом на русский язык ().
Мы же добавим некоторые соображения:
По настоящему массовое применение криптографии стало возможным только после появления асимметричных алгоритмов.
Действительно, проблемы авторизации, имитации, сохранения целостности и тому подобное, при штучном применении криптографии (правительственные информационные каналы и тому подобное) решаются административными методами (службы обеспечения секретности, дипкурьеры и тому подобное). Б'ольшая часть функций существующих криптографических протоколов выполняются при совместном применении асимметричных и симметричных алгоритмов.
Это объясняется тем, что существующие асимметричные алгоритмы в десятки тысяч раз медленнее симметричных, поэтому они применяются для выполнении вспомогательных функций. Однако, применение симметричных алгоритмов снижает надежность протокола, так как при этом ключ знают, минимум, два участника информационного процесса.
Тем временем, появились такие криптографические протоколы, как Электронные деньги, которые, с одной стороны, не могут быть реализованы без применения асимметричных алгоритмов, а с другой стороны, при существующих асимметричных алгоритмах с их малым быстродействием и громоздкой реализацией, имеют большие трудности при внедрении, так как требуют достаточно сложную и дорогостоящую аппаратуру.
Рассмотрим примеры применения КАМСИ в некоторых протоколах ().

Примеры выполнения некоторых протоколов

В литературе существует описание большого числа протоколов. Они отличаются друг от друга набором функций, для реализации которых предназначена система криптографических алгоритмов, которые применяются в системе.
Приведенные примеры предназначены для обсуждения преимущества применения асимметричного криптографического алгоритма, который не коммутативен и обладает быстродействием, соизмеримым с симметричным алгоритмом.





    Работа с информацией: Безопасность - Защита - Софт - Криптография