WikiSort.ru - Не сортированное

Подбрасывание монеты с помощью однонаправленных функций

Представим, что Алиса и Боб договорились об однонаправленной функции.

Шаг1. Алиса выбирает случайное число ${\displaystyle x}$ .Далее вычисляет ${\displaystyle y=f(x)}$ , где ${\displaystyle f(x)}$ - однонаправленная функция.

Шаг2. Алиса посылает ${\displaystyle y}$ Бобу.

Шаг3. Боб пытается угадать четность ${\displaystyle x}$ и посылает свое предположение Алисе (подбрасывает монету).

Шаг4. Алиса объявляет результат броска, посылая ${\displaystyle x}$ Бобу.Если Боб угадал, то результат броска - "орел", если не угадал, то "решка".

Шаг5. Боб проверяет, не обманула ли его Алиса, подставляя ${\displaystyle y=f(x)}$

К сожалению данный алгоритм легко поддается обману как со стороны Алисы, так и со стороны Боба. Если Алиса сможет найти ${\displaystyle x}$ и ${\displaystyle x'}$ , такие что ${\displaystyle x}$ - четно, а ${\displaystyle x'}$ - нечетно, и ${\displaystyle y=f(x)=f(x')}$ , то она каждый раз сможет обманывать Боба, так как Боб никак не сможет узнать, какой бит загадала Алиса. Алиса всегда сможет раскрыть тот бит, который ей удобен. Кроме того, наименьший значащий бит ${\displaystyle f(x)}$ должен быть некоррелирован с ${\displaystyle x}$ . В противном случае Боб сможет обманывать Алису, по крайней мере иногда. Например, если ${\displaystyle f(x)}$ в 75 процентах случаев четна, когда четен ${\displaystyle x}$ , то у Боба будет преимущество, так как он сможет угадывать значения ${\displaystyle x}$ .

Подбрасывание монеты с помощью криптографии с открытыми ключами

Шаг1. Алиса и Боб создают пары открытый/закрытый ключ.

Шаг2. Алиса создает два сообщения, одно для "орла", второе - для "решки". Сообщения должны включать некоторую случайную строку, чтобы она могла подтвердить их подлинность на последующих этапах протокола. Алиса шифрует оба сообщения своим открытым ключом и посылает их Бобу в произвольном порядке.

${\displaystyle E_{A}(M_{1}),E_{A}(M_{2})}$

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

${\displaystyle E_{B}(E_{A}(M))}$ , где ${\displaystyle M=M_{1}}$ или ${\displaystyle M=M_{2}}$

Шаг4. Алиса расшифровывает сообщение своим закрытым ключом и посылает обратно Бобу.

${\displaystyle D_{A}(E_{B}(E_{A}(M)))=E_{B}(M_{1})}$ , если ${\displaystyle M=M_{1}}$ , или ${\displaystyle E_{g}(M_{2})}$ , если ${\displaystyle M=M_{2}}$

Шаг5. Боб расшифровывает сообщение своим закрытым ключом, раскрывая результат броска монеты, и посылает расшифрованное сообщение Алисе.

${\displaystyle D_{B}(E_{B}(M_{1}))}$ или ${\displaystyle D_{B}(E_{B}(M_{2}))}$

Шаг6. Алиса читает результат броска монеты и проверяет, что случайная строка правильная.

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

Этот же алгоритм самодостаточен. Любая сторона может немедленно обнаружить мошенничество другой, и не требуется третья сторона ни для участия в протоколе, ни в качестае арбитра после завершения протокола. Покажем справедливость этого утверждения.
У Алисы есть три возможности смошенничать. Во-первых, она может зашифровать два сообщения для "орла" на шаге 2. Боб обнаружит это, когда Алиса раскроет свои ключи на шаге 7.Во-вторых, она может использовать другой ключ для расшифрования сообщения на шаге 4. Но Боб поймет это на шаге 5. И наконец, она может объявить неправильным сообщение на шаге 6. Боб также обнаружит это на 7-ом шаге.
У Боба также есть 3 пути для обмана. Во-первых, он может неправильно зашифровать сообщен ие на шаге 3, но Алиса обнаружит мошенничество на шаге 6.Во-вторых, он может сказать, что неправильно выполнил шаг 5 из-за жульничества Алисы, но это вскроется на шаге 7. В-третьих, он может послать Алисе сообщение о "решке" на шаге 5, независимо от расшифрованного сообщения, но Алиса может немедленно проверить достоверность сообщения на шаге 6.^[3]

Выводы

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

Ментальный покер

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

Обмен секретами

Обмен секретами - это общепринятое в литературе название типа криптографических протоколов, в которых у участников, вообще говоря, нет никакой конфиденциальной информации, но у каждого из них есть данные, представляющие для него определенную ценность, и он готов отдать их, но только в обмен на равноценную информацию.
Рассмотрим протокол с двумя участниками Алисой и Бобом.
У Алисы есть секрет ${\displaystyle S_{A}}$ , у Боба ${\displaystyle S_{B}}$ , которые будем считать двоичными строками.Участики согласны обменяться секретами.Проблема в том, что если первый шаг делает Алиса и посылает Бобу значение ${\displaystyle S_{A}}$ , то в ответ она может не дождаться ничего. Если первый Боб ситуация аналогична. Протокол подбрасывания монеты по телефону исключает такую возможность. Для понимания, каким образом это происходит, необходимо просто заменить в протоколе действие по подбрасыванию монеты, действием по передаче секрета. ^[5]

Электронная почта с уведомлением

Электронная почта с уведомлением - электронный аналог хорошо известной службы доставки заказной почтовой корреспонденции.В этом случае Алиса - служба доставки, у которой есть файл, адресованный Бобу. Файл должен быть передан Бобу только в обмен на расписку в получении.
В этом сценарии есть одно существенное отличие от общего случая обмена секретами: защищаться нужно от главным образом от нечестных действий получателя.
В качестве примера рассмотрим протокол из работы Атеньезе и Нита-Ротару.^[6]

Шаг1.Алиса выбирает случайное число ${\displaystyle r}$ , вычисляет ${\displaystyle y=r^{e}h(M)}$ , подписывает ${\displaystyle y}$ и посылает Бобу.Здесь ${\displaystyle M}$ - сообщение для Боба, ${\displaystyle h}$ - хеш-функция.

Шаг2.Боб вычисляет ${\displaystyle VE(y^{d})}$ , подписывает это сообщение и посылает Алисе. ${\displaystyle VE}$ - функция шифрования криптосистемы с проверяемым шифрованием.Открытый ключ этой криптосистемы общедоступен, секретный ключ доступен известен центру доверия. Криптосистема с проверяемым шифрованием - специальный вид шифра, оладающий следующим свойством. Алиса, получив криптограмму, может проверить, что она содержит подпись для ${\displaystyle rh(M)}$ .Но извлечь эту подпись, не зная секретный ключ, невозможно.

Шаг3.Алиса посылает Бобу сообщение ${\displaystyle M}$ .

Шаг4.Боб передает Алисе квитанцию ${\displaystyle h(M)^{d}}$ .

Если в ответ на сообщение Алиса не получила квитанцию, она обращается к центру доверия, передавая ему все отправленные и полученные сообщения, а также ${\displaystyle M}$ и ${\displaystyle r}$ .
Центр доверия проверяет все подписи, расшифровывает криптограмму и посылает Алисе ${\displaystyle h(M)^{d}}$ , а Бобу ${\displaystyle M}$ .
Данный пример является частным случаем обмена секретами. Протокол подбрасывания монеты по телефону используется здесь для одновременного получения обеими сторонами желаемого: Бобом письма, Алисой расписки.