- Ты помнишь, о чем я тебя просила?
- Нет.
- Ты обещал пропылесосить.
- Да? Что-то я такого не припомню…
- А я тебе говорю, что было такое!
Эта маленькая зарисовка является, пожалуй, самой нелепой иллюстрацией к алгоритму, которому посвящена эта запись. Но я уверен, что подобные ситуации случались с каждым в той или иной вариации. Целью семейства алгоритмов «вручение бита на хранение» является, как бы банально это не звучало, но именно вручение кому-то бита на хранение. Казалось бы, чего сложного – объяви адресату бит и пусть себе хранит? Но все становится не так просто, если мы хотим сохранить в тайне само значение бита. Более того, впоследствии мы хотим объявить значение бита и доказать, что именно данное значение мы отдали на хранение.
Вот такая вот хитрая цель. Давайте еще раз аккуратно сформулируем задачу:
У абонента Алиса есть некоторый бит b. Она желает передать его абоненту Боб, причем так, чтобы последний не знал его значения. В произвольный момент времени Алиса может объявить значение b и доказать, что Боб хранил именно его. Сам же Боб хочет сделать так, чтобы Алиса не могла изменить свой бит и обмануть его.
Возможно, у читателя уже появился вопрос – а зачем такие сложности? Вариантов использования данного протокола много – опубликование наследства, какого-нибудь предсказания (например, биржевые).
Вариант 1. Использование симметричной криптографии.
1) Боб создает случайную последовательность битов, назовем ее Random. Он вручает эту строку Алисе.
2) Алиса некоторым образом соединяет свой бит b с данной строкой, результат назовем RB. Кроме этого, она создает случайный ключ K и шифрует некоторым симметричным алгоритмом – E(RB, K). Результат она отсылает Бобу.
На секундочку остановимся. Уже сейчас мы видим, что раз Боб не знает значение ключа (хоть и знает алгоритм шифрования), то и расшифровать строку он не может. Фактически, Боб знает открытый текст и результат шифрования, но для восстановления ключа этого маловато.
3) Алиса решает объявить значение b. Она сообщает Бобу значение К, и тот расшифровывает E(RB, K), получая RB. Тут он проверяет честность Алисы.
Может ли Алиса обмануть Боба? Получается что нет – пусть она решила изменить свое мнение и пытается выдать бит за значение b’. Снова соединяя бит с последовательностью Random, получает RB’. Теперь самая сложная часть – ей нужно подобрать такое значение K’, чтобы E(RB’, K’) = E(RB, K). Изменение ключа таким образом, чтобы инвертировался ровно один бит – тоже вычислительно сложная задача. Конечно, все эти рассуждения основаны на той надежде, что алгоритм E достаточно криптостоек.
Вариант 2. Использование однонаправленных функций.
Под однонаправленными функциями в данный момент можно понимать хэш-функции, благо их много.
1) Алгоритм начинается с того, что Алиса создает две случайных последовательности бит Random1 и Random2.
2) Алиса соединяет все, что есть в ее распоряжении в единую последовательность – Random1, Random2 и b – получая новую последовательность RRB.
3) Далее она высчитывает значение хэш-функции H от RRB.
4) На опубликовании H(RRB) и, например, Random1 задача Алисы по вручению бита завершена.
Поскольку Боб не знает Random2, то вычислить бит b для него является проблемой – даже если он найдет некоторую последовательность (BobRandom), которая даст тот же хэш, что и RRB, Боб все равно не может быть уверен в том, что это именно та последовательность, что и у Алисы.
5) Для доказательства значения b, Алисе достаточно сообщить Random2. Боб повторяя ее действия и сравнивая результаты убеждается в истинности ее объявления.
Подменить свой бит Алиса не может, так как это означает, что ей нужно подобрать такую последовательность Random2’, что значение хэш-функции от RRB’ совпадет со значением хэш-функции от RRB. А ведь именно для защиты от таких вещей и используются хэш-функции, не так ли?
Преимуществом данного варианта алгоритма над первым состоит в том, что Боб выступает только некоторым пассивным запоминателем, что не требует от него ни действий по генерации случайных бит, ни возможности обратной связи с Алисой – сплошные упрощения.
Про данные алгоритмы можно отметить две важные детали: необязательно вручать на хранение именно один бит – можно вручать и некоторую последовательность, что является плюсом. А вот накладные расходы для передачи битов, являются минусом – чем больше длина случайных последовательностей, тем надежнее вручение.
Существуют и другие варианты алгоритмов вручения, но эти два самые наглядные и красивые, на мой взгляд.