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

Введение В истории криптографии очень много тайн и загадок. Ее история уходит своими корнями в очень далекую древность. Возможно она появилась сразу после появления письма. Но есть и довольно забавные истории. В 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 называется односторонней, если для любого Y 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 и набор чисел {M1, M2, …, Mk}. Надо найти в множестве {M1, M2, …, Mk} подмножество сумма чисел которое дает N, если полное подмножество существует. {10,14,21,18,32}, N=42 42= В общем случае ничего кроме перебора в настоящее время предложить нельзя. Однако как только полное подмножество найдется, мы легко это можем проверить.

Примеры Дискретный логарифм Пусть а и n-целые числа 1

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

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

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

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