|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Kabikov 2:5020/175.2 05 Mar 2003 15:35:22
To : Nick Poroshin
Subject : Хеш-функция с контролируемыми коллизиями
--------------------------------------------------------------------------------
Wed Mar 05 2003 12:37, Nick Poroshin wrote to Sergey Kabikov:
VV>>> Рабоче - крестьянский метод:
VV>>> Можно построить { x1 } = Encrypt( {x0} )
VV>>> Соответственно проверять if(Encrypt(x)) in { x1 }
VV>>> В качестве Encrypt использовать RSA или другой несимметричный
VV>>> криптоалгоритм.
SK>> Смеесси ? Отломают не шифрование, а последующую проверку на вхождение
SK>> в множество. Hе годится, я же на это намекал.
NP> Значит, надо его модифициpовать. Hазовём его РКМ-диффеp.
NP> 1. Есть Encrypt() - кpиптогpафическая хеш-функция с хоpошим
NP> pазмешиванием, пеpеводящая любой ключ в 256-битное число 2. Есть массив
NP> валидных ключей (стpоки т.е.) {x0}
NP> 3. Есть y0 -секpетное 32-битное число
NP> 4. Шифpуем нужный код y0-ым, желательно не xor-ом
NP> 5. Вычисляем массив 256-битных чисел {x1}={ Encrypt(x0)+y0 }, записываем
NP> его в пpогpамму
NP> 6. Искомая Хеш-функция = (MIN{ABS(Encrypt(x)-x1)})and 0xffffffff -этим
NP> значением и пытаемся pасшифpовывать код.
Попытка засчитывается ;-)
Аргумент против :
10 тысяч ключей (хотя бы) * 32 байта = 320 КБ ключевой информации. Многовато
будет. А 10 тысяч попыток расшифрования - долговато ;-) Разве что держать {x1}
уже отсортированным и по полученному Encrypt(x) искать ближайшее из x1
бинарным поиском.
И кроме того, такая постановка задачи плавно выходит за рамки эхотага. Я бы
предложил остановиться на терминологии модифицированной мной в предыдущем
письме задачи - поиск функции такой, что ее корнями... В той же формулировке
есть и п.4, касающийся именно компактности представления функции.
С уважением
Сергей
...с авторитетами приходится спорить. У них должность такая.(с)Лукьяненко
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
