СИСТЕМЫ ШИФРОВАНИЯ С ОТКРЫТЫМ КЛЮЧОМ Ассиметричные криптосистемы

Введение В истории криптографии очень много тайн и загадок. Ее история уходит своими корнями в очень далекую древность. Возможно она появилась сразу после появления письма. Но есть и довольно забавные истории. В 1983г. вышла книга М.Н. Аршипова и Л.Е. Садовского Коды и математика в которой было написано: Приемов тайнописи великое множество, и, скорее всего, это та область, где уже нет нужды придумывать что-нибудь существенно новое. Однако это было очередным заблуждением относительно криптографии.

В 1976г. вышла работа У.Диффи и М.Э. Хеллмана Новые направления в криптографии, которая содержала не только что существенно новое. Она сделала буквально революцию в криптографии. Она расширила применение криптографических методов от спец служб государства, до индивидуальных потребителей. Привлекло большой математический аппарат в криптографию и большую группу математиков.

Проблемы распределения ключей Основной проблемой возникающей при использовании криптосистем с секретным ключом, является проблема распределения ключей. Если например n человек хотят обмениваться информацией, то им необходимо n(n-1)/2 ключей(чтобы каждый мог читать только ему предназначенное сообщение). Эти ключи должны быть не только созданы, но и распределены между участниками информационного обмена по абсолютно секретным каналам. Что само по себе уже довольно сложно. Необходимость секретных каналов делает такой способ связи очень дорогостоящим, и практически неприменимым в коммерческих сетях связи.

Система Диффи - Хеллмана В 1976г. Диффи и Хеллман публикуют статью, которая явилось рождением криптографии с открытым ключом. Криптографический алгоритм в котором для шифровки и расшифровки используются разные ключи, называется ассиметричным. Общая схема: Каждый из участников имеет 2 функции : функция шифровки, которая известна всем, функция расшифровки только получателю сообщения. Пусть А хочет послать сообщение В, Е-функция шифровки для В, D-функция расшифровки для В. М - открытый текст, который посылает А. А применяет к М функцию шифрования Е и получает С=Е(М) т.е. шифротекст и посылает его к В. В применяет к С функцию расшифровки D и получает М=D(С). Т.к. функция D известна только В, то никто кроме него не может найти М по С(Е - открытый ключ, D секретный ключ).

Требования для функций Е и D Для любого сообщения М: D(Е(М))=М По сообщению Т легко вычисляются Е(Т) и D(T) Зная Е и С трудно или невозможно найти М т.ч. Е(М)=С (не зная D ). для любого сообщения М: Е(D(М))=М (это само по себе не нужно для шифрования по предложенной выше схеме, но очень удобно для цифровой подписи, которую рассмотрим в дальнейшем).

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

Пусть Еафункция шифровки абонентаА Dафункция расшифровки абонентаА Евфункция шифровки абонента В Dвфункция расшифровки абонента В и пусть А хочет послать сообщение М к В. А вычисляем Dа(М) и посылаем к В пару (М,Dа(М)) В - вычисляем Еа(Dа(М)) и сравниваем с М. Если М=Еа(Da(М)), то сообщение пришло от А, если нет, то нет (напомним что Еа известно всем).

Если А захочет отказаться от сообщения, то он не сможет этого сделать т.к. D известно только ему и найти С т.ч. Еа(С)=М не зная D очень сложно. Пусть теперь А хочет послать секретное сообщение М для В и подписать его. А вычисляет: С=Ев(Dа(М)) и посылает С к В. Абонент В расшифровывает С: Еа(Dв(С))=М. Пусть теперь А отказывается от сообщения М. Он предъявляет третьему лицу (арбитру) свой секретный ключ Dа. Арбитр сравнивает Dа(М) и Dв(С), если они совпали, то признается что А послал сообщение М. Предположим, что В будет утверждать что А послал сообщение М, которое А на самом деле не посылал, тогда ему надо найти C ' т.ч. Еа(Dв(С '))=М ' Но С ' =Ев(Dа(М ')), а Dа абонент В не знает.

Односторонние функции Пусть X,Y два произвольных множества Функция F: X Y называется односторонней, если для любого x из X F(x)-легко вычисляется (за линейное время ), и зная y=f(x) найти x очень трудно(x находится за экспоненциальное время ). Теоретически найти x из равенства y=f(x) можно всегда, перебрав все значения из x ( X,Y предполагаются конечные множества ), однако если X очень большое множество это не возможно практически. К сожалению (а может и к счастью) на сегодняшний день не известно ни одной односторонней функции.

Односторонние функции Основным критерием отнесения функции к классу односторонних является отсутствие эффективных алгоритмов обращения функции. Т.е. известен алгоритм позволяющий быстро вычислять f(x). И не известен алгоритм позволяющий по y=f(x) быстро найти x. Заметим что по y=f(x) очень трудно найти x, но как только x найден очень легко проверить верно ли он найден или нет, Т.е. проверить равенство f(x)=y.

Примеры Примеры односторонних функций. (не математические): Глиняный кувшин(разбили, собрать). Разорвать лист бумаги и собрать его. Пусть даны два очень больших числа: p и q перемножить их довольно легкая задача. Пусть теперь n = p q (мы знаем n, что n это произведение двух больших простых чисел), надо найти p и q. Это называется задачей факторизации эта задача очень трудна и не существует эффективных алгоритмов решить эту задачу за минимальное время. Дискретный логарифм Пусть а и n-целые числа 1

Односторонние функции с ловушкой Пусть f : X Y односторонняя функция и пусть послано сообщение f(X). Т.к. f(X) односторонняя функция, то сообщение X зашифрованно надежно, его не сможет расшифровать даже законный получатель. Поэтому в криптографии применяют так называемые односторонние функции с ловушками(или функции с потайными ходами ). Функция f: X Y называется односторонней функцией с ловушкой, если f –односторонняя функция и кроме того существует быстрый способ вычислить x по y=f(x), если известна некоторая дополнительная информация о функции f(X). При этом тот, кто отправляет сообщение не обязан знать секрет функции f (он только вычисляет f(x)). Но получатель сообщения безусловно должен знать секрет обращения, чтобы по f(x) получить x. Так же, как для односторонних функций, вопрос о существовании односторонних функций с ловушкой открыт. Имеется несколько кандидатов которые используются в криптографии.

Открытое распределение ключей Пусть абоненты А и В хотят сформировать секретный ключ взаимодействуя по открытому ключу. Эта задача на первый взгляд кажется неразрешимой. Но она решается. Абоненты А и В выбирают простое число Р и число n, большее, чем P. Абоненты А и В независимо друг от друга вырабатывают два секретных ключа Ха и Хв (секретные числа) А и В вычисляют и обмениваются сообщениями Ya и Yв. А вычисляет В вычисляет Число объявляется секретным ключом.

Открытое распределение ключей Если противник перехватил сообщение Ya и Yв, то по ним он не сможет вычислить Ха и Хв т.к. эта задача которая не решается за разумное время.

С1976г. появилось множество криптографических алгоритмов с отрытыми ключами. Многие из них не безопасны. Из тех которые являются безопасными, многие не пригодны для практической реализации. Они либо используют слишком большой ключ, либо размер шифротекста намного превосходит размер открытого текста. Немногие алгоритмы являются и безопасными и практичными. Почти все из них основываются на одной из трудных проблем рассмотренных в теме об односторонних функциях на слайдах выше. Некоторые из этих безопасных и практичных алгоритмов подходят только для распределения ключей. Другие подходят для шифрования (и для распределения ключей). Третьи полезны только для цифровых подписей. И только очень не многие алгоритмы хорошо работают как при шифровании, таки для цифровой партии. Все построенные на сегодняшний день алгоритмы очень медленные.

Немного о безопасности Пусть противник Z перехватывает сообщение С (шифротекст). Т.к. ему известен открытый ключ E (он известен всем), то он может подбором найти М т.е. Е(М)=С Если вариантов для М не очень много (например М- платежное поручение, с примерно известным текстом, но не известной суммой), то злоумышленник легко найдет М. Поэтому нужно, чтобы пространство возможных текстов было очень большим, или его надо искусственно расширить, например дополняя сообщения строкой случайных бит.