Здравствуйте, FDSC, Вы писали:

FDS>Странно, я не нашёл (я нашёл только это

Автор: Relayer
Дата: 14.05.06

. Или это оно и есть?)

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

============================================================================
1. Прелюдия
Задача: есть множество (предварительно сгенерированных) серийных
номеров, необходимо построить хеш-таблицу, которая будет вычислять
принадлежность произвольной строки этому множеству.

Решение 1:
хеш функция H()
битовый массив B
if B[H(sn)] == 1 then sn is valid
недостаток — высокий уровень ложного срабатывания

Решение 2 (Probabilistic Spell Checker):
хеш функции H1()..Hn()
битовый массив B
if B[Hj(sn)] == 1 для всех 1<=j<=n then sn is valid

весь остальной материал относится к вариации на 2е решение.

2. Практика
на практике вполне легко добиться вероятности ложной идентификации
порядка 10^-8 (при мощности множества серийных номеров порядка 10^4).
такое решение позволяет нам получить ответ на вопрос валиден серийный
номер или нет. но оно имеет и отрицательную сторону — взломщик легко
может вычислить значения хешфункций для некотрого серийника и
установить соответствующие биты в "1" (т.е. пропачить хештаблицу).

усложним ему работу рассмотрим битовую строку:
HB = ( B[H1(sn)], B[H2(sn)], B[H3(sn)], ... B[Hn(sn)] )
мы требовали чтобы в случае валидного сериника все ее элементы были
равны "1". откажемся от этого при генерации хеш таблицы выберем
некоторую константу KEY (размереностью n бит). потребуем чтобы
валидный серийник выдавал HB == KEY (это приведет к некоторому
усложнению формирования хештаблицы B). что мы имеем в данном случае ?
взломщику не известна константа KEY (программа в дальнейшем может этой
константой расшифровывать блоки кода).

тестовый прогон дал такие результаты:
размер B = 2^18 бит (32 Кб)
кол-во хеш функций n = 32 (использовался SHA1)
SizeOf(HB) == SizeOf(KEY) == n == 32 бита
кол-во используемых бит в хештаблице B = 41% (остальные биты заполнены
мусором)
кол-во серийных номеров = 3868
общее кол-во перебраных кандидатов в серийные номера ~= 10^6
время ~= 5 мин (P3 1Gz)

3. блек лист
при дискредитации серийного номера его не такто просто вычекнуть из
хеш-таблицы, т.к. одни и теже биты могут использоваться несколькими
серийниками из списка. для возможности "вычеркивания" введем следующее
условие: некоторая (nfix <= n) часть битов в HB из таблицы B должна
принадлежать только этому серийнику и никаким другим. для вычеркивания
серийника из таблицы достаточно установить в другое состояние его
"уникальные" биты. это никоим образом не отразится на верификации других
серийниках.

был проведен тестовый прогон с nfix = 8. результаты практически те же
что и без "уникальных" битов.

4. детали
4.1 ничто не запрещает нам наложить более сложное условие чем
HB == KEY
например:
HB xor HH(sn) == KEY
здесь HH() — некотрая хешфункция
4.2 при формировании хештаблицы достаточно легко достичь ее коэф.
заполнения порядка 50%. дальше начинаются существенные пробуксовки
4.3 заполнение неиспользуемых элементов в таблице B "мусором"
существенно усложняет реверсирование схемы
4.4 нет особых ограничений на вид серийника. при тестировании я
использовал серийники из 9ти символов (буквы+цифры). мощность
множества серийников 2^(9*5) = 2^45
4.5 ложка дегтя при дискредитации ключа KEY, очень сложно
сформировать хештаблицу для тех же серийников и другого ключа.

5. финита ля комедия
утверждение 4.5 портит всю картину. но если мы выберем nfix == n (т.е.
потребуем чтобы все биты в строке HB были "уникальными") то смена
ключа будет полностью безболезненной.

тестовый прогон:
размер B = 2^18 бит (32 Кб)
кол-во хеш функций n = 32 (использовался SHA1)
nfix == n == 32
SizeOf(HB) == SizeOf(KEY) == n == 32 бита
кол-во используемых бит в хештаблице B = 25% (остальные биты заполнены
мусором)
кол-во серийных номеров = 2503
общее кол-во перебраных кандидатов в серийные номера ~= 2*10^7
время ~= 2 часа (P3 1Gz)

отмечу что увеличивая размер B можно практически во столько же раз
увеличить кол-во серийников которые можно "втиснуть" в хеш.
т.е. при 64 кб ~= 5*10^4 серийников
128 кб ~= 10^5 серийников
============================================================================

(c) на все это — мой. вобщем юзайте на здоровье