|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Kabikov 2:5020/175.2 04 Mar 2003 09:30:36
To : All
Subject : Хеш-функция с контролируемыми коллизиями
--------------------------------------------------------------------------------
Hi All,
Hеобходимо построить функцию, y = f(x), где
0 <= x < 2^nx
0 <= y < 2^ny
ny < nx
Т.е. мощность множества значений результата меньше мощности множества значений
аргумента, т.н. функцию с коллизиями.
Основное требование к ней : для любого х, принадлежащего некоему заранее
заданному множеству {x0}, результат функции должен быть некой величиной у0, а
для любого х, не принадлежащего этому множеству - величиной, отличной от у0.
Дополнительное требование : по виду самой функции должно быть невозможно
определить правильные у0 и {x0}, т.е. должно существовать множество
приблизительно равномощных пар yi и {xi}, в идеале 2^(nx - ny) таких пар.
Поэтому типовой ответ
if x in {x0}
then y := y0
else y := random(2^ny)
не проходит.
Значения, составляющие множество {x0}, фиксированы заранее. Величину у0
допустимо определять на этапе "конструирования" функции.
В принципе, требования можно несколько ослабить :
- есть заданное множество {x0}, для любого х из которого f(x)=y0,
- есть заданное множество {x1}, для любого х из которого f(x)<>y0,
- для всех остальных значений х функция у может давать любое значение.
И еще одно пожелание - в идеале функция должна обладать свойствами
криптографического хеша : вычисление любого х из {x0} по известному у0 должно
быть вычислительно трудным (лучше всего - NP-полной задачей).
Мой пока единственный вариант таков :
- задаемся простым числом у0,
- вычисляем z = у0 + HОК {x0}
тогда искомая функция будет :
y := z modulo x
Доказательство для {x0} очевидно. Hедостатки - тоже. Если хотя бы одно число
из {x1} будет произведением сомножителей, уже входящих в HОК {x0} - алгоритм
не сработает.
Прошу помощи клуба ;-)
С уважением
Сергей
P.S. Я бы отправил это письмо в RU.CRYPT, но, похоже, все серьезные математики
из "там" уже здесь ;-)
...and the eyes in his head see the world spinning round... (c) Beatles
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
