Материал: Проектирование генератора истинно случайных чисел для криптографических приложений
Проектирование генератора истинно случайных чисел для криптографических приложений
Проектирование
генератора истинно случайных чисел для криптографических приложений
И. Коряков
Введение
Во многих криптографических приложениях требуются большие объемы и большие скорости генерации качественной ключевой информации.
Создание высококачественных скоростных генераторов случайных чисел (ГСЧ) является непростой задачей, решение которой подразумевает выполнение ряда требований на всех этапах жизни такого генератора, начиная от формирования Технического задания и заканчивая его эксплуатацией на протяжении всего срока службы.
В данной работе приведена попытка формулировки
совокупности требований к высокопроизводительным генераторам случайных чисел,
порождающим истинно случайные ключевые данные для криптографических приложений.
1. Приводится пример проектирования ГСЧ.
Гипотеза о генераторе случайных чисел
Генератор случайных чисел (далее подразумевается генератор истинно случайных чисел, ГИСЧ) - это объект, вырабатывающий последовательность нулей и единиц, который обладает следующими двумя свойствами: случайностью и непредсказуемостью.
Под случайностью понимается равновероятное появление нулей и единиц на выходе такого генератора в независимости от его предыдущих или последующих значений.
Непредсказуемость ГИСЧ означает невозможность определить значение его выхода (или предсказать с вероятностью, отличной от 0.5) по известным предыдущим или последующим значениям.
В криптографических приложениях формируются наиболее жесткие критерии близости последовательностей к случайным, так как стойкость криптографических алгоритмов напрямую связана с качеством генератора.
Актуальным является вопрос об определении качества генератора случайных чисел, степени его соответствия идеалу.
В классических работах по генераторам случайных чисел [1,2,3] рассматривается проверка так называемой Нуль Гипотезы (H0). В данном случае она заключатся в утверждении, что тестируемый генератор случайный. Сопряженной с нуль гипотезой является Альтернативная Гипотеза (Ha), утверждающая, что генератор не случайный.
Для проверки этих гипотез обычно оценивают правдоподобие выборки случайных чисел, полученных с помощью конкретного генератора. Нуль гипотеза отвергается, если испытываемая выборка попадает в область малого правдоподобия. При этом возможны четыре варианта:
1) Гипотеза верна и она принимается
2) Гипотеза неверна и она отвергается
) Гипотеза верна и она отвергается (ошибка первого рода)
) Гипотеза неверна и она принимается (ошибка второго рода)
В данном случае опасными являются ошибки второго
рода, так как они позволяют неслучайному генератору успешно пройти тест на
случайность. Поэтому минимизация такой ошибки является одной из главных задач,
для которой известны эффективные решения [1,2,3].
. Методы предельного уменьшения ошибки второго
рода
Автор обращает внимание на подход, укоренившийся в области создания генераторов случайных чисел: вопросы проектирования генераторов и их тестирования рассматриваются раздельно, без их взаимной увязки. То есть, некто разрабатывает и затем предъявляет генератор СЧ, а, затем, некто пытается определить, действительно ли этот генератор является случайным, наблюдая только его выходные последовательности.
Вопрос проверки Нуль Гипотезы непростой, он даже не совсем четко определен с философской точки зрения. В частности, может быть предъявлен ГСЧ с отличными статистическими характеристиками выходных последовательностей, а затем вдруг выявится детерминированная составляющая этих последовательностей, не выявляемая статистическими тестами. Знание этой составляющей может, например, привести к снижению стойкости криптографического алгоритма.
Ниже предлагается рассмотрение проверки Нуль Гипотезы не только по оценке правдоподобия выборок, но и по множеству других факторов, влияющих на вероятность подтверждения Нуль Гипотезы и определяемых глобально, на протяжении срока жизни генератора, начиная от формирования принципов его построения и кончая определения качества функционирования в процессе генерации случайных чисел.
Декомпозиция Нуль Гипотезы заключается в замене одной гипотезы об истинности ГСЧ на несколько более просто проверяемых гипотез.
Например, гипотеза «данный генератор истинно случайный» заменяется рядом гипотез: «источник случайности имеет требуемые характеристики», «преобразование в битовую последовательность выполняется правильно», «источники питания в норме», «длинные серии встречаются с требуемой частотой» и т.д.
Более того, в состав композиции гипотез могут входить просто факты, требующие подтверждения. Например, «схема выравнивания статистических характеристик имеет теоретическое обоснование» или «схема выравнивания статистических характеристик глубоко изучена». Их можно не включать в состав каких либо регулярных тестов, но принимать на соответствующем этапе жизни ГИСЧ, как подтвержденный факт.
Наиболее естественно, по мнению автора,
представлять вероятность подтверждения Нуль Гипотезы произведением вероятностей
подтверждения составляющих гипотез:
.
Практически это будет означать оценку вероятностей каждой из составляющих гипотез, вычисление оценки вероятности подтверждения Нуль Гипотезы, сравнение ее с заданным порогом (уровнем значимости) и принятие решения о подтверждении Нуль Гипотезы. Если гипотеза подтверждена, то мы применяем данный генератор, в противном случае - не применяем и, возможно, выполняем действия по восстановлению свойств генератора, влияющих на подтверждение гипотез. Алгоритмы оценки вероятностей гипотез могут формировать «жесткое» решение: например, если значения всех питающих напряжений находятся внутри заданных пределов, то вероятность подтверждения соответствующей составляющей гипотезы оценивается как единица, иначе - как ноль.
Мероприятия по снижению ошибки второго рода необходимы на всех этапах создания и эксплуатации ГИСЧ, таких как:
– Проектирование ГИСЧ. На этом этапе доказательно обосновываются все технические и алгоритмические решения, все параметры и граничные значения контролируемых величин, проводится выбор элементной базы и создание макетов (образцов), над которыми выполняются все необходимые испытания и все возможные статистические тесты. Определяются испытания ГИСЧ, которые выполняются в процессе его разработки (лабораторные) и приемки Заказчиком (приемочные). Испытаниям подвергаются макет и опытный образец разработанного ГИСЧ. Цель этих испытаний - подтвердить правильность принятых технических решений и соответствие разработанного изделия требованиям, предъявляемым к нему Техническим заданием.
– Производство и приемка ГИСЧ. Данный уровень определяет испытания, проводимые над серийными экземплярами ГИСЧ в процессе производства, для определения их работоспособности. При этом используются следующие категории испытаний: приемо-сдаточные (применяются к каждому образцу ГИСЧ) и периодические. Цель данных испытаний - подтвердить соответствие технологического процесса производства ГИСЧ и качества используемых комплектующих Техническим условиям на Изделие. Периодические испытания ГИСЧ проводят с целью контроля качества изготовления, стабильности технологического регламента и подтверждения возможности дальнейшего изготовления ГИСЧ.
– Типовые испытания, которые проводят после внесения изменений в конструкцию ГИСЧ, его программное обеспечение или технологию изготовления, при замене материалов или элементов, которые могут повлиять на параметры и характеристики ГИСЧ, а также при появлении часто повторяющихся неисправностей. Цель типовых испытаний - подтвердить соответствие изделия, с внесенными в него изменениями, требованиям, предъявляемым к нему Техническим заданием.
– Регламентные работы. Цель испытаний при регламентных работах - проверка параметров и характеристик ГИСЧ на соответствие требованиям нормативных документов, а также анализ возможности их выхода за границы допустимых интервалов в период эксплуатации до следующих регламентных работ по причине старения элементов.
– Подготовка изделия к работе. Выполняется ряд проверок при включении, цель которых - предупредить возможность использования неисправного изделия.
– Непрерывный контроль функционирования. Такой контроль предназначен для выявления неисправности в процессе генерации случайных данных. Особенностями этого вида контроля является: обеспечение непрерывного контроля в течении всего времени работы ГИСЧ; выполнение процедуры контроля параллельно с работой основных функций генератора; минимальное время обнаружения неисправности; прекращение работы генератора при обнаружении неисправности. Если некоторые тесты не могут выполняться непрерывно, то допускается выполнять их перед этапом генерации порции случайных данных и после него.
Эти мероприятия будут рассмотрены ниже на
примере проектирования высококачественного ГИСЧ для криптографических
приложений.
. Структура ГИСЧ
Генератор истинно случайных чисел содержит в своем составе ряд обязательных элементов:
– Источник случайности;
– Усилитель шумового сигнала;
– Дискретизатор (дискретизатор обычно входит в состав АЦП, при применении компаратора следует учитывать, что стробируемый компаратор также выполняет функцию дискретизации);
– Аналого-цифровой преобразователь (АЦП, компаратор);
– Формирователь случайной последовательности;
– Декоррелятор (узел выравнивания статистических характеристик, может быть объединен с формирователем случайной последовательности);
– Подсистема контроля параметров и статистических характеристик;
– Интерфейс с оборудованием потребителя (криптографический аппарат, накопитель данных, компьютер).
Далее проводится попытка выбора и определения
параметров элементов ГИСЧ с возможно меньшим риском снижения вероятностей
подтверждения составляющих гипотез.
. Источник случайности
Источником случайности должен быть фундаментальный физический процесс, параметр которого теоретически не предсказуем, в частности, как указывает Крис Монро (Chris Monroe), «По настоящему случайными могут быть только квантовые процессы» [5].
Квантовые процессы и величины свойственны элементарным частицам, таким как протоны, электроны и фотоны света. Несмотря на то, что параметры этих частиц (положение в пространстве или величина энергии), могут быть определены, каждое конкретное значение параметра частица принимает только в тот момент, когда происходит измерение этой величины. Этот процесс носит подлинно случайный характер.
Тепловой (Джонсона-Найквиста) шум любого проводника порождается броуновским движением электронов в объеме проводника и такой параметр, как разность потенциалов на его концах, является суммой параметров очень большого числа частиц. Одновременное измерение значения параметра каждой из частиц или его предсказание не представляется технически возможным в любом обозримом будущем, поэтому напряжение теплового шума можно считать истинно случайной величиной, пригодной для генерации истинно случайных чисел. Следует указать на очень высокую степень приближения такого шума к идеальному «белому» шуму, так как его полоса ограничена только волновыми свойствами проводника и квантовыми эффектами при частотах порядка Терагерц.
Использование других источников случайности требует доказательного обоснования.
Например, существуют шумовые диоды, генерация шума в которых основана на флуктуациях тока, возникающих в процессе ударной ионизации при электрическом пробое полупроводникового перехода. Характер флуктуации определяет шумовые свойства диода. Так, флуктуации числа носителей заряда в стационарном лавинном процессе при токах пробоя порядка единиц мА обусловливают низкие уровни спектральной плотности мощности в области от десятков до тысяч МГц. Спонтанное прерывание лавинного процесса, наблюдаемое при невысоких токах от 1 до 1000 мкА, обусловливает более высокий уровень шума в области низких частот от десятков Гц до десятков МГц.
В радиоэлектронике шумовые диоды применяются в качестве источника широкополосного сигнала для проверки чувствительности приёмников и усилительных устройств, определения помехоустойчивости систем автоматического регулирования, а также в качестве источника калиброванного шума при измерении шумов и др.
Такие диоды также часто применяют в генераторах случайных чисел для криптографических приложений, что с точки зрения практики может быть допустимо. Однако следует понимать, что глубокие доказательства истинной случайности параметров такого диода пока неизвестны.
Таким образом, наиболее приемлемым источником
случайного сигнала является джонсоновское тепловое напряжение на концах
проводника, определяемое формулой Найквиста:
,
где k - постоянная Больцмана, k = 1.38 10-23 Дж/К; T - абсолютная температура в градусах Кельвина; R - активное сопротивление проводника; W - полоса частот, в которой производится измерение.
Например, на резисторе с
сопротивлением 200 Ом при температуре 300°К (27°С) в полосе частот 1 ГГц
выделяется напряжение шума 57.5 мкВ эфф., а на резисторе 100 кОм - 1.28 мВ эфф.
. Усиление шумового сигнала
Для дальнейшей обработки такой шумовой сигнал, как правило, требуется усилить. Необходимо учитывать, что в силу своей природы, шум Джонсона-Найквиста имеет нормальное распределение амплитуд и равномерную спектральную плотность мощности в определенном диапазоне частот. При усилении шумового сигнала мы не должны существенно исказить исходный шум, то есть, не добавить дополнительные шумы усилителя, природу которых может потребоваться дополнительно определять, и обеспечить минимальные искажения шума для сохранения распределения вероятности его значений и равномерности спектра в заданной полосе. Современные высококачественные малошумящие усилители с коэффициентом шума менее 2 дБ вполне подходят для этой цели.
При согласованном подключении
источника сигнала к идеальному усилителю, мощность на входе усилителя будет
определяться только шумовой температурой источника и полосой:
.
Эта величина для полосы 1 ГГц и температуры 300°К составляет 4.14 нВт.
Если температура входного
сопротивления соответствует температуре источника, то напряжение на
согласованном входе определяется как:
и, например, при сопротивлении источника и входа 200 Ом составит 39 мкВ.
Следует учитывать, что пик-фактор нормального шума для гарантированного отсутствия ограниченных отсчетов необходимо приравнивать к 5 или более, например, для АЦП с диапазоном входного напряжения 1 В шум резистора 200 Ом требуется усиливать не более, чем в 2500 раз (68 дБ).
Для уменьшения влияния внешних
наводок на источник шума и входы усилителя желательно применять
дифференциальное подключение источника к усилителю и помещать источник вместе с
усилителем и стабилизатором питания в электромагнитный экран.