Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| ОПРЕДЕЛЕНИЕ 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; см. ссылку в конце главы. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|