Предыдущий пост Поделиться Следующий пост
Вопрос про математику
lex_kravetski

Где-то когда-то видел математический метод, с помощью которого можно проделать следующее. Каждому участнику некоторой группы выдан идентификатор. Некоторым образом из него делается другой идентификатор, по которому нельзя отследить исходный, однако можно убедится, что первый идентификатор, соответствующий второму, присутствует в числе выданных.

То есть, с одной стороны проверяется, что доступ легален – его получил кто-то из группы идентифицированных, с другой стороны – нельзя вычислить, кто именно получил доступ.

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

Кто-то ещё знает про этот метод?

Или, быть может, кто-то готов его сходу вывести? Было бы весьма интересно.

UPDATE

На всякий случай приведу более конкретный пример этой общей задачи.

Проводятся серии интернет-голосований (абстрагируемся сейчас от подписок на контент и прочее).

1. Каждому желающему выдают идентификационный номер (по паспортным данным, например, дабы гарантировать, что номер у гражданина будет один).

2. В каждом голосовании гражданин может проголосовать максимум один раз. Для этого как-то используется его номер. (Вопрос: как?).

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

4. Обрабатывающий результаты не может узнать, кто именно, как проголосовал (то есть, не способен связать идентификаторы, выданные по паспортным данным, с с экземпляром ответов на вопросы голосования).

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

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


Re: Ответ на вашу запись...

По сертификату устанавливается личность абонента (в терминологии апдейта статьи - проголосовавшего).

Re: Трипокод?

> Типа: http://en.wikipedia.org/wiki/Tripcode ? Или просто
> http://en.wikipedia.org/wiki/Hash_function ?

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

Обычное использование хэш-функций.

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

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

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

Я так понял, что задача хитрее: если клиент передаёт на сервер хэш, то нельзя определить имя клиента, но сервер может запомнить: "Заходил клиент с таким-то хэшем; он же заходил ещё в такие дни и делал вот это..."

Надо же, чтобы сервер мог определить, что клиент из числа авторизованных, но вовсе не мог понять, кто это именно из клиентов и что он ещё делал раньше на сервере.

Хвостом чую тему хэш-функций, но подожду математиков.

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

> 1. Каждому можно выдать по 10000000
> одноразовых ключей.

Нельзя. В том-то и фокус, что идентификатор должен быть один. А не миллион у каждого человека.

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

Вот в эту сторону уже можно копать. Хотелось бы однако более подробный алгоритм.

Lex, а зачем анонимность про покупке фильмов? Вопрос анонимности должен не беспокоить сервер с фильмами. Если пользователь хочет анонимности - это его проблема.

И пользователь будет решать эту проблему там, где ему это решение предложат - на левых серверах.

Это это... как его... асимметричное шифрование, как оно там... Методы RSA, Эль Гамаля, ещё всяких хватает.

Односторонняя функция.
F(X) -> Y

Зная X легко получить Y.

Зная Y
1. Сложно получить X
либо
2. Невозможно получить X

(1) - шифрование с открытым ключом (см. RSA, Elgamal), для получения Y по X без знания секретного ключа нужно решить трудоёмкую задачу (разложение числа простые на множители, либо дискретный логарифм)
(2) - хэш-функция (см. MD5, но можно (и лучше) использовать современные блоковые шифры - см. AES(Rijndael), RC6), получить Y по X невозможно за разумное время, кроме того, функция не биективна: одному Y соответствует множество X.

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

Re: Ответ на вашу запись...

> Односторонняя функция. F(X) -> Y

> Зная X легко получить Y.

> Зная Y 1. Сложно получить X либо 2.
> Невозможно получить X

Запомнить-то результаты функции на выданных идентификаторах как? Нам же не только невозможность обратного преобразования нужна, но ещё и доказательство истинности значения функции.

Можно, конечно, просто делать означенное преобразование при выдаче идентификатора, а его результат где-то сохранять, однако тут, - внутренний голос подсказывает, - анонимность под суровой угрозой.

Алгоритм создания открытого и секретного ключей</h3>
  1. Выбираются два случайных простых числа p\, и q\, заданного размера (например, 512 битов каждое).
  2. Вычисляется их произведение n=pq \,
  3. Вычисляется значение функция Эйлера от числа n:
    \varphi(n)=(p-1)(q-1).
  4. Выбирается целое число e\,, взаимно простое со значением функции \varphi(n) \,. Обычно в качестве e берут простые числа, содержащие небольшое количество единичных битов в двоичной записи, например, простые числа Ферма 17, 257, или 65537.
  5. Вычисляется число d \, мультипликативное обратное к числу e \, по модулю \varphi(n) \,, т.е число удовлетворяющее сравнению:
    d e \equiv  1\pmod{\varphi(n)}; т.е. de = 1 + k\varphi(n), где k любое натуральное число ( 0, 1, 2...).
  6. Пара P=(e,n) \, публикуется в качестве открытого ключа RSA (RSA public key).
  7. Пара S=(d,n) \, играет роль секретного ключа RSA (RSA secret key) и держится в секрете.

Число n\, называется модулем, а числа e\, и d\, — открытой и секретной экспонентами, соответственно.


Названия не знаю, но на подумать задача интересная. А у нас есть возможность раздать сразу 100 идентификаторов заранее известным клиентам, или раздача происходит исключительно по одному, по мере регистрации?

Re: Ответ на вашу запись...

В апдейте переформулировал задачу.

http://nature.web.ru/db/msg.html?mid=1157083&uri=node21.html

Глава про "неотслеживаемость".

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

Изменения в протоколе минимальны и упрощающи (поскольку манипулировать СУММАМИ не надо).

Клиент получает от банка электронную банкноту
Клиент передаёт электронную банкноту серверу
Сервер проверяет в банке подлинность электронной банкноты и, в случае подлинности, предоставляет клиенту доступ к контенту.

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

вот когда приходят с такими задачами всегда возникает один вопрос: а зачем? копнешь поглубже и оказывается это нафиг никому не нужно...

можно вообще обойтись без всяких функций и чегобы-то ни было...

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

Re: Ответ на вашу запись...

> вот когда приходят с такими задачами
> всегда возникает один вопрос: а зачем?
> копнешь поглубже и оказывается это
> нафиг никому не нужно...

Бывают задачи, которые просто интересны как задачи.

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

Доступ с логином будет связан. А логин - по паспорту выдали.

Тарлита давно уже не читаю.

Однако если вводить элементы прямой демократии, поставленная задача - прямо совсем про них. Интересный вариант.

Кстати, если получится сделать вот такой вот агрегат, это будет идеальная система для голосования на политических выборах. Киношные - нафиг. :?)

?

Log in

No account? Create an account