Любая подстрока хэша (md5, sha1) более "случайна", чем другая?

Question

Вот 3 примера md5 хэшей

$ md5 -s "1" && md5 -s "2" && md5 -s "3"
MD5 ("1") = c4ca4238a0b923820dcc509a6f75849b
MD5 ("2") = c81e728d9d4c2f636f067f89cc14862c
MD5 ("3") = eccbc87e4b5ce2fe28308fd9f2a7baf3

Скажем, я хотел взять 8 символов из любого хэша.Является ли начальная часть хэша более «случайной», чем конечная?средний?Или все подстроки одинаково "случайны"?

Answer 1

Мне было любопытно, поэтому я решил написать программу , чтобы проверить это.Вам понадобится Crypto ++ для компиляции кода.

Отказ от ответственности: Когда дело доходит до криптографии или даже математики в целом, я знаю, что достаточно, чтобы выстрелить себе в ногу.Итак, возьмите следующие результаты с небольшим количеством соли и имейте в виду, что у меня есть только поверхностное знание инструментов, которые я использую.

Я выбрал только три подстроки: первые 8 байтов, средние 8байтов, а последние 8 байтов.Короче говоря, они одинаково случайны.

Однако при использовании меньшего выборочного пространства кажется, что последние 8 битов немного более случайны.Чем больше пространство выборки, тем ближе все три подстроки приближаются к полной случайности.

---

1000 итераций:

First:  0.995914
Middle: 0.996546
Last:   0.998104

5000 итераций:

First:  0.998387
Middle: 0.998624
Last:   0.999501

10000 итераций:

First:  0.999614
Middle: 0.999457
Last:   1

30000 итераций:

First:  1
Middle: 1
Last:   1

---

"Случайность" измеряется классом Crypto ++ MaurerRandomnessTest .Для справки: исполняемый файл, скомпилированный из приведенного выше кода, имеет значение случайности 0.632411, а копия Маккета Шекспира, загруженная из Project Gutenburg, имеет значение случайности 0.566991.

Answer 2

Все подстроки хорошего хэша (и md5 достаточно хорошие, несмотря на то, что они криптографически небезопасны) одинаково случайны, так что да, возьмите любые понравившиеся биты из строки, они должны быть равномерно распределены.

Answer 3

Nitpick: «случайное» - это неправильное слово, используемое здесь, поскольку хеш-функции являются детерминированными.

Что касается ответа на то, что вы имеете в виду :), то желательным свойством хеш-функций является достижение лавинообразного эффекта : в основном, каждый бит ввода вызывает радикальные изменения в выводе. Таким образом, для хорошо спроектированного хэша каждая подстрока должна затрагиваться одинаково часто (« be as random »), как и любая другая.

Answer 4

Измерение случайности выходных данных хеш-функции может быть выполнено с использованием статистических тестов, выполненных на генераторах псевдослучайных чисел. Согласно Справочнику по прикладной криптографии §5.4.4 (образцы глав доступны бесплатно), существует пять основных тестов:

1. Частотный тест (монобитный тест)
2. Последовательный тест (двухбитный тест)
3. Покерный тест
4. Выполнение теста
5. Автокорреляционный тест

Тогда, конечно, есть универсальный статистический тест Маурера, о котором Куриге уже упоминал.