Инструменты пользователя

Инструменты сайта


examination:mszki:question35

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

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

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

{ : } — набор шифрования, а { : } — соответствующий набор для расшифрования. Каждая пара имеет свойство: зная , невозможно решить уравнение , то есть для данного произвольного шифротекста , невозможно найти сообщение . Это значит, что по данному невозможно определить соответствующий ключ расшифрования . является односторонней функцией, а — лазейкой.

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

1. Боб выбирает пару и шлёт ключ шифрования (открытый ключ) Алисе по открытому каналу, а ключ расшифрования (закрытый ключ) защищён и секретен (он не должен передаваться по открытому каналу).

2. Чтобы послать сообщение Бобу, Алиса применяет функцию шифрования, определённую открытым ключом : , — полученный шифротекст.

3. Боб расшифровывает шифротекст , применяя обратное преобразование , однозначно определённое значением .

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

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

2. Можно выделить легкую подзадачу из . Она должна решаться за полиномиальное время и лучше, если за линейное.

3. «Перетасовываем и взбалтываем» , чтобы получить задачу , совершенно не похожую на первоначальную. Задача должна по крайней мере выглядеть как оригинальная труднорешаемая задача .

4. открывается с описанием, как она может быть использована в роли ключа зашифрования. Как из получить , держится в секрете как секретная лазейка.

5. Криптосистема организована так, что алгоритмы расшифрования для легального пользователя и криптоаналитика существенно различны. В то время как второй решает -задачу, первый использует секретную лазейку и решает -задачу. Криптография с несколькими открытыми ключами

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

Тогда Алиса может зашифровать сообщение ключом , а Эллен расшифровать ключами , , Кэрол — зашифровать ключом , а Дэйв расшифровать ключами , . Если Дэйв зашифрует сообщение ключом , то сообщение сможет прочитать Эллен, если ключом , то его сможет прочитать Франк, если же обоими ключами и , то сообщение прочитает Кэрол. По аналогии действуют и другие участники. Таким образом, если используется одно подмножество ключей для шифрования, то для расшифрования требуются оставшиеся ключи множества. Такую схему можно использовать для n ключей. Теперь можно посылать сообщения группам агентов, не зная заранее состав группы. Рассмотрим для начала множество, состоящее из трех агентов: Алисы, Боба и Кэрол. Алисе выдаются ключи и , Бобу — и , Кэрол — и . Теперь, если отправляемое сообщение зашифровано ключом , то его сможет прочитать только Алиса, последовательно применяя ключи и . Если нужно отправить сообщение Бобу, сообщение шифруется ключом , Кэрол — ключом . Если нужно отправить сообщение и Алисе и Кэрол, то для шифрования используются ключи и .

Преимущество этой схемы заключается в том, что для её реализации нужно только одно сообщение и n ключей (в схеме с n агентами). Если передаются индивидуальные сообщения, то есть используются отдельные ключи для каждого агента (всего n ключей) и каждого сообщения, то для передачи сообщений всем различным подмножествам требуется ключей.

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

examination/mszki/question35.txt · Последние изменения: 2014/01/15 12:20 (внешнее изменение)