Как найти себе подобного

Антон любит играть с резиновыми куклами, изготовители которых потрудились на славу, тщательно скопировав в натуральную величину определенные особенности анатомического строения женщины. А Борису нравится во всех красочных подробностях наблюдать за жизнью соседей из многоквартирного дома напротив при помощи современных оптических приспособлений. Оба тщательно скрывают свои пристрастия от родственников, друзей и коллег по работе, но очень хотели бы найти людей, которые разделяют их интересы.

Фирма “Совместные анонимные вычисления” готова оказать необходимую помощь Антону, Борису и им подобным в подборе таких же чудаков, как они сами. Сотрудники фирмы составили всеобъемлющий список всех человеческих чудачеств, каждое из которых снабжено уникальным идентификатором из семи цифр. Обратившись в фирму, Антон и Борис принимают участие в выполнении шагов некоторого протокола, после чего узнают, испытывают ли они склонность к одним и тем же чудачествам. При положительном ответе они смогут связаться друг с другом. Если ответ будет отрицательным, об их необычных пристрастиях не узнает никто, включая сотрудников “Совместных анонимных вычислений”.

Протокол выглядит так:

1. Используя однонаправленную функцию, Антон преобразует 7-значный

идентификатор своего чудачества в другое 7-значное число.

2. Трактуя полученное на шаге 1 число как телефонный номер, Борис

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

3. Антон сообщает в фирму, сколько раз Борис должен применять

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

4. С помощью однонаправленной функции Борис преобразует 7-значный

идентификатор своего чудачества столько раз, сколько это делал Антон, и получает 7-значное число, которое трактует как телефонный номер. Борис звонит по полученному им номеру и спрашивает, нет ли для него какой-либо информации.

Следует отметить, что Борис может предпринять атаку с выбранным открытым текстом. Узнав идентификаторы распространенных человеческих чудачеств, Борис будет по очереди перебирать их, применять к ним однонаправленную функцию и звонить по получающимся у него телефонным номерам. Поэтому необходимо сделать так, чтобы количество возможных чудачеств было достаточно велико, и подобного рода атака стала в результате неосуществимой.