Идея открытого ключа – революция в криптографии

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

Обмен информацией в зашифрованном виде это не единственная задача, в решении которой могут быть заинтересованы участники А и Б. Рассмотрим ряд других задач.

1) Электронная цифровая подпись. Очевидно, что при передаче сообщений в электронном виде обычная подпись не имеет смысла.

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

3) Распределение ключей. Для того, чтобы участники А и Б могли установить шифрованную связь, им нужен общий ключ. Ключ должен обладать следующими свойствами:

· должен быть секретным;

· должен быть одинаковым для участников;

· должен быть быстро и просто заменен при плановой смене ключей или компрометации;

· должен иметь достаточно большой объем (но существенно меньший, чем длина сообщений).

Пусть (X,K,Y,(f_k)_{k K}) – шифр используемый абонентами А и Б. Покажем, что этот же шифр может быть использован для решения перечисленных выше трех задач.

Проверка подлинности лица с помощью симметричного шифра. Рассмотрим, например, протокол распознавания «свой или чужой». Представим, что самолет подлетел к Радиолокационной Станции (РЛС), и там решают свой это самолет или чужой. Свой самолет имеет номер iи секретный ключ , который также имеется на РЛС. На земле составляют запрос x_t X, который зависит от времени t и передают его на подлетающий самолет. Летчик шифрует x_t на ключе и возвращает пару ( на РЛС. На РЛС по номеру i определяют ключ и также шифруют x_t на ключе . Если полученные два шифртекста совпадают, то делается вывод, что самолет свой. В противном случае делается вывод, что самолет чужой. Очевидно, что требование однозначности расшифрования здесь не используется. Фактически на РЛС проверяют знание летчиком пары: несекретный номер i, секретный ключ .

Распознавания целостности получаемой информации с помощью симметричного шифра. При передачи сообщения в зашифрованном виде его целостность обеспечивается за счет избыточности открытого текста. Действительно, пусть А передает Б шифртекст . Если в процессе передачи шифртекст y был заменен на y’, то при расшифровании Б получит . Вероятно, x’ не имеет необходимую структуру открытого текста, то есть избыточность, фиксированные комбинации на фиксированных местах и т.д.

Если открытый текст не имеет избыточности, то ее вносят искусственно. Если сообщение передается в открытом виде, то есть без шифрования, то вносимая избыточность должна зависеть от ключа. Тогда вместо открытого текста x передают , где F некоторое несекретное сжимающее отображение. На приеме значение также может быть вычислено и проверено на совпадение. Как видно, целостность обеспечивается наличием на приемном и передающем концах общего ключа .

Электронная подпись для сообщения с помощью симметричного шифра. Пусть А, Б располагают общим секретным ключом k. При этом Б уверен, что ключ k не известен никому помимо А. Тогда электронная подпись для сообщения x может быть обеспечена вычислением F(f_k(x)). Подписанное сообщение имеет вид x, F(f_k(x)). Получатель Б зашифровывает x и вычисляет значение F от f_k(x). Затем сравнивает полученное значение с принятым от А значением F(f_k(x)). Однако этот способ подписи не обеспечивает важнейшее свойство обычной подписи. Действительно, А может отказаться от своей подписи, а Б не сможет доказать третьему лицу, что именно А подписал данное сообщение.

Отметим, что все рассмотренные протоколы используют наличие общего секретного ключа.

Доставка ключа для симметричного шифра. До 1970-х годов было известно три способа доставки ключа.

1) Центр распределения ключей вырабатывает ключ (для i -го сеанса связи), фельдъегерская служба доставляет абонентам А и Б,

2) Фельдъегерская служба доставляет ключ . Ключ передается Центром распределения ключей абонентам А и Б в зашифрованном виде на ключе . Таким образом, абонентам передают (Здесь мы предположили, что k_i X).

3) Фельдъегерская служба доставляет ключ абонентам А, Б. Ключи получают посредством несекретного преобразования: F_i

.

Возможны различные комбинации этих способов.

Классическая модель криптографической системы (модель К. Шеннона). Для решения проблемы распределения ключей в классических шифрах (симметричных шифрах) как было сказано выше предусмотрено наличие секретного канала связи, с помощью которого пользователи могут передавать ключи.

Но можно ли передавать ключи, если такого защищенного канала связи нет? Могут ли, например, два удаленных абонента обменяться секретными сообщениями, пользуясь лишь таким средством связи, как электронная почта?

Идея ассиметричного ключа. В 1970-х годах была совершена революция в области криптографических протоколов и в области криптографии в целом. Было обнаружено, что

1) ключ шифрования и ключ расшифрования не обязательно должны быть одинаковыми и один из них может быть несекретным.

2) абоненты могут договориться о секретном ключе, обмениваясь информацией по несекретному каналу связи.

Эти открытия сделали криптографию доступной не только государственным организациям и коммерческим фирмам, но и рядовым гражданам.

Классическая модель криптографической системы (модель Шеннона)

В отличие от классических криптографических систем, где ключи шифрования и расшифрования совпадают (такие системы называют симметричными), новые системы получили название асимметричных или систем открытого шифрования. В них ключ шифрования и ключ расшифрования различаются и ключ зашифрования является несекретным.

Системы выработки общего секретного ключа посредством обмена несекретной информацией стали называть системами открытого распределения ключей.

Общая схема открытого шифрования. Пусть M множество всех открытых сообщений, С – множество шифрованных тексов. Предположим, что для всех можно построить алгоритм шифрования и алгоритм расшифрования таким образом, чтобы противник, зная , не смог бы вычислить k или за приемлемое время. То есть задача вычисления k или по данному требует очень большого объема вычислений.

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

1) Алиса выбирает секретный ключ k, генерирует открытый алгоритм шифрования и секретный алгоритм расшифрования .

2) Алиса передает в центр сертификации ключей (или просто центр сертификации, центр доверия) алгоритм , который публикуется в виде таблицы

Имя	Алгоритм
Алиса

3) Боб составляет сообщение m, обращается к таблице, извлекает открытый алгоритм Алисы , вычисляет шифртекст и передает с Алисе.

4) Алиса расшифровывает .

Цифровая подпись с использованием шифров с открытым ключом. Ранее отмечалось, чтопроблема цифровой подписи состоит в том, чтобы дать возможность получателю сообщения демонстрировать другим людям, что полученное им сообщение пришло от конкретного лица, то есть, фактически, обеспечить аналог обычной подписи. Иногда получателю достаточно удостовериться в том, что сообщение не было навязано (изменено или имитировано) третьим лицом. Противодействовать данному типу угроз позволяет обычная система обеспечения имитостойкости. Но она не может предоставить получателю электронного сообщения юридическое доказательство личности отправителя, то есть не может разрешить спор между отправителем и получателем относительно того, какое было послано сообщение и было ли оно послано вообще. Оказывается, обе эти проблемы могут быть решены с помощью шифров с открытым ключом.

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

3) Алиса вычисляет подпись для сообщения m (хэш – значение сообщения), то есть вычисляет . Она передает Бобу подписанное сообщение m,c.

4) Боб проверяет выполнение равенства . Если оно выполнено, то подпись принимается. В противном случае подпись отвергается.

Подписанный документ m,c может быть предъявлен Бобом третьему лицу, например, в суде. Если Алиса хочет отказаться от своей подписи, она должна убедить судей, что решена сложная задача вычисления по или ее секретный ключ был скомпрометирован.