Black spy vs White spy

[Леша]

Задача с форума головоломок на sciteclibrary.
Есть шпионская сесть. Шпионы обмениваются информацией, посылая друг другу посылки, закрытые на замок.
У каждого шпиона есть свой уникальный секретный ключ своего цвета. Кроме того у всех остальных шпионов есть много замков того же цвета, которые можно открыть только этим единственным ключом. Например, у Белого шпиона есть один белый ключ, а у всех остальных шпионов есть много белых замков. Поэтому шпионы могут посылать Белому шпиону секретные сообщения, запирая их белыми замками, и быть уверенными, что только Белый шпион их может прочесть.
Теперь допустим Черный и Белый шпионы хотят обмениваться секретными сообщениями, но так, чтобы каждый из них знал, что получает сообщения от своего партнера, а не от кого-нибудь постороннего. Как им это сделать?

[Dendr]

Недостаточно данных.

1. Есть ли у Белого белые замки? (правда, это можно обойти таким образом, что Черный будет присылать ему их в неограниченном количестве)
2. Можно ли одну посылку закрывать на несколько замков таким образом, что открыть ее можно только открыв их все?

[Atson]

А метить замки можно?

[team55]

Посылки всегда доходят до адресата?
Если да, то алгоритм:

1 Блэк пишет записку с кодовым словом "ПРЕВЕД!", запирает её на чёрный замок, шлёт Уайту.
2 Уайт получает эту посылку, пишет записку с секретной инфой "ВЕРБЛЮДЫ ИДУТ НА СЕВЕР!", кладёт её и полученную посылку в большую посылку, запирает на чёрный замок, шлёт Блэку.
3 Блэк получает посылку в посылке с чёрным замком. Открывает обе, проверяет кодовое слово. Если слово - "ПРЕВЕД!", то про верблюдов писал Уайт. А если там "МЕДВЕД!" то верблюды идут нафиг...
4 Уайт получает письма от Блэка по такому же алгоритму.

[Slavaa]

Черный отправляет двойную посылку:
1. послание запертое на черный замок
2 его черный ключ запертый на белый замок
Белый открывает своим ключом белый замок и находит черный ключ(который может быть только у одного шпиона) и открывает им посылку с посланием

[team55]

Черный отправляет ... черный ключ

А отвечать Белому на письмо Чёрного как?

Черный и Белый шпионы хотят обмениваться секретными сообщениями

Просто отправить ему чёрный ключ по почте назад в незапертой посылке? Тогда как Чёрный подтвердит получение ключа?

[Леша]

1. Есть ли у Белого белые замки? (правда, это можно обойти таким образом, что Черный будет присылать ему их в неограниченном количестве)
2. Можно ли одну посылку закрывать на несколько замков таким образом, что открыть ее можно только открыв их все?

1. Да, белые замки есть у всех, включая Белого.
2. Пусть будет можно.

А метить замки можно?

В смысле писать что-то на них? Можно. Только шпионы на почте надписи на замках, как и на посылках, могут менять (если эти надписи не под замком).

Посылки всегда доходят до адресата?

Нет. Почта очень ненадежна. Другие шпионы их могут изымать, могут менять посылки на другие.
Но нам главное, не то чтобы наша посылка дошла, а чтобы, другие шпионы не послали бы сообщения от нашего имени.
Если моя посылка не дойдет, это полбеды. А если от моего имени прийдет посылка с сообщением: "снять с моего счета £1000", а я ее не посылал, это будет плохо.

1 Блэк пишет записку с кодовым словом "ПРЕВЕД!", запирает её на чёрный замок, шлёт Уайту.
2 Уайт получает эту посылку, пишет записку с секретной инфой "ВЕРБЛЮДЫ ИДУТ НА СЕВЕР!", кладёт её и полученную посылку в большую посылку, запирает на чёрный замок, шлёт Блэку.
3 Блэк получает посылку в посылке с чёрным замком. Открывает обе, проверяет кодовое слово. Если слово - "ПРЕВЕД!", то про верблюдов писал Уайт. А если там "МЕДВЕД!" то верблюды идут нафиг...
4 Уайт получает письма от Блэка по такому же алгоритму.

Этот алгоритм не будет работать, если Серый шпион перехватит первую посылку Черного (ПРЕВЕД!): он может от имени Белого написать Черному любое сообщение.

Черный отправляет двойную посылку:
1. послание запертое на черный замок
2 его черный ключ запертый на белый замок
Белый открывает своим ключом белый замок и находит черный ключ(который может быть только у одного шпиона) и открывает им посылку с посланием

Если у Белого будет ключ Черного, то он может послать кому-нибудь другому посылку от имени Черного. А этого не хотелось бы!

[team55]

1 Блэк пишет записку с кодовым словом "ПРЕВЕД!", запирает её на чёрный и на белый замок, шлёт Уайту.
2 Уайт получает эту посылку, снимает белый замок, оставляя посылку запертой на чёрный, пишет записку с секретной инфой "ВЕРБЛЮДЫ ИДУТ НА СЕВЕР!", кладёт её и полученную посылку в большую посылку, запирает на чёрный замок, шлёт Блэку.
3 Блэк получает посылку в посылке с чёрными замками. Открывает обе, проверяет кодовое слово. Если слово - "ПРЕВЕД!", то про верблюдов писал Уайт. А если там "МЕДВЕД!" то верблюды идут нафиг...
4 Уайт получает письма от Блэка по такому же алгоритму.

[Valentin]

Из объяснения алгоритмов шифрования с открытым ключом (к примеру RSA) на пальцах.
Клара хочет послать сообщение Карлу.
Она кладёт его в шкатулку, запирает её на замок, ключ от которого есть только у неё, и в таком виде отправляет Карлу.
Карл, получив шкатулку, вешает на неё ещё один замок, ключ от которого есть только у него, и отправляет назад Кларе.
Клара получает шкатулку, снимает с неё свой замок и опять отправляет Карлу.
Замок здесь выступает в роли public key, а ключ private key.

[Dendr]

Из объяснения алгоритмов шифрования с открытым ключом (к примеру RSA) на пальцах.
Клара хочет послать сообщение Карлу.
Она кладёт его в шкатулку, запирает её на замок, ключ от которого есть только у неё, и в таком виде отправляет Карлу.
Карл, получив шкатулку, вешает на неё ещё один замок, ключ от которого есть только у него, и отправляет назад Кларе.
Клара получает шкатулку, снимает с неё свой замок и опять отправляет Карлу.
Замок здесь выступает в роли public key, а ключ private key.

Не пойдет. Клара всегда уверена, что ее секретное сообщение может прочесть только Карл, и никто иной. А вот Карл никогда не будет уверен, что эта данная посылка от Клары.
Смотрим со стороны Карла:
1. Он получает посылку, на ней замок "Клара".
2. Вешает дополнительно замок "Карл", отправляет Кларе.
3. Он получает посылку с замком "Карл".

Внимание, вопрос - как он может быть уверен, что это та самая посылка, из пп. 1-2? Другие шпионы могли перехватить ее и сделать копию.

[Valentin]

1. Он получает посылку, на ней замок "Клара".
Внимание, вопрос - как он может быть уверен, что это та самая посылка, из пп. 1-2? Другие шпионы могли перехватить ее и сделать копию.

Ну для вящей надёжности начать можно с отправки Кларе пустой шкатулки закрытой её замком.

[Dendr]

И другие варианты - не катят.
Вообще, я думал так:
Допустим, существует такой алгоритм отправки сообщения от Белого к Черному.
Последним шагом алгоритма (очевидно!) будет получение Черным посылки (назовем ее посылка типа "А"), запертая на N черных замками. Внутри посылки типа "А" лежит ИКС плюс секретное сообщение.

Код: Выделить всё

Здесь и далее, ИКС - это произвольный набор всякой всячины: надписи на посылке, внутри нее, секретные вещи, записки, другие замки, другие посылки типа "Б", запертые на разные замки, а также посылки типа "А" и т.д. и т.п. 
Внутри каждой посылки типа "А", я напомню, снова лежит ИКС.

Обращаю внимание: ИКС - исчисляемое множество (или мета-исчисляемое мета-множество, не суть важно, но главное, что исчисляемое).

Теперь рассмотрим мегашпиона Серого, который узнал про то, что Белый и Черный решили переписываться. Он, разумеется, догадался, какой алгоритм эти двое используют. Поскольку он мегашпион, то он делает бесконечно большую работу за бесконечно короткое время. Иначе говоря, он может наделать любое количество поддельных посылок, внутри каждой будет ИКС - точнее, какой-то элемент множества ИКС - и может повторяться, чтобы запутать Черного. Мало того, будут и точные копии нужного Черному ИКСа. Ложные копии Черный отбросит, но, отобрав те, которые выглядят правильными, он увидит, что секретные сообщения в них разные, и выбрать истинное он никогда не сможет, потому что это была последняя посылка из алгоритма: если он будет переспрашивать Белого, то последней будет уже другая...

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

(продолжение следует...)

[Dendr]

Начал было писать длинное сообщение, но потом понял, что оно слишком длинное и бестолковое даже.
Поэтому только начало и конец оставлю (если что, остальное сохранил - по просьбам могу выложить)

Другая идея - по концепции простая, только объяснение сложное и жутко путаное. Используем историю и память шпионов и ветвление.

Итак, шпион Белый отправляет Черному письмо: "начинацию опираем!", и дальше - секретное сообщение А0. Все это в запертой на черный ключ посылке.
(дальше - мелким шрифтом, чтоб не корежить страницы)

Черный получает его письмо и, возможно, еще зиллион писем с подделкой (А1, А2...). Он их все собирает, дописывает каждой в конце свой ответ Б00 (Б10, Б20...) и отправляет Белому в одной посылке, запертой на белый ключ. Он пока не знает, какое из них - от Белого. То есть, еще раз - он отправтляет Белому пачку писем А0-Б00, А1-Б10, А2-Б20 в посылке (назовем эту пачку "альфа"). И он помнит, что это - "альфа".

Теперь смотрим, что получает Белый. Он получает от Черного "альфу". Он понимает, что только одно из них - настоящее, потому что он помнит, что писал-то А0! Поэтому Белый продолжает первое - А0-Б00-В00, а остальные перечеркивает цветными фломастерами и складывает всю пачку в посылку, запертую на черный замок. Но также, он получает еще зиллион посылок с другими пачками. Среди них (вы помните, что Серый - мегашпион и крайне трудолюбив до той степени, что перебирает все варианты), случайно, попадаются пачки, в которых есть письмо, в котором содержится сообщение А0, но продолжается оно, соответственно, как Б01, Б02 и т.д. Он не может знать, какая именно из пачек пришла от Черного, поэтому он поступает с каждой из них точно также, дописывая В001, В002... Он только выбрасывает в утиль (для страховки заперев на белые замки, чтобы никто не вскрыл) те посылки, в которых не было письма с А0.
В итоге, он отправляет Черному несколько посылок (упаковав их в одну большую), в каждой их которых пачки с письмами: (А0-Б00-В000, А1-Б10-*, А2-Б20-*, ...)+(А0-Б01-В001, ...)+(А0-Б02-В002, ...)+... (здесь * - зачеркивание). Назовем эту посылку - "бета".

Таким же образом действие продолжается.

Видно, в общем, что если возможности шпионов неограничены, то такая чехарда может продолжаться бесконечно: Серый, посылая каждому из двоих бесконечное количество ложных посылок, будет продолжать водить обоих за нос. Но если он может послать ограниченное количество посылок, то рано или поздно число совпадений уменьшится.
Допустим, "сигма" будет содержать всего три "ро". А получивший "сигму" (он же - отправлявший "ро" партнеру), выбирая из ложных "сигм", отправит уже только одну обратно, тем самым, узнав всю "правильную" переписку. Вот только с вложениями будет страшная путаница.

[Леша]

Среди них (вы помните, что Серый - мегашпион и крайне трудолюбив до той степени, что перебирает все варианты), случайно, попадаются пачки, в которых есть письмо, в котором содержится сообщение А0

Шпионы трудолюбивы, но они не могут послать посылок больше, чем атомов во вселенной.

[Леша]

1 Блэк пишет записку с кодовым словом "ПРЕВЕД!", запирает её на чёрный и на белый замок, шлёт Уайту.
2 Уайт получает эту посылку, снимает белый замок, оставляя посылку запертой на чёрный, пишет записку с секретной инфой "ВЕРБЛЮДЫ ИДУТ НА СЕВЕР!", кладёт её и полученную посылку в большую посылку, запирает на чёрный замок, шлёт Блэку.
3 Блэк получает посылку в посылке с чёрными замками. Открывает обе, проверяет кодовое слово. Если слово - "ПРЕВЕД!", то про верблюдов писал Уайт. А если там "МЕДВЕД!" то верблюды идут нафиг...
4 Уайт получает письма от Блэка по такому же алгоритму.

Хороший протокол! Хорошо бы еще и доказать, что он надежный.