Копыленко Владимир Матвеевич : другие произведения.

Криптографическая конечно-автоматная модель

Самиздат: [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь|Техвопросы]
Ссылки:
 Ваша оценка:
  • Аннотация:
    Рассмотрен асимметричный алгоритм кодирования на базе конечно-автоматной модели. Показано, что, если трудность взлома RSA определяется сложностью выполнения операции разложения числа на простые сомножители (это и приводит к необходимости использования ћдлинной арифметикиЋ), то для конечно-автоматной модели аналогичной операцией является декомпозиция кодера на простые компоненты. Показано, что сложность декомпозиции конечного автомата возрастает экспоненциально, в то время, как его быстродействие не зависит от размера его таблицы переходов. По аналогии с понятиями сложного и простого числа в теории чисел, введены понятия композиции конечных автоматов и примитивов. Особенность этих понятий заключается в том, что, сложное число в теории чисел представляет собой произведение простых чисел и это произведение не зависит от порядка расположения в нем сомножителей. Для конечного же автомата, эквивалентного композиции примитивов, имеют значение, как их набор, так и порядок их взаимного расположения в композиции, то есть, композиция автоматов не обладает свойством коммутативности.
  
  Предисловие
  
  Если Вы хотите сохранить секрет, не доверяйте его никому.
  
  Сенека (5 до н.э. - 65 н.э.),
  
  
  
  Как следует из эпиграфа, проблема сохранения секретов волновала людей со времени появления секретов. Сенека до сих пор прав, и истина, 'знают двое - знает свинья', как говаривал папаша Мюллер, всегда будет актуальна. Иллюстрацией этого в криптографии может служить наличие двух типов алгоритмов: симметричного и асимметричного.
  
  Первый, как это существует до сих пор, обладает высоким быстродействием, но предполагает наличие секретного ключа, который должен быть известен минимум двум участникам процесса обмена информацией ('знает свинья').
  
  Второй тип алгоритма, асимметричный, до настоящего времени имеет малое быстродействие, сложную реализацию, но он имеет два ключа:
  
  " один, который известен всем участникам обмена информацией, и
  
  " второй - известный только одному участнику обмена информацией - тому, кому эта информация предназначается (см. рекомендацию Сенеки).
  
  Это обстоятельство настолько существенно, что, несмотря на ряд преимуществ симметричных алгоритмов, они используются в криптографических протоколах только совместно с асимметричными алгоритмами.
  
  Следует добавить, что, как мы покажем далее, асимметричные алгоритмы - это самое удивительное и, парадоксальное явление, и не только в криптографии.
  
  Действительно, в обыденной жизни всем понятно, что если все знают, как спрятан предмет, то нет большого секрета в том, как его найти. И вдруг в криптографии появляется способ, при котором все могут знать, как спрятан предмет. Более того, любой может спрятать предмет. Но найти его может только тот, кто придумал, как его спрятать, а не тот, кто его спрятал. Конечно, это не очень строгая аналогия с асимметричным криптографическим алгоритмом, но вызывает те же ощущения.
  
  Действительно, что может быть привлекательнее для защиты информации, передаваемой по незащищенному каналу, чем способ кодирования, при котором все знают ключ шифрования и могут им воспользоваться для кодирования информации, в том числе и недобросовестные участники информационного обмена. Но раскодировать ее может только единственный участник, который разработал алгоритм кодирования.
  
  Как всегда, воплощение мечты решает меньше проблем, чем создает новых.
  
  Тем не менее, в нашей работе мы сосредоточим внимание только на решении проблемы низкой производительности существующих асимметричных алгоритмов, которая не позволяет достаточно эффективно применить их в криптографии. Другими словами, предлагаемая работа будет посвящена решению проблемы создания асимметричного быстродействующего алгоритма.
  
  Какие соображения используются при этом?
  
  Причина низкой производительности существующих асимметричных алгоритмов заключается в том, что применяемые на практике алгоритмы используют, так называемую, 'длинную' арифметику, то есть арифметику, предназначенную для работы с числами размером от сотни и более цифр. Вследствие этого быстродействие асимметричных алгоритмов на несколько порядков меньше симметричных алгоритмов.
  
  Надежды на то, что с ростом быстродействия технических средств разрыв между быстродействием асимметричных и симметричных алгоритмов будет сокращаться, безосновательны. Это происходит потому, что с ростом быстродействия технических средств, при сохранении размера чисел, снижается степень защищенности алгоритма, а это, в свою очередь, приводит к необходимости увеличить размерность 'арифметики' ([1]).
  
  Возникло целое направление в криптографии, так называемые теоретико-числовые алгоритмы (например, RSA), которое за последние двадцать лет привело к появлению большого числа оригинальных асимметричных алгоритмов и это создало иллюзию, что термины 'асимметричный алгоритм' и 'длинная арифметика' - синонимы.
  
  Так ли это?
  
  Для того, чтобы опровергнуть это утверждение, далее будет рассмотрен асимметричный алгоритм кодирования на базе конечно-автоматной модели.
  
  " Будет показано, что, если трудность взлома RSA определяется сложностью выполнения операции разложения числа на простые сомножители (это и приводит к необходимости использования 'длинной арифметики'), то для конечно-автоматной модели аналогичной операцией является декомпозиция кодера на простые компоненты.
  
  " Будет показано, что сложность декомпозиции конечного автомата возрастает экспоненциально, в то время, как его быстродействие не зависит от размера его таблицы переходов[2].
  
  По аналогии с понятиями сложного и простого числа в теории чисел, далее будут введены понятия композиции конечных автоматов и примитивов.
  
  Особенность этих понятий заключается в том, что, сложное число в теории чисел представляет собой произведение простых чисел и это произведение не зависит от порядка расположения в нем сомножителей. Для конечного же автомата, эквивалентного композиции примитивов, имеют значение, как их набор, так и порядок их взаимного расположения в композиции, то есть, композиция автоматов не обладает свойством коммутативности.
  
  
  
  Структура предлагаемой работы определялась тем обстоятельством, что до настоящего времени Теория Конечных Автоматов и Криптология развиваются параллельно и независимо. Каждая из них имеет специфический язык, объекты изучения, область применения и своих специалистов.
  
  Это создает трудности при изложении материала:
  
  " С одной стороны, для понимания сути проблемы, изложение должно предполагать знакомство читателя с Теорией Конечных Автоматов, хотя бы в объеме работы Zvi Kohavi 'Switching and Finite Automata Theory'.
  
  " С другой стороны, изложение должно предполагать знакомство читателя с Криптологией, хотя бы в объеме работы Bruce Schneier 'Applied Cryptography'.
  
  Понимая, что одновременное совмещение задачи просвещения и обсуждения предлагаемого способа решения проблемы создания асимметричного криптографического алгоритма, может привести к ситуации, когда ни та, ни другая задача не будет достаточно эффективно решена, автор выбрал компромиссный вариант.
  
  В основу его положены соображения, что, принятый способ изложения может быть рассчитан хотя бы на одну из трех категорий читателей:
  
  1. Читатель, который слабо знаком с Криптографией и Теорией Конечных Автоматов, но обладает достаточной математической культурой. Его интересует логика изложения и корректность проводимых расчетов, которые используются для оценки параметров предлагаемого асимметричного алгоритма. Такой читатель может ограничиться Частью 1 (см. стр 17) и составить собственное мнение, насколько можно доверять выводам, сделанным в работе.
  
  2. Читатель, который знаком с проблематикой предлагаемой работы. Такому читателю можно предложить предварительно познакомиться с работой Лунина А.В., Сальникова А.А 'Перспективы развития и использования асимметричных алгоритмов в криптографии' (см. стр. 81) и четырнадцатой главой работы Цви Кохави 'Память, определенность и конечные автоматы, сохраняющие информацию' (см. стр. 97). Эти работы позволяют оценить существующее положение асимметричных алгоритмов в криптографии, и, после перехода к Части 1, оценить правильность выводов, сделанных в ней.
  
  3. И, наконец, наиболее приятная автору третья категория читателей - это те, которые не обладают необходимой математической культурой и при этом не знакомы с проблематикой Криптографии и Теории Конечных Автоматов. Но ими движет здоровая природная любознательность. Таким читателям автор рекомендует поверить на слово, что все, о чем далее пойдет речь - очень интересно. Если автор уже убедил Вас в этом, то ему остается порекомендовать, не теряя времени, как можно скорее перейти в одну из первых двух категорий читателей.
  
  
  
  
  
  
  
  
  
  Мы ставим здесь перед собой задачу
  
  исследования множества объектов
  
  нашей любознательности, причем мы
  
  будем исследовать их с тем недоверием,
  
   с каким надо относиться к
  
  любой системе до тех пор, пока она
  
   не продемонстрирована нашим глазам
  
   или не доказана нашему разуму.
  
  Вольтер, "О феноменах природы"
  
  
  
  
  Введение
  
  Предлагаемая работа предполагает знания, хотя бы в объеме следующих работ:
  
   * Лунин А.В. и Сальников А.А. 'Перспективы развития и использования асимметричных алгоритмов в криптографии'[3]. В ней перечислены преимущества асимметричных алгоритмов перед симметричными алгоритмами. Там же показано, что главный недостаток существующих асимметричных алгоритмов - малая скорость кодирования, связанная с выполнением трудоемких математических преобразований. Это привело к тому, что существующие асимметричные алгоритмы применяются только для выполнения вспомогательных (относительно процесса обеспечения секретности) функций, таких, как кодирование ключей применяемых симметрических алгоритмов и тому подобное.
   * Zvi Kohavi 'Switching and finite automata theory'. Книга была издана в 1978 году. Zvi Kohavi, ссылаясь на работы других авторов сделал достаточно полное описание КАМСИ (Конечно-Автоматная Модель, Сохраняющая Информацию). (гл. 14).
  
  В нашей работе мы построим криптографический алгоритм на базе КАМСИ.
  
  Наиболее ранняя работа о КАМСИ была опубликована во второй половине пятидесятых годов двадцатого столетия. Более того, сегодня можно утверждать, что это были первые предложения асимметричного алгоритма ([4]).
  
  Способ применения КАМСИ для кодирования был описан Huffman D.A. за двадцать лет (см. Список литературы, стр. 132) до того, как Уитвелд Диффи и Мартин Хеллман сформулировали общую концепцию асимметричных алгоритмов.
  
  Почему же описанная Huffman D.A. КАМСИ до сих пор не нашла применения в криптографии?
  
  Для того, чтобы ответить на этот вопрос, следует обратиться к работам Уитвелда Диффи и Мартина Хеллмана.
  
  Главная заслуга Уитвелда Диффи и Мартина Хеллмана заключалась
  
   в том, что они ввели понятие однонаправленной функции.
  
  Упрощенно, идею однонаправленной функции можно представить на примере трафика движения по городским улицам с односторонним движением.
  
  Допустим, водитель прибыл в пункт Б из пункта А (решил прямую задачу). Спрашивается
  
   * Каким путем он должен воспользоваться, чтобы вернуться в пункт А (обратная задача)?
   * Можно ли, двигаясь из А в Б, одновременно получить информацию о пути движения из Б в А? (чтобы упростить решение обратной задачи)
  
  Не трудно видеть, что в рассмотренной ситуации, для любого водителя, участвующего в этом процессе, есть единственный способ поиска решения обратной задачи (то есть, возвращение из пункта Б в пункт А) - это полный перебор возможных вариантов.
  
  Характерная особенность рассмотренного процесса заключается в том, что сложность решения прямой задачи (движение из А в Б) намного проще решения обратной задачи, которая может даже не иметь решения. Именно по этой причине, функция, описывающая рассмотренную выше ситуацию, называется однонаправленной.
  
  Положение может измениться, если кто-либо из участников процесса движения секретно обзаведется, например, вертолетом (или воздушным шаром, или чем-либо, позволяющим ему изменить механизм движения). Понятно, что для него решение прямой задачи (движение из А в Б), и обратной (движение из Б в А), обладают одинаковой сложностью. Такую задачу называют однонаправленной задачей с секретом. В рассмотренном случае 'секретом' является наличие вертолета у одного из участников ([5]).
  
  Таким образом, для обладателей секрета, решение обратной задачи имеет сложность, такую же, как и для прямой задачи, в то время как для всех остальных участников движения, обратная задача может даже не иметь решения.
  
  Уитвелд Диффи и Мартин Хеллман показали, что
  
   * Асимметричный криптографический алгоритм может быть построен только на базе однонаправленной функции; Например, асимметричный алгоритм RSA основан на том, что сложность вычисления произведения двух простых чисел неизмеримо проще разложения этого произведения на простые сомножители. До настоящего времени все усовершенствования мало упростили операцию разложения на простые сомножители. То есть, при достаточно большом размере сомножителей (500 и более бит), обратная задача практически не разрешима.
   * Однонаправленная функция, на базе которой создан асимметричный криптографический алгоритм, должна обладать 'секретом'. Именно это обстоятельство позволяет обладателю 'секрета', в отличие от остальных, выполнить обратную операцию (декодирование) за приемлемое время и с достаточными для этого вычислительными ресурсами.
  
  Например, в RSA прямая задача (кодирование), выполняется с применением упомянутого выше произведения двух простых чисел. Произведение этих простых чисел известно всем, желающим закодировать информацию, и называется открытым ключем.
  
  Однако, легко раскодировать информацию может только обладатель секрета - знания сомножителей - двух простых чисел, которые образуют произведение (открытый ключ) и называются секретным ключем.
  
  Особенность такого процесса заключается в том, что открытый ключ не может использоваться для декодирования и по этому его допустимо передавать по незащищенным каналам, с тем, чтобы им мог воспользоваться любой, желающий передать конфиденциальную информацию, в то время, как секретный ключ хранится только у 'хозяина' сгенерированных ключей.
  
  Вернемся к КАМСИ (Конечно-Автоматной Модели, Сохраняющей Информацию).
  
  Как это будет показано ниже, применение КАМСИ в криптографии предполагает существование пары конечных автоматов, один из которых выполняет функцию кодера, и другой, инверсный кодеру, функцию декодера.
  
  В работах, список которых приведен на стр. 132, показан способ построения инверсных КАМСИ (необходимых для декодирования).
  
  Ниже будет показано, что уже при числе состояний таблицы переходов кодера, равном 1250, сложность построения инвертора (декодера) требует около 260 ≈ 1018 операций (В Table 9 (см. стр. 54) приведены значения 'Больших чисел'). Такое количество операций показывает, что практически невозможно построить инвертор. Описанная в цитированных работах КАМСИ представляет собой однонаправленную функцию, у которой сложность построения таблицы переходов кодера линейно зависит от числа состояний, а сложность построения инвертора - приближается к экспоненциальной зависимости. Сложность построения инвертора одинакова для всех участников процесса обмена информацией, то есть, в таком виде КАМСИ представляет собой однонаправленную функцию без секрета.
  
  Это объясняет, почему КАМСИ до сих пор не были использованы в криптографии. Факт тем более огорчительный, что по всем остальным параметрам КАМСИ превосходят существующие асимметричные алгоритмы.
  
  КАМСИ обладают:
  
   * Высоким быстродействием. Оно определяется временем перехода конечного автомата из одного состояния в другое и не зависит от числа состояний таблицы переходов.
   * Легкой перестройкой оконечного устройства для реализации очередного криптографического алгоритма.
   * Простотой реализации в виде аппаратного устройства, например на базе FPGA (настраиваемые матрицы). Кроме того,
  
  " реализация алгоритмов на базе КАМСИ использует только логические (самые быстрые) операции.
  
  Почему же, несмотря на то, что КАМСИ были достаточно полно исследованы более сорока лет назад, они не нашли до сих пор применения в криптографии, несмотря на то, что существующие, так называемые, паблик-кей технологии по производительности и сложности реализации оставляют желать лучшего?
  
  Этому может быть несколько объяснений:
  
   * Описанный в литературе способ применения КАМСИ представляет собой однонаправленную функцию без секрета.
  
  Действительно, асимметрия здесь заключается в том, что алгоритмы кодирования отличаются от алгоритмов декодирования. Однако, сложность построения инвертора экспоненциально зависит от ч (одного из параметров КАМСИ, о котором будет сказано ниже). Эта сложность в этом случае одинакова для всех участников процесса обмена информацией.
  
   * Можно высказать различные предположения о том, почему эта проблема не была разрешена до сих пор. Но, учитывая высокий уровень ученых - специалистов в области Теории Конечных Автоматов, которые разрабатывали теорию КАМСИ (см. список литературы на стр. 132), можно выделить одно - Теория Конечных Автоматов изначально создавалась только для анализа и технической реализации алгоритмов управления технологическими процессами, которые разрабатывались в других областях науки. То есть, Теория Конечных Автоматов изначально создавалась для анализа алгоритмов управления технологическими процессами, разрабатываемыми вне нее. В криптографии же возникает проблема генерации криптографических алгоритмов, которые должны обладать определенными свойствами.
  
  Каковы же перспективы применения КАМСИ в криптографии?
  
  В каком направлении следует исследовать проблему создания однонаправленной функции с секретом на базе КАМСИ?
  
  Очень заманчиво, но бесполезно для применения в криптографии, попытаться усовершенствовать алгоритм инвертирования КАМСИ.
  
  Как любое усовершенствование, оно представляет технический интерес. Однако, любое усовершенствование 'облегчит жизнь' всем участникам процесса обмена информацией, в том числе, и недобросовестным. Так, рассмотренные Цви Кохави в разделе 'Последовательные линейные машины' называются линейными потому, что сложность их преобразования линейно зависит от размера Машины. Однако, это 'облегчает жизнь' всем участникам процесса обмена информацией. То есть, оно не может привести к созданию 'секрета' однонаправленной функции. Кроме того, трудно рассчитывать, что любые усовершенствования удастся длительно держать в секрете, тем более, что понятие 'недобросовестный пользователь' среди участников информационного процесса может изменяться в зависимости от характера защищаемой информации.
  
  Все это показывает, что сама по себе, разработка теории КАМСИ не может привести к созданию однонаправленной функции с секретом.
  
  Есть и еще одно обстоятельство, которое создавало проблему применения КАМСИ в криптографии. Это - необходимость автоматизации процесса генерации кодера. Проблема генерации существует в любом криптографическом протоколе, но не существует в Теории Конечных Автоматов, так как к ней обращаются с готовым алгоритмом, который следует проанализировать.
  
  Для симметричного алгоритма процесс решен достаточно успешно, но при этом возникает проблема 'защищенной' доставки нового сгенерированного ключа по назначению.
  
  В асимметричном алгоритме проблема 'защищенной' доставки отсутствует, так как открытый ключ не от кого охранять, а секретный - некому посылать. При этом следует учитывать, что 'секретность' держится на 'трудности' получения секретного ключа из открытого.
  
  Например, в RSA, для 'взломщиков' существует проблема разложения сложного числа (открытый ключ) большой размерности (сто цифр и больше) на простые сомножители (секретный ключ). Это действительно так, если не существует рациональный способ автоматической генерации простых чисел большого размера. Трудность связана с тем, что сам процесс генерации, с одной стороны, должен исключать повторяемость, то есть, должен быть случайным, (для того, чтобы его не мог повторить другой участник процесса обмена информацией), а, с другой стороны, должна быть гарантия генерации именно простого числа большого размера. К сожалению (для науки) и к счастью (для создателей алгоритма), до сих пор процесс тестирования большого числа на 'простоту' требует огромных затрат времени и технических ресурсов.
  
  Это является одной из причин, по которой существующие асимметричные алгоритмы сложны для внедрения.
  
  Коротко сложившуюся ситуацию можно назвать проблемой отсутствия правила.([6])
  
  Для RSA - это отсутствие правила проверки 'на простоту'. На практике это приводит к тому, что часто используют псевдопростые числа.
  
  Для КАМСИ в опубликованных исследованиях так же отсутствует простое правило проверки на 'КАМСИ-шность'. Это еще одна причина, по которой КАМСИ до сих пор не получила применения в криптографии.
  
  В предлагаемой работе проблема 'правила' для КАМСИ решена неожиданным образом: предложена ситуация, в которой нет необходимости в 'правиле'. Это возможно при условии, если к КАМСИ применяются преобразования, сохраняющие свойство КАМСИ (для простых чисел известно, что любые преобразования простых чисел дают сложные числа, но не наоборот). Такие преобразования КАМСИ разработаны в прелагаемой работе.
  
  Для этого введены понятия КАМСИ-примитива и КАМСИ-композиции, которые можно считать аналогами простого и сложного числа в теории чисел.
  
  По аналогии с RSA, в предлагаемом алгоритме, 'секретом' является декомпозиция КАМСИ-композиции на примитивы. Особенность 'секрета' однонаправленной функции на базе КАМСИ, в отличие от RSA, является то, что, если для сложного числа существует, в виде секретного ключа, набор простых чисел - сомножителей, для которых безразличен порядок их использования для получения произведения (транзитивность), то для каждой КАМСИ-композиции существует, кроме набора примитивов, порядок расположения их в композиции (не транзитивность).
  
  
  Нужны ли сегодня новые асимметричные алгоритмы?
  
  Мы рассмотрели особенности асимметричных алгоритмов.
  
  Коротко рассмотрели отличие применения асимметричных алгоритмов от симметричных.
  
  Попытались понять причины, по которым КАМСИ в течение последних сорока лет не были применены в криптографии, несмотря на то, что существующие и применяемые асимметричные алгоритмы основаны на применении 'длинной' арифметики, что делает невозможным использовать их самостоятельно из-за малой скорости обработки информации.
  
  Тем не менее, криптография существует, развивается и нет ощущения, что малая скорость RSA и ему подобных не позволяет решить какие-либо проблемы защиты информации.
  
  Более того, внимательный взгляд на пятитысячную историю криптографии показывает, что большую часть времени существования криптографии она благополучно обходилась только симметричными алгоритмами.
  
  Нуждался ли Гай Юлий Цезарь в асимметричных алгоритмах кодирования?
  
  А сотрудники многочисленных разведок (разведчики и шпионы)?
  
  Всевозможные дипломатические представительства?
  
  Можно ответить однозначно: нет.
  
  Более того, каждый, кто предложил бы Цезарю систему обмена информацией по схеме 'все - одному' (все кодируют, но только Цезарь декодирует), рисковали бы своей жизнью.
  
  Задумывались ли Вы, почему папаша Мюллер так возбудился, обнаружив 'пальчики' Штирлица на чемодане радистки Кэт? Почему в этом случае его больше интересовал информационный канал, а не передаваемые по нему сообщения - к тому моменту у него скопилось много перехваченных шифровок.
  
  Во всех упомянутых случаях секретной была не только закодированная информация, но и информационный процесс, который включал в себя информационный канал и причастных к этому процессу людей. Более того, обеспечение секретности информационного процесса зачастую ставилось на первое место. Иногда это приводило к абсурду ([7]). Известно, что в СССР работы, связанные с криптографией и люди, которые ею занимались, были засекречены. Нуждались ли подобные системы в криптографии с открытым ключем? Конечно, нет.
  
  Существовали ли в подобной криптографии такие проблемы, как контроль целостности документа, контроль подписи (истинности) и тому подобное? Защиты базы данных? Существовали, но решения были больше административные, чем криптографические.
  
  Параллельно с рассмотренной выше криптографией, которую можно назвать государственной, на первых порах не так интенсивно, но настойчиво развивалась другая криптография, которую можно назвать коммерческой ([8]). В ней, на первом этапе, решались сходные задачи, но условия их решения были другими.
  
  Главное отличие государственной криптографии от коммерческой заключается в качестве информационного канала. В первом случае информационный канал охраняется всей мощью государственного аппарата и поэтому кодирование информации, в первую очередь, предназначено для защиты шифруемой информации от представителей этого самого 'аппарата'. Во втором случае участники информационного процесса - кроме тех, для кого информация предназначается, это: а) люди, заинтересованные в не легитимном получении информации, б) люди, заинтересованные изменить или заменить передаваемую информацию и в) случайные люди.
  
  В этих условиях необходимость обмена ключами при симметричных алгоритмах создает трудности, которые иногда не преодолимы.
  
  При применении асимметричных алгоритмов проблемы обмена ключами просто не существует: один из двух ключей может быть открыт для любого, желающего закодировать информацию. В то же время второй ключ, в качестве секретного, хранится у получателя информации, и при этом нет необходимости передавать этот ключ по информационному каналу.
  
  Иные условия работы коммерческих криптографических систем породили такие задачи, как
  
  " Защита базы данных;
  
  " Контроль целостности документа;
  
  " Электронная подпись;
  
  " Электронные деньги и тому подобное.
  
  Некоторые из этих задач могут быть решены только применением либо только асимметричных криптографических алгоритмов, либо комбинацией асимметричных и симметричных алгоритмов. Более того, появление асимметричных алгоритмов позволило решать такие задачи, которые с трудом можно отнести к области защиты информации.
  
  Это упомянутые выше 'электронная подпись', 'электронные деньги' и тому подобное.
  
  Решение этих задач стало возможным только благодаря применению асимметричных криптографических алгоритмов, с одной стороны, а с другой стороны, сделало возможным решение многих задач взаимодействия абонентов без необходимости непосредственного контакта в сети. Другими словами, появление асимметричных алгоритмов позволило создать принципиально новый способ взаимодействия людей, при котором их географическое расположение не имеет значение.
  
  Иногда быстрое внедрение в практику прогрессивных разработок приводит к трагикомическим, а для некоторых - катастрофическим, ситуациям.
  
  В первой половине девяностых годов фирма DigiCash разработала технологию Электронных денег в Сети, а крупнейший банк Mark Twain Bank и 1995 году взялся опробовать разработанную систему.
  
  Результаты оказались настолько впечатляющими, что в течение следующих трех лет последовало еще восемь сделок о лицензировании технологии с крупнейшими европейскими банками, австралийским банком, влиятельным финским провайдером Internet, японской корпорацией и, наконец, - верх признания - c консервативным швейцарским банком Crйdit Suisse.
  
  И вдруг ..., сегодня фирма DigiCash объявила о своем банкротстве.
  
  Причиной краха оказалось главное преимущество разработанных DigiCash платежных средств - анонимность, то есть, качество, которое делало разработанные фирмой электронные платежные средства похожими на наличные деньги.
  
  Именно это качество первыми по достоинству оценили фирмы - производители порнографии. Анонимность при расчетах позволила резко увеличить доходы этих фирм. Это вызвало энергичные протесты протестантских организаций США. Они призвали бойкотировать по всему миру банки, которые поддерживают разработки DigiCash и ... вот Вам результат.
  
  Приведенный курьез показывает, что мало создать толковое техническое средство, следует затратить не меньше, а часто и больше интеллектуальных усилий на решение не только технических, но и социальных проблем.
  
   В связи с решением технических проблем появилось понятие протокол, которое будет достаточно подробно рассмотрено в следующем разделе.
  
  В нем будет показано, как наиболее эффективно можно использовать асимметричные алгоритмы на базе КАМСИ.
  
  
  Особенности применения криптографического алгоритма с открытым ключем
  
  Криптографическая система может быть сильна лишь настолько, насколько таковыми являются алгоритмы шифрования, алгоритмы цифровой подписи, односторонние хэш-функции и коды идентификации сообщений, на которые она опирается. Взломайте что-нибудь одно, и вы взломаете систему. И как можно построить слабую структуру из крепких материалов, так и возможно построить слабую криптографическую систему из надежных алгоритмов и протоколов.
  
  Брюс Шнайер 'Подводные камни безопасности в криптографии'[9]
  
  
  
  Приведенные в эпиграфе слова Брюса Шнайера - это мнение человека, который стоял у истоков современной криптографии и продолжает сейчас активно развивать ее. В перечне алгоритмов, определяющих качество криптографической системы, присутствует криптографический алгоритм (из перечня Б.Шнайера - алгоритм шифрования) - одна из четырех составляющих системы, и, кроме того, определяет алгоритмы функционирования остальных компонентов системы, в том числе и их качество.
  
  א. Например, в качестве алгоритма шифрования в существующих криптографических системах применяются симметричные алгоритмы. Эти алгоритмы просты в реализации, обладают высоким быстродействием и устойчивы к взлому.
  
  Пока информационные системы предназначались для обслуживания относительно небольшого числа абонентов, свойства симметричных алгоритмов обеспечивали все требования, предъявляемые к криптографическим системам. С увеличением сложности информационных систем стали проявляться проблемы, связанные с применением симметричных алгоритмов:
  
   a. Применение симметричного алгоритма в информационной системе, основано на существовании 'секрета для двоих'[10] - ключа для кодирования и декодирования конфиденциальной информации, которой могут обмениваться эти абоненты.
  
  o Для информационной системы, обслуживающей n абонентов общее число ключей N (всевозможных пар из n) можно вычислить по формуле. N= n( n-1)/2.
  
  o Это значит, что для информационной системы, обслуживающей n=100 абонентов, следует сгенерировать и обеспечить секретность при обмене ключами не менее N =4900 ключей.
  
  o Информационная система, обслуживающая сто абонентов - это маленькая система, но уже при n=200 число ключей (число сочетаний из 200 по 2) равно N=19800. При n=1000 абонентов (количество абонентов локальной информационной системы) число ключей равно N=499000. Понятно, что такое число ключей требует создания отдельной службы обслуживания в системе, которая обеспечивает генерацию, мониторинг и секретность распределения ключей.
  
   b. Криптографический алгоритм в системе применяется не только для шифрования текста, но и для обеспечения его авторизации, идентификации и контроля целостности. Это приводит к тому, что при использовании симметричного алгоритма, вместе с текстом абонент должен хранить ключ кодирования - декодирования.
  
   c. Учитывая, что каждый ключ известен, минимум, двум абонентам, возникает необходимость периодически менять ключи. Это приводит к тому, что каждый абонент вынужден, наряду с действующими N ключами, сохранять другие ключи, которые использовались ранее для текстов из его архива (это необходимо в случае, когда сохраняются документы, для которых важна не только информация, но и признаки ее достоверности и сохранности).
  
  Ситуация становится еще более сложной при необходимости обеспечить защиту информации в банковских системах (платежные системы, электронные деньги и тому подобное).
  
  ב. Как альтернативу применения симметричных алгоритмов, рассмотрим преимущества криптографических алгоритмов c открытым ключем:
  
   a. Каждый абонент открытой криптографической системы, имеет два ключа - открытый, известный всем, и секретный, известный только одному абоненту - 'хозяину' ключа. При этом в криптографической системе:
  
  o открытый ключ может передаваться по незащищенным информационным каналам.
  
  o секретный ключ известен только одному абоненту и для нормальной работы системы никогда не возникает необходимость передавать этот ключ кому бы то ни было.
  
   b. Криптографическая система с открытым ключем, обслуживающая n абонентов имеет n открытых и n секретных ключей, то есть, N=2n.
  
   c. Система требует генерации количества ключей в (n-1)/4 раз меньше, чем для симметричной системы[11].
  
  И всё-таки, есть причина, по которой существующие криптографические алгоритмы с открытым ключем не получили достойного применения - это их малое быстродействие. Поэтому они выполняют в системах вспомогательные функции. Объясняется это тем, что все существующие алгоритмы с открытым ключем используют особые свойства простых чисел. Эти свойства становятся определяющими для чисел, которые можно записать с применением 100 и более цифр, потому, что их преобразования требуют, так называемой, 'длинной' арифметики. Быстродействие таких систем в тысячу раз меньше существующих симметричных алгоритмов.
  
  Характерная особенность арифметических операций над числами заключается в том, что они коммутативны. Поэтому и существующие открытые алгоритмы коммутативны. Этот факт можно показать с помощью выражения, из которого видно, что перестановка операторов кодирования EA () и декодирования DA () не изменяет результата декодирования:
  
  Форм. 1
  
   DB (EB (DA (EA (P))) ≡ DB (DA (EB (EA (P))))→P
  
  где:
  
  " EA (),DA () - операторы кодирования и декодирования абонента А. Соответственно, открытый и секретный ключи абонента А будем обозначать EA., DA
  
  " P- исходный текст.
  
  " EA (P) - процесс кодирования текста P открытым ключем абонента А. Как правило, это происходит при необходимости защитить содержание текста P, предназначенного для абонента А. Иногда, закодированный текст мы так же будем обозначать EA(P)→J
  
  " DA (EA (P)) →P - процесс декодирования с помощью секретного ключа DA абонента А. Особенность этой записи заключается в том, что процесс, записанный таким способом, исполняется, справа налево, то есть: EA (P) → DA (EA (P)) →P. В нашем случае, сначала выполняется операция EA (P) - кодирование открытым ключем, и после этого - декодирование. В такой записи отсутствуют указания на время и место выполнения операций. Единственная информация, которую можно получить из подобной записи - это порядок (очередность) их исполнения.
  
  " Левая часть приведенного выше выражения Форм. 1 DB(EB(DA(EA(P))))→P описывает следующую последовательность операций:
  
  o Один из абонентов сети (но не абонент А) кодирует текст P (EA(P)→J) и передает его через незащищенный канал абоненту А.
  
  o Абонент А выполняет операцию DA(EA(P)) →P и получает предназначенный ему текст P..
  
  o Абонент А кодирует текст P : EB(DA(EA(P))) и передает его по незащищенному каналу абоненту В.
  
  o Абонент В декодирует принятое сообщение: DB(EB(DA(EA(P))))→P ..
  
  " Правая часть Форм. 1 DB (DA (EB (EA (P))))→P отличается от левой части положением операторов EB () и DA (), то есть порядком исполнения этих операторов. Знак тождества '≡' между левыми и правыми частями показывает, что перестановка операторов EB () и DA () не изменяет результата.
  
  Определение. Алгоритм, который допускает перестановку операций в выражении вида Форм. 1 называется коммутативным.
  
  Примером такого алгоритма являются такие арифметические операции, как умножение и сложение.
  
  Известно, что любые комбинации этих операций также коммутативны, в том числе и существующие асимметричные криптографические алгоритмы.
  
  Следствие. Так как перестановка операций в выражении Форм. 1 не меняет тождества, то выражение Форм. 1 имеет 24 эквивалентные формы (n!), так как любая из этих форм имеет один и тот же результат кодирования.
  
  Отсюда следует, что коммутативность криптографического алгоритма уменьшает число различных способов кодирования, то есть снижает надежность алгоритма.
  
  Пример. Допустим, существует текст J, полученный после последовательности операций ...(... DA (...DB(...EB(P))...)...)→J.
  
  Тогда, если криптографический алгоритм коммутативен, то выполняется тождество:
  
  EA (EB (...(...DA (...DB (...EH (P))...)...)...)))≡
  
  ≡ EB (EA (...(...DA (...DB (...EH (I))...)...)...)))≡
  
  ≡...(...(EH (I)...)...)
  
  которое показывает, что результаты применения операций EA ()и EB () одинаковы, независимо от порядка их применения.
  
  Если алгоритм не коммутативен, то для последовательности ... (...(...DA (...DB (...EH (P))...)...)→J существует единственный порядок декодирования, обратный порядку кодирования и начинается он с DH (EH (P)). Как это будет показано ниже, некоммутативность криптографического алгоритма позволяет упростить некоторые функции системы и увеличить ее надежность.
  
  Прежде, чем рассматривать различные аспекты применения асимметричных алгоритмов, рассмотрим понятие протокола.
  
  Что же такое протокол?
  
  В работе Леонида Левкович-Маслюка([12]) приводится, на мой взгляд, самое корректное определение криптографического протокола:
  
  '...что такое протокол, сказать точно нельзя. Это такая вещь, которую можно на примерах пояснить, но не определить формально. Понятие протокола появилось в программировании. Грубо говоря, это распределенный алгоритм (то есть алгоритм, выполняемый несколькими участниками) плюс соглашения о формате пересылаемых сообщений, о действиях в случае сбоев и т. д. Есть три задачи криптографии - обеспечить конфиденциальность, целостность и неотслеживаемость. Считается, что если протокол обеспечивает хотя бы одно из этих свойств, то это криптографический протокол'.
  
  Так как подавляющее число работ, вышедших после цитированной выше работы Брюса Шнайера - чаще всего, недобросовестное заимствование его текстов, то мне остается отослать любознательного читателя к его работе, которую можно найти в Интернете. Она представлена в двух вариантах: на языке оригинала ([13]) и неплохим переводом на русский язык ([14]).
  
  Мы же добавим некоторые соображения:
  
  По настоящему массовое применение криптографии стало возможным только после появления асимметричных алгоритмов.
  
  Действительно, проблемы авторизации, имитации, сохранения целостности и тому подобное, при 'штучном' применении криптографии (правительственные информационные каналы и тому подобное) решаются административными методами (службы обеспечения секретности, дипкурьеры и тому подобное).
  
  Б`ольшая часть функций существующих криптографических протоколов выполняются при совместном применении асимметричных и симметричных алгоритмов.
  
  Это объясняется тем, что существующие асимметричные алгоритмы в десятки тысяч раз медленнее симметричных, поэтому они применяются для выполнении вспомогательных функций. Однако, применение симметричных алгоритмов снижает надежность протокола, так как при этом ключ знают, минимум, два участника информационного процесса.
  
  Тем временем, появились такие криптографические протоколы, как Электронные деньги, которые, с одной стороны, не могут быть реализованы без применения асимметричных алгоритмов, а с другой стороны, при существующих асимметричных алгоритмах с их малым быстродействием и громоздкой реализацией, имеют большие трудности при внедрении, так как требуют достаточно сложную и дорогостоящую аппаратуру.
  
  Рассмотрим примеры применения КАМСИ в некоторых протоколах ([15]).
  Примеры выполнения некоторых протоколов
  
  В литературе существует описание большого числа протоколов. Они отличаются друг от друга набором функций, для реализации которых предназначена система криптографических алгоритмов, которые применяются в системе.
  
  Приведенные примеры предназначены для обсуждения преимущества применения асимметричного криптографического алгоритма, который не коммутативен и обладает быстродействием, соизмеримым с симметричным алгоритмом.
  Защита Базы Данных (БД).
  
  Примем, что в памяти компьютера В расположена База Данных (БД), которая обслуживает абонентов А,С,... .
  
  
  
  Рис. 1
  
  
  
  В рассматриваемом случае
  
  " Абоненты А,С,... могут находиться на любом удалении от компьютера В и взаимодействовать с ним через незащищенный канал связи,
  
  " В отличие от архива, База Данных может участвовать в информационном процессе абонентов в реальном масштабе времени. Для обеспечения правильного функционирования необходимо, чтобы
  
  o информационные каналы и БД были защищены криптографическим алгоритмом, и
  
  o криптографический алгоритм обладал быстродействием, достаточным для обеспечения информационного процесса.
  
  В настоящее время эти условия могут быть удовлетворены только при использовании симметричного криптографического алгоритма - ни один из существующих асимметричных алгоритмов не обладает достаточным быстродействием.
  
  При применении симметричного алгоритма
  
  " информация БД закодирована с применением ключа Администратора Системы,
  
  " каждый абонент имеет свой ключ,
  
  " все ключи хранятся в Базе Данных.
  
  Понятно, что такую систему можно взломать просто, проникнув в компьютер БД.
  
  Защита расположенной на компьютере В базы данных, как правило, связана с решением двух проблем:
  
  " Защита паролем компьютера В от проникновения злоумышленника([16]) в компьютер.
  
  " Защита от перехвата пароля, который открывает доступ к БД.
  
  Проблема защиты заключается в том, что для сравнения предъявленного пароля с существующим, пароль должен быть расположен в памяти компьютера, и, как бы его ни маскировали, он может быть обнаружен.
  
  Создание защитных экранов (firewall), создает больше сложностей легитимным пользователям, чем хакерам.
  
  Каким будет протокол при применении асимметричного алгоритма?
  
  Допустим абоненту А необходимо получить доступ к Базе Данных (БД), расположенной на сервере В.
  
  Примем, что
  
  " Абонент А имеет:
  
   i. Имя 'А'.
  
   ii. Открытый ключ EA,
  
   iii. Секретный ключ DA.
  
  " Сервер В имеет:
  
   i. Открытый ключ EB и
  
   ii. секретный ключ DB.
  
   iii. На сервере, кроме Базы Данных, расположен список абонентов, в котором записано имя каждого абонента и его открытый ключ.
  
   iv. Все элементы БД закодированы секретным ключем DB. Это позволяет, с одной стороны, прочитать содержимое любого элемента БД с помощью известного всем EB, с другой стороны, защитить БД от несанкционированного внесения изменений.
  
  Для доступа абонента А к БД выполняется следующая последовательность действий абонента и сервера (протокол):
  
  1. допустим, абоненту А необходимо получить информацию о к-ом элементе bdk базы данных. БД. Для этого он посылает серверу по незащищенному каналу запрос - свое имя А.
  
  2. Сервер генерирует случайное число R и посылает его по незащищенному каналу абоненту А.
  
  3. Абонент А, получив R', выполняет операцию: DA ([R'+bdk]) (где [R'+bdk] - конкатенация R' и bdk) и посылает этот код серверу В.
  
  4. Сервер В выполняет операцию EA (DA ([R'+bdk]))→ R'+bdk, сравнивает R' со сгенерированным случайным числом R. Если они совпадают, то это значит, что, обратившийся действительно абонент А.
  
  5. Сервер В выполняет запрос: считывает содержимое к-го элемента базы данных, присоединяет в конец bdk число R, кодирует: EA (DB ([bdk+R])) и результат посылает абоненту А.
  
  6. Абонент А выполняет последовательность операций:
  
  Форм. 2 DA(EA(DB([bd'k+R']))) → DB([bd'k+R']) →
  
  EB(DB([bd'k+R'])) → bd'k+R'
  
  сравнивает R` с R и если они совпадают, то это значит, что bd'k соответствует bdk, то есть, абонент А получил запрошенный к-ый элемент БД.
  
  Обратите внимание на операции пунктов 3 и 5.
  
   a. В первом случае мы используем конкатенацию [R'+bdk]. Она предназначена для сервера В, которому известен размер числа R. Факт совпадения R` и R в пункте 4 указывает на то, что запрашивается именно bdk, то есть не было искажений при передаче запроса.
  
   b. Во втором случае используется конкатенация [bdk+R], которая, при совпадении R` и R позволяет в пункте 6 сделать вывод об истинности принятого от сервера bd'k.
  
  
  Виды атак и способы защиты
  
  Рассмотрим возможные атаки на криптографический протокол и способы его защиты.
  
  Примем, что в системе существует абонент С, который нелигетимно участвует в диалоге абонента А и сервера В. Абонент С не только имеет доступ к информационному каналу, но и может принять участие в выполнении операций криптографического протокола (чаще всего абонент С так же, как и абонент А, имеет доступ к серверу В, то есть является легитимным абонентом БД, но заинтересован в том, чтобы абонент А получил искаженную информацию).
  
  Рассмотрим несколько ролей, которые может играть абонент С.
  
  I. Авторизация. В этом случае абонент С от имени абонента А перехватывает значение R. Но единственное, что он может сделать в ответ на посылку сервером числа R - это сформировать DC(R) и послать его серверу вместо DA(R) ('замена автора'). Сервер, выполнив операцию EA(DC(R))≠R , убеждается, что диалог ведет не абонент А.
  
  II. Имитация.. В этом случае абонент С выполняет 'врезку' в информационный канал между сервером В и абонентом А с целью передать абоненту А измененную информацию bd'k, то есть перехватывает DB([bdk+R]). Разумеется, имея EB - открытый ключ сервера В, абонент С может получить значение bd'k и изменить его, получив bd''k. Однако он не может построить DB([bd''k+R]), так как ему не известен секретный ключ сервера DB. Следовательно, абоненту С нет смысла начинать атаку 'имитация'
  
  Следует отметить, что проблема 'врезки' получила довольно простое решение при использовании асимметричного алгоритма из-за того, что элементы БД были закодированы секретным ключем асимметричного алгоритма сервера В. Однако, использование в этом качестве существующих асимметричных алгоритмов не возможно из-за их малой скорости кодирования. Применение симметричных алгоритмов для кодирования элементов БД не эффективно, так как, абонент С может быть легитимным участником, а это значит, что ему известен ключ симметричного алгоритма БД, в то время, как DB известен только одному - серверу В.
  
  III. Подстановка. В этом случае абонент С не легитимно проникает в компьютер сервера, для того, чтобы изменить содержимое БД.. Но если память компьютера защищена асимметричным алгоритмом сервера, то абонент С может прочитать содержимое БД, но не может изменить его.
  
  Кроме всего приведенного выше следует добавить, что использование асимметричного алгоритма позволяет сделать протокол однородным, так как его быстродействие сравнимо с симметричными алгоритмами, а это единственная причина, по которой их используют в криптографических системах.
  
  
  
  
  Электронная подпись
  
  
  
  Понятие подписи появилось вместе с понятием документа. Фактически, подпись - это та часть текста, которая делает его документом. Она призвана удостоверять авторство, истинность, целостность и массу других полезных качеств документа (отсутствие любого из этих качеств делает документ никому не нужным, набором символов). Как правило, подпись располагается на том же носителе, что и основной текст документа.
  
  С появлением Интернета возникла проблема достоверной передачи документа от одного абонента к другому. Возникла проблема электронной подписи.
  
  В настоящее время существует большое число определений понятия электронной подписи. Это связано с тем, что серьезный документооборот в Интернете возможен только при условии обеспечения достоверности передаваемой информации. Ниже приводится одно из определений электронной подписи ([17]), которое позволяет оценить задачи, для решения которых предназначена электронная подпись.
  
  'Электронная цифровая подпись - реквизит электронного документа, предназначенный для защиты данного электронного документа от подделки, полученный в результате криптографического преобразования информации с использованием закрытого ключа электронной цифровой подписи и позволяющий идентифицировать владельца сертификата ключа подписи, а также установить отсутствие искажения информации в электронном документе' (текст выделен мною).
  
  Это достаточно полное определение позволяет перечислить виды атак и способы защиты электронной подписи:
  
   1. Отказ от выполненных действий. Субъект утверждает, что он не посылал некоторый документ, хотя на самом деле он его послал.
  
   2. Модификация документа. Получатель изменяет содержание полученного документа и утверждает, что именно такую версию документа он и получил.
  
   3. Подделка. Субъект фабрикует сообщение и утверждает, что оно ему прислано.
  
   4. Перехват. Злоумышленник С перехватывает и модифицирует сообщение, посланное А к В.
  
   5. Маскировка. Посылка сообщения от чужого имени.
  
   6. Повтор. Злоумышленник С посылает перехваченное им ранее сообщение от А к В повторно.
  
  Для обсуждения протокола передачи документа, защищенного электронной печатью примем, что
  
  " в информационной системе сгенерирована пара криптографических ключей (открытый и секретный) ES и DS администратора системы. ES известен всем абонентам системы, а DS - только администратору системы, который создает БД. Элементами БД являются записи DS(BDk) закодированной информации о зарегистрированных абонентах сети. (в рассматриваемом случае это может быть сертифицированная информация об абонентах сети),
  
  " абонент А (как и все абоненты сети), при регистрации в сети получает файл DS(BDA), где BDA - файл, в котором содержится сертифицированная информация об абоненте А, в том числе EA ([18]). Так как ES известно всем, то операцию ES(DS(BDA))→ BDA может выполнить любой абонент и прочитать BDA, но он, включая абонента А, не может внести в него изменения, так как он не может выполнить операцию DS(BDA).
  
  Для того, чтобы абонент А передал документ Р абоненту В ему следует выполнить две операции:
  
   1. с помощью EB и DA вычислить код:
  
  PΨA=EB(DA([P+DS(BDA)])). ,
  
  где:[P+DS(BDA) - конкатенация (последовательность) двух файлов Р и DS(BDA); и
  
   2. применяя EB абонент А кодирует свой сертификационный файл DS(BDA) ΘA =EB(DS(BDA)):.
   3. Передать ΘA и абоненту В.
   4. Абонент В, приняв ΘA и PΨA, выполняет операцию
  
  DB(ΘA)= DB(EB(DS(BDA)))= DS(BDA)→
  
  ES(DS(BDA))= BDA.
  
  Форм. 3
  
   2. Прочитав BDA, абонент В узнает, что к нему обращается абонент А, и что его открытый алгоритм кодирования EA.
   3. После этого абонент В выполняет операции:
  
  Форм. 4
  
  DB(EB(DA([P + DS(BDA)]))) = DA([P + DS(BDA)]) → EA(DA([P + DS(BDA)])) =
  
  = P , DS(BDA).
  
  Таким образом, абонент В получил текст Р и DS(BDA).
  
  Используя операцию ES(DS(BDA))= BDA, абонент В определит BDA и сравнит с полученным ранее. Если они совпадают, то абонент В считает, что документ Р изготовлен и послан абонентом А и, кроме того, в процессе кодирования, передачи и декодирования целостность его не была нарушена. В противном случае BDA полученная с помощью операций Форм. 3 и Форм. 4 не идентичны. Это происходит потому, что EA(DA([P + DS(BDA)])) == P , DS(BDA), но
  
  EA(DA([P' +DS(BDA)])) == P' , DS(BDA).
  
  Для того, чтобы абонент А не мог отрицать свое авторство документа Р, абоненту В следует сохранить файл PΨA=EB(DA([P+DS(BDA)])) и, выполнив операцию EA(DA([P' +DS(BDA)])) == P' , DS(BDA), доказать авторство А.
  
  Рассмотрим способы защиты от перечисленных выше атак применением асимметричного криптографического алгоритма.
  
  
  Отказ от выполненных действий
  
  
  
  Допустим, абонент А послал абоненту В документ Р (это могут быть некоторые обязательства абонента А перед абонентом В) и, через некоторое время заявил о том, что никакого документа он не посылал. Возникает конфликт между абонентами А и В.
  
  Это достаточно распространенная ситуация при взаимодействии людей. Если речь идет о документе на твердом носителе, она разрешается с помощью либо 'честного слова', если партнеры хорошо знают и доверяют друг другу, либо применением нотариальной записи.
  
  В рассматриваемом случае документ Р представляет собой последовательность битов, к которой невозможно прикрепить нотариальную запись и печать, но которую, при необходимости, можно воспроизвести на твердом носителе. Однако, в этом случае пропадают преимущества, которые может предоставить Интернет.
  
  При использовании описанного выше протокола абоненту В достаточно предъявить код DA([P+DS(BDA)]), который может быть получен только при знании DA, и, так как ключ EA известен всем, то достаточно применить операцию EA(DA([P+DS(BDA)])) = P,DS(BDA) , чтобы доказать авторство абонента А.
  Модификация документа
  
  В случае атаки 'модификация документа' получатель (абонент В) модифицирует полученный документ и утверждает, что именно такую версию документа он получил.
  
  Допустим, абонент А изготовил документ Р и послал его абоненту В. Абонент В выполнил операцию EA(DA([P+DS(BDA)])), получил документ Р и модифицировал его, то есть, превратил его в Р`. Однако, для того, чтобы доказать, что Р` был изготовлен абонентом А, абонент В должен предъявить DA(P',DS(BDA)]), который он не может изготовить, так как он не имеет секретный ключ DA абонента А.
  Подделка.
  
  Допустим, что по прошлым контактам абонента В с абонентом А, абонент В имеет файлы BDA и DS(BDA).
  
  Абонент В фабрикует сообщение Р и утверждает, что оно ему прислано абонентом А. Эта ситуация равносильна той, которая возникла при попытке модифицировать документ (см. 'Модификация документа', стр. 28)
  
  Кроме того, абонент В может предъявить полученный ранее и однажды уже использованный PΨA=EB(DA([P+DS(BDA)])).
  
  Для того, чтобы исключить такую возможность, посылаемый код должен содержать информацию, достаточную для исключения возможности подделки. Это может быть метка времени. В этом случае передаваемый код будет сформирован операцией
  
  Форм. 5 PΨA=EB(DA([P+DS(BDA) + PTA]))
  
  где PTA - информация о времени формирования документа Р.
  
  Другим способом, например, изготовление абонентом В шифра текста Р не возможно, так как он не имеет DA.
  
  
  Перехват.
  
  
  
  Злоумышленник С перехватывает сообщение, посланное А к В с целью модификации
  
  Допустим, злоумышленник перехватил коды, предназначенные для абонента В^
  
  ΘA=EB(DS(BDA)), PΨA=EB(DA([P+DS(BDA) + PTA])) и
  
  его задача - модифицировать текст Р ([19]). Как видно из приведенных выражений, для того, чтобы модифицировать Р, его необходимо декодировать, то есть применить известный только В алгоритм DS, который является секретным.
  Маскировка.
  
  При этой атаке злоумышленник С посылает сообщения абоненту В от имени абонента А.
  
  Как было принято выше, абонент В должен получить два кода
  
  Форм. 6 ΘA=EB(DS(BDA)) и
  
  Форм. 7 PΨA=EB(DA([P+DS(BDA) + PTA])).
  
  и из BDA (см. Форм. 6) он определит, что автором является абонент А, а из Форм. 7 - текст Р.
  
  Так как EB известен всем, в том числе и абоненту С, то операцию Форм. 6 он может выполнить, получив информацию об абоненте А. Однако, DA абоненту С не известен, поэтому он не может сформировать код операции Форм. 7.
  
  Отсюда следует, что атака 'маскировка' не выполнима при применении криптографического асимметричного алгоритма.
  
  Решения проблем, рассмотренные в этом разделе, основаны на том, что, с одной стороны, секретный алгоритм, например DS, который применяется администратором БД для кодирования элементов БД, не передается по каналам и поэтому может быть надежно защищен.
  
  С другой стороны, код DS(BDA) 'прозрачен' для всех участников информационного процесса (добросовестных и недобросовестных) потому, что всем известен алгоритм , и все-таки, модифицировать BDA, как это было показано выше, может только обладатель DS.
  
  Это обстоятельство позволяет решить некоторые проблемы, связанные с созданием электронных денег.
  Электронные деньги
  
  Деньги - они,
  
  или они есть, или их нет.
  
  Так говорят все
  
  
  
  На тему денег существует такое количество исследований, что вряд ли существует специалист, который может утверждать, что прочел их все. Этим, наверное, можно объяснить, что рост числа новых публикаций подобен взрыву ([20]). И, все-таки, в последнее время появилась проблематика, которую невозможно объяснить только графоманскими наклонностями населения - это электронные деньги.
  
  Появление Всемирной паутины - Интернета первоначально предназначалось для обмена информацией между родственными организациями. Это оказалось настолько эффективным, что круг участников расширялся, не только количественно, но и географически. Возникла проблема оплаты информации. Первоначально, пока участники информационного процесса знали друг друга, проблема заключалась только в выборе механизма платежей, который был традиционным (телефон, телеграф, почта, банковские счета и тому подобное). Далее, по мере расширения круга участников и географии их размещения, возникли проблемы кредитоспособности участников. В качестве механизма стал применяться механизм расчета с помощью кредитных карточек.
  
  К этому времени расширился и ассортимент услуг через Интернет. Выяснилось, что организация торговли через Интернет требует значительно меньших капитальных вложений при более гибком учете особенностей спроса. И здесь обозначилась проблема, решение которой не существует до сего времени.
  
  Во первых, производя платеж с помощью собственной кредитной карточки в Интернете Вы сообщаете незнакомому человеку реквизиты своего банковского счета, подвергая его искушению воспользоваться им для решения собственных финансовых проблем.
  
  Во вторых, если Вы активно используете коммерцию Интернета, Вы становитесь доступными недобросовестному контролю над Вашей финансовой деятельностью.
  
  В этом отношении наличные деньги позволяют сделать жизнь любого человека анонимной в той степени, в какой он заинтересован.
  
  Существует еще одно отличие наличных денег от электронных - если наличные деньги у Вас в кармане, то они есть, и ничто не может отменить этот факт ([21]).
  
  С электронными деньгами дело обстоит более сложно - если они 'у Вас в кармане', то Вы должны еще доказать, что это не произвольный набор нулей и единиц, организованных в файл, а электронные деньги, имеющие номинальную стоимость, обеспеченную счетом в каком либо банке.
  
  Кроме того, наличные деньги, кроме обеспечения процесса купли-продажи призваны решать экономические, политические и прочие проблемы того региона, где они имеют хождение.
  
  Как правило, электронные деньги таких границ не имеют и это является одной из причин, по которым электронные деньги не вызывают восторга у властей предержащих.
  
  Понятно, что Криптология не претендует на решение всех этих проблем.
  
  Более того, мы понимаем, что даже те проблемы, которые относятся к криптологии, требуют более полных исследований, что не входит в круг вопросов предлагаемой работы.
  
  Является ли абсолютно новой идея, которая лежит в основе электронных денег?
  
  В настоящее время существуют две концепции, которые положены в основу существующих систем электронных денег.
  
   * Безналичный расчет, при котором покупатель выдает чек или предъявляет магнитную карточку, которые обеспечены размером банковского счета. Концепция хороша всем, кроме того, что она не выполняет требование анонимности, и кроме того, надежность определяется мерами надежности, принятыми в банке.
   * Эмиссия банкнот, при которой банк изготавливает банкноты фиксированного достоинства. Стоимость банкноты в этом случае гарантирована банком. Банкноты одинакового достоинства имеют собственные идентификационные номера. Банки могут гарантировать, что при продаже номера банкнот не фиксируются, что обеспечивает анонимность, но это, разумеется, зависит от добросовестности банковских служащих.
  
  Таким образом, существующие системы электронных денег не гарантируют анонимности.
  
  Здесь же мы рассмотрим реализацию некоторых функций электронных денег, при использовании асимметричного алгоритма с высоким быстродействием. Рассмотренная далее реализация представляет собой эмиссию банкнот, достоинство которой и идентификационный номер задаются клиентом, но номер остается закрытым для всех, включая и клиента до тех пор, пока банкнота не будет предъявлена продавцом для ее утилизации.
  
  Допустим, существует абонент А (EA(),DA()), , которого будем называть покупателем, абонент В (EB(),DB()), которого будем называть продавцом и банк (ES(),DS()), который является эмитентом банкнот по запросу абонента А. В этом случае предполагается, что абонент А имеет счет в этом банке.
  
  Допустим, что абонент А решил приобрести товар у абонента В. Процесс купли-продажи можно разбить на несколько этапов:
  
   1. изготовление банкнот электронных денег абонентом А; на этом этапе абонент А сам определяет номинал банкноты и ее индивидуальный номер - признак, который отличает создаваемую банкноту от других.
   2. сертификация банком изготовленных банкнот; на этом этапе банк удостоверяет, что номинал банкнот обеспечен расчетным счетом абонента А, уменьшает счет абонента А на величину стоимости банкноты и переводит ее в свой Эмиссионный фонд.
   3. передача по каналу абонентом А электронных банкнот абоненту В;
   4. передача по каналу абонентом В банку полученных электронных банкнот для проверки их на состоятельность;
   5. проверка банком полученных электронных банкнот на состоятельность (не являются ли полученные банкноты подделкой, либо не представляют ли они копии уже использованных банкнот);
   6. если представленные банкноты несостоятельные, то банк сообщает об этом абоненту В и процесс купли-продажи заканчивается. Если проверка заканчивается положительно, то банк переводит на счет абонента В номинал полученных банкнот, снимая определенную сумму со своего Эмиссионного фонда и извещает об этом абоненту В.
   7. абонент В передает абоненту А проданный товар.
  
  Рассмотрим выполнение перечисленных операций.
  
  
  Изготовление банкнот электронных денег абонентом А
  
  
  
  В отличие от реального мира, в виртуальном мире абоненту А допустимо участвовать в процессе изготовления банкнот.
  
  Примем, что банкнота (файл Σ) состоит из двух частей:
  
  " Номинала ΣN и
  
  " Индивидуального номера (имени) Σr банкноты.
  
  При этом, следует принять, что значение номинала ΣN должно быть доступно для любого заинтересованного лица, в то время, как Σr банкноты должен быть 'закрыт' до тех пор, пока банкнота будет предъявлена банку для оплаты. Значение Σr не должно быть связано с именем 'хозяина'.
  
  Для изготовления банкноты абонент А:
  
  1. формирует ΣN, записав в нем значение номинала банкноты;
  
  2. генерирует с помощью генератора случайных чисел номер будущей банкноты и записывает его в файл Σr.
  
  3. выполняет операции EA(ES(Σr)) . Особенность этой операции заключается в том, что алгоритм EA здесь применяется для запрета определения серийного номера банкноты. Для этого следует знать DA, DS, и применить их в порядке DA, DS.,
  
  Пока есть EA, банк не может применить DS и предпринять действия для определения DA и, затем Σr. Это вытекает из того, что в рассматриваемом случае алгоритм не коммутативен, то есть DS(EA(ES(Σr))) ≠ EA (Σr).
  
  4. выполняет операцию ΣaS= ES([ΣN + EA(ES(Σr))]) и посылает этот код банку.
  
  
  Сертификация банком изготовленных банкнот
  
  
  
  Банк, приняв ΣaS от абонента А
  
  1. выполняет операцию
  
  DS(ΣaS) = DS(ES([ΣN + EA(ES(Σγ))])) → ΣN + EA(ES(Σγ)),
  
  то есть, определяет значение номинала.
  
  Обратите внимание, что индивидуальный номер банкноты банк прочитать не может.
  
  2. уменьшает банковский счет абонента А на величину ΣN и увеличивает на эту сумму свой Эмиссионный фонд,
  
  3. кодирует ΣN и получает DS(ΣN),
  
  4. формирует конкатенацию ΣS=[ DS(ΣN) + EA(ES(Σγ))],
  
  5. выполняет операцию EA(ΣS) = EA(DS(ΣN) + EA(ES(Σγ))) и посылает EA(ΣS) абоненту А.
  
  Таким образом, абонент А получил подтвержденную банком банкноту EA(ΣS) достоинством ΣN.
  
  Обратите внимание, что,
  
  " если бы банк захотел соединить информацию этой конкретной банкноты с именем абонента А, то ему это не удалось бы, так как значение Σγ ему не известно,
  
  " банкнота ΣS хранится у абонента А в виде EA(ΣS), а это значит, что
  
   a. ее никто, кроме абонента А не может прочитать,
  
   b. никто, включая абонента А и банк не могут, порознь, изменить значение ΣN. Это могут сделать, договорившись, совместно банк и абонент А, но в этом случае они могут решить задачу проще, переведя на счет абонента А любую сумму.
  
  Это значит, что никто не может ни украсть, ни изменить 'наличность' абонента А.
  
  
  Передача по каналу электронных банкнот абонентом А абоненту В (оплата)
  
  
  
  Допустим, абонент В имеет товар, который нужен абоненту А и он готов уплатить за него ΣN. денежных единиц.
  
  Если абонент В готов уступить свой товар за эту сумму, то
  
  абонент А выполняет следующие действия:
  
  1. декодирует EA(ΣS):
  
  DA(EA(ΣS)) → DA( EA(DS(ΣN) + EA(ES(Σγ)))) → DS(ΣN) + EA(ES(Σγ)).
  
  2. декодирует EA(ES(Σγ)):
  
  ΣB = DS(ΣN), DA(EA(ES(Σγ))) → DS(ΣN), ES(Σγ)
  
  3. кодирует открытым ключем абонента В:
  
  EB(ΣB) = EB(DS(ΣN) + ES(Σγ))
  
  и посылает EB(ΣB) абоненту В.
  
  Абонент В:
  
  1. выполняет операцию
  
  DB(EB(ΣB)) → DB(EB(DS(ΣN) + ES(Σγ))) → ΣB = DS(ΣN), ES(Σγ),
  
  2. проверяет, соответствует ли достоинство полученной банкноты объявленной абонентом А: ES(DS(ΣN)) = ΣN.
  
  3. выполняет операции
  
  BΣS = DB([DS(ΣN)+ES(Σγ)]), ES(BΣS)= ES(DB([DS(ΣN)+ES(Σγ)]))
  
  и посылает полученный код банку для проверки банкноты на подделку.
  
  Проверка банком полученных электронных банкнот на состоятельность
  
  
  
  Банк получает от абонента В ES(BΣS)= ES(DB([DS(ΣN)+ES(Σγ)])) и выполняет следующие операции:
  
  1. декодирует принятый код с помощью DS :
  
  DS(ES(BΣS))=DS(ES(DB([DS(ΣN)+ES(Σγ)]))),
  
  BΣS = DB([DS(ΣN)+ES(Σγ)]),
  
  2. а затем декодировать с помощью EB:
  
  EB(DB([DS(ΣN), ES(Σγ)])) = DS(ΣN), ES(Σγ),
  
  3. ES(DS(ΣN), ES(Σγ)) = ΣN , Σγ , проверяет, находится ли в базе данных идентификационный номер банкноты Σγ. Если такой номер находится в БД банка, то это значит, что банкнота однажды уже использовалась, то есть, предъявленная банкнота является копией. Если это не так, то банк извещает абонента В о том, что банкнота легитимна, и заносит на счет абонента В сумму ΣN..
  Асимметричные алгоритмы, кому они нужны?
  
  Странно поставленный вопрос, не правда ли?
  
  Ведь все написанное выше должно было бы привести к одному ответу: 'асимметричные алгоритмы нужны всем тем, кто нуждается в надежной защите своей информации'.
  
  Тем не менее, вся история современной криптографии вызывает сомнения в истинности приведенного выше ответа.
  
  Рассмотрим некоторые факты.
  
  א. В первой половине семидесятых годов ХХ века появился первый стандарт криптографического алгоритма DES (Data Encryption Standard) - симметричного криптографического алгоритма, который до последнего времени обеспечивал надежность кодирования информации. Появившийся на смену DES новый стандарт отличается от прежнего некоторыми техническими характеристиками, но по надежности он не намного превосходит DES. Вызывает недоумение факт в истории DES: сразу же по выходе в свет, было наложено ограничение сверху на размер ключа экспортного варианта DES. Вдумайтесь только, надежность экспортного варианта криптографического алгоритма сознательно ограничивалась сверху. Со временем, эта граница постепенно поднималась, но не отменялась. Можно предположить, что ограничение сверху повышалось вместе с ростом производительности суперкомпьютеров Агентства Национальной Безопасности (National Security Agency - NSA), которое долго публично не признавало факта своего существования. Можно высказывать разные предположения относительно такой связи, но не трудно представить себе, какой была бы реакция названного выше и подобных ему ведомств, на предложенный асимметричный алгоритм с производительностью, соизмеримой с DES. С этой точки зрения RSA устраивал всех. Появление стандарта DES позволило выделить две группы пользователей криптографического алгоритма:
  
   a. Пользователи, которые заинтересованы в защите информации. Это достаточно многочисленная группа, но с ограниченными возможностями влиять на параметры алгоритма. Единственное их требование к криптографическому алгоритму - это 'чем надежнее, тем лучше'.
  
   b. Пользователи, заинтересованные в контроле и даже изменении информации. В США к этой группе относится Агентство Национальной Безопасности (АНБ). АНБ имеет в своем распоряжении самые современные суперкомпьютеры и обладает возможностью влиять на решения, принимаемые на государственном уровне. В других государствах подобные конторы могут иметь разные названия, но их цели совпадают с АНБ.
  
  Таким образом, государственные ведомства безопасности заинтересованы в 'прозрачности' шифров, в то время, как коммерческие структуры заинтересованы в сильных криптографических алгоритмах.
  
  Для того, чтобы алгоритм полностью отвечал требованиям государственных структур, он должен быть полностью 'прозрачным'. Это делает защищаемую информацию доступной для любого участника информационного процесса, то есть, теряется смысл применения криптографических алгоритмов.
  
  В то же время коммерческие структуры заинтересованы в сильных алгоритмах.
  
  Компромиссный вариант - это принятие 'верхней границы' надежности криптографического алгоритма, при которой государственные структуры, обладающие мощной вычислительной техникой (недоступной большинству коммерческих структур), имеют возможность контролировать кодируемую информацию.
  
   ב. Во второй половине восьмидесятых годов ХХ века была разработана спецификация общеевропейской сети мобильной связи, названная Global System for Mobile Communications или просто GSM.
  
  
  
  
  
  
  
  Рис. 2
  
  На Рис. 2 показана упрощенная структура GSM ([22]). Мы приводим ее только для того, чтобы показать, насколько сложна система.
  
  В девяностые годы была создана цифровая GSM. Переход на цифровую систему преследовал решение двух задач: повышение надежности и применение криптографических алгоритмов. Зная уровень развития криптографии и высокую квалификацию создателей GSM , следовало бы ожидать, что цифровая GSM представляет собой образец применения криптографических методов защиты. Тем более, что в настоящее время GSM служит основой для 70% мобильных систем в мире.
  
  Для того, чтобы представить надежность системы, обратимся к двум цитатам. ([23])
  
  Вот что говорит Джеймс Моран, директор подразделения, отвечающего в консорциуме GSM за безопасность и защиту системы от мошенничества: "Никто в мире не продемонстрировал возможность перехвата звонков в сети GSM. Это факт... Насколько нам известно, не существует никакой аппаратуры, способной осуществлять такой перехват" ([24]).
  
  А вот мнение Питера Гутмана, весьма известного хакера-криптографа из Оклендского университета (Новая Зеландия): "Имея ситуацию, когда целый ряд компаний продает оборудование для перехвата GSM (причем делается это уже в течение определенного времени и с весьма открытой рекламой в Сети), этот директор по безопасности "либо лжет, либо некомпетентен, либо и то, и другое разом" (цитируя строку из книги Deep Crack). Интересно то, что сейчас все рекламирующие данное оборудование фирмы устроили ограниченный доступ на свои сайты, по-видимому, для поддержания мифа о том, что "не существует аппаратуры, способной осуществлять такой перехват""([25]).
  
   Что же это такое?
  
  Как реализуется защита информации в GSM, если она вызывает такие противоречивые высказывания?
  
  Во первых, криптографические алгоритмы GSM засекречены.
  
  Вся история криптографии показывает, что засекречивание криптографического алгоритма свидетельствует о его слабости.
  
  Во вторых, GSM содержит три алгоритма: А3, А5 и А8.
  
  А3 (симметричный) - предназначен для защиты информации о местоположении абонента,
  
  А8 - (асимметричный) - для генерации и защиты ключей. Оба эти алгоритма расположены в NSS (см. Рис. 2).
  
  Алгоритм А5 - (симметричный) расположен в телефонной трубке и предназначен для защиты информации. Так как он должен работать в режиме реального времени, то и выбран симметричный алгоритм.
  
  Приведенное выше объясняет высказывание Джеймса Морана.
  
  Какова же причина высказывания Питера Гутмана?
  
  Обратите внимание на примечание 25 на стр. 37 (название статьи), где упоминается алгоритм А5/1.
  
  Дело в том, что GSM имеет две модификации алгоритма А5: А5/1 и А5/2.
  
  Отличаются эти алгоритмы 'слабостью'. А5/1 - более слабый, чем А5/2.
  
  И действительно, вскоре был взломан А5/1.
  
  Это событие очень живо обсуждалось в печати. Взломом занимались такие криптоаналитики, как А.Бирюков и А.Шамир - один из создателей RSA (S - первая буква имени Shamir).
  
  Как выяснилось, алгоритм А5 - регистровый потоковый алгоритм и структура его такова, что его можно сделать достаточно сильным. Что же помешало разработчикам сделать его надежным? Для чего потребовалось две модификации алгоритма А5: А5/1 и А5/2?
  
  Ситуация несколько прояснится, если принять во внимание, что GSM, предназначенный для Западной Европы содержал А5/2, а для России - А5/1.
  
  Если вернуться к причинам экспортных ограничений DES (см. выше), то можно сделать вывод, что суперкомпьютеры служб безопасности Западной Европы более мощные, чем у Российских спецслужб.
  
  Примеры DES и GSM показывают, что существуют две категории групп пользователей, заинтересованных в сильном криптографическом алгоритме для собственных нужд и ослабленном для прочих пользователей: а) службы безопасности и б) военные, то есть, организации, для которых должны быть исключены любые способы контроля их информации ([26]).
  
  Характерная особенность этих групп - это возможность непосредственно (путем запретов и правительственных постановлений) влиять на производителей коммерческих криптографических систем. Разумеется, при равных условиях, применение асимметричного алгоритма только усложнит 'жизнь' служб безопасности.
  Пример криптографической защиты асимметричным алгоритмом мобильной связи
  
  Что же может измениться при использовании асимметричного алгоритма, если его быстродействие позволяет работать в реальном масштабе времени для GSM?
  
  " Отпадает необходимость алгоритма А3.
  
  " Отпадает необходимость алгоритма А8.
  
  Взамен протокола с симметричным алгоритмом А5/2 можно привести протокол на базе асимметричного алгоритма. Допустим, существуют: станция S: ES(), DS() и два абонента A: EA(), DA() и B: EB(), DB() из которых абоненту А необходимо обменяться информацией с абонентом В. В трубке абонента А находятся микроконтроллер, в который 'зашит' секретный алгоритм декодирования DA() и микрочип, например, на базе FPGA, который может быть настроен на выполнение любого открытого алгоритма кодирования. Аналогичные устройства находятся в трубке абонента В и в станции S.
  
  Протокол обмена информацией состоит из следующих шагов:
  
   * Абонент А генерирует запрос к станции: ES(DA(B)).
   * По этому запросу станция S по имени абонента В находит в своей базе данных (см. 'Защита Базы Данных (БД).', стр. 22) параметры абонента В и запрашивает его о готовности связи с абонентом А: DS(EB(A+EA)).
   * Если абонент В готов к взаимодействию с А, то он отвечает станции: ES(DB(A)) и настраивает свой микрочип FPGA на исполнение EA.
  
  Обратите внимание, что операторы DA(),DB() и DS() используются в качестве подписи. Удостовериться, что информация была подготовлена именно абонентом А можно, применив к коду DA(B) оператор EA(). Таким образом, запрос на организацию взаимодействия абонентов А и В происходит анонимно для всех остальных.
  
   * Получив ответ от абонента В: ES(DB(A)), станция создает канал связи между А и В (полоса частот, физический канал, и тому подобное), сообщив об этом А: DS(EB(A+EA)), то есть, передает имя абонента и его открытый код. Микрочип абонента А на базе FPGA абонента А настраивается на открытый код EB()
   * Абоненты А и В начинают диалог: А начинает кодировать поток битов абоненту В в виде кода - EB(DA(PA)), а абонент В отвечает абоненту А кодом - EA(DB(PB)).
  
  Здесь приведено схематическое описание протокола криптографической защиты мобильной связи, но и при этом можно видеть, что применение асимметричного криптографического алгоритма позволяет обеспечить криптографическую защиту аудиоинформации, анонимность и идентификацию.
  Обеспечение безопасной связи с движущимся объектом.
  
  Допустим, существует объект А: EA(), DA() одноразового применения, с которым возникает необходимость связи с центром управления S: ES(), DS() только в процессе движения объекта А.
  
  В отличие от предыдущего примера (см. 'Пример криптографической защиты асимметричным алгоритмом мобильной связи ', стр. 38) в данном случае объект А должен обмениваться информацией только с центром управления. Это значит, что алгоритмы ES(), DA() ([27]) должны быть реализованы микроконтроллером объекта А.
  
  Криптографический протокол можно представить в виде:
  
   * Сразу после запуска, объект А начинает передавать телеметрическую информацию PA в виде кода ES(DA(PA)) и ожидает команду с центрального пункта управления.
   * Центральный пункт управления принимает телеметрическую информацию: EA(DS(ES(DA(PA)))) → PA.
   * При необходимости центральный пункт посылает команду PS в виде кода DS(EA(PS)).
  
  
  
  
  
  
  
  
  
  
  Обоснование применения КАМСИ
  
  Зри в корень!
  
  Козьма Прутков
  
  Для понимания идеи применения КАМСИ в криптографии достаточно иметь представление о таблице переходов и преобразовании с ее помощью информации.
  КАМСИ?
  
  До сих пор мы обсуждали проблему асимметричных алгоритмов в криптографии и привели некоторые соображения относительно применения КАМСИ. Все эти соображения приводились без обсуждения свойств КАМСИ.
  
  Однако, прежде чем мы перейдем к рассмотрению свойств КАМСИ, следует заметить, что для их реализации используются такие 'короткие' операции, как логические, сдвиговые и тому подобные 'быстрые' операции. Это может служить оптимистической основой для обсуждения перспектив применения КАМСИ в криптографии.
  
  Что же такое КАМСИ, и как она выглядит?
  
  Прежде всего, КАМСИ, как любой конечный автомат, может быть задан таблицей переходов, которая полностью описывает алгоритм ее функционирования. Известно, что основное назначение любого конечного автомата - преобразование входной последовательности сигналов в выходную последовательность ([28]). Казалось бы, уже этого должно бы быть достаточно для применения его в информационных системах. На это обстоятельство обратили внимание авторы работ, перечисленных на стр. 132.
  
   Рассмотрим пример.
  Пример КАМСИ
  
  Пример 1.
  
  На Рис. 3 показано взаимодействие двух конечных автоматов А1 и SS1.
  
  Первый из них, А1 принимает на вход поток битов Р (назовем его исходным текстом), и на выходе его появляется поток битов Е (назовем его кодом, а сам автомат - кодером).
  
  Второй из этих автоматов SS1 принимает на вход поток битов Е, а на выходе при этом появляется поток битов Р (такой же, какой был подан на вход А1) поэтому SS1 будем называть декодером.
  
  
  
  
  
  
  
  
  
   E
  
   P
  
   P
  
  
  
  
  
  
  
  
  
  Рис. 3 Структура процесса кодирования-декодирования
  
  Казалось бы, эта пара автоматов ничего не сделала: на вход А1 подан поток битов Р, и этот поток битов появляется на выходе SS1, то есть, эта пара автоматов вместе выполняет функцию повторителя. Но это только на первый взгляд.
  
  Конечные автоматы А1 и SS1 могут находиться на любом расстоянии друг от друга и в этом случае говорят, что их соединяет информационный канал. По информационному каналу передается поток битов Е. Если информационный канал не защищен, то информация, передаваемая по нему доступна любому, кто имеет доступ к каналу. В этом случае защищенность информации полностью зависит от того, насколько код Е содержит информацию об исходном тексте Р. Это значит, что качество защиты информации зависит от алгоритма функционирования конечного автомата А1. Конечный автомат А1 может обладать одним из следующих свойств:
  
   * Алгоритм автомата А1 может быть настолько примитивным, что по потоку битов Е не трудно восстановить Р. В этом случае теряет смысл применение А1 и, соответственно, SS1.
   * Алгоритм автомата А1 может быть таким, что по Е, никто и никогда не сможет восстановить Р. В этом случае отпадает необходимость не только в применении А1 и SS1, но и самого информационного канала.
   * Алгоритм автомата А1 может быть таким, что исходный текст Р может быть восстановлен по Е только с помощью конечного автомата SS1. Это значит, что если засекретить конечный автомат SS1, то доступ к информации Р будет иметь только тот, кто обладает этим автоматом. Конечные автоматы А1 и SS1 могут реализовать такие алгоритмы кодирования и декодирования, что обладатель конечного автомата А1 не сможет по полученному им потоку Е, восстановить Р.
  
  Конечные автоматы А1 и SS1 реализуют алгоритмы, которые могут быть заданы с помощью таблиц переходов.
  
  Рассмотрим Table 1, в которой приведены таблицы переходов конечных автоматов А1 и SS1.
  
  
  
  
  
  
  
   Rounded Rectangular Callout: Состояние (А), в которое перейдет автомат при Р=1. На выходе установится Е=0.
  
   Rounded Rectangular Callout: Название автомата
  
  
  
  
  
  Rounded Rectangular Callout: Состояние,(А) в котором находится автомат А1А1
  
  
  P,E
  
  P=0
  
  
  P=1
  
  A
  
  
  B,0
  
  
  A,0
  
  B
  
  
  A,1
  
  
  B,1
  
  (A)
  
  
  
  
  
  
  
  
  
  
  SS1
  
  
  E,P
  
  E=0
  
  
  E=1
  
  S0
  
  
  S1,1
  
  
  S2,1
  
  S1
  
  
  S1,1
  
  
  S2,1
  
  S2
  
  
  S3,0
  
  
  S4,0
  
  S3
  
  
  S1,0
  
  
  S2,0
  
  S4
  
  
  S3,1
  
  
  S4,1
  
  (B)
  
  
  
  Table 1
  
  Само название таблицы переходов показывает, что она описывает изменения, которые произойдут в состоянии автомата при изменении сигнала на его входе.
  
  Таблица переходов имеет три столбца:
  
   * в первом столбце приведены состояния конечного автомата. В рассматриваемом примере это два состояния: А и В ([29]);
   * во втором столбце - записано имя состояния, в которое будет переход, при подаче на вход Р значения 0. Через запятую записано значение, которое появится на выходе Е.
  
  Например, если автомат А1 находится в состоянии А (строка А), и на его вход Р подается 0 (Р=0), то автомат А1 перейдет в состояние В (строка В) и на его выходе Е установится значение 0 (это записано в виде В,0). Аналогично интерпретируется содержимое третьего столбца.
  
  На Рис. 3 (стр 40) показаны:
  
  1. Кодер и декодер:
  
  " кодер А1 (Table 1A); он задан таблицей переходов конечного автомата, на вход которого подаются входные биты, а на выходе устанавливаются значения выходных битов. Например, пусть автомат А1 находится в состоянии А (первая строка таблицы переходов). Если на его вход Р подать 1, то он останется в состоянии А, а на выходе появится 0. Если опять подать на вход 1, то автомат останется в состоянии А, а на выходе появится 0. Обратите внимание: подали на вход последовательность 11, а на выходе появилась последовательность 00. значит ли это, что автомат А1 инвертирует входные биты? Продолжим эксперимент и подадим на вход 0, автомат перейдет в состояние В, и на выходе появится значение 0. На Рис. 4 в строках (a), (b) и (c) показан весь процесс кодирования.
  
  " декодер SS1 (Table 1B) - инвертор кодера А1. Он задан таблицей переходов конечного автомата, на вход которого подаются биты, полученные с выхода кодера Е. Так как SS1 - инвертор кодера, то на выходе декодера появляются значения Р (см. Рис. 3). Строки (d) и (e) Рис. 4 показывают процесс декодирования.
  
  
  
  Процесс кодирования-декодирования
  
  A1
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  
  
  
  
  
  
  (a)
  
  
  
  
  A
  
  
  A
  
  
  A
  
  
  B
  
  
  B
  
  
  A
  
  
  B
  
  
  B
  
  
  B
  
  
  A
  
  
  B
  
  
  B
  
  
  A
  
  
  B
  
  
  B
  
  
  
  
  
  (b)
  
  
  
  
  
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  
  
  
  (c)
  
  SS1
  
  
  
  
  
  S0
  
  
  S1
  
  
  S1
  
  
  S1
  
  
  S2
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  S4
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  (d)
  
  
  
  
  
  
  
  
  
  
  1
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  (e)
  
  
  
  Рис. 4
  
  
  
  Особенность кодера (КАМСИ) заключается в том, что
  
  " в его таблице переходов (см. Table 1А) есть состояния, переход из которых формирует одинаковые значения на выходе, независимо от сигнала на входе. Например, при переходе из состояния А и при Р=0 и при Р=1 на входе, значение на выходе Е равно 0. Это обстоятельство затрудняет восстановление входного сигнала по значению на выходе (reverse engineering). Инвертор (В) так же представляет собой КАМСИ.
  
  " В строке (e) таблицы (Рис. 4), исходный текст начинается с третьего бита. Это равносильно тому, что закодированная входная последовательность появляется на выходе SS1 с задержкой, равной 2. Это означает, что для получения раскодированного текста целиком, в конце его следует дополнительно добавить, минимум, два бита, значения которых могут выбираться произвольно.
  
  Следует заметить, что не всякая таблица, похожая на рассмотренную таблицу переходов, является КАМСИ.
  
  Формализуем понятия, которые были использованы в рассмотренном примере.
  
  В работе [8] (см. стр 97) приведено определение конечно-автоматной модели с памятью: 'Машина М называется машиной с конечной памятью порядка ч, если ч есть наименьшее целое, такое что текущее состояние М (а значит, и значение на выходе) может быть определено однозначно из предшествующих ч значений выходов'.
  
  В рассмотренном выше примере КАМСИ имеет ч=2 (см Рис. 4, стр. 43).
  
  Следует обратить внимание, что приведенное определение машины с памятью не является конструктивным, то есть, оно не содержит признаков, по которым можно непосредственно, без тестирования определить, обладает ли конкретный конечный автомат конечной памятью. Для этого существует единственный способ - проделать определенные тестирующие проверки.
  
  Аналогичная ситуация существует в Теории Чисел, где, со времен Эратосфена, определение основного объекта теории - простого числа, предполагает тривиальную. проверку, имеет ли оно, в качестве делителя, простые числа. Кстати, именно это обстоятельство легло в основу однонаправленной функции с секретом, что позволило создать асимметричный алгоритм RSA.
  
  Разумеется, подобное сравнение не предполагает применения суждения по аналогии, и требует дополнительной аргументации.
  
  Для применения КАМСИ в криптографическом протоколе необходимо создать алгоритм генерации открытого и секретного ключей, в состав которого не входили бы достаточно трудоемкие операции тестирования на информационную сохраняемость. Более того, алгоритм генерации должен позволять генерировать КАМСИ с заданными значениями параметров. Эти обстоятельства выгодно отличают алгоритм на базе КАМСИ от RSA, в котором часто вынуждены применять псевдопростые числа из-за большой трудоемкости генерации простых чисел.
  
  В работе [8] (см. стр 97) показано, что существует класс конечно-автоматных моделей, для которых наличие таблицы переходов позволяет закодировать исходный текст, и, при этом, знание ч - декодировать его. Там же обсуждается способ тестирования конечно-автоматной модели на информационную сохраняемость (КАМСИ), и приводится способ построения обратного автомата - декодера.
  
  Введем некоторые определения и преобразования КАМСИ, которые позволят нам построить однонаправленную функцию с секретом на базе КАМСИ.
  Операции преобразования КАМСИ
  
  В этом разделе вводятся понятия КАМСИ-композиции и КАМСИ-примитивов. Показано, что если КАМСИ-композиция (кодер) состоит из N КАМСИ-примитивов, то легитимная сложность инвертирования кодера линейно зависит от N.
  
  Вводятся преобразования КАМСИ-примитивов, которые сохраняют свойства КАМСИ и доказано, что композиция КАМСИ так же сохраняет свойство КАМСИ.
  КАМСИ-композиция
  
  В последующих двух разделах (Свойства последовательного соединения КАМСИ и Алгоритм построения КАМСИ-композиции) мы введем операцию построения конечного автомата, эквивалентного последовательно включенным КАМСИ. Такой конечный автомат назван КАМСИ-композицией. Показано, что КАМСИ-композиция - так же КАМСИ и приводятся формулы, позволяющие вычислить ч-порядок и число состояний таблицы переходов КАМСИ-композиции.
  
  
  Свойства последовательного соединения КАМСИ
  
  Рассмотрим последовательное соединение двух КАМСИ А1 и А2 (см. Рис. 5). Выше, на стр. 41 (см. Рис. 3) мы уже рассматривали последовательное соединение двух КАМСИ, кодера и декодера, которые соединены информационным каналом. Теперь мы рассмотрим такое объединение конечных автоматов, которое интересует нас постольку, поскольку его можно заменить эквивалентным конечным автоматом. Нас интересует способ построения такого автомата и его свойства и параметры.
  
  
  
  Рис. 5
  
  Докажем следующее утверждение.
  
  Утверждение 1 Композиция двух последовательно включенных КАМСИ А1=>А2 (Рис. 5) является КАМСИ, которая имеет порядок μ= μ(A1) + μ(A2), где μ(A1) и μ(A2) - μ-порядки КАМСИ А1 и А2, соответственно
  
  Доказательство. Из определения КАМСИ следует, что μ(A1) символов входного потока битов (Р), поданных на вход КАМСИ А1 достаточно, чтобы определить первый символ Р на выходе Е1. Однако, на выходе Е2 он может появиться только через μ(A2) битов Е1 на входе КАМСИ А2. Отсюда следует, что первый символ Р на выходе Е2 может быть получен после μ= μ(A1) + μ(A2), символов, поданных на вход Р, то есть, композиция КАМСИ А1,А2 также является КАМСИ и имеет порядок μ= μ(A1) + μ(A2).
  
  Пример 2
  
   В Table 2(a) и (b) приведены таблицы переходов КАМСИ А1 и А2 ч-порядка 2, а в Table 2(c) и (d) - инверсные им автоматы SS1 и SS2, соответственно ([30]).
  
  
  
  
  
  
  
  А1
  
  
  P,E
  
  P=0
  
  
  P=1
  
  A
  
  
  B,0
  
  
  A,0
  
  B
  
  
  A,1
  
  
  B,1
  
  (a)
  
  А2
  
  
  P,E
  
  P=0
  
  
  P=1
  
  A
  
  
  A,1
  
  
  B,1
  
  B
  
  
  B,0
  
  
  A,0
  
  (b)
  
  
  
  μ(A1) = 2
  
  
  
  
  
  
  
  
  SS1
  
  
  P,E
  
  E=0
  
  
  E=1
  
  S0
  
  
  S1,1
  
  
  S2,1
  
  S1
  
  
  S1,1
  
  
  S2,1
  
  S2
  
  
  S3,0
  
  
  S4,0
  
  S3
  
  
  S1,0
  
  
  S2,0
  
  S4
  
  
  S3,1
  
  
  S4,1
  
  (c)
  
  SS2
  
  
  P,E
  
  E=0
  
  
  E=1
  
  S0
  
  
  S1,0
  
  
  S2,0
  
  S1
  
  
  S1,0
  
  
  S2,0
  
  S2
  
  
  S3,1
  
  
  S4,1
  
  S3
  
  
  S1,1
  
  
  S2,1
  
  S4
  
  
  S3,0
  
  
  S4,0
  
  (d)
  
  
  
  
  
  Table 2
  
  
  
  Обозначим через А1 и SS1 кодер и декодер, соответственно, (аналогично А2 и SS2). В Table 3 и в Table 4 (строка (а)) приведен один и тот же поток Р бит (кодируемый текст, который известен только отправителю, см. Table 3(а)). В строках (b) таблиц приведены состояния, в которые переходят автоматы А1 и А2, соответственно. В строках (с) - значения на выходе - закодированный текст, который может быть известен всем. В строках (d) и (e) приведены результаты декодирования, которые показывают, что результаты декодирования совпадают с исходным текстом, но появляются, начиная с третьего бита, то есть, с задержкой, равной двум.
  
  
  
  
  
  A1
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  
  
  
  
  
  
  (a)
  
  (b)
  
  (c)
  
  (d)
  
  (e)
  
  
  
  
  A
  
  
  A
  
  
  A
  
  
  B
  
  
  B
  
  
  A
  
  
  B
  
  
  B
  
  
  B
  
  
  A
  
  
  B
  
  
  B
  
  
  A
  
  
  B
  
  
  B
  
  
  
  
  
  
  
  
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  
  
  SS1
  
  
  
  
  
  S0
  
  
  S1
  
  
  S1
  
  
  S1
  
  
  S2
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  S4
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  
  
  
  
  
  
  
  
  1
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  Table 3
  
  A2
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  
  
  
  
  
  
  (a)
  
  (b)
  
  (c)
  
  (d)
  
  (e)
  
  
  
  
  A
  
  
  B
  
  
  A
  
  
  A
  
  
  B
  
  
  B
  
  
  B
  
  
  A
  
  
  B
  
  
  B
  
  
  B
  
  
  A
  
  
  A
  
  
  A
  
  
  B
  
  
  
  
  
  
  
  
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  
  
  SS2
  
  
  
  
  
  S0
  
  
  S2
  
  
  S3
  
  
  S2
  
  
  S4
  
  
  S3
  
  
  S1
  
  
  S1
  
  
  S2
  
  
  S3
  
  
  S1
  
  
  S1
  
  
  S2
  
  
  S4
  
  
  S4
  
  
  
  
  
  
  
  
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  Table 4
  
  Отсюда следует, что для того, чтобы передать все биты исходного текста, их следует дополнить двумя (ч=2) произвольными символа. При декодировании эти биты не появляются, а выходная последовательность у декодера начинается с ч=2 произвольных, символов ([31]).
  
  Так как автоматы в Table 3 и Table 4 правильно декодируют исходный текст Р, то можно предположить, что они оба КАМСИ ([32]).
  
  В Table 5 показан процесс кодирования последовательностью приведенных выше автоматов, из которого видно, что при этом задержка равна ч=4. Следует обратить внимание на то, что, если кодирование производилось в порядке A1 →A2, то декодирование - должно выполняться в обратном порядке SS2 →SS1 .
  
  В качестве примера в Table 6 показан процесс декодирования в другом порядке: SS1 →SS2, из которого видно, что процесс декодирования должен выполняться в порядке, обратном кодированию.
  
  
  
  P
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  (a)
  
  A1
  
  
  A
  
  
  A
  
  
  A
  
  
  B
  
  
  B
  
  
  A
  
  
  B
  
  
  B
  
  
  B
  
  
  A
  
  
  B
  
  
  B
  
  
  A
  
  
  B
  
  
  B
  
  
  B
  
  
  B
  
  
  
  
  
  
  
  
  
  
  
  (b)
  
  E1
  
  
  
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  
  
  
  
  
  
  
  
  
  (c)
  
  A2
  
  
  
  
  
  A
  
  
  A
  
  
  A
  
  
  A
  
  
  B
  
  
  A
  
  
  A
  
  
  B
  
  
  A
  
  
  B
  
  
  B
  
  
  A
  
  
  B
  
  
  B
  
  
  A
  
  
  B
  
  
  A
  
  
  
  
  
  
  
  
  (d)
  
  E2
  
  
  
  
  
  
  
  
  1
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  
  
  
  
  
  
  (e)
  
  SS2
  
  
  
  
  
  
  
  
  S0
  
  
  S2
  
  
  S4
  
  
  S4
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  S3
  
  
  S1
  
  
  S2
  
  
  S3
  
  
  S1
  
  
  S2
  
  
  S3
  
  
  
  
  
  (f)
  
  
  
  
  
  
  
  
  
  
  
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  
  
  
  (g)
  
  SS1
  
  
  
  
  
  
  
  
  
  
  
  S0
  
  
  S1
  
  
  S2
  
  
  S3
  
  
  S1
  
  
  S1
  
  
  S2
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  S4
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  (h)
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  (k)
  
  
  
  Table 5
  
  
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  
  
  
  
  
  
  
  
  
  
  
  A1
  
  
  A
  
  
  A
  
  
  A
  
  
  B
  
  
  B
  
  
  A
  
  
  B
  
  
  B
  
  
  B
  
  
  A
  
  
  B
  
  
  B
  
  
  A
  
  
  B
  
  
  B
  
  
  B
  
  
  B
  
  
  
  
  
  
  
  
  
  
  E1
  
  
  
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  
  
  
  
  
  
  
  
  A2
  
  
  
  
  
  A
  
  
  A
  
  
  A
  
  
  A
  
  
  B
  
  
  A
  
  
  A
  
  
  B
  
  
  A
  
  
  B
  
  
  B
  
  
  A
  
  
  B
  
  
  B
  
  
  A
  
  
  B
  
  
  A
  
  
  
  
  
  
  
  E2
  
  
  
  
  
  
  
  
  1
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  
  
  
  
  
  SS1
  
  
  
  
  
  
  
  
  S0
  
  
  S2
  
  
  S4
  
  
  S4
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  S3
  
  
  S1
  
  
  S2
  
  
  S3
  
  
  S1
  
  
  S2
  
  
  S3
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  
  
  SS2
  
  
  
  
  
  
  
  
  
  
  
  S0
  
  
  S2
  
  
  S3
  
  
  S2
  
  
  S4
  
  
  S3
  
  
  S1
  
  
  S1
  
  
  S2
  
  
  S3
  
  
  S1
  
  
  S1
  
  
  S2
  
  
  S3
  
  
  S1
  
  
  S2
  
  
  S3
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  Table 6
  
  
  
  Из приведенных примеров и Утверждений 1 и 2 можно вывести следствие: если последовательность автоматов состоит из m компонентов, то они представляют собой КАМСИ-композицию ч-порядка, равного
  
   μ= μ(1)... +.. μ(i)...+... μ(m); (i:=1,m) Форм. 8 .
  
  Алгоритм построения КАМСИ-композиции
  
  Выше, в Table 5 показан процесс последовательного кодирования и декодирования двух последовательно включенных КАМСИ А1 и А2. Рассмотрим теперь способ построения автомата, эквивалентного последовательному включению двух автоматов.
  
  Алгоритм построения КАМСИ-композиции из компонентов КАМСИ рассмотрим на примере композиции двух автоматов.
  
  Пример 3
  
  Пусть заданы две КАМСИ и (см. Table 7(а) и (b)). Следует построить таблицу переходов автомата Σ, эквивалентного последовательному соединению КАМСИ .
  
  
  
  
  
  
  
  
  
  
  
  P,E1
  
  P=0
  
  
  P=1
  
  A
  
  
  B,0
  
  
  A,0
  
  B
  
  
  A,1
  
  
  B,1
  
  (a)
  
  
  
  
  
  Е1,E2
  
  P=0
  
  
  P=1
  
  A
  
  
  A,1
  
  
  B,1
  
  B
  
  
  B,0
  
  
  A,0
  
  (b)
  
  
  
  
  
  
  
  
  
  
  Σ
  
  
  P,E2
  
  P=0
  
  
  P=1
  
  1
  
  
  2
  
  
  3
  
  AA
  
  
  BA,1
  
  
  AA,1
  
  AB
  
  
  BB,0
  
  
  AB,0
  
  BA
  
  
  AB,1
  
  
  BB,1
  
  BB
  
  
  AA,0
  
  
  BA,0
  
  (c)
  
  
  
  Σ
  
  
  P,E2
  
  P=0
  
  
  P=1
  
  A
  
  
  C,1
  
  
  A,1
  
  B
  
  
  D,0
  
  
  B,0
  
  C
  
  
  B,1
  
  
  D,1
  
  D
  
  
  A,0
  
  
  C,0
  
  (d)
  
  
  
  
  
  
  
  
  
  Table 7
  
  
  
  P
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  
  
  
  
  
  
  
  
  
  (a)
  
  Σ
  
  
  A
  
  
  A
  
  
  A
  
  
  C
  
  
  D
  
  
  A
  
  
  C
  
  
  D
  
  
  C
  
  
  B
  
  
  D
  
  
  C
  
  
  B
  
  
  D
  
  
  C
  
  
  D
  
  
  C
  
  
  
  
  
  
  
  
  (b)
  
  
  
  
  
  
  
  1
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  
  
  
  
  
  
  (c)
  
  SS2
  
  
  
  
  
  S0
  
  
  S2
  
  
  S4
  
  
  S4
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  S3
  
  
  S1
  
  
  S2
  
  
  S3
  
  
  S1
  
  
  S2
  
  
  S3
  
  
  
  
  
  (d)
  
  
  
  
  
  
  
  
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  
  
  
  (e)
  
  SS1
  
  
  
  
  
  
  
  
  S0
  
  
  S1
  
  
  S2
  
  
  S3
  
  
  S1
  
  
  S1
  
  
  S2
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  S4
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  S4
  
  
  S3
  
  
  S2
  
  
  (f)
  
  
  
  
  
  
  
  
  
  
  
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  (g)
  
  Table 8
  
  Выполним следующую последовательность операций:
  
   1. построить таблицу переходов, содержащую 2х2=4 ([33]) строки;
   2. в первом столбце вписать все сочетания по два состояний КАМСИ и (первым стоит обозначение состояния , а вторым - );
   3. на пересечении АА (см. Table 7(с)) и столбца Р=0 записать:
   1. символ В (переход при Р=0 в КАМСИ из А в В, Е1=0);
   2. символ А (переход при Е1=0 в КАМСИ из А в А, Е2=1);
   3. через запятую записать значение Е2 равное 1; Аналогично заполнить остальные клетки столбцов 2 и 3.
   4. построить Table 7(d). Для этого АА из Table 7(с) заменить: АА на А, АВ на В, ВА на С и ВВ на D ([34]).
  
  Приведенный пример показывает, что если число компонентов КАМСИ в композиции равно m, таблица переходов i-го автомата имеет состояний, то общее число N состояний композиции равно: N=n1...٠ni...٠nm;.
  
  Примеры на стр. 45 и 48 позволяют сформулировать следующее утверждение:
  
  Утверждение 2: 'Последовательное соединение m компонентов КАМСИ эквивалентно КАМСИ-композиции, которая имеет ч-порядок, равный
  
  μ= μ(1)... +.. μ(i)...+... μ(m); (i:=1,m)
  
  и таблицу переходов с N=n1...٠ni...٠nm; состояниями'.
  
  Доказательство этого Утверждения можно провести по индукции, если считать, что примеры на стр. 45 и 48 позволяют доказать его для m=2. Далее, можно продолжить доказательство, увеличивая m на единицу.
  
  Утверждение 2 позволяет сделать выводы, о том, что не всякая КАМСИ является КАМСИ-композицией, а только та, которая может быть представлена последовательностью компонент КАМСИ, отвечающих приведенному Утверждению.
  Ну, и ... что?
  
  Мы показали, что на базе КАМСИ можно построить однонаправленную функцию без секрета.
  
  Это объясняет, почему КАМСИ до сих пор не нашли применения в криптографии.
  
  Ну, и что?
  
  Существует ли возможность построить на базе КАМСИ однонаправленную функцию с секретом?
  
  Рассмотрим, обладает ли КАМСИ-композиция свойствами, которые позволяют построить однонаправленную функцию с секретом? ([35])
  
  Обсудим два способа построения инвертора КАМСИ-композиции:
  
  1. Первый способ, описан в 14 разделе работы Цви Кохави 'Минимальная инверсная машина' (см. здесь, стр.114), назовем его непосредственный способ инвертирования. В соответствии с 'Утверждение 2' (стр. 51) и сложность инвертирования такой КАМСИ-коипозиции может быть вычислена по формуле:
  
  ,
  
  где m - число КАМСИ-компонент,
  
   - ч-порядок i-ой КАМСИ-компоненты.
  
  Если принять, что у всех компонентов ч-порядки одинаковые, то сложность непосредственного инвертирования равна
  
  .
  
  Эта формула получена на основании оценок, сделанных в разделе.
  
  Таким образом, сложность построения КАМСИ-композиции (кодера, в соответствии с 'Утверждение 2', стр. 51) зависит от числа состояний , в то время, как сложность инвертирования КАМСИ-композиции (то есть, построение инвертора) равна
  
  не трудно показать, что это возможно только при .
  
  Если принять, что все компоненты имеют одинаковые параметры, то
  
  и сложность решения обратной задачи (инвертирование КАМСИ-композиции) больше сложности решения прямой задачи (создание КАМСИ-композиции) в
  
   раз.
  
  Если принять, что , то
  
   раз.
  
  Мы показали, что непосредственный способ инвертирования КАМСИ-композиции, как и любой КАМСИ, позволяет построить однонаправленную функцию, но так как сложность инвертирования одинаковая для всех, эта однонаправленная функция без 'секрета'.
  
  2. Второй способ инвертирования, назовем его покомпонентным, заключается в том, что инверсию КАМСИ-композиции можно представить, как последовательное соединение инверсий КАМСИ-компонент (см. Table 5 и Table 6 стр. 48). Если принять, что сложность инвертирования i-ой КАМСИ-компоненты равна , то сложность покомпонентного инвертирования m компонентов равна . Если у всех компонентов ч-порядки одинаковые, то сложность покомпонентного инвертирования равна .
  
  Отсюда, при принятых допущениях о равенстве параметров всех КАМСИ-компонентов, сложность непосредственного инвертирования превосходит покомпонентное инвертирование в
  
  раз.
  
  Таким образом, знание набора компонентов и последовательности их взаимодействия в КАМСИ-композиции позволяет упростить процесс инвертирования (то есть легитимного построения декодера) в раз.
  
  Это дает возможность построить на базе КАМСИ-композиции однонаправленную функцию с секретом.
  
  'Секрет' заключается в том, что тот, кто сгенерировал КАМСИ-компоненты и КАМСИ-композицию получает возможность упростить в раз построение инвертора кодера.
  
  Далее мы будем сравнивать различные величины, используя числовые значения известных, так называемых Больших чисел (см. . Table 9).
  
  
  
  Физический аналог
  
  
  Число
  
  Время до следующего оледенения
  
  
  14000 (~214)
  
  Время до превращения Солнца в сверхновую звезду
  
  
  109 (230)
  
  Возраст планеты
  
  
  109 (230)
  
  Возраст Вселенной
  
  
  1010(234) лет
  
  Число атомов планеты
  
  
  1051 (2170)
  
  Число атомов Солнца
  
  
  1057 (2190)
  
  Число атомов галактики
  
  
  1067 (2223)
  
  Число атомов Вселенной
  
  
  1077 (2280)
  
  Объем Вселенной
  
  
  1084 (2280) sm3
  
  
  
  Table 9 Большие числа
  
  
  
  В Table 10 приводятся значения Ω(m,μ(m)) в зависимости от m, изменяющегося в диапазоне 1 .. 7 и μ(m) - в диапазоне 2 .. 5. Из этой таблицы видно, что уже при μ(10) =5 сложность инвертирования КАМСИ-композиции при покомпонентном инвертировании может быть уменьшена в Ώ(7,3)≈1018 раз.
  
  В этом случае μ=mμ(7) =7٠5=35, и, в то время, как сложность непосредственного инвертирования равна 270 ≈1021 (сравните с числами в Table 9, строка 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 10
  
  Полученные оценки показывают, что проблема взлома криптографической системы на базе КАМСИ-композиции (то есть инвертирования кодера) сводится к проблеме декомпозиции кодера.
  
  Это позволяет провести аналогию проблемы декомпозиции с проблемой факторизации с той разницей, что, если при факторизации порядок сомножителей в произведении не играет роли, то для КАМСИ-композиции важен не только состав, но и взаимное расположение компонентов.
  
  Собственно, из приведенного видно, каким может быть асимметричный алгоритм на базе КАМСИ.
  
  Для этого следует:
  
  1. Выбрать множество КАМСИ-компонент;
  
  2. Построить m-позиционный кортеж, расположив выбранные в п.1 КАМСИ-компоненты на m позициях (допустимо с повторениями);
  
  3. Построить КАМСИ-композицию Σ(m), которая является открытым ключем; Разослать всем заинтересованным абонентам открытый ключ Σ(m) по незащищенному информационному каналу.
  
  4. Построить инверсии КАМСИ-компонентов и создать из них последовательность, в которой компоненты расположены в порядке, обратном порядку КАМСИ-композиции. Это секретный ключ Ξ(m), который хранится у получателя информации.
  
  Рассмотрим, каким может быть, в первом приближении криптографический протокол.
  
  " Допустим, что абонент В сгенерировал Σ(m) и Ξ(m) и разослал всем абонентам информационной сети открытый ключ Σ(m). У абонента В остается секретный ключ Ξ(m).
  
  " Допустим, абоненту А необходимо послать абоненту В конфиденциальную информацию Р. Для этого:
  
  A. Абонент А с помощью Σ(m) кодирует информацию Р, получая закодированную информацию Е и передает ее абоненту В по незащищенному каналу.
  
  B. Абонент В принимает информацию Е, декодирует ее с помощью секретного ключа Ξ(m) и получает информацию Р.
  
  Обратим внимание, что если открытый ключ Σ(m), для обеспечения информационного обмена, непременно распространяется любым способом, в том числе, по незащищенным информационным каналам, то для Ξ(m), за все время обмена информацией не возникает необходимость передавать его, либо сообщать его кому бы то ни было.
  
  Вроде бы, решение задачи инвертирования кодера нам удалось упростить. Однако, как это видно из 'Утверждение 1' (см. стр. 45), КАМСИ-композиция может быть получена из композиции КАМСИ-компонентов. То есть, задача построения КАМСИ остается, но понижается сложность ее решения.
  
  Таким образом, чтобы асимметричный алгоритм на базе КАМСИ был эффективным, необходимо решить следующие проблемы:
  
   I. Разработать метод построения КАМСИ-компонентов, определив какими свойствами должна обладать КАМСИ-компонента. В этой связи вводится понятие КАМСИ-примитива.
  
   II. Разработать метод оптимальной размерности m-позиционного кортежа. В этой связи вводится понятие библиотеки КАМСИ-примитивов.
  
  
  Основная концепция алгоритма построения криптографической КАМСИ.
  
  В предыдущих разделах было показано, что сложность непосредственного инвертирования КАМСИ соизмерима с .
  
  Было показано, что при достаточно больших значениях ч непосредственное инвертирование КАМСИ-композиции становится практически не выполнимым.
  
  Как следует из описания криптографического алгоритма, КАМСИ-композиция, доступна всем в качестве открытого ключа. Это позволяет недобросовестному участнику обмена информацией проводить различные эксперименты с ней. Как ни парадоксально это выглядит, но знание таблицы переходов кодера и возможность экспериментального кодирования известного текста мало способствует получению информации о ч-порядке кодера по полученному закодированному тексту. Этот код будет иметь длину, на (где - максимально возможное значение ч-порядка, а R - число дополнительных битов, такое, чтобы имело размер порядка 100 или больше).
  
  Значение может быть известно всем.
  
  Какую же информацию недобросовестный абонент может получить из таблицы переходов кодера? ([36])
  
  " Во-первых, число состояний таблицы переходов, равное N.
  
  " Во-вторых, он может разложить N на сомножители, для того, чтобы определить предполагаемое значение m - количество КАМСИ-компонентов. Как показывает Утверждение 2, m может удовлетворять формулам:
  
  Форм. 9 ,
  
  где - число состояний i-ой компоненты и число компонент соответственно,
  
  и:
  
  Форм. 10 ,
  
  где - ч-порядок i-ой компоненты.
  
  
  
  "
  
  Форм. 9 и Форм. 10 представляют собой систему из двух диофантовых ([37]) уравнений от (2 х m) неизвестных (одно нелинейное уравнение от переменных , и другое - линейное от переменных ). Совместное решение этих уравнений дает один из вариантов набора компонентов КАМСИ-композиции. Проблема усложняется тем, что m не известно, так как представляет собой часть секретного ключа.
  
  Таким образом, КАМСИ-композиция дополнительно, в качестве альтернативы к описанной Цви Кохави (см. стр. 114) процедуре построения инвертора, позволяет применить процедуру, которая состоит из нескольких этапов:
  
  1. совместное решение описанной выше системы диофантовых уравнений, в результате которого будет получено значение m и один из вариантов набора компонентов КАМСИ-композиции.
  
  2. определение порядка расположения найденных компонентов при декодировании.
  
  3. инвертирование компонентов КАМСИ-композиции.
  
  
  
  В следующих разделах будет оценена сложность выполнения операций декодирования для недобросовестного([38]) участника процесса обмена информацией и сравнение ее с легитимным декодированием.
  Основная идея
  
  Допустим что:
  
   * существует КАМСИ-композиция, которая состоит из m компонент,
   * таблица переходов каждой из компонент имеет одинаковый ч-порядок равный и одинаковое число состояний таблиц переходов .
  
  " Это значит, что
  
  Форм. 9 и Форм. 10 примут вид:
  
  Форм. 11 и
  
  Форм. 12
  
  Сложность инвертирования КАМСИ-композиции при этом равна , в то время, как сложность инвертирования m компонент -.
  
  Выше было показано, что сложность инвертирования КАМСИ-композиции больше сложности инвертирования m ее компонент в
  
  Форм. 13 раз.
  
  Например, для m=8 и ч-порядок равен ч=16, и раз.
  
  При этом, сложность инвертирования этой КАМСИ-композиции равна , а сложность инвертирования всех восьми компонентов - операций.
  
  Сложность инвертирования КАМСИ-композиции, равная , не такая уж большая величина. И выбран этот пример для демонстрации возможностей КАМСИ.
  
  Тем не менее, этот пример показывает, что если принять, в качестве открытого ключа, КАМСИ-композицию, а в качестве секретного ключа - совокупность компонентов композиции, инверторы которых, при декодировании, применяются последовательно, но в обратном порядке, то сложность построения секретного ключа, в этом случае, в раз меньше сложности инвертирования открытого ключа.
  
  Таким образом, показано, что на базе КАМСИ можно построить однонаправленную функцию с 'секретом'.
  Криптографический алгоритм на базе КАМСИ-композиции
  
  Продолжим рассмотрение, начатое в предыдущем разделе, и примем, что для каждого компонента а число таких компонентов равно m=12. Это значит, что такая композиция имеет задержку ч=24 и сложность непосредственного инвертирования в
  
   раз
  
   превосходит сложность покомпонентного инвертирования, а число состояний таблицы переходов КАМСИ-композиции равно . При этом непосредственное инвертирование КАМСИ-композиции требует выполнения операций, в то время, как при построения инверторов для соответствующей совокупности m=12 компонентов - операции. Рассмотренные примеры позволяют сделать вывод:
  
  Что совокупность компонентов может облегчить инвертирование (служить секретом), если декомпозиция КАМСИ-композиции сложнее, чем построение ее инвертора (иначе, более целесообразно инвертировать кодер).
  
  Это верно, если доказать, что:
  
  " Мощность множества компонентов такова, что перебор множества возможных компонентов более сложен, чем построение инвертора КАМСИ-композиции; и
  
  " Процесс генерации компонентов КАМСИ-композиции прост настолько, что позволяет воспроизвести его на достаточно простом локальном устройстве.
  
  Начнем с рассмотрения КАМСИ-компонент. Для этого ответим на вопрос:
  Какая КАМСИ наиболее подходит в качестве КАМСИ-компоненты?
  
  Вернемся к Форм. 11 и Форм. 12:
  
  Форм. 14 и .
  
  Первая из них позволяет определить число состояний таблицы переходов КАМСИ-композиции, а вторая - ее ч-порядок.
  
  Если N характеризует ресурсы памяти, необходимой для размещения таблицы переходов, то ч характеризует эффективность применения КАМСИ, то есть при равных , та КАМСИ более эффективна, у которой ч-порядок больше.
  
  
  
  (А)
  
  
  (Б)
  
  a1
  
  
  P,E
  
  P=0
  
  
  P=1
  
  A
  
  
  A,0
  
  
  E,0
  
  B
  
  
  D,0
  
  
  F,0
  
  C
  
  
  F,1
  
  
  C,1
  
  D
  
  
  B,1
  
  
  E,1
  
  E
  
  
  C,0
  
  
  B,0
  
  F
  
  
  A,1
  
  
  D,1
  
  
  
  
  
  P,E1
  
  P=0
  
  
  P=1
  
  A
  
  
  B,0
  
  
  A,0
  
  B
  
  
  A,1
  
  
  B,1
  
  n =6, ч=7
  
  
  n =2, ч=2
  
  Table 11
  
  Пример 4
  
  В Table 11 показаны две КАМСИ с разными параметрами. Так, для КАМСИ с (см. столбец Б)) если m=12, то ч-порядок КАМСИ-композиции равен ч=24, а раз, и число состояний таблицы переходов КАМСИ-композиции равно .
  
  Если же взять КАМСИ-компонент, показанный в столбце (А), то для получения КАМСИ-композиции, близкой к полученной выше, следует принять: m=4, , тогда ч=28([39]), , и .
  
  Обратите внимание, что в первом случае число состояний равно , а во втором случае: , не смотря на то, что во втором случае ч=28.
  
  КАМСИ-компоненты, приведенные в Table 11 обе обладают одним интересным свойством, которое будет видно после обсуждения следующего Утверждения:
  
  Утверждение 3. Если существует КАМСИ, у которой , то она не КАМСИ-композиция (то есть, ее нельзя разложить на компоненты).
  
  Допустим противное, то есть что существует КАМСИ-композиция, у которой . Это значит, что (см. Форм. 14, стр. 59). Из этого вытекает, что
  
  Форм. 15 .
  
  Не трудно показать, что это условие выполнимо только при и m=2. Один из примеров такой КАМСИ показан в Table 11(Б).([40])
  
   Утверждение 3 можно считать доказанным.
  
  КАМСИ, отвечающие этому утверждению (по аналогии с понятием простых чисел) ([41]) будем называть примитивами.
  
  Приведенное выше показывает, что КАМСИ-композицию наиболее целесообразно строить на базе примитивов.
  
  Что же такое примитивы?
  
  Достаточно ли их количество, чтобы строить на их основе секретные криптографические ключи ([42])?
  
  Это обстоятельство очень важно. Действительно, если окажется, что примитивы находятся в малом количестве, то при определении кортежа ([43]) композиции (числа и порядка расположения примитивов в композиции) пространство перебора будет настолько ограниченным, что будет практически реализуемым.
  
  
  КАМСИ-композиция и КАМСИ-примитив
  
  Введем несколько определений.
  
  Допустим, существует два примитива и , где i и j - i -ый и j -ый примитивы типа , а - мощность множества примитивов к-го типа.
  
  Не трудно показать, что две КАМСИ-композиции, каждая из которых состоит из одинаковых примитивов и , и отличаются только порядком расположения примитивов - имеют разные таблицы переходов. Одну из этих КАМСИ-композиций можно обозначить, например, и другую - , где нижние индексы показывают позицию в КАМСИ-композиции. В математике такие последовательности называются кортежами.
  
  В общем виде, m-позиционные кортежи у которых одинаковый набор типов КАМСИ-композиции можно записать в виде:
  
  Форм. 16
  
  где:
  
  - примитив типа q, который расположен в i-ой позиции кортежа;
  
   q - один из множества примитивов типа q.([44])
  
  Общее число m-позиционных кортежей, которые имеют одни и те же примитивы и отличаются только порядком их расположения равно ([45]):
  
  Форм. 17
  
  где:
  
   - множество примитивов типа w, один из которых расположен в t-ой позиции кортежа.
  
  Приступим к определению мощности множества примитивов.
  
  Введем определение.
  
  Два состояния А и В таблицы переходов, которые имеют вид
  
  где C и D - любые состояния таблицы переходов,
  
  будем называть взаимообратимыми. Взаимообратимые состояния имеют одинаковое заполнение в тестирующей таблице.
  
  Предварительно сформулируем несколько утверждений.
  
  Утверждение 4: Таблица переходов КАМСИ не содержит взаимообратимых состояний.
  
  Это утверждение вытекает из Theorem 14-1 цитированной выше книги Zvi Kohavi (стр. 510).
  
  Утверждение 5: 'Перестановка переходов в любой строке таблицы переходов КАМСИ сохраняет свойство КАМСИ и его тип (величину ч-задержки)'.
  
  Доказательство.
  
  Первая часть Утверждения вытекает из способа построения тестирующей таблицы (см. 'Switching and Finite Automata Theory', Zvi Kohavi), в которой каждой строке верхней половины тестирующей таблицы ставится упорядоченное сочетание названий состояний переходов в соответствующей строке таблицы переходов. Из этого следует, что перестановка переходов сохраняет свойство КАМСИ.
  
  Вторая часть Утверждения вытекает из того факта, что если верхняя часть тестирующей таблицы при перестановке переходов в одной строке таблицы не изменяется, то нижняя часть тестирующей таблицы также не изменяется, то есть, величина ч-задержки при перестановке переходов не изменяется.
  
  Как следует из способа построения тестирующей таблицы (с) (см. 'Switching and Finite Automata Theory', Zvi Kohavi), каждому из них соответствует одна и та же тестирующая таблица (с).
  
  
  
  
  
  
  
  
  
  P,E1
  
  P=0
  
  
  P=1
  
  A
  
  
  B,0
  
  
  A,0
  
  B
  
  
  A,1
  
  
  B,1
  
  (a)
  
  
  
  P,E1
  
  P=0
  
  
  P=1
  
  A
  
  
  A,0
  
  
  B,0
  
  B
  
  
  A,1
  
  
  B,1
  
  (b)
  
  
  
  
  
  
  
  Е1,Р
  
  Е1=0
  
  
  У1=1
  
  A
  
  
  AB
  
  
  
  
  B
  
  
  
  
  
  AB
  
  AB
  
  
  -
  
  
  -
  
  (c)
  
  μ=2
  
  
  
  Table 12
  
  
  
  Утверждение 6 : 'Инвертирование всех значений выходов автомата в таблице переходов КАМСИ сохраняет свойство КАМСИ и его тип'.
  
  Доказательство следует из того, что инвертирование всех значений равносильно перестановке столбцов P=0 и P=1 в тестирующей таблице, что не может изменить характеристики автомата.
  
  Например, в Error! Reference source not found. в столбцах (А) и (В) в строках 000 и 100 расположены таблицы переходов, полученные инвертированием значений выходов, соответственно. Другие строки таблицы получены последовательным применением операций, описанных в 'Error! Reference source not found.' и 'Error! Reference source not found.'.
  
  Таким образом, в Error! Reference source not found. (столбце А) приведены все варианты таблицы переходов 000, к которой применена операция 'Error! Reference source not found.', а в столбце В - операция 'Error! Reference source not found.'.
  
  
  
  
  
  Столбец А
  
  
  
  
  
  Столбец В
  
  
  
  P,E1
  
  P=0
  
  
  P=1
  
  A
  
  
  B,0
  
  
  A,0
  
  B
  
  
  A,1
  
  
  B,1
  
  
  
  
  
  
  
  
  P,E1
  
  P=0
  
  
  P=1
  
  A
  
  
  B,1
  
  
  A,1
  
  B
  
  
  A,0
  
  
  B,0
  
  000
  
  
  
  
  
  100
  
  
  
  P,E1
  
  P=0
  
  
  P=1
  
  A
  
  
  A,0
  
  
  B,0
  
  B
  
  
  A,1
  
  
  B,1
  
  
  
  
  
  
  
  
  P,E1
  
  P=0
  
  
  P=1
  
  A
  
  
  A,1
  
  
  B,1
  
  B
  
  
  A,0
  
  
  B,0
  
  001
  
  
  
  
  
  101
  
  
  
  P,E1
  
  P=0
  
  
  P=1
  
  A
  
  
  B,0
  
  
  A,0
  
  B
  
  
  B,1
  
  
  A,1
  
  
  
  
  
  
  
  
  P,E1
  
  P=0
  
  
  P=1
  
  A
  
  
  B,1
  
  
  A,1
  
  B
  
  
  B,0
  
  
  A,0
  
  010
  
  
  
  
  
  110
  
  
  
  P,E1
  
  P=0
  
  
  P=1
  
  A
  
  
  A,0
  
  
  B,0
  
  B
  
  
  B,1
  
  
  A,1
  
  
  
  
  
  
  
  
  P,E1
  
  P=0
  
  
  P=1
  
  A
  
  
  A,1
  
  
  B,1
  
  B
  
  
  B,0
  
  
  A,0
  
  011
  
  
  
  
  
  111
  
  
  
  Table 13
  
  
  
  Не трудно показать, что общее число примитивов при этом равно
  
  Форм. 18
  
  .
  
  где - число состояний таблицы переходов примитива.
  
  Полученная оценка справедлива только для примитивов. Действительно, если в таблице переходов есть взамнообратимые состояния А и В такие, что , то после перестановки переходов, например, в состоянии А мы получим эквивалентные состояния А и В. После 'объединения' эквивалентных состояний, мы получим таблицу переходов с числом состояний, равным . Не трудно видеть, что - не простое число, то есть полученная таблица переходов - не примитив. Если это все еще КАМСИ - то скорее всего - композиция примитивов (а может быть - и нет). В любом случае - применение такой таблицы переходов требует трудоемких проверок, что уничтожает эффект применения примитивов.
  
  Форм. 18 позволяет преобразовать Error! Reference source not found. к виду:
  
  Форм. 19
  
  если принять, что m-кортеж состоит из примитивов одинакового типа, то эта формула примет вид:
  
  Форм. 20
  
  Так, для кортежа с числом позиций m=12, и общее число кортежей равно , а для m=4 и (обратите внимание что обе эти цифры соизмеримы с возрастом Вселенной).
  
  Полученные цифры показывают, что даже если использовать только примитив , , то и этого достаточно, чтобы обеспечить всех желающих сгенерировать пару разных ключей любое количество раз в течение всего времени существования нашей цивилизации без опасности, что результаты генерации повторятся. Кроме того, ничто не противоречит утверждению, что число различных типов примитивов бесконечно.
  
  Докажем еще одно не тривиальное утверждение.
  
  Утверждение 7. Если существует две композиции
  
  где:
  
   - четыре разных примитива,
  
   - композиция примитивов и , которая выполняет операцию ,
  
   - множество примитивов y-го типа, то есть с одинаковым числом состояний и величиной ч,
  
  и (где - закодированный композициями , соответственно, текст Р), то и .
  
  Доказательство. Допустим, что , то есть . Примем, что в таблицах переходов примитивов и :
  
  Форм. 21
  
  где
  
  фрагмент соответствует переходу примитива из состояния S в состояние Q, если на его входе P=0. При этом на выходе устанавливается значение t (ноль или единица).
  
  Принятое выше допущение является условием эквивалентности композиций и. Другими словами, при обходе всех состояний таблиц переходов и на их выходах появляется одинаковая последовательность битов.
  
  Допустим, что и эквивалентны, а для и существует состояние S, которое имеет вид Форм. 21 (см. Error! Reference source not found., стр. 63).
  
  Допустим, на входы и подан поток битов, который перевел оба автомата в состояние S. Из Форм. 21 следует, что при очередном изменении на входах и один из автоматов перейдет в состояние Q, а другой - в F (это зависит от значения Р). Но так как Q не эквивалентно F, то при продолжении эксперимента на выходах и появятся разные последовательности битов.
  
  Не трудно показать, что ситуация не изменится, если операция, описанная в 'Error! Reference source not found.' будет применена к разному числу примитивов композиций и.
  
  Из этого следует, что имея набор двух-трех типов примитивов, можно организовать криптографический алгоритм на базе КАМСИ, при котором:
  
   * Отпадает необходимость строить КАМСИ, применяя описанные выше тестирующие процедуры;
   * Отпадает необходимость обеспечивать секретность принятому набору типов примитивов.
  
  Рассмотрим далее процесс формирования кортежей.
  
  Двоичная запись чисел, поставленных в соответствие примитиву в Error! Reference source not found., показывает способ, как из компоненты с номером 000 (назовем ее базовой ([46])) получить компоненту, соответствующую заданному числу.
  
  На это указывает взаимное расположение в этом числе единиц и нулей:
  
  " Единица в первом (слева) разряде показывает, что в базовой модели следует инвертировать значения выходов во всех состояниях (то есть, применить операцию из 'Error! Reference source not found.');
  
  " Для остальных разрядов заданного двоичного числа выполнить операцию, описанную в 'Error! Reference source not found.' для всех состояний базовой модели, номера которых совпадают с номерами позиций, в которых располагаются единицы.
  
  Например, для компонентов типа (2,2) кортеж 5370061 соответствует КАМСИ-композиции (m=7, откуда ч=14), в которой примитивы расположены в порядке 101, 011, 111, 000, 000, 110, 001 (см. Error! Reference source not found.).
  
  Приведенные утверждения позволяют построить кортеж для КАМСИ-композиции. Для этого достаточно выбрать (можно с повторениями) m компонентов из таблицы, подобной Error! Reference source not found..
  
  Не трудно показать, что сложность перебора вариантов больше сложности инвертирования кодера в
  
   раз.
  
  Если принять, что , то
  
  .
  
  
  
  Следовательно, для взлома криптографического алгоритма более целесообразно непосредственно инвертировать кодер, чем строить его декомпозицию в виде кортежа КАМСИ-композиции.
  
  Однако, эти оценки были получены при допущении, что известен ч-порядок кодера.
  
  В действительности, криптоаналитику известны:
  
   * Таблица переходов кодера; и, иногда,
   * Множество всех примитивов.
  
  ч-порядок же кодера не известен.
  Оценка количества операций при анализе асинхронного криптографического алгоритма на базе КАМСИ.
  
  Примем, что при анализе асинхронного криптографического алгоритма на базе КАМСИ, криптоаналитику известна таблица переходов кодера, содержащая N состояний и библиотека ξ-компонентов. Рассмотрим две ситуации:
  
   1. криптоаналитик не имеет возможности манипулировать входным текстом и контролирует только выходной текст;
   2. криптоаналитик манипулирует входным текстом и контролирует соответствующий ему выходной текст (шифр).
  
  В обоих случаях целью криптоанализа является либо построение декодера, либо определение исходного текста, либо то и другое вместе, но в обоих случаях, конечная цель - получение возможности контролировать кодируемые тексты.
  
  Одна из задач, которую приходится решать при криптоанализе - это:
  
  " определение μ-порядка кодера; либо,
  
  " определение ξ-кортежа;
  
  Оценим сложность выполнения перечисленных операций.
  Оценка сложности построения инверсного автомата.
  
  В последующих двух разделах приведен процесс оценки сложности построения инверсного автомата.
  Оценка сложности определения μ-порядка кодера
  
  
  
  Определим сложность построения тестирующей таблицы и тестирующего графа.
  Оценка сложности построения тестирующей таблицы.
  
  В Error! Reference source not found. (см. стр. Error! Bookmark not defined.) показан процесс тестирования. В Error! Reference source not found.(а) показана таблица переходов, которую следует проверить, во-первых, на информационную сохраняемость (то есть, является ли она КАМСИ) и, если таблица отвечает этим условиям, то, во-вторых, определить ее ч-порядок.
  
  Error! Reference source not found.(b) - это тестирующая таблица, которая состоит из двух половин
  
  a) верхняя половина, которая состоит из N строк, и
  
  b) нижняя половина, количество строк в которой содержит число строк, не превышающее число сочетаний из N по 2, равное ;
  
  c) учитывая то, что для заполнения каждой строки нижней части таблицы требуется 4 операции, общее число операций при заполнении таблицы, равно .
  
  Например, для КАМСИ Error! Reference source not found.(a) приведены параметры, характеризующие сложность определения μ-порядка, который в рассматриваемом случае равен 7.
  
  
  
  
  
  
  
  
  
  a1
  
  
  P,E
  
  P=0
  
  
  P=1
  
  A
  
  
  A,0
  
  
  E,0
  
  B
  
  
  D,0
  
  
  F,0
  
  C
  
  
  F,1
  
  
  C,1
  
  D
  
  
  B,1
  
  
  E,1
  
  E
  
  
  C,0
  
  
  B,0
  
  F
  
  
  A,1
  
  
  D,1
  
  
  
  N=6
  
  (a)
  
  
  
  
  
  
  a1
  
  
  P,E
  
  P=0
  
  
  P=1
  
  A
  
  
  AE
  
  
  
  
  B
  
  
  DF
  
  
  
  
  C
  
  
  
  
  
  CF
  
  D
  
  
  
  
  
  BE
  
  E
  
  
  BC
  
  
  
  
  F
  
  
  
  
  
  AD
  
  AE
  
  
  (AB)(AC)
  
  (DE)(EF)
  
  
  
  
  DF
  
  
  
  
  
  (AB)(BD)
  
  (AE)(DE)
  
  CF
  
  
  
  
  
  (AC)(CD)
  
  (AF)(DF)
  
  BE
  
  
  (BD)(CD)
  
  (BF)(CF)
  
  
  
  
  BC
  
  
  
  
  
  
  
  AD
  
  
  
  
  
  
  
  AB
  
  
  (AD)(AF)
  
  (DE)(EF)
  
  
  
  
  AC
  
  
  
  
  
  
  
  DE
  
  
  
  
  
  
  
  EF
  
  
  
  
  
  
  
  BD
  
  
  
  
  
  
  
  CD
  
  
  
  
  
  (BC)(CE)
  
  (BF)(EF)
  
  AF
  
  
  
  
  
  
  
  BF
  
  
  
  
  
  
  
  CE
  
  
  
  
  
  
  
  
  
  (b)
  
  
  
  
  
  
  
  
  
  
  (c)
  
  l=5
  
  ч=l+2=7
  
  
  
  Table 14
  
  
  
  
  
  
  
  
  Оценка сложности построения таблицы μ-кортежей
  
  
  
  PS
  
  
  NS,z
  
  x=0
  
  
  x=1
  
  A
  
  
  C,0
  
  
  D,1
  
  B
  
  
  D,0
  
  
  С,1
  
  C
  
  
  А,0
  
  
  B,0
  
  D
  
  
  C,1
  
  
  D,1
  
  (a)
  
  
  
  
  A
  
  
  B
  
  
  C
  
  
  D
  
  00
  
  
  +
  
  
  
  
  
  +
  
  
  
  
  01
  
  
  
  
  
  +
  
  
  +
  
  
  
  
  10
  
  
  
  
  
  +
  
  
  
  
  
  +
  
  11
  
  
  +
  
  
  
  
  
  
  
  
  +
  
  (b)
  
  
  
  
  
  
  
  
  
  PS
  
  
  NS,x
  
  
  
  
  z=0
  
  
  z=1
  
  S0
  
  
  (A,0,0)
  
  
  (C, 0,0),0
  
  
  (C, 0,1),0
  
  S1
  
  
  (A,0,0)
  
  
  (C,0,0),0
  
  
  (C,0,1),0
  
  S2
  
  
  (A,1,1)
  
  
  (D,1,0),1
  
  
  (D,1,1),1
  
  S3
  
  
  (B,0,1)
  
  
  (D,1,0),0
  
  
  (D,1,1),0
  
  S4
  
  
  (B,1,0)
  
  
  (C,0,0),1
  
  
  (C,0,1),1
  
  S5
  
  
  (C,0,0)
  
  
  (A,0,0),0
  
  
  (B,0,1),1
  
  S6
  
  
  (C,0,1)
  
  
  (B,1,0),1
  
  
  (A,1,1),0
  
  S1
  
  
  (D,1,0)
  
  
  (C,0,0),0
  
  
  (C,0,1),0
  
  S2
  
  
  (D,1,1)
  
  
  (D,1,0),1
  
  
  (D,1,1),1
  
  (c)
  
  
  
  
  
  
  
  
  PS
  
  
  NS,x
  
  z=0
  
  
  z=1
  
  S0
  
  
  S5,0
  
  
  S6,0
  
  S1
  
  
  S5,0
  
  
  S6,0
  
  S2
  
  
  S1,1
  
  
  S2,1
  
  S3
  
  
  S1,0
  
  
  S2,0
  
  S4
  
  
  S5,1
  
  
  S6,1
  
  S5
  
  
  S1,0
  
  
  S3,1
  
  S6
  
  
  S4,1
  
  
  S2,0
  
  (d)
  
  
  
  
  
  X
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  
  
  
  
  
  Au
  
  
  A
  
  
  C
  
  
  A
  
  
  D
  
  
  C
  
  
  B
  
  
  C
  
  
  A
  
  
  C
  
  
  B
  
  
  C
  
  
  B
  
  
  D
  
  
  C
  
  
  
  
  
  
  
  
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  
  
  SS
  
  
  
  
  
  S0
  
  
  S5
  
  
  S1
  
  
  S6
  
  
  S2
  
  
  S1
  
  
  S6
  
  
  S4
  
  
  S5
  
  
  S1
  
  
  S6
  
  
  S4
  
  
  S5
  
  
  S3
  
  
  
  
  
  
  
  
  
  
  0
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  (e)
  
  
  
  
  
  Table 15
  
  
  
  
  
  
  
  Введем понятие μ-кортежа.
  
  μ-кортеж представляет собой последовательность значений на выходе последних μ переходов, первый из которых появляется при переходе из заданного состояния КАМСИ.
  
  Построим таблицу μ-кортежей, которая состоит из строк и N столбцов. Для заполнения клетки таблицы, которая расположена в jой строке и pго столбце следует проверить, существует ли переход из pго состояния, который порождает jой μ-кортеж на выходе кодирующего КАМСИ. Если кортеж существует, то соответствующую клетку необходимо отметить (в Error! Reference source not found.(b) клетка отмечена крестиком, см. стр. Error! Bookmark not defined.).
  
  Не трудно показать, что для заполнения одной клетки таблицы следует проверить μ переходов, и, учитывая, что общее число клеток равно , общее число операций, которые необходимо выполнить равно .
  
  
  
  
  
  Кратн.
  
  Композ.
  
  
  N
  
  
  
  
  μ
  
  
  
  
  
  
  a
  
  
  b
  
  
  c
  
  
  d
  
  
  e
  
  
  f
  
  
  h
  
  1
  
  
  5
  
  
  
  
  6
  
  
  
  
  
  
  2
  
  
  25
  
  
  
  
  12
  
  
  
  
  
  
  3
  
  
  125
  
  
  
  
  18
  
  
  
  
  
  
  4
  
  
  250
  
  
  
  
  24
  
  
  
  
  
  
  5
  
  
  1250
  
  
  
  
  30
  
  
  
  
  
  
  6
  
  
  6250
  
  
  
  
  36
  
  
  
  
  
  
  7
  
  
  31250
  
  
  
  
  42
  
  
  
  
  
  
  8
  
  
  156250
  
  
  
  
  48
  
  
  
  
  
  
  Table 16
  
  В Error! Reference source not found. в столбцах (d,e) показано, как изменяется сложность построения таблицы μ-кортежей (μ, ).
  
  Так как конечной целью построения таблицы μ-кортежей является построение таблицы переходов инверсного автомата, то оценим сложность построения таблицы переходов инверсного автомата. Число строк в такой таблице равно числу заполненных клеток в таблице μ-кортежей (см. выше). Не трудно показать, что оно соизмеримо с .
  
  Оценим сложность построения таблицы переходов для инверсного автомата:
  
  " заполнение трех столбцов таблицы переходов - операций (первый столбец - μ-плы ([47]), соответствующие состояниям, из которых выполняется переход; второй и третий столбцы - μ-плы, соответствующие состояниям, в которые может быть переход);
  
  " проверка μ-плов, второго и третьего столбца, находятся ли они в первом столбце, если нет, то замена их на другие. Общее число таких проверок ('каждый с каждым') .
  
  Общее число операций:
  
  Форм. 22 .
  
  В Error! Reference source not found.(h) показана сложность построения обратного автомата.
  
  Анализ этой таблицы позволяет сделать следующие выводы:
  
  " сложность построения инверсного автомата возрастает вместе с увеличением кратности композиции (размер m кортежа КАМСИ-композиции). Например, кодер, полученный композицией 6 КАМСИ с N=5, имеет таблицу переходов с N равным N=6250 состояний и сложность инвертирования такого кодера в то время, как легитимное построение декодера (шесть КАМСИ с N=5 и μ=6) равно . Это меньше сложности анализа кодера в раз.
  
  " Общее число ζ-кортежей размерностью m=6, μ=6 и N=5 равно , что делает практически не выполнимым процесс подбора нужного ζ-кортежа.
  
  " Время шифрования, с помощью таблицы переходов КАМСИ, не зависит от числа состояний таблицы переходов и определяется только временем выполнения одного перехода ([48]).
  
  " Время декодирования линейно зависит от числа элементов композиции - кодера (в рассмотренном примере скорость декодирования в шесть раз медленнее скорости кодирования - шесть, это число компонентов в КАМСИ-композиции).
  Какова же сложность построения КАМСИ-декодера?
  
  Выше было показано, что для КАМСИ применим один из способов инвертирования: непосредственный и метод декомпозиции.
  
  Для обоих этих методов выше были построены формулы для оценки сложности выполнения операций построения декодера и показано, что более просто применить метод непосредственного инвертирования.
  
  Все ли так просто?
  
  Обратимся к примеру КАМСИ-композиции, который мы рассматривали выше.
  
  Пример 5
  
  В Error! Reference source not found. показаны примитивы и , Σ - их КАМСИ-композиция и инверторы примитивов: для - SS1, а для - SS2.
  
  
  
  
  
  
  
  
  
  P,E1
  
  P=0
  
  
  P=1
  
  A
  
  
  B,0
  
  
  A,0
  
  B
  
  
  A,1
  
  
  B,1
  
  (a)
  
  
  
  
  
  Е1,E2
  
  P=0
  
  
  P=1
  
  C
  
  
  C,1
  
  
  D,1
  
  D
  
  
  D,0
  
  
  C,0
  
  (b)
  
  
  
  
  
  
  
  
  Σ
  
  
  P,E2
  
  P=0
  
  
  P=1
  
  1
  
  
  2
  
  
  3
  
  AC
  
  
  BC,1
  
  
  AC,1
  
  AD
  
  
  BD,0
  
  
  AD,0
  
  BC
  
  
  AD,1
  
  
  BD,1
  
  BD
  
  
  AC,0
  
  
  BC,0
  
  (c)
  
  
  
  Σ
  
  
  P,E2
  
  P=0
  
  
  P=1
  
  A
  
  
  C,1
  
  
  A,1
  
  B
  
  
  D,0
  
  
  B,0
  
  C
  
  
  B,1
  
  
  D,1
  
  D
  
  
  A,0
  
  
  C,0
  
  (d)
  
  
  
  
  
  
  
  
  
  
  SS1
  
  
  P,E
  
  E=0
  
  
  E=1
  
  S0
  
  
  S1,1
  
  
  S2,1
  
  S1
  
  
  S1,1
  
  
  S2,1
  
  S2
  
  
  S3,0
  
  
  S4,0
  
  S3
  
  
  S1,0
  
  
  S2,0
  
  S4
  
  
  S3,1
  
  
  S4,1
  
  (e)
  
  SS2
  
  
  P,E
  
  E=0
  
  
  E=1
  
  S0
  
  
  S1,0
  
  
  S2,0
  
  S1
  
  
  S1,0
  
  
  S2,0
  
  S2
  
  
  S3,1
  
  
  S4,1
  
  S3
  
  
  S1,1
  
  
  S2,1
  
  S4
  
  
  S3,0
  
  
  S4,0
  
  (f)
  
  
  
  
  
  
  
  (g)
  
  
  
  
  
  
  
  P
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  
  
  
  
  
  
  
  
  Σ
  
  
  A
  
  
  A
  
  
  A
  
  
  C
  
  
  B
  
  
  D
  
  
  C
  
  
  B
  
  
  B
  
  
  D
  
  
  C
  
  
  D
  
  
  A
  
  
  A
  
  
  C
  
  
  B
  
  
  
  
  
  
  
  E2
  
  
  
  
  
  1
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  
  
  
  
  
  SS2
  
  
  
  
  
  S0
  
  
  S2
  
  
  S4
  
  
  S4
  
  
  S4
  
  
  S3
  
  
  S1
  
  
  S2
  
  
  S3
  
  
  S1
  
  
  S1
  
  
  S2
  
  
  S3
  
  
  S2
  
  
  S4
  
  
  S4
  
  
  
  
  
  
  
  
  
  
  
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  
  
  SS1
  
  
  
  
  
  
  
  
  S0
  
  
  S1
  
  
  S2
  
  
  S3
  
  
  S1
  
  
  S1
  
  
  S2
  
  
  S3
  
  
  S2
  
  
  S4
  
  
  S3
  
  
  S1
  
  
  S2
  
  
  S4
  
  
  S4
  
  
  S3
  
  
  
  
  
  
  
  
  
  
  
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  (h)
  
  
  
  
  
  
  
  
  
  
  
  Table 17
  
  В Error! Reference source not found.(g) показана структура кодера КАМСИ-композиции, на вход которого подан поток битов Р, а на выходе получается шифр Е2, который передается по каналу связи.
  
  В Error! Reference source not found.(h) показан процесс кодирования композицией Σ потока битов Р в поток битов Е2 и декодирования его декодерами в порядке SS2=> SS1. Последняя строка Error! Reference source not found.(h) показывает, что декодированное сообщение получено с задержкой ч=4. Из этого можно сделать вывод, что Σ обладает задержкой ч=4.
  
  
  
  
  
  Σ
  
  
  P,E2
  
  P=0
  
  
  P=1
  
  1
  
  
  2
  
  
  3
  
  AC
  
  
  BC,1
  
  
  AC,1
  
  AD
  
  
  BD,0
  
  
  AD,0
  
  BC
  
  
  AD,1
  
  
  BD,1
  
  BD
  
  
  AC,0
  
  
  BC,0
  
  
  
  (a)
  
  
  
  Σ
  
  
  P,E2
  
  P=0
  
  
  P=1
  
  A
  
  
  C,1
  
  
  A,1
  
  B
  
  
  D,0
  
  
  B,0
  
  C
  
  
  B,1
  
  
  D,1
  
  D
  
  
  A,0
  
  
  C,0
  
  
  
  (b)
  
  
  
  
  
  
  Σ
  
  
  
  
  
  
  
  
  
  AC
  
  
  
  
  
  AC/BC
  
  AD
  
  
  AD/BD
  
  
  
  
  BC
  
  
  
  
  
  AD/BD
  
  BD
  
  
  AC/BC
  
  
  
  
  AC/BC
  
  
  
  
  
  (AC/AD)(AC/BD)
  
  (AD/BC)(BC/BD)
  
  AD/BD
  
  
  (AC/AD)(AC/BD)
  
  (AD/BC)(BC/BD)
  
  
  
  
  AC/AD
  
  
  
  
  
  
  
  AC/BD
  
  
  
  
  
  
  
  AD/BC
  
  
  
  
  
  
  
  BC/BD
  
  
  
  
  
  
  
  
  
  (c)
  
  
  
  Σ
  
  
  
  
  
  
  
  
  
  A
  
  
  
  
  
  AC
  
  B
  
  
  BD
  
  
  
  
  C
  
  
  
  
  
  BD
  
  D
  
  
  AC
  
  
  
  
  AC
  
  
  
  
  
  (AB)(AD)
  
  (BC)(CD)
  
  BD
  
  
  (AB)(AD)
  
  (BC)(CD)
  
  
  
  
  AB
  
  
  
  
  
  
  
  AD
  
  
  
  
  
  
  
  BC
  
  
  
  
  
  
  
  CD
  
  
  
  
  
  
  
  
  
  
  
  
  Table 18
  
  В Error! Reference source not found. показан процесс построения тестирующего графа композиции Σ. Как это видно из графа, его l=1, следовательно ч= l+2=3. То есть, КАМСИ-композиция, в соответствии с тестирующим графом имеет ч=3, а 'ведет себя', как ч=4 (см. Error! Reference source not found.(h)).
  
  Более того, для КАМСИ-композиции невозможно построить описанным в литературе способом инвертор. Это видно из Error! Reference source not found.(b), где выходные последовательности 1101 и 1110 не могут появиться на выходе кодера, но инвертор должен быть определен на них (см. Error! Reference source not found.(b) строки A1100 и A1111).
  
  С другой стороны, так как известны инверсии КАМСИ и (SS1, SS2), то можно построить инверсию автомата Σ в виде композиции автоматов SS2=>SS1. В Error! Reference source not found. показан процесс построения композиции , а в Error! Reference source not found. показан процесс кодирования-декодирования, который совпадает с процессом, показанным в Error! Reference source not found.(h).
  
  Информация, приведенная в этом разделе требует проведения дополнительных исследований.
  
  Тем не менее, даже та информация, которая приведена, позволяет сделать следующие выводы:
  
  
  
  
  
  
  
  
  
  
  A
  
  
  B
  
  
  C
  
  
  D
  
  0000
  
  
  
  
  
  +
  
  
  
  
  
  
  
  0001
  
  
  
  
  
  +
  
  
  
  
  
  
  
  0010
  
  
  
  
  
  +
  
  
  
  
  
  
  
  0011
  
  
  
  
  
  +
  
  
  
  
  
  
  
  0100
  
  
  
  
  
  
  
  
  
  
  
  +
  
  0101
  
  
  
  
  
  
  
  
  
  
  
  +
  
  0110
  
  
  
  
  
  
  
  
  
  
  
  +
  
  0111
  
  
  
  
  
  
  
  
  
  
  
  +
  
  1000
  
  
  
  
  
  
  
  
  +
  
  
  
  
  1001
  
  
  
  
  
  
  
  
  +
  
  
  
  
  1010
  
  
  
  
  
  
  
  
  +
  
  
  
  
  1011
  
  
  
  
  
  
  
  
  +
  
  
  
  
  1100
  
  
  +
  
  
  
  
  
  
  
  
  
  
  1101
  
  
  
  
  
  
  
  
  
  
  
  
  
  1110
  
  
  
  
  
  
  
  
  
  
  
  
  
  1111
  
  
  +
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  (a)
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  P=0
  
  
  P=1
  
  (A1100)
  
  
  (A1100),1
  
  
  (A1101),1
  
  (A1111)
  
  
  (C1110),0
  
  
  (A1111),1
  
  (B0000)
  
  
  (B0000),1
  
  
  (B0001),1
  
  (B0001)
  
  
  (B0000),1
  
  
  (B0001),1
  
  (B0010)
  
  
  (B0010),1
  
  
  (B0011),1
  
  (B0011)
  
  
  (B0010),1
  
  
  (B0011),1
  
  (C1000)
  
  
  (C1000),1
  
  
  (C1001),0
  
  (C1001)
  
  
  (C1000),0
  
  
  (C1001),0
  
  (C1010)
  
  
  (C1010),1
  
  
  (C1011),0
  
  (C1011)
  
  
  (C1010),1
  
  
  (C1011),0
  
  (D0100)
  
  
  (D0100),1
  
  
  (D0101),0
  
  (D0101)
  
  
  (D0100),1
  
  
  (D0101),0
  
  (D0110)
  
  
  (D0110),1
  
  
  (D0111),0
  
  (D0111)
  
  
  (D0110),1
  
  
  (D0111),0
  
  
  
  Ситуации A1101 и C1110 отсутствуют
  
  (b)
  
  Table 19
  
   * Композиция КАМСИ-примитивов является КАМСИ, однако, к ней нельзя применить известные методы определения величины ч-задержки.
   * Единственный, известный способ построения инвертора - это перебор в пространстве кортежей. Сложность такого перебора можно определить по Error! Reference source not found. и Error! Reference source not found. (, см. стр. Error! Bookmark not defined.). Следует иметь ввиду, что Error! Reference source not found. и Error! Reference source not found. получены при допущении, что размер кортежа m известен криптоаналитику.
  
  SS1
  
  
  P,E
  
  E=0
  
  
  E=1
  
  S0
  
  
  S1,1
  
  
  S2,1
  
  S1
  
  
  S1,1
  
  
  S2,1
  
  S2
  
  
  S3,0
  
  
  S4,0
  
  S3
  
  
  S1,0
  
  
  S2,0
  
  S4
  
  
  S3,1
  
  
  S4,1
  
  
  
  SS2
  
  
  P,E
  
  E=0
  
  
  E=1
  
  S0
  
  
  S1,0
  
  
  S2,0
  
  S1
  
  
  S1,0
  
  
  S2,0
  
  S2
  
  
  S3,1
  
  
  S4,1
  
  S3
  
  
  S1,1
  
  
  S2,1
  
  S4
  
  
  S3,0
  
  
  S4,0
  
  
  
  
  
  
  
  
  SS2=>SS1
  
  
  E,P
  
  E=0
  
  
  E=1
  
  S0
  
  
  S0S0
  
  
  S1S1,1
  
  
  S2S1,1
  
  S1
  
  
  S0S1
  
  
  S1S1,1
  
  
  S2S1,1
  
  S2
  
  
  S0S2
  
  
  S1S3,0
  
  
  S2S3,0
  
  S3
  
  
  S0S3
  
  
  S1S1,0
  
  
  S2S1,0
  
  S4
  
  
  S0S4
  
  
  S1S3,1
  
  
  S2S3,1
  
  S5
  
  
  S1S0
  
  
  S1S1,1
  
  
  S2S1,1
  
  S6
  
  
  S1S1
  
  
  S1S1,1
  
  
  S2S1,1
  
  S7
  
  
  S1S2
  
  
  S1S3,0
  
  
  S2S3,0
  
  S8
  
  
  S1S3
  
  
  S1S1,0
  
  
  S2S1,0
  
  S9
  
  
  S1S4
  
  
  S1S3,1
  
  
  S2S3,1
  
  S10
  
  
  S2S0
  
  
  S3S2,1
  
  
  S4S2,1
  
  S11
  
  
  S2S1
  
  
  S3S2,1
  
  
  S4S2,1
  
  S12
  
  
  S2S2
  
  
  S3S4,0
  
  
  S4S4,0
  
  S13
  
  
  S2S3
  
  
  S3S2,0
  
  
  S4S2,0
  
  S14
  
  
  S2S4
  
  
  S3S4,1
  
  
  S4S4,1
  
  S15
  
  
  S3S0
  
  
  S1S2,1
  
  
  S2S2,1
  
  S16
  
  
  S3S1
  
  
  S1S2,1
  
  
  S2S2,1
  
  S17
  
  
  S3S2
  
  
  S1S4,0
  
  
  S2S4,0
  
  S18
  
  
  S3S3
  
  
  S1S2,0
  
  
  S2S2,0
  
  S19
  
  
  S3S4
  
  
  S1S4,1
  
  
  S2S4,1
  
  S20
  
  
  S4S0
  
  
  S3S1,1
  
  
  S4S1,1
  
  S22
  
  
  S4S1
  
  
  S3S1,1
  
  
  S4S1,1
  
  S23
  
  
  S4S2
  
  
  S3S3,0
  
  
  S4S3,0
  
  S24
  
  
  S4S3
  
  
  S3S1,0
  
  
  S4S1,0
  
  S25
  
  
  S4S4
  
  
  S3S3,1
  
  
  S4S3,1
  
  
  
  
  
  E,P
  
  E=0
  
  
  E=1
  
  S0
  
  
  S0S0
  
  
  S6,1
  
  
  S11,1
  
  S1
  
  
  S0S1
  
  
  S6,1
  
  
  S11,1
  
  S2
  
  
  S0S2
  
  
  S8,0
  
  
  S13,0
  
  S3
  
  
  S0S3
  
  
  S6,0
  
  
  S11,0
  
  S4
  
  
  S0S4
  
  
  S8,1
  
  
  S13,1
  
  S5
  
  
  S1S0
  
  
  S1,1
  
  
  S11,1
  
  S6
  
  
  S1S1
  
  
  S6,1
  
  
  S11,1
  
  S7
  
  
  S1S2
  
  
  S8,0
  
  
  S13,0
  
  S8
  
  
  S1S3
  
  
  S6,0
  
  
  S11,0
  
  S9
  
  
  S1S4
  
  
  S8,1
  
  
  S13,1
  
  S10
  
  
  S2S0
  
  
  S17,1
  
  
  S23,1
  
  S11
  
  
  S2S1
  
  
  S17,1
  
  
  S23,1
  
  S12
  
  
  S2S2
  
  
  S19,0
  
  
  S25,0
  
  S13
  
  
  S2S3
  
  
  S17,0
  
  
  S23,0
  
  S14
  
  
  S2S4
  
  
  S19,1
  
  
  S25,1
  
  S15
  
  
  S3S0
  
  
  S7,1
  
  
  S12,1
  
  S16
  
  
  S3S1
  
  
  S7,1
  
  
  S12,1
  
  S17
  
  
  S3S2
  
  
  S9,0
  
  
  S14,0
  
  S18
  
  
  S3S3
  
  
  S7,0
  
  
  S12,0
  
  S19
  
  
  S3S4
  
  
  S9,1
  
  
  S14,1
  
  S20
  
  
  S4S0
  
  
  S16,1
  
  
  S22,1
  
  S22
  
  
  S4S1
  
  
  S16,1
  
  
  S22,1
  
  S23
  
  
  S4S2
  
  
  S18,0
  
  
  S24,0
  
  S24
  
  
  S4S3
  
  
  S16,0
  
  
  S22,0
  
  S25
  
  
  S4S4
  
  
  S18,1
  
  
  S24,1
  
  
  
  Table 20
  
  P
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  
  
  
  
  
  Σ
  
  
  A
  
  
  A
  
  
  A
  
  
  C
  
  
  B
  
  
  D
  
  
  C
  
  
  B
  
  
  B
  
  
  D
  
  
  C
  
  
  D
  
  
  A
  
  
  A
  
  
  C
  
  
  B
  
  
  
  
  E2
  
  
  
  
  
  1
  
  
  1
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  
  1
  
  
  
  
  
  
  
  
  
  S0
  
  
  S11
  
  
  S23
  
  
  S24
  
  
  S22
  
  
  S16
  
  
  S7
  
  
  S13
  
  
  S17
  
  
  S9
  
  
  S8
  
  
  S11
  
  
  S17
  
  
  S14
  
  
  S25
  
  
  S24
  
  
  
  
  
  
  
  
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  P
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  1
  
  
  1
  
  
  0
  
  
  0
  
  
  0
  
  
  1
  
  
  0
  
  
  1
  
  
  0
  
  
  1
  
  
  1
  
  Table 21
  
  
  
  
   Список литературы
  
  1. Lui, C. L.: Some Memory Aspects of Finite Automata, M.I.T.Rcs. Lab. Electron. Tech. Rept. 411, May, 1963.
  
  2. Lui, C. L.: Determination of the Final State of an Automaton Who's Initial State Is Unknown, IEEE Trans. Electron. Computers, vol. EC-12, December, 1963.
  
  3. Lui C. L.: kth-order Finite Automaton, IEEE Trans. Electron. Computers, vol. EC-12, October, 1963.
  
  4. Massey, J. L.: Note on Finite Automaton Sequential Machines, IEEE Trans. Electron. Computers, vol. EC-15, pp. 658-659, 1966.
  
  5. Simon, S.M.: A Note on Memory Aspects of Sequence Transducers, IRE Trans. Circuit Theory, vol. CT-6, Special Supplement, pp. 26-29, May, 1959.
  
  6. Perles, M., M. O. Rabin, and E. Shamir: The Theory of Definite Automata, IEEE Trans. Electron. Computers, June, 1963, pp. 233-243.
  
   7. Huffman, D. A.: Canonical Forms for Information Lossless Finite-state Machines, IRE Trans. Circuits Theory, vol. CT-6, Special Supplement, pp. 41-59, May, 1959.
   8. Memory, Definiteness, and Information Losslessness of Finite Automata chat. 14, pp. 507. Zvi Kohavi, Switching and Finite Automata Theory, Second Edition 1978
   9. Взломан алгоритм шифрования RSA,
  
   http://www.cnews.ru/topnews/2001/02/05/content4.shtml
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  [1] В 2000 г. сотрудники RSA Laboratories предложили всем желающим взломать 140-битовый ключ шифрования RSA. В течение месяца ключ был взломан. Тогда RSA Laboratories бросила криптографической общественности новый вызов, предложив проверить на прочность 512-битовый ключ. На этот раз 'крепость' RSA держалась чуть больше семи месяцев. После этих экспериментов специалисты RSA Laboratories рекомендуют использовать ключи шифрования длиной не менее 768 бит. Растет вычислительная мощность процессоров, а параллельно совершенствуются средства, позволяющие быстро взламывать криптографические системы.
  
  Паула Шерик - редактор Windows 2000 Magazine и консультант по вопросам планирования, реализации и взаимодействия сетей.
  
  [2] Это существенное отличие предлагаемого алгоритма от существующих, в которых увеличение трудности взлома приводит к уменьшению быстродействия.
  
  [3] См. http://www.km.ru/education/ref_show.asp?id=B9E12642ED4943B8A48D1C0B74B2ED28
  
  [4] Термин 'асимметричный алгоритм' появился позднее, через двадцать лет
  
  [5] Обратите внимание, что 'секретом' здесь является не вертолет, а недоступность его для остальных участников.
  
  [6] Под правилом здесь понимается совокупность признаков, по которым, не выполняя преобразования, можно однозначно определить наличие или отсутствие определенного качества. Например, правило проверки числа на четность и тому подобное.
  
  [7] Наверное не все знают, что в СССР перед защитой диссертации следовало опубликовать автореферат диссертации, на публикацию которого следовало получить разрешение цензурного комитета Главлит. Так вот, когда автор этой работы тридцать лет тому назад обратился за разрешением публикации автореферата, ему было отказано, так как в тексте встречался термин коды состояний конечного автомата.
  
  [8] Такое название условно. В этом случае речь идет не только о коммерции, но решаются проблемы групп людей, связанных общими интересами.
  [9] http://www.citforum.ru/internet/securities/pitfalls.shtml
  
  [10] Здесь имеется в виду, что ключ должен сохраняться в секрете сразу двумя абонентами. Не трудно показать, что 'секрет для двоих' - такая же бессмыслица, как 'секрет для всех'. Термин секрет имеет смысл только тогда, когда он известен только одному.
  
  [11] Кроме того, в открытых системах нет необходимости организовать процесс распределения ключей. Забавно, но приведенное соотношение становится не в пользу систем с открытым ключем при n ≤ 5. .
  
  Такое условие соответствует системам, обслуживающим государственные организации. Это одно из обстоятельств, объясняющих причину, по которой во многовековой истории криптографии применялись симметричные алгоритмы. Потребность систем с открытым ключем возникла с появлением негосударственных (научных, коммерческих и т.п. систем) только в 20 веке.
  
  [12] См. http://www.cryptography.ru/db/msg.html?mid=1161992&uri=index.html 'Николай Варновский: Протоколы = распределенные алгоритмы + соглашения о форматах"'
  
  [13] См. http://www.ssl.stu.neva.ru/psw/crypto/applied/ewtoc.html. Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C.
  
  [14] См. http://www.ssl.stu.neva.ru/psw/crypto/appl_rus/appl_cryp.htm. Брюс Шнайер, Прикладная криптография, 2-е издание, Протоколы, алгоритмы и исходные тексты на языке С.
  
  [15] Следует заметить, что здесь будет рассмотрен далеко не полный перечень протоколов, а только те, на примере которых можно увидеть преимущества применения алгоритмов на базе КАМСИ.
  
  [16] В общем случае, злоумышленником может оказаться абонент сети, который пытается участвовать в обмене информации под другим именем.
  
  [17] РОССИЙСКАЯ ФЕДЕРАЦИЯ. ФЕДЕРАЛЬНЫЙ ЗАКОН ОБ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ. http://www.akdi.ru/gd/proekt/086086GD.SHTM
  
  [18] Пара ключей EA , DA генерируется абонентом А. Ключ EA посылается администратору по незащищенному каналу для формирования BDA, а ключ DA остается у абонента А.
  
  [19] Разумеется, злоумышленник С может просто портить код передаваемый по информационному каналу. Это подобно технологическому сбою и может быть компенсировано применением избыточных кодов. Однако, это не криптологическая проблема..
  
  [20] Скорее всего, и в этой области знаний верен принцип 'чукча не читатель, чукча писатель'
  
  [21] Это утверждение верно только в первом приближении. В действительности это иллюзия. Примером фокуса с исчезновением денег может служить инфляция - легальный способ государственного изъятия денег.
  
  [22] Рисунок взят из http://ixbt.stack.net/mobile/gsm-nets.html, там же можно увидеть расшифровку обозначений блоков.
  [23] 'Безопасность GSM: история, анализ, вскрытие',
  http://www.computerra.ru/offline/2000/331/2857/
  
  [24] Cell Phone Crypto Penetrated ", Wired News 6 Dec 1999.
  
  [25] Peter Gutmann, "Re: Forthcoming Biryukov/Shamir result against A5/1 GSM privacy algorithm", posting to cryptography@c2.net mailing list, 7 Dec 1999.
  
  [26] К сожалению, корпоративность этих служб часто играет с ними злые шутки. Дело в том, что криптографическими алгоритмами в этих службах, как и везде, занимаются люди. Для которых часто появление новых алгоритмов связано с дилеммой: стоит ли затрачивать усилия на освоение нового алгоритма, или проще - 'похоронить' его?
  
  [27] В этом случае нет необходимости реализовать EA()
  
  [28] Известно, что конечные автоматы могут быть типа Мили и Мура, но в данном случае это не имеет значения.
  
  [29] Названия состояний могут быть разными, это не влияет на реализацию алгоритма.
  
  [30] Алгоритм построения инверсного автомата рассмотрен в разделе 'Минимальная инверсная машина'. (В работе [8] (см. стр 97))
  
  [31] На практике, для того, чтобы это обстоятельство не позволяло определить значение μ, следует принять фиксированное число оконечных символов, равное, например 100 бит.
  
  [32] Процесс тестирования описан в работе [8] (см. стр 97). Более того, если бы А1 не был КАМСИ, то для него невозможно построить инвертор.
  
  [33] Имеется ввиду, что обе таблицы переходов имеют по 2 состояния.
  
  [34] Не трудно показать, что при изменении обозначения состояний в таблице переходов, алгоритм не изменяется.
  
  [35] Рассмотрение проведем для случая, когда параметры всех компонентов композиции равны между собой.
  
  [36] Следует обратить внимание, (см. Рис. 3 Структура процесса кодирования-декодирования,. стр. 41) что эксперимент в этом случае теряет смысл, так как для этого необходимо знать декодер SS1.
  
  [37] Диофантовыми эти уравнения названы потому, что предполагаемое их решение должно быть в целых числах.
  
  [38] Следует помнить, что один и тот же участник обмена информации, который сертифицирован в системе, в зависимости от информации, может быть, либо добросовестным, либо недобросовестным.
  
  [39] Значение не кратно 24, поэтому принято m=4 и поэтому ч=28, а не ч=24.
  
  [40] Не трудно показать, если ч > N, то уравнение Форм. 15 не имеет решения.
  
  [41] В этой связи можно заметить, что понятие примитивов более богатое, чем понятие простых чисел. Действительно, если в сложном числе не важен порядок расположения делителей, то КАМСИ-композиция зависит не только от набора примитивов, но и их взаимного расположения.
  
  [42] Количество примитивов должно быть таким, чтобы существовала возможность выбора из достаточно большого числа вариантов.
  
  [43] Понятие кортежа будет дано в следующем разделе.
  
  [44] Допустимо применять одинаковые примитивы в разных позициях.
  
  [45] В приведенной формуле m!- число перестановок.
  
  [46] Базовой может быть любая КАМСИ-компонента.
  
  [47] μ-пл - кортеж, в котором на первом месте стоит символ, соответствующий состоянию, обозначающему соответствующий столбец таблицы μ-кортежей, а далее следует μ-кортеж.
  
  [48] Это объясняется тем, что если не учитывать способ технической реализации автомата, то быстродействие определяется временем перехода из одного состояния в другое, которое не зависит от размера таблицы переходов.
 Ваша оценка:
Связаться с программистом сайта.

Новые книги авторов СИ, вышедшие из печати:
О.Болдырева "Крадуш. Чужие души" М.Николаев "Вторжение на Землю"

Как попасть в этoт список
Сайт - "Художники" .. || .. Доска об'явлений "Книги"