Хеш-функция с контролируемыми коллизиями

From

Sergey Kabikov (2:5020/175.2)

To

Vladimir Vassilevsky ()

Date

2003-03-04T15:15:46Z

Area

RU.ALGORITHMS

From: "Sergey Kabikov" <kser@elsov.ru>

Tue Mar 04 2003 15:00, Vladimir Vassilevsky wrote to Sergey Kabikov:


 SK>> Необходимо построить функцию, y = f(x), где
 SK>>  0 <= x < 2^nx
 SK>>  0 <= y < 2^ny
 SK>>  ny < nx
 SK>> Т.е. мощность множества значений результата меньше мощности множества
 SK>> значений аргумента, т.н. функцию с коллизиями.
 VV>  Имеется наперед заданное множество ключей. Требуется функция F(ключ), 
 VV>  которая == 0 для любого из ключей, и гарантированно != 0 для всех прочих
 VV>  случаев. Не так ли? :) 
Ну вот, прятался, прятался - а меня сразу и вычислили ;-)
Почти так. За вычетом двух мелочей :
- не нулю (никаких сравнений с константой !), а некоему значению, которое
потом будет использовано как ключ для расшифрования. Ergo требуемое значение
у0 останется неизвестным, пока не получен хотя бы один валидный х.
- "изначальное" множество допустимых значений, входящих в {x0}, я
действительно могу выбрать произвольно. Например, "все простые числа в
диапазоне от .. до .., арктангенс логарифма пятой степени которых лежит в
диапазоне от 20 до 22 градусов" ;-) Но потом мне надо опеределенные значения
"поштучно" из этого множества вычеркивать. Вся эта затея - попытка найти
замену табличному blacklist-у, который должен блокировать краденые ключи.

 SK>> Дополнительное требование : по виду самой функции должно быть невозможно
 SK>> определить правильные у0 и {x0}, т.е. должно существовать множество
 SK>> приблизительно равномощных пар yi и {xi}, в идеале 2^(nx - ny) таких
 SK>> пар.  Поэтому типовой ответ
 SK>>   if x in {x0}
 SK>>   then y := y0
 SK>>   else y := random(2^ny)
 SK>> не проходит.
 VV>  Рабоче - крестьянский метод:
 VV>  Можно построить { x1 } = Encrypt( {x0} )
 VV>  Соответственно проверять if(Encrypt(x)) in { x1 }
 VV>  В качестве Encrypt использовать RSA или другой несимметричный
 VV> криптоалгоритм.
Смеесси ? Отломают не шифрование, а последующую проверку на вхождение в
множество. Не годится, я же на это намекал.

 SK>> Мой пока единственный вариант таков :
 VV>  Боюсь, что для произвольно заданного { x } решения нет и быть не может.
Если никто не подкинет идею - рожу ее сам. И никому не скажу. Вот ;-)

 VV> "Хотели как лучше - получилось как всегда.   (с) В. С. Черномырдин"
А у меня ориджин лучше ;-)

С уважением
Сергей

...с авторитетами приходится спорить. У них должность такая.(с)Лукьяненко

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)