В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 10. Генерация случайных чисел ных обстоятельств. Возможно, вам придется внести изменения в компоненты операционной системы или даже в само оборудование. Это еще один пример влияния безопасности на другие части системы. Сделайте все, что только в ваших силах. Удачи! 10.8 Выбор случайных элементов Наш генератор выдает последовательности случайных байтов. Иногда это именно то, что нужно. Существуют, однако, ситуации, когда нам требуется выбрать случайный элемент из множества элементов. Правильное выполне- ние этой задачи требует определенного внимания. Когда мы выбираем случайный элемент, то неявно предполагаем, что этот элемент выбирается равновероятным случайным образом из заданного мно- жества элементов (если только не указано другого вероятностного распре- деления). Это означает, что возможность выбора каждого элемента должна обладать в точности одной и той же вероятностью 6 . Реализовать данное усло- вие в программном обеспечении намного сложнее, чем кажется на первый взгляд. Пусть n — это число элементов множества, из которого требуется выбрать случайный элемент. В дальнейшем будем говорить только о том, как выбрать случайный элемент из диапазона 0 , 1 , . . . , n − 1 . Когда вы научитесь решать эту задачу, то сможете выбирать элементы из любого множества размером n . Если n = 0 , тогда у нас вообще нет элементов и мы получаем простую ошибку. Если n = 1 , у нас нет вариантов выбора и мы вновь получаем про- стой случай. Если n = 2 k , мы можем просто получить от генератора k бит случайных данных и интерпретировать их как простое число в диапазоне 0 , . . . , n − 1 . Полученное число будет случайным и выбранным равновероят- ным образом. (Возможно, вам придется получить от генератора целое коли- чество байт и отбросить несколько бит последнего байта, чтобы оставшееся число бит равнялось k , но реализовать такую схему очень просто.) Что делать, если n не является степенью двух? Некоторые программы вы- бирают случайное 32-битовое число и подсчитывают его значение по модулю n . К сожалению, использование данного алгоритма приводит к смещению ре- зультирующего распределения вероятностей. В качестве примера рассмотрим n = 5 и определим m := ¥ 2 32 / 5 ¦ . Если мы равновероятным образом выберем случайное 32-битовое число и подсчитаем его значение по модулю 5, то каж- дое из чисел 1, 2, 3 и 4 будет встречаться с вероятностью m/ 2 32 , а число 0 — 6 Если мы разрабатываем систему со 128-битовым уровнем безопасности, то можем поз- волить себе отклонение в 2 − 128 от равномерного распределения, но реализовать точное равномерное распределение все-таки проще. 10.8. Выбор случайных элементов 207 с вероятностью ( m + 1) / 2 32 . В данном случае отклонение от равномерного распределения вероятностей невелико, однако оно может быть и значитель- ным. Умному злоумышленнику не составит труда распознать отклонение за те 2 128 шагов, которые мы отводим ему на осуществление атаки. Чтобы правильно выбрать случайное число из произвольного диапазона, следует воспользоваться методом проб и ошибок. Например, чтобы сгенери- ровать случайное число в диапазоне 0 , . . . , 4 , мы вначале генерируем слу- чайное число в диапазоне 0 , . . . , 7 . Последняя операция возможна, поскольку 8 является степенью двух. Если полученное число окажется больше или рав- но 5, мы отбросим его и выберем новое число в диапазоне 0 , . . . , 7 . Так будет продолжаться до тех пор, пока полученное случайное число не попадет в же- лаемый диапазон 0 , . . . , 4 . Другими словами, мы генерируем случайное число, состоящее из нужного количества бит и отбрасываем все неподходящие числа. Ниже приведено более формальное описание того, как следует выбирать случайное число из диапазона 0 , . . . , n − 1 для n ≥ 2 . 1. Пусть k — наименьшее целое число, для которого 2 k ≥ n . 2. Воспользуйтесь генератором псевдослучайных чисел, чтобы получить k -битовое случайное число K . Это число будет находиться в диапазоне 0 , . . . , 2 k − 1 . Возможно, вам придется сгенерировать целое число байт и отбросить часть последнего байта, но это несложно реализовать. 3. Если K ≥ n , вернитесь к шагу 2. 4. Число K является требующимся результатом. Описанный алгоритм может оказаться не совсем эффективным. В худшем случае нам придется отбросить примерно половину попыток, поэтому попро- буем немного улучшить предложенное решение. Вернемся к примеру с n = 5 . Поскольку 2 32 − 1 делится на 5, мы можем выбрать случайное число из диа- пазона 0 , . . . , 2 32 − 2 и подсчитать значение полученного числа по модулю 5. Чтобы выбрать число из диапазона 0 , . . . , 2 32 − 2 , мы снова воспользуемся “неэффективным” методом проб и ошибок, однако на сей раз вероятность того, что полученное случайное число придется отбросить, очень мала. Общее правило состоит в том, чтобы выбрать удобное k , для которого 2 k ≥ n . Определим q := ¥ 2 k /n ¦ . Вначале выберем случайное число r в диапа- зоне 0 , . . . , nq − 1 , используя метод проб и ошибок. Когда подходящее r будет найдено, окончательный результат подсчитывается как ( r mod n ) . Мы не знаем другого способа сгенерировать равномерно распределенные случайные числа, размер которых в битах не является степенью двух, кроме отбрасывания от полученного результата нескольких случайных битов. Это не проблема. При наличии современного генератора псевдослучайных чисел проблем с нехваткой случайных битов быть не должно. |