206
1/10 и 90 элементов случаются с вероятностью 1/100 имеет минимальную энтропию
log 10 ≈ 3.3. Минимальная энтропия распределения измеряет вероятность, с которой
атакующий может угадать значение, взятое из распределения; наилучшая стратегия
атакующего - угадать наиболее возможное значение, и поэтому, если распределение
имеет минимальную энтропию m, атакующий угадает правильно с вероятностью
максимум 2−m. Это объясняет, почему минимальная энтропия (в отличие от других
понятий энтропии) является полезной в нашем контексте. Расширение
минимальной
энтропии под названием вычислительная минимальная энтропия определяется, как
описано выше, кроме того, что от распределения требуется быть только вычислитель-
но неотличимым от распределения с данной минимальной энтропией. (Понятие вы-
числительно неотличимости формально определено в Разделе 7.8.)
Функция установления ключа обеспечивает способ получить единообразно рас-
пределенную строку из любого распределения с высокой (вычислительной) мини-
мальной энтропией. Не трудно заметить, что, если мы смоделируем хэш-функцию
H как случайного оракула, тогда H служит в качестве хорошей функции установле-
ния ключа. Рассмотрим неопределенность атакующего касательно H(X), где X взят
из распределения с минимальной энтропией m (с технической точки зрения нам
требуется, чтобы распределение было независимым от H). Каждый запрос атаку-
ющего к H может считаться поп ыткой «угадывания» значения X; по предположе-
нию о минимальной энтропии распределения атакующий, делающий q запросов
H будет опрашивать H(X) с вероятностью максимум q • 2−m.
Если атакующий не
делает
запросов по X к H, тогда H(X) является универсальной строкой.
Также возможно разработать функции установления ключа без необходимо-
сти опираться на модель со случайным оракулом с использованием ключевых
хэш-функций под названием (сильные) экстракторами. Ключ для экстрактора
должен быть универсальным, но необзязательно секретным. Один из стандар-
тов
для этого - это HKDF; см. ссылку в конце главы.
Достарыңызбен бөлісу: