Криптосистемы с открытым ключом

Министерство  образования и науки Украины

Запорожский национальный технический  университет 
 
 
 
 
 
 
 

Кафедра КСС 
 
 
 
 
 
 

Реферат

по защите информации

«Криптосистемы с открытым ключом» 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Выполнил студент группы IОТ-617

      Жицкий Андрей

Принял Неласая А.В.  
 
 
 
 
 
 
 
 

Запорожье, 2011

     Криптографическая система с открытым ключом (или Асимметричное  шифрование, Асимметричный  шифр) — система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу, и используется для проверки ЭЦП и для шифрования сообщения. Для генерации ЭЦП и для расшифрования сообщения используется секретный ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME.

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

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

     Понять  идеи и методы криптографии с открытым ключом помогает следующий пример —  хранение паролей в компьютере. Каждый пользователь в сети имеет свой пароль. При входе он указывает имя и вводит секретный пароль. Но если хранить пароль на диске компьютера, то кто-нибудь его может считать (особенно легко это сделать администратору этого компьютера) и получить доступ к секретной информации. Для решения задачи используется односторонняя функция. При создании секретного пароля в компьютере сохраняется не сам пароль, а результат вычисления функции от этого пароля и имени пользователя. Например, пользователь Алиса придумала пароль «Гладиолус». При сохранении этих данных вычисляется результат функции f(ГЛАДИОЛУС), пусть результатом будет строка РОМАШКА, которая и будет сохранена в системе. В результате файл паролей примет следующий вид: 

 

     Вход  в систему теперь выглядит так: 

       
 
 

     Когда Алиса вводит «секретный» пароль, компьютер проверяет, даёт или нет  функция, применяемая к ГЛАДИОЛУС, правильный результат РОМАШКА, хранящийся на диске компьютера. Стоит изменить хотя бы одну букву в имени или в пароле, и результат функции будет совершенно другим. «Секретный» пароль не хранится в компьютере ни в каком виде. Файл паролей может быть теперь просмотрен другими пользователями без потери секретности, так как функция практически необратимая.

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

     

      

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

     Примеры таких криптотекстов: 

 

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

     Схема шифрования с открытым ключом

     Пусть K — пространство ключей, а e и d — ключи шифрования и расшифрования соответственно. Ee — функция шифрования для произвольного ключа eK, такая что:

     E_e(m) = c

     Здесь cЄC, где C — пространство шифротекстов, а mЄM, где M — пространство сообщений.

     D_d — функция расшифрования, с помощью которой можно найти исходное сообщение m, зная шифротекст c :

     D_d(c) = m

     {E_e: eЄK} — набор шифрования, а {D_d: dЄK} — соответствующий набор для расшифрования. Каждая пара (E,D) имеет свойство: зная E_e, невозможно решить уравнение E_e(m) = c, то есть для данного произвольного шифротекста cЄC, невозможно найти сообщение mЄM. Это значит, что по данному e невозможно определить соответствующий ключ расшифрования d. Ee является односторонней функцией, а d — лазейкой.

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

 

1. Боб выбирает пару (e,d) и шлёт ключ шифрования e (открытый ключ) Алисе по открытому каналу, а ключ расшифрования d (закрытый ключ) защищён и секретен (он не должен передаваться по открытому каналу).
2. Чтобы послать сообщение m Бобу, Алиса применяет функцию шифрования, определённую открытым ключом e: E_e(m) = c, c — полученный шифротекст.
3. Боб расшифровывает шифротекст c, применяя обратное преобразование Dd, однозначно определённое значением d.

 

     Начало  асимметричным шифрам было положено в работе «Новые направления в  современной криптографии» Уитфилда Диффи и Мартина Хеллмана, опубликованной в 1976 году. Находясь под влиянием работы Ральфа Меркле (Ralph Merkle) о распространении открытого ключа, они предложили метод получения секретных ключей, используя открытый канал. Этот метод экспоненциального обмена ключей, который стал известен как обмен ключами Диффи-Хеллмана, был первым опубликованным практичным методом для установления разделения секретного ключа между заверенными пользователями канала. В 2002 году Хеллман предложил называть данный алгоритм «Диффи — Хеллмана — Меркле», признавая вклад Меркле в изобретение криптографии с открытым ключом. Эта же схема была разработана Малькольмом Вильямсоном в 1970-х, но держалась в секрете до 1997 года. Метод Меркле по распространению открытого ключа был изобретён в 1974 году и опубликован в 1978, его также называют загадкой Меркле.

     В 1977 году учёными Рональдом Ривестом (Ronald Linn Rivest), Ади Шамиром (Adi Shamir) и Леонардом Адлеманом (Leonard Adleman) из Массачусетского Технологического Института (MIT) был разработан алгоритм шифрования, основанный на проблеме о разложении на множители. Система была названа по первым буквам их фамилий (RSA — Rivest, Shamir, Adleman). Эта же система была изобретена Клиффордом Коксом (Clifford Cocks) в 1973 году, работавшим в центре правительственной связи (GCHQ). Но эта работа хранилась лишь во внутренних документах центра, поэтому о её существовании было не известно до 1977 года. RSA стал первым алгоритмом, пригодным и для шифрования, и для цифровой подписи.

     Вообще, в основу известных асимметричных  криптосистем кладётся одна из сложных  математических проблем, которая позволяет строить односторонние функции и функции-лазейки. Например, криптосистемы Меркля — Хеллмана и Хора — Ривеста опираются на так называемую задачу об укладке рюкзака. 

     Основные  принципы построения криптосистем с открытым ключом:

1. Начинаем с трудной задачи P. Она должна решаться сложно в смысле теории: не должно быть алгоритма, с помощью которого можно было бы перебрать все варианты решения задачи P за полиномиальное время относительно размера задачи. Более правильно сказать: не должно быть известного полиномиального алгоритма, решающего данную задачу — так как ни для одной задачи ещё пока не доказано, что для неё подходящего алгоритма нет в принципе.
2. Можно выделить легкую подзадачу P' из P. Она должна решаться за полиномиальное время, лучше, если за линейное.
3. «Перетасовываем и взбалтываем» P', чтобы получить задачу P'', совершенно не похожую на первоначальную. Задача P'', по крайней мере, должна выглядеть как оригинальная труднорешаемая задача P.
4. P'' открывается с описанием, как она может быть использована в роли ключа зашифрования. Как из P'' получить P', держится в секрете как секретная лазейка.
5. Криптосистема организована так, что алгоритмы расшифрования для легального пользователя и криптоаналитика существенно различны. В то время как второй решает P'' задачу, первый использует секретную лазейку и решает P' задачу.

 

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

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

     Пусть есть 3 ключа KA, KB, KC, распределенные так, как показано в таблице.