OTR, криптография и нематематические задачки

Многие пользуются OTR-шифрованием. Протокол OTR взят за основу в известном мессенджере Signal, он же является самым популярным у пользователей Jabber-клиентов. И, хотя даже поверхностное описание протокола выглядит для неспециалистов непостижимо из-за математики, примечательно, что некоторые принципы работы OTR (и вообще криптографии) можно объяснить вовсе без математики.

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

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

Например, менеджеру Алисе сотрудник высказал жалобу на компанию, причём деликатного характера, попросив не раскрывать своего имени. Менеджер Боб рассказал Алисе, что получил такую же жалобу, и не может назвать имя сотрудника. Алиса и Боб хотят понять – им пожаловался один и тот же сотрудник или разные?

Читатель на этом моменте может прервать чтение на час-другой и попробовать придумать решение самостоятельно. Их, как минимум, два. Одно, более простое, подходит, если количество вариантов (сотрудников) не очень большое. Другое, посложнее, позволяет проверить совпадение вообще любого секрета, который можно записать – хоть набора букв.

Решение первое

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

Решение второе

Допустим, сотрудников в компании очень, очень много. Или задача такова, что секретом может быть не имя сотрудника, а набор букв. На самом деле, задачу можно адаптировать под проверку секрета, состоящего из набора вообще любых символов. Допустим, что секретом является набор букв русского алфавита (в нём 33 буквы).

Нужно взять 66 игральных карт: 33 красных и 33 чёрных. Разделить красные и чёрные, немного перетасовать каждую колоду (главное, чтобы карты не шли по порядку). Положить обе колоды на стол рубашками вверх так, чтобы было известно – вот эта колода с чёрными картами, а эта – с красными. Дальше манипуляции с картами проводят так, чтобы не видеть их лица.

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

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

Теперь все эти карты берутся стопкой. Часть из них лежит рубашкой вверх, часть – картинками. Теперь нужно посмотреть, есть ли в колоде хотя бы одна красная карта лицом вверх. Только сначала нужно перемешать карты, чтобы никто не понял, какая именно по счёту карта лежит определённым образом.

Можно, например, "снять" колоду примерно в середине (то есть разделить её на две части и поменять части местами). А потом немного перетасовать карты, не переворачивая их. Дальше карты снимаются по одной сверху колоды, кладутся на стол одна на другую, образуя новую колоду. Это делается до тех пор, пока колода не закончится или пока не будет замечена первая красная карта лицом вверх.

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

Если секретное слово может состоять не только из букв, это удлинняет проверку, но не делает её невозможной. Допустим, в слове могут быть буквы, цифры и некоторые символы. Собеседникам в таком случае нужно выписать все буквы, цифры и символы и присвоить им всем порядковые номера. А дальше действовать, как в случае выше.