Если Вы хотите сохранить секрет,
Если Вы хотите сохранить секрет, не доверяйте его никому.
Сенека (5 до н.э. - 65 н.э.),
Как следует из эпиграфа, проблема сохранения секретов волновала людей со времени появления секретов. Сенека до сих пор прав, и истина, «знают двое – знает свинья», как говаривал папаша Мюллер, всегда будет актуальна. Иллюстрацией этого в криптографии может служить наличие двух типов алгоритмов: симметричного и асимметричного.
Первый, как это существует до сих пор, обладает высоким быстродействием, но предполагает наличие секретного ключа, который должен быть известен минимум двум
участникам процесса обмена информацией («знает свинья»).
Второй тип алгоритма, асимметричный, до настоящего времени имеет малое быстродействие, сложную реализацию, но он имеет два ключа:
- один, который известен всем
участникам обмена информацией, и - второй – известный только одному
участнику обмена информацией – тому, кому эта информация предназначается (см. рекомендацию Сенеки). - Будет показано, что, если трудность взлома RSA определяется сложностью выполнения операции разложения числа на простые сомножители (это и приводит к необходимости использования «длинной арифметики»), то для конечно-автоматной модели аналогичной операцией является декомпозиция кодера на простые компоненты.
- Будет показано, что сложность декомпозиции конечного автомата возрастает экспоненциально, в то время, как его быстродействие не зависит от размера его таблицы переходов[2].
- С одной стороны, для понимания сути проблемы, изложение должно предполагать знакомство читателя с Теорией Конечных Автоматов, хотя бы в объеме работы Zvi Kohavi “Switching and Finite Automata Theory”.
- С другой стороны, изложение должно предполагать знакомство читателя с Криптологией, хотя бы в объеме работы Bruce Schneier “Applied Cryptography”.
Это обстоятельство настолько существенно, что, несмотря на ряд преимуществ симметричных алгоритмов, они используются в криптографических протоколах только
совместно с асимметричными алгоритмами.
Следует добавить, что, как мы покажем далее, асимметричные алгоритмы – это самое удивительное и, парадоксальное явление, и не только в криптографии.
Действительно, в обыденной жизни всем понятно, что если все знают, как спрятан предмет, то нет большого секрета в том, как его найти. И вдруг в криптографии появляется способ, при котором все могут знать, как спрятан предмет. Более того, любой может спрятать предмет. Но найти его может только тот, кто придумал, как его спрятать, а не тот, кто его спрятал. Конечно, это не очень строгая аналогия с асимметричным криптографическим алгоритмом, но вызывает те же ощущения.
Действительно, что может быть привлекательнее для защиты информации, передаваемой по незащищенному каналу, чем способ кодирования, при котором все знают ключ шифрования и могут им воспользоваться для кодирования информации, в том числе и недобросовестные участники информационного обмена. Но раскодировать ее может только единственный участник, который разработал алгоритм кодирования.
Как всегда, воплощение мечты решает меньше проблем, чем создает новых.
Тем не менее, в нашей работе мы сосредоточим внимание только на решении проблемы низкой производительности существующих асимметричных алгоритмов, которая не позволяет достаточно эффективно применить их в криптографии. Другими словами, предлагаемая работа будет посвящена решению проблемы создания асимметричного быстродействующего алгоритма.
Какие соображения используются при этом?
Причина низкой производительности существующих асимметричных алгоритмов заключается в том, что применяемые на практике алгоритмы используют, так называемую, «длинную» арифметику, то есть арифметику, предназначенную для работы с числами размером от сотни и более цифр. Вследствие этого быстродействие асимметричных алгоритмов на несколько порядков меньше симметричных алгоритмов.
Надежды на то, что с ростом быстродействия технических средств разрыв между быстродействием асимметричных и симметричных алгоритмов будет сокращаться, безосновательны. Это происходит потому, что с ростом быстродействия технических средств, при сохранении размера чисел, снижается степень защищенности алгоритма, а это, в свою очередь, приводит к необходимости увеличить размерность «арифметики» ([1]).
Возникло целое направление в криптографии, так называемые теоретико-числовые алгоритмы (например, RSA), которое за последние двадцать лет привело к появлению большого числа оригинальных асимметричных алгоритмов и это создало иллюзию, что термины «асимметричный алгоритм» и «длинная арифметика» - синонимы.
Так ли это?
Для того, чтобы опровергнуть это утверждение, далее будет рассмотрен асимметричный алгоритм кодирования на базе конечно-автоматной модели.
По аналогии с понятиями сложного и простого числа в теории чисел, далее будут введены понятия композиции конечных автоматов и примитивов.
Особенность этих понятий заключается в том, что, сложное число в теории чисел представляет собой произведение простых чисел и это произведение не зависит от порядка расположения в нем сомножителей. Для конечного же автомата, эквивалентного композиции примитивов, имеют значение, как их набор, так и порядок их взаимного расположения в композиции, то есть, композиция автоматов не обладает свойством коммутативности.
Структура предлагаемой работы определялась тем обстоятельством, что до настоящего времени Теория Конечных Автоматов и Криптология развиваются параллельно и независимо. Каждая из них имеет специфический язык, объекты изучения, область применения и своих специалистов.
Это создает трудности при изложении материала:
Понимая, что одновременное совмещение задачи просвещения и обсуждения предлагаемого способа решения проблемы создания асимметричного криптографического алгоритма, может привести к ситуации, когда ни та, ни другая задача не будет достаточно эффективно решена, автор выбрал компромиссный вариант.
В основу его положены соображения, что, принятый способ изложения может быть рассчитан хотя бы на одну из трех категорий читателей:
1. Читатель, который слабо знаком с Криптографией и Теорией Конечных Автоматов, но обладает достаточной математической культурой. Его интересует логика изложения и корректность проводимых расчетов, которые используются для оценки параметров предлагаемого асимметричного алгоритма. Такой читатель может ограничиться Частью 1 (см. стр 15) и составить собственное мнение, насколько можно доверять выводам, сделанным в работе.
2. Читатель, который знаком с проблематикой предлагаемой работы. Такому читателю можно предложить предварительно познакомиться с работой Лунина А.В., Сальникова А.А «Перспективы развития и использования асимметричных алгоритмов в криптографии» (см. стр. Ошибка! Закладка не определена.) и четырнадцатой главой работы Цви Кохави «Память, определенность и конечные автоматы, сохраняющие информацию» (см. стр. Ошибка! Закладка не определена.). Эти работы позволяют оценить существующее положение асимметричных алгоритмов в криптографии, и, после перехода к Части 1, оценить правильность выводов, сделанных в ней.
3. И, наконец, наиболее приятная автору третья категория читателей – это те, которые не обладают необходимой математической культурой и при этом не знакомы с проблематикой Криптографии и Теории Конечных Автоматов. Но ими движет здоровая природная любознательность. Таким читателям автор рекомендует поверить на слово, что все, о чем далее пойдет речь - очень интересно. Если автор уже убедил Вас в этом, то ему остается порекомендовать, не теряя времени, как можно скорее перейти в одну из первых двух категорий читателей.
Мы ставим здесь перед собой задачу исследования множества объектов нашей любознательности, причем мы будем исследовать их с тем недоверием, с каким надо относиться к любой системе до тех пор, пока она не продемонстрирована нашим глазам или не доказана нашему разуму. Вольтер, "О феноменах природы" |
