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