25.05.2014

Подбрасывание монетки по телефону (coin flipping)

by Lazy Panda — Categories: КриптографияLeave a comment

Поскольку я не осилил подобрать метафорическую цитату, которая бы характеризовала идею данного алгоритма, то поделюсь воспоминанием из детства. Когда я был школьником, то нередко участвовал в мероприятии, которое называлось «математический бой». Когда-нибудь я опишу эту штуку, но для данной записи существенен только один момент – конкурс капитанов. Чаще всего это простая задачка, которую можно решить в уме. Но иногда это был некоторый случайный процесс, например такой: капитаны отворачивают части доски и каждый пишет случайное натуральное число между единицей и сотней. Когда это сделают оба капитана, доски открывают и числа складывают – если сумма четная победил один первый капитан, нечетная – победил второй. Очевидно, что именно участие доски (точнее независимость выборов капитанов, которую эта доска обеспечивает) позволяет этому конкурсу иметь случайный результат. Если капитаны будут «в открытую» записывать свои числа, то, скорее всего, тот капитан, что будет записывать свое число вторым, просто подберет число исходя из нужного ему числа.

Семейство алгоритмов с общим названием «подбрасывание монетки по телефону» призваны как раз для того, чтобы можно было обменяться данными так, чтобы «случайный» результат нельзя было подтасовать. Фактически это способ генерации бита так, что участие принимают оба абонента, что позволяет быть уверенным в том, что даже если она сторона скомпрометирована, то генерация все равно будет достаточно случайной. Незаменимая вещь для совместной генерации общих ключей.

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

Вариант 1. Вручение бита.

Крайне простой вариант – использовать любой протокол вручения бита (update).

1)      Алиса генерирует случайный бит b1 и «вручает на хранению» Бобу.

2)      Боб генерирует свой случайный бит b2. Боб оглашает значение бита.

3)      Алиса раскрывает значение своего бита.

4)      Если биты совпадают, то считаем, что монета подброшена со значением «орел», в противном случае – «решка».

Отличный способ, обоснование которого полностью лежит на протоколе вручения бита.

Вариант 2. Использование однонаправленных функций.

Привлечем математический аппарат – воспользуемся однонаправленными функциями.

1)      Алиса генерирует случайное число и считает значение h = f(x), где – однонаправленная функция, о которой Алиса и Боб предварительно договорились. Значение передается Бобу.

2)      Боб делает предположение о числе – четное оно или нет.

3)      Алиса раскрывает значение числа x.

4)      Если предположение Боба верно, то считаем, что монета подброшена со значением «орел», в противном случае – «решка».

Интересный способ, который позволяет подбросить монетку, используя минимум математики. Но, как всегда, есть свои особенности. Первая особенность состоит в том, что если Алиса может подобрать два таких числа и x’ разной четности, что f(x) = f(x’), то Алиса на третьем этапе может выдавать подходящее число и определять исход броска. Вторая особенность может помочь Бобу – нередко значение однонаправленной функции коррелирует с аргументом функции. Особенно плохо, если эта зависимость связана с крайним битом (фактически, на четность). При использовании такой функции Боб может прогнозировать четность аргумента и делать свое предположение осознанно, а не случайно.

Вариант 3. Использование алгоритмов шифрования.

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

В виде формулы, это, пожалуй, понятнее:

Dk1(Ek2(Ek1)) = Ek2

Ek1 и Ek2 – шифрование на ключах k1 и k2, соответственного, а Dk1 – расшифровывание на ключе k1.

Собственно сам алгоритм:

1)      Алиса создает случайную строку Rand и создает на ее основе две новых строки, включая оба значения бита b (одно значение соответствует «орлу», а другое – «решке»). Так она получает Rand1 и Rand2.

2)      Алиса и Боб создают ключи Ka и Kb, соответственно.

3)      Алиса шифрует на своем ключе оба сообщения Ea1 = Eka(Rand1) и Ea2 = Eka(Rand2). После она отсылает полученные данные Бобу.

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

5)      Алиса расшифровывает полученное сообщение на своем ключе, таким образом, получая зашифрованную строку Rand1 или Rand2 на ключе Боба – Eb2. Она отдает ее Бобу.

6)      Боб расшифровывает сообщение в последний раз и оглашает значение b.

7)      Производится раскрытие всех параметров – Rand, Ka и Kb, для того, чтобы можно было убедиться в корректности всех этапов.

Вся идея алгоритма состоит в том, что на протяжении всего алгоритма – с пункта 3 по пункт 5 – значение бита зашифровано хотя бы на одном ключе. В алгоритме много мест где могут пытаться сжульничать и Боб и Алиса, но ни одно из таких мест не выдержит проверки на 7 этапе.

Здесь я бы хотел остановиться и дать всем возможность аккуратно переварить написанное. Мне очень нравиться именно семейство алгоритмов броска монеты по телефону – очень полезные алгоритмы для криптографии с практической точки зрения, при этом основная идея очень красивая и достаточно простая.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

© 2019 [Panda Tower] All rights reserved - Powered by [WordPress] and [Wallow]