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

34
например, просто подбрасывая правильную монету. Однако такой подход не 
очень удобен и не масштабен.
Современная генерация случайных чисел осуществляется в два этапа. Сначала 
собирается массив данных с высокой энтропией. (Для наших целей формальное 
определение энтропии не требуется, достаточно считать энтропию степенью 
непредсказуемости.) Затем эти данные с высокой энтропией обрабатываются 
с целью получения последовательности почти по-настоящему произвольных 
битов. Этот второй этап необходим, поскольку данные с высокой энтропией не 
обязательно будут единообразны.
На первом этапе требуется некоторый источник непредсказуемых данных. 
Такие данные могут быть получены несколькими способами. Один из методов 
основывается на внешнем воздействии, например, простоях между сетевыми 
событиями, времени доступа к жесткому диску, нажатии клавиш или передви-
жении мыши пользователем, и т.д . Такие данные, скорее всего, будут далеки от 
единообразия, но если будет произведено достаточно измерений, то получен-
ный массив данных будет обладать достаточной энтропией. Также используют-
ся более сложные подходы, которые, согласно замыслу, включают в себя гене-
рацию случайных чисел, более тесно связанную с системой на уровне жесткого 
диска. В их основе лежат такие физические явления, как тепловые помехи, 
дробовый шум или радиоактивный распад. Недавно компания Intel (Интел) 
разработала процессор, включающий в себя цифровой генератор случайных 
чисел на микросхеме чипа и дающий специальные инструкции для доступа к 
полученным случайным битам (после их надлежащей обработки и получения 
по-настоящему произвольных битов, о которой расскажем далее). 
Обработка, необходимая для «уравнивания» данных с высокой энтропией, с 
целью получения (почти) единообразных битов нетривиальна и кратко описы-
вается в разделе 5.6.4. Здесь же мы только приведем простой пример, чтобы 
дать представление о том, что было сделано. Представьте, что наш массив с 
высокой энтропией был получен из последовательности подбрасываний несим-
метричной монеты, где вероятность выпадения «орла» равняется p, а вероят-
ность выпадения «решки» равняется 1−p. (Однако мы допускаем, что результат 
любого подбрасывания монеты не зависит от всех остальных подбрасываний. 
На практике такое допущение обычно неверно.) Результат 1 000 таких под-
брасываний монеты, конечно, будет обладать высокой энтропией, но будет не 
совсем единообразным. Мы можем получить равномерное распределение, рас-
сматривая подбрасывания монеты по парам: если мы видим, что за «орлом» 
следует «решка», то мы выводим «0», а если за «решкой» следует «орел», то 
«1». (Если мы видим, что подряд выпали два «орла» или две «решки», то мы 
ничего не выводим, а просто переходим к следующей паре.) Вероятность того, 

35
что результатом любой пары будет «0», составляет p• (1−p), что в точности со-
ответствует вероятности того, что результатом любой пары будет «1». Таким 
образом, мы получаем равномерно распределенные выходные данные из на-
шего первоначального массива с высокой энтропией.
Необходимо крайне внимательно относиться к получению случайных битов, 
поскольку использование неэффективных генераторов случайных чисел часто 
может привести к тому, что хорошая криптосистема окажется уязвимой к атаке. 
Следует использовать генератор случайных чисел, специально разработанный 
для криптографического использования, а не генератор случайных чисел «об-
щего назначения», не подходящий для криптографического использования. В 
частности, функция rand() в языке C в стандартной библиотеке stdlib.h не явля-
ется криптографически надежной , а ее использование для криптографических 
параметров может иметь катастрофические последствия.

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: