Как проверить номер с Бобом, не зная Еву?

Вы должны проверить, что ваш друг, Боб, имеет ваш правильный номер телефона, но вы не можете спросить его напрямую. Вы должны написать вопрос на карточке и передать его Еве, которая передаст карточку Бобу и вернет вам ответ. Что вы должны написать на карточке, помимо вопроса, чтобы Боб мог закодировать сообщение, чтобы Ева не смогла прочитать ваш номер телефона?

Примечание. Этот вопрос находится в списке "вопросов об интервью Google". В результате в Интернете существует множество версий этого вопроса, и многие из них не имеют четких или даже правильных ответов.

Примечание 2: язвительный ответ на этот вопрос заключается в том, что Боб должен написать «позвони мне». Да, это очень умно, «вне коробки» и все такое, но не использует никаких техник в той области CS, где мы называем нашего героя «Боб» и его подслушивающего противника «Ева».

Обновление:
бонусные баллы за алгоритм, который вы и Боб могли бы разумно завершить вручную.

Обновление 2:
обратите внимание, что Бобу не нужно отправлять вам произвольное сообщение, он только подтверждает, что у него есть ваш правильный номер телефона, и Ева не может его расшифровать, что может привести или не привести к более простым решениям.

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

(Чтобы почтить давние традиции, две честные стороны, участвующие в разговоре, называются Алиса и Боб. В своем тексте вы сказали «вы». Мое настоящее имя не «Алиса», но я отвечу так же, как если бы вы написали что Алиса хочет проверить номер телефона Боба.)

Простой (но слабый) ответ - использовать хеш-функцию. Алиса пишет на карточке: «верните мне хэш SHA-256 вашего номера телефона». SHA-256 - это криптографическая хеш-функция, которая считается безопасной в отношении хеш-функций. Вычислять его вручную было бы утомительно, но все же выполнимо (это примерно 2500 32-битных операций, где каждая операция представляет собой сложение, сдвиг или поворот слова или битовую комбинацию битов; Боб должен быть в состоянии сделать это за день или так).

Что в этом слабого? SHA-256, являющаяся криптографической хеш-функцией, устойчива к «прообразам»: это означает, что при хеш-выходе очень трудно восстановить соответствующий вход (с этой проблемой сталкивается Ева). Однако «очень сложно» означает «самый простой метод - грубая сила: пробовать возможные входные данные, пока не будет найдено совпадение». Проблема в том, что грубая сила здесь проста: возможных телефонных номеров не так много (в Северной Америке это 10 цифр, то есть всего 10 миллиардов). Боб хочет делать что-то вручную, но мы не можем предположить, что Ева так ограничена. Базовый ПК может пробовать несколько миллионов хэшей SHA-256 в секунду, поэтому Ева будет выполнена менее чем за один час (менее 5 минут, если она использует графический процессор).

Это общая проблема: если Боб является детерминированным (то есть для данного сообщения от Алисы, он всегда будет возвращать один и тот же ответ), Ева может смоделировать его. А именно, Ева знает все о Бобе, кроме номера телефона, поэтому она фактически управляет 10 миллиардами Бобов, которые отличаются только предполагаемым номером телефона; и она ждет, пока один из виртуальных Бобов вернет то, что на самом деле вернул настоящий Боб. Недостаток затрагивает многие виды «умных» решений, включающих случайные одноразовые номера и симметричное шифрование и тому подобное. Это сильный недостаток, и его корень лежит в огромной разницы в вычислительной мощности между Евой и Бобом (теперь, если Боб также был компьютер как большой , как Ева, то он мог бы использовать медленныйхеш-функция за счет использования множества итераций; в этом и заключается суть хеширования пароля с помощью номера телефона вместо пароля; см. bcrypt, а также этот ответ ).

$e = 3$

• $n = pq$$p$$q$$n$$p-1$$q-1$

• $n$

• $n$$n$

• $m$$m^3 \mathrm{\ mod\ } n$

• $p$$q$$m$$m^3 \mathrm{\ mod\ } n$$m$

Для вычислений Алисы потребуется компьютер (то, что делает компьютер, всегда элементарно и выполнимо вручную, но компьютер чертовски быстр в этом, поэтому на практике «выполнимость» может занять слишком много времени; расшифровка RSA вручную займет много времени). недель).

(На самом деле мы могли бы ускорить вычисления вручную, используя шифрование McEliece , но тогда открытый ключ - то, что Алиса пишет на карте - был бы огромным, а карта - просто не годилась бы; Еве пришлось бы перевозить полную книгу цифр.)

Похоже на классическое приложение криптосистемы с открытым ключом, такое как RSA .

Вы отправляете свой открытый ключ, BoB шифрует номер вашего телефона из списка контактов и отправляет его вам.

Одна из самых простых вещей, которую вы можете сделать, - это обмен ключами Диффи-Хеллмана . Это не требует, чтобы вы установили ключи до того, как начнется обмен данными, поскольку он согласовывает их таким образом, что слушатели не могут сами получить ключ. Смотрите подробные статьи в Википедии .

$p$$g$$p$$g$$g^{a} \mathop{\mathrm{mod}} p$$a$

• $g^{b} \mathop{\mathrm{mod}} p$$b$
• $g^{a\,b} \mathop{\mathrm{mod}} p$

$g^{a} \mathop{\mathrm{mod}} p$$g^{b} \mathop{\mathrm{mod}} p$$g^{a\,b} \mathop{\mathrm{mod}} p$

Пока все реализовано правильно, и коммуникаторы и злоумышленник имеют в своем распоряжении примерно одинаковую вычислительную мощность, это безопасно.

Бобу не нужно отправлять сообщения, которые вы можете расшифровать. Он только должен доказать вам, что у него есть ваш номер телефона. Поэтому Cryptographic Hash Functions (одностороннее шифрование) предлагает альтернативу криптосистеме с открытым ключом. SHA-2 в настоящее время является популярным примером такой функции.

В этой стратегии вам никогда не придется расшифровывать сообщение Боба обратно к вам. Вы говорите Бобу, какую хеш-функцию вы бы хотели, чтобы он использовал, например: «Боб, пожалуйста, используйте SHA-2, чтобы зашифровать мой номер телефона и попросите Еву передать результат мне». Затем вы используете тот же алгоритм для хеширования своего номера телефона и проверяете, получаете ли вы тот же хеш, что и Боб. Крайне маловероятно, что два разных телефонных номера приведут к одному и тому же хешу, и вы сможете определить, есть ли у Боба правильный номер телефона.

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

Простое решение будет:

И Алиса, и Боб соглашаются в одном цвете. и это не проблема, если Ева знает это, мы назовем это P. Скажем, это желтый. Теперь Алиса и Боб случайным образом выбирают закрытый цвет, скажем «х». Алиса выбирает красный, а Боб выбирает синий. Теперь они смешивают их вместе с P. У Алисы теперь есть оранжевый, а у Боба зеленый. Алиса посылает оранжевый цвет Бобу, а Боб посылает свой зеленый цвет Алисе Ив, теперь он знает о желтом, оранжевом и зеленом, но Алиса также знает свой личный красный цвет, а Боб знает свой личный синий цвет, которого никто больше не знает. И Алиса, и Боб берут свои оригинальные личные цвета и добавляют их к тем, которые они только что обменяли. Теперь, если они смешают свои оригинальные частные цвета, красный и синий, в общий цвет, они оба получат один и тот же цвет, вроде коричневого или красного кирпича.

Вместо того, чтобы смешивать цвета вместе, вы можете использовать , так что p - это большое простое число, а g - примитивный корень из p, потому что если вы сделаете для любого x, результат (число от нуля до p - 1) одинаково вероятен для любого из них, поэтому существует примитивный корень. если p простое число 2n + 1 такое, что n также простое, то вы знаете, что 2 является примитивным корнем p (что означает, что вам не нужно беспокоиться о вычислении примитивного корня, что довольно сложно), таким образом, общий секрет = для Боба и для Алисы.$g^x\pmod{p}$$g^x\pmod{p}$Б $A^x\pmod{p}$$B^y\pmod{p}$

Я думаю, что вы можете написать что-то вроде этого на карте:

Число кратно 3,5 и 7 (например).

Есть ( - количество цифр) возможностей, и эта идея просто лишит законной силы несколько возможностей для того, кто знает об этом. Так что расшифровка Евой не произойдет.$(10)^n$$n$

Просто попросите Боба умножить число на 2 или 3 или что-нибудь еще и переписать это число с самим числом. Это выполнимо вручную и обратимо, если число известно. Нет ша, RSA или MD5. Просто математика.

Отправьте Бобу кодовое слово, зашифрованное вашим номером телефона; если он отправит вам кодовое слово обратно, вы знаете, что он имеет правильный номер.

Слабость в том, что Ева может симулировать Боба, поэтому просто пробуйте каждый номер телефона, пока она не получит тот, который дает какое-то кодовое слово, когда Боб вернулся.

Поэтому попросите Боба добавить очень большое случайное число к кодовому слову, а затем зашифровать его перед отправкой обратно вам. Это делает пространство поиска Eves настолько большим, насколько вы пожелаете.

Я напишу около 10 телефонных номеров на карточке, и среди них я позабочусь о том, чтобы мой номер был рядом с номером Боба, и я упомяну: «Эй, Боб, мой номер рядом с вашим номером, пожалуйста, проверьте» :)

Я думаю, что вопрос намного проще, чем все думают. Мы должны убедиться, что число, которое имеет Боб, является правильным (или, как могло бы быть, неправильным). Поскольку мы «проверяем», верен ли номер, можно предположить, что у Боба уже есть ваш номер. Поэтому нет необходимости отправлять Бобу свой номер в каком-то коде. Мой ответ будет: «Дорогой Боб, пожалуйста, позвони по моему номеру. Спасибо, Алиса»

попробуйте сыграть в трик, как это

решение1: если число 37, хэш-карта будет выглядеть так

01 07

15 12

25 20

31 36

49 43

53 50

60 62

72 72

85 82

91 94

и сделать то же самое для 10 цифр или даже больше, чтобы просто перепутать: P

решение2: или построить многочлен, в котором ваш номер становится другим уникальным числом

решение 3: напишите это в письме "чувак, позвони мне"

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

Я думаю, что мы можем сделать это, используя основные побитовые операции или, возможно, настроить его для работы с бумагой и карандашом. Если число Алисы, например, 663, то она может просто преобразовать число, используя эту методологию. Преобразуйте каждую цифру в эквивалентное двоичное представление, скажем, что это A 663-> 110 110 011, а затем переверните соответствующие биты для каждого отдельного числа, скажите это как B-> 011 011 110 Теперь сделайте A и B-> 010 010 010 Теперь отправьте этот номер на Боб и попросить сделать то же самое, если результат будет таким же, попросите его сказать «да» или «нет». В этом случае Ева не сможет декодировать число, и существует очень низкая вероятность того, что разные числа закончат одно и то же представление. Единственный способ, которым может догадаться Ева, - это записать все возможные комбинации, а затем попробовать их все, кроме того, чтобы учесть, что мы можем усложнить это, используя сдвиг влево или вправо и добавление фиктивных битов.

Пожалуйста, позвоните мне (меня зовут 1001001). Если вы не можете связаться со мной, пожалуйста, запишите номер вашего телефона и попросите Еву вернуть меня.

Объяснение: если Боб получил мой правильный #, он может связаться со мной, тогда я знаю, что это правильный #; если Боб не понял моего права, Ева тоже не сможет прочитать мой (правильный) номер телефона. Таким образом, я уже проверил, есть ли у моего друга Боба правильный номер телефона или нет.