Радужные столы - как выбрать исходный текст
Я выполняю задание, в котором мне дается 1000 дайджестов SHA1 и соответствующие им пароли (каждый из 24-битных или 6-тизначных цифр). Я должен построить радужную таблицу <2MB на диске, а в Java я вижу, что наличие цепочек длин> 192 делает процесс поиска слишком медленным.
Требование состоит в том, что эта радужная таблица должна обрабатывать как минимум 45% (или 450) хешей и возвращать пароль. Функция Редукции проста - взять из хеша 32 старших значащих бита (скажем, d0, d1, d2), добавить текущую длину цепочки (я иду от 0 до 191) только к d0 (как показано ниже), а затем:
d0 = (d0+i)%256 //8bits
d1 = d1%256 //8bits
d2 = d2%256 //8bits
Я уверен, что код (хэш и редукция) функции верны. Но таким образом я могу решить только около 250 хешей (точность 25%) для соответствующих им паролей.
Если я увеличу количество цепочек, то увижу, что решено уменьшение возвращений в соответствующем количестве хэшей. Как и в случае, если я удваиваю количество цепочек, точность не удваивается, но размер радужного стола уже>2 МБ (это как 8 МБ).
Для начальных слов - я пробовал просто начинать с 0 (полный диапазон будет от 0 до 2^24) и увеличивать на единицу, или я даже пытался сделать его случайным между этим диапазоном. Радужные таблицы не имеют петель, и хотя в функции сокращения возникают некоторые коллизии (на той же глубине, что и функции сокращения, как описано выше), я не принимаю цепочки, где конечная точка уже находится в таблице.
Буду признателен за любые советы о том, что я мог бы сделать, чтобы повысить точность до 45%.