Pull to refresh

Честный жребий

Reading time 2 min
Views 18K
Алиса, Боб, Кэрол и Дейв решили выбрать кому бежать за Клинским. Они бы могли спросить у Трэнта, который заслуживает доверия, но он уже в стельку пьяный лежит в соседней комнате. Тогда оставшиеся в сознании друзья решили придумать распределённый протокол для жребия.

Алиса шифрует все четыре имени своим ключом и в случайном порядке записывает на бумажке и показывает всем. Затем Боб берёт зашифрованные строки на этой бумажке, шифрует своим ключом и так же на новой бумажке записывает шифротексты в случайном порядке. После чего так делают Кэрол и Дейв.
Таким образом перед Алисой лежит листик с четырьмя зашифрованными строками, и при этом каждый из участников сортировал их как хотел.

Рисунок 1 — Схема передачи зашифрованных сообщений между участниками (записью Еа(s) обозначается шифрование ключом Алисы сообщения s)

Затем Алиса выбирает одну из этих строк.
После этого Дейв показывает каким ключом он шифровал строки и вся подвыпившая компания напряжённо расшифровывает строки ключом Дейва, убеждаясь что расшифрованные строки совпадают с теми что Кэрол дала Дейву и запоминая какую из них выбрала Алиса. То же происходит с ключами остальных участников. Наконец Алиса показывает свой ключ, и мучаясь от жажды, наши герои расшифровывают последний раз строки и видят какое имя было выбрано Алисой.

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

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

P. S. Протокол придуман во время обеда с коллегой и навеян книгой Брюса Шнайера «Прикладная криптография». И спасибо моей музе за помощь в подготовке статьи
Tags:
Hubs:
+30
Comments 71
Comments Comments 71

Articles