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

       

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


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

Брюс Шнайер «Подводные камни безопасности в криптографии»[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]).


      Содержание раздела