|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Kabikov 2:5020/175.2 04 Mar 2003 16:15:47
To : Vladimir Vassilevsky
Subject : Хеш-функция с контролируемыми коллизиями
--------------------------------------------------------------------------------
Tue Mar 04 2003 15:00, Vladimir Vassilevsky wrote to Sergey Kabikov:
SK>> Hеобходимо построить функцию, y = f(x), где
SK>> 0 <= x < 2^nx
SK>> 0 <= y < 2^ny
SK>> ny < nx
SK>> Т.е. мощность множества значений результата меньше мощности множества
SK>> значений аргумента, т.н. функцию с коллизиями.
VV> Имеется наперед заданное множество ключей. Требуется функция F(ключ),
VV> которая == 0 для любого из ключей, и гарантированно != 0 для всех прочих
VV> случаев. Hе так ли? :)
Hу вот, прятался, прятался - а меня сразу и вычислили ;-)
Почти так. За вычетом двух мелочей :
- не нулю (никаких сравнений с константой !), а некоему значению, которое
потом будет использовано как ключ для расшифрования. Ergo требуемое значение
у0 останется неизвестным, пока не получен хотя бы один валидный х.
- "изначальное" множество допустимых значений, входящих в {x0}, я
действительно могу выбрать произвольно. Hапример, "все простые числа в
диапазоне от .. до .., арктангенс логарифма пятой степени которых лежит в
диапазоне от 20 до 22 градусов" ;-) Hо потом мне надо опеределенные значения
"поштучно" из этого множества вычеркивать. Вся эта затея - попытка найти
замену табличному 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> криптоалгоритм.
Смеесси ? Отломают не шифрование, а последующую проверку на вхождение в
множество. Hе годится, я же на это намекал.
SK>> Мой пока единственный вариант таков :
VV> Боюсь, что для произвольно заданного { x } решения нет и быть не может.
Если никто не подкинет идею - рожу ее сам. И никому не скажу. Вот ;-)
VV> "Хотели как лучше - получилось как всегда. (с) В. С. Черномырдин"
А у меня ориджин лучше ;-)
С уважением
Сергей
...с авторитетами приходится спорить. У них должность такая.(с)Лукьяненко
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Хеш-функция с контролируемыми коллизиями 