Алиса, Боб, Кэрол и Дейв решили выбрать кому бежать за Клинским. Они бы могли спросить у Трэнта, который заслуживает доверия, но он уже в стельку пьяный лежит в соседней комнате. Тогда оставшиеся в сознании друзья решили придумать распределённый протокол для жребия.
Алиса шифрует все четыре имени своим ключом и в случайном порядке записывает на бумажке и показывает всем. Затем Боб берёт зашифрованные строки на этой бумажке, шифрует своим ключом и так же на новой бумажке записывает шифротексты в случайном порядке. Затем так делают Кэрол и Дейв.
Таким образом перед Алисой лежит листик с четырьмя зашифрованными строками, и при этом каждый из участников сортировал их как хотел.
Рисунок 1 — Схема передачи зашифрованных сообщений между участниками (записью Еа(s) обозначается шифрование ключом Алисы сообщения s)
Затем Алиса выбирает одну из этих строк.
После этого Дейв показывает каким ключом он шифровал строки и вся подвыпившая компания напряжённо расшифровывает строки ключом Дейва, убеждаясь что расшифрованные строки совпадают с теми что Кэрол дала Дейву и запоминая какую из них выбрала Алиса. То же происходит с ключами остальных участников. Наконец Алиса показывает свой ключ, и мучаясь от жажды, наши герои расшифровывают последний раз строки и видят какое имя было выбрано Алисой.
Всё конечно хорошо, но что если лиса-Алиса захочет всех обмануть, или безмерно уважающие Боба друзья захотят сговориться против него?
Казалось бы Алиса первая шифрует сообщения и сама же выбирает один из шифротекстов. Но при этом она не знает как его отсортировали другие участники, и зашифровали своими ключами. Поэтому перед ней просто встаёт слепой выбор между четыремя равнозначными строками.
В случае Боба даже если все участники за спиной Боба будут показывать друг другу свои ключи они всё равно не знают как зашифровал и отсортировал строки на своём шаге Боб и после его очереди перед ними также будет набор из непонятных шифротекстов, отсортированных в бобовском порядке.
P. S. Протокол придуман во время обеда с коллегой и навеян книгой Брюса Шнайера «Прикладная криптография»
Автор: oldHamtick
