Введение в современную криптографию



Pdf көрінісі
бет152/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   148   149   150   151   152   153   154   155   ...   249
Криптография Катц

ОПРЕДЕЛЕНИЕ 5.12 Распределение вероятностей X имеет m бит минимальной 
энтропии, m если для каждого фиксированного значения x справедливо, что PrX←X 
[X = x] ≤ 2−m−наиболее возможный исход случается с вероятностью максимум 2−m. 
Единообразное распределение по набору размером S имеет минимальную эн-
тропию log S. Распределение, в котором один элемент случается с вероятностью 


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; см. ссылку в конце главы.


Достарыңызбен бөлісу:
1   ...   148   149   150   151   152   153   154   155   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет