Задачка с кредитной карточкой

[Шшок]

Некий Вася постоянно пользуется услугами некоей компании "Хрень" (допустим, интернет-провайдера) и ежемесячно осуществляет постоянный платеж этой компании посредством имеющейся у него кредитной карточки. Естественно, номер его кредитной карточки известен этой компании.
В один прекрасный день у Васи звонит телефон.
Вася: Алло.
Голос в трубке: Здравствуйте, это Вася?
Вася: Да.
Голос: Это говорит Иван из компании "Хрень". Вы - наш давний клиент, и мы хотим предоставить вам новый пакет наших услуг по очень выгодной цене (тут следует описание нового пакета, ценовое предложение и так далее).
Вася: Ну что же, звучит привлекательно, я согласен.
Голос: Вы готовы продолжать платить нам посредством вашей кредитной карточки?
Вася: Да, конечно.
Голос: Какой номер вашей карточки?
Вася: Стоп-стоп-стоп... А откуда я знаю, что вы - представитель компании "Хрень"? А вдруг вы - жулик, который хочет узнать номер моей карточки для каких-то неблагородных целей? Если вы - действительно из компании "Хрень", то у вас должен быть номер моей карточки. Скажите мне, какой номер моей карточки у вас фигурирует, и если все правильно, то мы заключим сделку.
Голос: У нас действительно есть номер вашей карточки. Но мы должны убедиться что вы - действительно Вася. А вдруг я, звоня Васе, просто ошибся номером, а вы - жулик, который хочет воспользоваться случайной возможностью и узнать от меня номер карточки ни в чем не повинного Васи?
Вася: Нет, так не пойдет. Я не знаю, кто вы. Диктуйте номер, который есть у вас, а я вам скажу, правильный он или нет.
Голос: Нет, не могу.

И получился замкнутый круг.

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

[Юляша]

Комбинация методов "контрольная сумма" и "пароль-отзыв" должна убедить Васю и Ивана, что они оба знают правильный номер, и при этом практически исключить выдачу полезной информации собеседнику.

Конкретный пример - чуть позже, постараюсь придумать похитрее)).

[Шшок]

Использование паролей-отзывов запрещено, так же как и контрольных сумм. Никакая другая информация, кроме непосредственно номера карточки, передаваться не должна.
И учтите еще вот что: и Иван и Вася не хотят передавать друг другу номер карточки даже частично. Иначе было бы примитивное решение: Вася диктует Ивану первые 8 цифр номера, а Иван Васе в ответ - последние 8 цифр (или наоборот).
Считаем, что Иван и Вася не хотят передать друг другу НИ ОДНОЙ ЦИФРЫ В НОМЕРЕ КАРТОЧКИ.

[Юляша]

Что значит запрещено?

Можно ли, например, складывать цифры номера и передавать результат?

[Шшок]

Что значит запрещено?

Можно ли, например, складывать цифры номера и передавать результат?

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

[Шшок]

Давайте формализуем вопрос.

Иван должен передать информацию Васе так, чтобы удовлетворялись следующие условия:

1. Если Вася - это действительно Вася, то он по этой информации должен убедиться в том, что Ивану известен точный 16-значный номер карточки.
2. Если Вася - это не Вася, а жулик, то он не должен иметь возможности по полученной информации определить НИ ОДНОЙ ЦИФРЫ НОМЕРА.
3. После этого Вася должен каким-то образом доказать Ивану, что он - действительно Вася.

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

[Юляша]

Нет, конечно. Суммирование - это пример.

Мысль у меня примерно такая (в общих терминах, не до конца продумано, но что-то такое). №№№ - номер карты


N=F(№№№)

M=G(N, №№№)

P=H(M, №№№)

И -> В: F
В -> И: N, G
И -> В: M, H
В- > И: P

Зная номер карты, каждый способен проверить правильность сообщенного результата. В итоге, возникает уверенность, что каждый из собеседников знает номер карты. Естественно, по функции не должно быть возможности вычислить аргумент (отсюда - "контрольная сумма"). Какими должны быть функции F, G, H, я пока представляю лишь приблизительно; но, например, они могут сводить 16-значный номер карты к четырехзначному числу, что исключит угадывание.

[Шшок]

Известное мне решение основано на совершенно другом принципе.
Можешь для собственного удовольствия попробовать довести свое решение до конца.
Мне бы хотелось увидеть абсолютно другое решение, простое и практичное.

[Dendr]

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

Ну и понятно, что нормальные люди не будут устраивать телефонное соревнование по устному счету. Васе проще сказать: "Мужик, хватит валять дурака. Я лучше с работы отпрошусь пораньше и к вам в офис лично заеду."

[Шшок]

Вот тут уже что-то просвечивает....
Разумеется, это НЕ идея о том, чтобы отпросиццо с работы. Все вопросы надо разрулить по телефону.
Подсказка заключается в том, что телефонный разговор, позволяющий обоим собеседникам убедиться в искренности намерений, будет очень даже коротким. И не понадобится ни калькулятор, ни арифмометр...
И еще одна подсказка: если бы этот разговор смог прослушать кто-то третий, то он по окончании разговора знал бы точный номер карточки.

[Леша]

Каждый говорит, четность (или остаток деления на 5) половины цифр.
Это нормальное решение? Или никто не должен получать никакой информации о номере карточки.

[Аскет]

1. Если Вася - это действительно Вася, то он по этой информации должен убедиться в том, что Ивану известен точный 16-значный номер карточки.
2. Если Вася - это не Вася, а жулик, то он не должен иметь возможности по полученной информации определить НИ ОДНОЙ ЦИФРЫ НОМЕРА.
3. После этого Вася должен каким-то образом доказать Ивану, что он - действительно Вася.

И еще одна подсказка: если бы этот разговор смог прослушать кто-то третий, то он по окончании разговора знал бы точный номер карточки.

Слишком много подсказок.
Понятно, что Иван сообщает нечто, уникальное, связанное с номером карты (почему тут не подходит, например сумма некоторых числе в номере, или результат деления, не ясно). В ответ, если предложенное Иваном верно, Вася тупо называет номер карты.

По большому счету не вижу проблем с сообщением НОМЕРА карты, это открытая инфа обычно, нет?
Так же не понимаю, что мешает Васе перезвонить в офис компании Хрень по известному телефону, и спросить данного Ивана?

[Шшок]

Понятно, что Иван сообщает нечто, уникальное, связанное с номером карты (почему тут не подходит, например сумма некоторых числе в номере, или результат деления, не ясно). В ответ, если предложенное Иваном верно, Вася тупо называет номер карты.

По большому счету не вижу проблем с сообщением НОМЕРА карты, это открытая инфа обычно, нет?
Так же не понимаю, что мешает Васе перезвонить в офис компании Хрень по известному телефону, и спросить данного Ивана?

Давайте все-таки не искать обходных путей типа перезвонить в Хрень и попросить Ивана. Давайте попробуем решить задачу в том виде, в каком я ее формализовал несколькими постами выше.
Действительно, Иван сообщает нечто УНИКАЛЬНОЕ, причем настолько уникальное, что у Васи не остается никаких сомнений в том, что Ивану известен весь номер карты. Сумма некоторых чисел, даже если она сообщена правильно, еще ни о чем не говорит. Для большей убедительности Ивану придется назвать не одну какую-то сумму, а несколько. Васе для проверки правильности названных сумм может потребоваться калькулятор и время. А я уже сказал, что разговор очень короткий и не требует никаких вычислений.
Правильным в посте Аскета является только то, что после того, как Иван сообщит Васе нечто уникальное, Вася действительно тупо называет номер карты, поскольку Васе уже нечего опасаться - у него уже нет ни малейших сомнений, что Ивану этот номер известен.
Итак, какую же инфу должен сообщить Иван Васе?

[Katrine]

Представитель Хрени позвонил по конкретному номеру и мало того вышел на Васю (что подтвердилось в начале разговора), зачем Вася должен что-то доказывать?

Ну могу все-таки предположить такой вариант раскладки.
пусть Вася имеет номер мобильного телефона, где его последние цифры АБС
И номер кредитной карточки, где ее последние цифры ЭЮЯ.

Он в уме составляет уравнения, где из ЭЮЯ делает АБС, и если представитель решает их, то звонит на сотовый Васе.
(я так предполагаю разговор ведется по домашнему телефону).

[Dendr]

Действительно, Иван сообщает нечто УНИКАЛЬНОЕ, причем настолько уникальное, что у Васи не остается никаких сомнений в том, что Ивану известен весь номер карты.

CSC?
Правда, мошенник (лже-Иван) может просто угадать. Шанс 0,1%, но все-таки. Тогда Вася обречен.