Проектирование генератора истинно случайных чисел для криптографических приложений

Размещено на http://www.allbest.ru/

Проектирование генератора истинно случайных чисел для криптографических приложений

И. Коряков

Введение

Во многих криптографических приложениях требуются большие объемы и большие скорости генерации качественной ключевой информации.

Создание высококачественных скоростных генераторов случайных чисел (ГСЧ) является непростой задачей, решение которой подразумевает выполнение ряда требований на всех этапах жизни такого генератора, начиная от формирования Технического задания и заканчивая его эксплуатацией на протяжении всего срока службы.

В данной работе приведена попытка формулировки совокупности требований к высокопроизводительным генераторам случайных чисел, порождающим истинно случайные ключевые данные для криптографических приложений.

1. Приводится пример проектирования ГСЧ.

Гипотеза о генераторе случайных чисел

Генератор случайных чисел (далее подразумевается генератор истинно случайных чисел, ГИСЧ) - это объект, вырабатывающий последовательность нулей и единиц, который обладает следующими двумя свойствами: случайностью и непредсказуемостью.

Под случайностью понимается равновероятное появление нулей и единиц на выходе такого генератора в независимости от его предыдущих или последующих значений.

Непредсказуемость ГИСЧ означает невозможность определить значение его выхода (или предсказать с вероятностью, отличной от 0.5) по известным предыдущим или последующим значениям.

В криптографических приложениях формируются наиболее жесткие критерии близости последовательностей к случайным, так как стойкость криптографических алгоритмов напрямую связана с качеством генератора.

Актуальным является вопрос об определении качества генератора случайных чисел, степени его соответствия идеалу.

В классических работах по генераторам случайных чисел [1,2,3] рассматривается проверка так называемой Нуль Гипотезы (H₀). В данном случае она заключатся в утверждении, что тестируемый генератор случайный. Сопряженной с нуль гипотезой является Альтернативная Гипотеза (H_a), утверждающая, что генератор не случайный.

Для проверки этих гипотез обычно оценивают правдоподобие выборки случайных чисел, полученных с помощью конкретного генератора. Нуль гипотеза отвергается, если испытываемая выборка попадает в область малого правдоподобия. При этом возможны четыре варианта:

1) Гипотеза верна и она принимается

2) Гипотеза неверна и она отвергается

3) Гипотеза верна и она отвергается (ошибка первого рода)

4) Гипотеза неверна и она принимается (ошибка второго рода)

В данном случае опасными являются ошибки второго рода, так как они позволяют неслучайному генератору успешно пройти тест на случайность. Поэтому минимизация такой ошибки является одной из главных задач, для которой известны эффективные решения [1,2,3].

2. Методы предельного уменьшения ошибки второго рода

Автор обращает внимание на подход, укоренившийся в области создания генераторов случайных чисел: вопросы проектирования генераторов и их тестирования рассматриваются раздельно, без их взаимной увязки. То есть, некто разрабатывает и затем предъявляет генератор СЧ, а, затем, некто пытается определить, действительно ли этот генератор является случайным, наблюдая только его выходные последовательности.

Вопрос проверки Нуль Гипотезы непростой, он даже не совсем четко определен с философской точки зрения. В частности, может быть предъявлен ГСЧ с отличными статистическими характеристиками выходных последовательностей, а затем вдруг выявится детерминированная составляющая этих последовательностей, не выявляемая статистическими тестами. Знание этой составляющей может, например, привести к снижению стойкости криптографического алгоритма.

Ниже предлагается рассмотрение проверки Нуль Гипотезы не только по оценке правдоподобия выборок, но и по множеству других факторов, влияющих на вероятность подтверждения Нуль Гипотезы и определяемых глобально, на протяжении срока жизни генератора, начиная от формирования принципов его построения и кончая определения качества функционирования в процессе генерации случайных чисел.

Декомпозиция Нуль Гипотезы заключается в замене одной гипотезы об истинности ГСЧ на несколько более просто проверяемых гипотез.

Например, гипотеза «данный генератор истинно случайный» заменяется рядом гипотез: «источник случайности имеет требуемые характеристики», «преобразование в битовую последовательность выполняется правильно», «источники питания в норме», «длинные серии встречаются с требуемой частотой» и т.д.

Более того, в состав композиции гипотез могут входить просто факты, требующие подтверждения. Например, «схема выравнивания статистических характеристик имеет теоретическое обоснование» или «схема выравнивания статистических характеристик глубоко изучена». Их можно не включать в состав каких либо регулярных тестов, но принимать на соответствующем этапе жизни ГИСЧ, как подтвержденный факт.

Наиболее естественно, по мнению автора, представлять вероятность подтверждения Нуль Гипотезы произведением вероятностей подтверждения составляющих гипотез:

.

Практически это будет означать оценку вероятностей каждой из составляющих гипотез, вычисление оценки вероятности подтверждения Нуль Гипотезы, сравнение ее с заданным порогом (уровнем значимости) и принятие решения о подтверждении Нуль Гипотезы. Если гипотеза подтверждена, то мы применяем данный генератор, в противном случае - не применяем и, возможно, выполняем действия по восстановлению свойств генератора, влияющих на подтверждение гипотез. Алгоритмы оценки вероятностей гипотез могут формировать «жесткое» решение: например, если значения всех питающих напряжений находятся внутри заданных пределов, то вероятность подтверждения соответствующей составляющей гипотезы оценивается как единица, иначе - как ноль.

Мероприятия по снижению ошибки второго рода необходимы на всех этапах создания и эксплуатации ГИСЧ, таких как:

– Проектирование ГИСЧ. На этом этапе доказательно обосновываются все технические и алгоритмические решения, все параметры и граничные значения контролируемых величин, проводится выбор элементной базы и создание макетов (образцов), над которыми выполняются все необходимые испытания и все возможные статистические тесты. Определяются испытания ГИСЧ, которые выполняются в процессе его разработки (лабораторные) и приемки Заказчиком (приемочные). Испытаниям подвергаются макет и опытный образец разработанного ГИСЧ. Цель этих испытаний - подтвердить правильность принятых технических решений и соответствие разработанного изделия требованиям, предъявляемым к нему Техническим заданием.

– Производство и приемка ГИСЧ. Данный уровень определяет испытания, проводимые над серийными экземплярами ГИСЧ в процессе производства, для определения их работоспособности. При этом используются следующие категории испытаний: приемо-сдаточные (применяются к каждому образцу ГИСЧ) и периодические. Цель данных испытаний - подтвердить соответствие технологического процесса производства ГИСЧ и качества используемых комплектующих Техническим условиям на Изделие. Периодические испытания ГИСЧ проводят с целью контроля качества изготовления, стабильности технологического регламента и подтверждения возможности дальнейшего изготовления ГИСЧ.

– Типовые испытания, которые проводят после внесения изменений в конструкцию ГИСЧ, его программное обеспечение или технологию изготовления, при замене материалов или элементов, которые могут повлиять на параметры и характеристики ГИСЧ, а также при появлении часто повторяющихся неисправностей. Цель типовых испытаний - подтвердить соответствие изделия, с внесенными в него изменениями, требованиям, предъявляемым к нему Техническим заданием.

– Регламентные работы. Цель испытаний при регламентных работах - проверка параметров и характеристик ГИСЧ на соответствие требованиям нормативных документов, а также анализ возможности их выхода за границы допустимых интервалов в период эксплуатации до следующих регламентных работ по причине старения элементов.

– Подготовка изделия к работе. Выполняется ряд проверок при включении, цель которых - предупредить возможность использования неисправного изделия.

– Непрерывный контроль функционирования. Такой контроль предназначен для выявления неисправности в процессе генерации случайных данных. Особенностями этого вида контроля является: обеспечение непрерывного контроля в течении всего времени работы ГИСЧ; выполнение процедуры контроля параллельно с работой основных функций генератора; минимальное время обнаружения неисправности; прекращение работы генератора при обнаружении неисправности. Если некоторые тесты не могут выполняться непрерывно, то допускается выполнять их перед этапом генерации порции случайных данных и после него.

Эти мероприятия будут рассмотрены ниже на примере проектирования высококачественного ГИСЧ для криптографических приложений.

3. Структура ГИСЧ

Генератор истинно случайных чисел содержит в своем составе ряд обязательных элементов:

– Источник случайности;

– Усилитель шумового сигнала;

– Дискретизатор (дискретизатор обычно входит в состав АЦП, при применении компаратора следует учитывать, что стробируемый компаратор также выполняет функцию дискретизации);

– Аналого-цифровой преобразователь (АЦП, компаратор);

– Формирователь случайной последовательности;

– Декоррелятор (узел выравнивания статистических характеристик, может быть объединен с формирователем случайной последовательности);

– Подсистема контроля параметров и статистических характеристик;

– Интерфейс с оборудованием потребителя (криптографический аппарат, накопитель данных, компьютер).

Далее проводится попытка выбора и определения параметров элементов ГИСЧ с возможно меньшим риском снижения вероятностей подтверждения составляющих гипотез.

4. Источник случайности

Источником случайности должен быть фундаментальный физический процесс, параметр которого теоретически не предсказуем, в частности, как указывает Крис Монро (Chris Monroe), «По настоящему случайными могут быть только квантовые процессы» [5].

Квантовые процессы и величины свойственны элементарным частицам, таким как протоны, электроны и фотоны света. Несмотря на то, что параметры этих частиц (положение в пространстве или величина энергии), могут быть определены, каждое конкретное значение параметра частица принимает только в тот момент, когда происходит измерение этой величины. Этот процесс носит подлинно случайный характер.

Тепловой (Джонсона-Найквиста) шум любого проводника порождается броуновским движением электронов в объеме проводника и такой параметр, как разность потенциалов на его концах, является суммой параметров очень большого числа частиц. Одновременное измерение значения параметра каждой из частиц или его предсказание не представляется технически возможным в любом обозримом будущем, поэтому напряжение теплового шума можно считать истинно случайной величиной, пригодной для генерации истинно случайных чисел. Следует указать на очень высокую степень приближения такого шума к идеальному «белому» шуму, так как его полоса ограничена только волновыми свойствами проводника и квантовыми эффектами при частотах порядка Терагерц.

Использование других источников случайности требует доказательного обоснования.

Например, существуют шумовые диоды, генерация шума в которых основана на флуктуациях тока, возникающих в процессе ударной ионизации при электрическом пробое полупроводникового перехода. Характер флуктуации определяет шумовые свойства диода. Так, флуктуации числа носителей заряда в стационарном лавинном процессе при токах пробоя порядка единиц мА обусловливают низкие уровни спектральной плотности мощности в области от десятков до тысяч МГц. Спонтанное прерывание лавинного процесса, наблюдаемое при невысоких токах от 1 до 1000 мкА, обусловливает более высокий уровень шума в области низких частот от десятков Гц до десятков МГц.

В радиоэлектронике шумовые диоды применяются в качестве источника широкополосного сигнала для проверки чувствительности приёмников и усилительных устройств, определения помехоустойчивости систем автоматического регулирования, а также в качестве источника калиброванного шума при измерении шумов и др.

Такие диоды также часто применяют в генераторах случайных чисел для криптографических приложений, что с точки зрения практики может быть допустимо. Однако следует понимать, что глубокие доказательства истинной случайности параметров такого диода пока неизвестны.

Таким образом, наиболее приемлемым источником случайного сигнала является джонсоновское тепловое напряжение на концах проводника, определяемое формулой Найквиста:

,

где k - постоянная Больцмана, k = 1.38 10-²³ Дж/К; T - абсолютная температура в градусах Кельвина; R - активное сопротивление проводника; W - полоса частот, в которой производится измерение.

Например, на резисторе с сопротивлением 200 Ом при температуре 300°К (27°С) в полосе частот 1 ГГц выделяется напряжение шума 57.5 мкВ эфф., а на резисторе 100 кОм - 1.28 мВ эфф.

5. Усиление шумового сигнала

Для дальнейшей обработки такой шумовой сигнал, как правило, требуется усилить. Необходимо учитывать, что в силу своей природы, шум Джонсона-Найквиста имеет нормальное распределение амплитуд и равномерную спектральную плотность мощности в определенном диапазоне частот. При усилении шумового сигнала мы не должны существенно исказить исходный шум, то есть, не добавить дополнительные шумы усилителя, природу которых может потребоваться дополнительно определять, и обеспечить минимальные искажения шума для сохранения распределения вероятности его значений и равномерности спектра в заданной полосе. Современные высококачественные малошумящие усилители с коэффициентом шума менее 2 дБ вполне подходят для этой цели.

При согласованном подключении источника сигнала к идеальному усилителю, мощность на входе усилителя будет определяться только шумовой температурой источника и полосой:

.

Эта величина для полосы 1 ГГц и температуры 300°К составляет 4.14 нВт.

Если температура входного сопротивления соответствует температуре источника, то напряжение на согласованном входе определяется как:

и, например, при сопротивлении источника и входа 200 Ом составит 39 мкВ.

Следует учитывать, что пик-фактор нормального шума для гарантированного отсутствия ограниченных отсчетов необходимо приравнивать к 5 или более, например, для АЦП с диапазоном входного напряжения 1 В шум резистора 200 Ом требуется усиливать не более, чем в 2500 раз (68 дБ).

Для согласованного входа подключение резистора - источника шума эквивалентно уменьшению сопротивления в цепи входа в 2 раза, что, соответственно, в корень из двух раз уменьшает напряжение шума, вырабатываемое парой резистор - эквивалентное сопротивление входа. Поэтому, если вход усилителя имеет встроенные цепи согласования, то внешний резистор подключать не требуется. Тогда для вышеприведенного примера усиление должно составлять не более 1820 (65 дБ).

Для уменьшения влияния внешних наводок на источник шума и входы усилителя желательно применять дифференциальное подключение источника к усилителю и помещать источник вместе с усилителем и стабилизатором питания в электромагнитный экран.

6. Дискретизация по времени

Одним из этапов преобразования аналогового сигнала в числовую последовательность является дискретизация по времени. Дискретизация порождает отражения в частотной области, причем для получения равномерного спектра после дискретизации шумового сигнала достаточно использовать аналоговый фильтр Найквиста типа «корень из приподнятого косинуса», частотная характеристика которого для параметра = 1.0 и частоты дискретизации f_s определяется как

.

На рисунке 1 приведен вид характеристики H(f). Если составляющие исходного шума на частотах f_s/2 + df и f_s/2 - df независимы, то при отражении в результате дискретизации они суммируются как корень из суммы квадратов и дают в результате единицу:

,

поскольку .

Рисунок 1 - Фильтр Найквиста «корень из приподнятого косинуса»

Существует еще один класс шумов, так называемый фликер-шум, спектральная плотность мощности которого обратно-пропорциональна частоте. Такой шум присущ любым электрическим и полупроводниковым элементам, в том числе резисторам. Как показано на рисунке 2, присутствие фликкер-шума может искажать равномерность спектра в низкочастотной области, что означает появление статистических зависимостей в шумовом сигнале.

Рисунок 2 - Спектр шумового сигнала с фликер-шумом

Современные АЦП имеют полосу входного сигнала, существенно превышающую частоту дискретизации и могут работать с сигналами, спектр которых размещен не только в 1-й зоне Найквиста. Для борьбы с фликер-шумом можно использовать фильтр Найквиста, нулевая частота которого смещена на величину f_s. Частотная характеристика такого фильтра приведена на рисунке 3.

Рисунок 3 - Фильтр шумового сигнала в 1 - 4 зонах Найквиста

Если же ширина спектра исходного шума, а также полоса входного сигнала АЦП превышают частоту дискретизации в 5 и более раз, то аналоговый фильтр можно не применять - шум нормализуется и приобретает равномерную спектральную плотность мощности за счет большого числа независимых слагаемых (в соответствии с центральной предельной теоремой).

На рисунке 4 приведен спектр дискретизированного шумового сигнала резистора, сформированный фильтром Найквиста для 1 - 4 зон. Неравномерность в полосе 0 - 24 Мгц составляет всего ± 0.12 дБ, что соответствует практически равномерной спектральной плотности мощности.

Рисунок 4 - Реальный спектр с разрешением 0.1 дБ дискретизированного шума резистора

7. Аналого-цифровое преобразование

Для того, чтобы получить случайную последовательность из аналогового шума, дискретизированный сигнал подвергается аналого-цифровому преобразованию при помощи одноразрядного (компаратор) или многоразрядного АЦП.

Многоразрядный АЦП

Случайный процесс с симметричным распределением и равномерным спектром формирует на выходе идеального многоразрядного АЦП двоичный код, каждый разряд которого представляет собой случайную двоичную последовательность, независимую от последовательностей других разрядов.

Реальный АЦП имеет погрешности, из которых наибольший вклад в распределение вероятностей нулей (единиц) вносит напряжение смещение нуля U_cm. На рисунке 5 показано, как U_cm влияет на смещение вероятности нуля P₀ отдельных разрядов АЦП.

Рисунок 5 - Влияние смещения входа АЦП на смещение вероятности Р₀ на выходах АЦП

При малых величинах напряжения U_cm смещение вероятности P_cm можно представить произведением плотности f(U) на величину U_cm в точке смены состояния соответствующего разряда (заштрихованные прямоугольники). Например, для старшего разряда Q_n-1 весь диапазон входных напряжений АЦП (обычно от 0 В до U_ref) представляется двумя областями значений Q_n-1 = 1, U < U_ref /2 и Q_n-1 = 0, U >= U_ref /2. При наличии смещения за счет увеличения доли единиц вероятность P₀ уменьшится на величину:

,

где = U_ref /5 при оговоренном выше значении пик-фактора, равном 5. Например, при U_ref = 1.0 В и U_cm = 10 мВ, смещение вероятности P_cm старшего разряда составит 1.99 %.

Для младших разрядов, за счет увеличения числа точек, в которых происходит смена состояний с разными значениями смещения, общая вероятность P_cm уменьшается и становится минимальной для самого младшего разряда АЦП.

Таким образом, использование младших разрядов АЦП является предпочтительным для получения случайной последовательности.

Смещение АЦП может быть устранено схемой компенсации смещения на основе регулятора с обратной связью, выравнивающего частоты состояний «0» и «1» на выходе старшего разряда АЦП. Постоянная времени такого регулятора должна быть достаточно большой, чтобы не вносить зависимости между битами последовательности, например, эквивалентной 10⁶ бит. Требуется учитывать наличие задержки в регуляторе при переходе в рабочий режим после включения ГИСЧ.

Компаратор

Компаратор идентичен старшему разряду АЦП. Применение компаратора без схемы компенсации смещения крайне нежелательно. В соответствии со структурой рекомендуемого ниже формирователя первичной последовательности, применение компараторов требует, как минимум, 2 генератора аналогового шума и 2 компаратора.

8. Формирователь случайной последовательности

Формирование случайной последовательности предполагает преобразование ряда первичных последовательностей в одну, строго несмещенную и некоррелированную последовательность.

Существенной проблемой здесь является возможное наличие смещения, автокорреляции и взаимной корреляции в первичных последовательностях.

Смещение

При суммировании по модулю 2 нескольких независимых последовательностей, смещенных на величину e, результирующее смещение быстро уменьшается с ростом числа последовательностей k :

.

Например, сумма 4-х последовательностей, смещенных на e = 0.01, дает результирующее смещение 0.8х10-⁷. Причем, одинаковые смещения - это худший случай, реальное результирующее смещение будет уменьшаться еще быстрее.

Для идеализации смещения может быть применен Т-триггер [3] - простейший автомат, изменяющий свое состояние на противоположное при единичном значении входа. Значение выхода q Т-триггера определяется как противоположное ему значение ^q в случае, если значение входа x изменяется из «0» в «1»:

.

Основным свойством последовательности q является равенство вероятностей значений «0» и «1». При этом искажается распределение вероятностей серий нулей и единиц. В частности, вероятность серий «0» или «1» длины 1 становится равной нулю, длины 2 - 1/4, длины 3 - 1/8, и т. д.

Для идеализации смещения можно использовать две независимые случайные но, возможно, смещенные последовательности x и y, одна из которых, x, преобразуется Т-триггером в последовательность q, которая складывается по модулю 2 с последовательностью y:

.

В результате выходная последовательность z сохраняет свойство несмещенности последовательности q и исходное распределение вероятностей серий нулей и единиц последовательности y.

В качестве x и y могут быть использованы выходы отдельных разрядов АЦП.

9. Корреляция

Автокорреляционная функция r характеризует степень взаимозависимости между элементами последовательности s, разнесенными на n позиций:

.

Для вычисления функции r в битовой последовательности, содержащей значения «0» и «1» значения «0» заменяются на «-1». Тогда нулевые значения математического ожидания автокорреляционной функции для n = 1,2,… будут означать отсутствие связи между битами последовательности, разнесенными на соответствующие расстояния.

Корреляция или взаимная корреляция между двумя последовательностями s₁ и s₂ определяется как

.

Точно так же, как и для автокорреляционной функции, нулевые значения математического ожидания взаимной корреляционной функции для n = 0,1,2,… будут означать отсутствие связи между s₁ и s₂.

Практическая оценка отсутствия корреляционных зависимостей заключается в вычислении коэффициентов r(n) или r₁₂(n) для 10..20 значений n на последовательностях с достаточно большой длиной N и оценки правдоподобия нулевого математического ожидания этих коэффициентов.

Ожидание каждого из отсчетов автокорреляционной (кроме нулевого) и взаимнокорреляционной функции для идеальных последовательностей равно нулю.

По аналогии с частотным тестом [2] для каждого значения корреляционной функции можно вычислить P-значение:

.

P-значение является вероятностью появления на выходе некоего идеального генератора последовательности, с большим модулем коэффициента корреляции для задержки n, чем у тестируемой последовательности. Таким образом, гипотеза о том, что последовательность на выходе разряда АЦП или последовательности на двух разрядах АЦП независимы, принимается, если Р > , где - выбранный уровень значимости. P-значение вычисляется для всех n, затем определяется пропорция удачных тестов. Например, для = 0.01 и 63-х значений n, пропорция составляет 0.962 и гипотеза будет подтвержденной, если из 63 отсчетов АКФ Р > будет не менее, чем для 61.

Среднее значение автокорреляции, вычисленное по i = 1..(n -1) для определенного разряда АЦП, характеризует смещение вероятности нулей в этом разряде. В таблице 1 приведены средние значения автокорреляции и пропорции P-значений конкретного образца 10-ти разрядного АЦП типа AD9215BRU-65 с диапазоном напряжения 1 В при частоте дискретизации 48 МГц и эффективном значении напряжения шумового сигнала 40 мВ. Как видно, наибольшее смещение вероятности имеют два младших и три старших разряда, а у разрядов d2, d3, d4, и d5 - очень малое смещение и они имеют пропорцию P-значений, выше порога, равного 0.962 для = 0.01. Похожие результаты получены для всех испытанных АЦП.

Таблица 1. Средние значения автокорреляции и пропорции P-значений

Разряд АЦП	d0	d1	d2	d3	d4	d5	d6	d7	d8	d9
Среднее значение r , %	9.084	2.482	-0.004	0.003	0.009	0.009	0.149	0.678	0.692	0.692
Пропорция P-значений	0	0	0.968	0.968	0.984	0.984	0.015	0.015	0.015	0.015

Средние значения взаимнокорреляционной функции для АЦП AD9215BRU-65 приведены в таблице 2.

Таблица 2. Средние значения взаимнокорреляционной функции , %

Разряд АЦП	d1	d2	d3	d4	d5	d6	d7	d8	d9
d0	4.391	-0.109	0.032	-0.080	0.098	1.221	2.574	2.601	2.601
d1		-0.062	0.013	-0.030	0.064	0.655	1.374	1.389	1.389
d2			0.002	0.020	0.002	0.017	0.033	0.033	0.033
d3				0.005	0.009	0.074	0.139	0.140	0.140
d4					-0.005	0.112	0.225	0.228	0.228
d5						0.317	0.565	0.569	0.569
d6							1.556	1.563	1.563
d7								2.249	2.249
d8									2.260

Анализ значений взаимнокорреляционной функции показывает, что по пропорции P-значений разряды АЦП слабо коррелированы при n 0 и существенно коррелированы при n = 0. В таблице 3 приведены значения взаимнокорреляционной функции для n = 0.

Таблица 3. Значения взаимнокорреляционной функции для n = 0

Разряд АЦП	d1	d2	d3	d4	d5	d6	d7	d8	d9
d0	-0.28805	0.00175	0.00173	-0.00103	0.00006	0.01276	0.02724	0.02753	0.02753
d1		-0.00134	-0.00444	0.00684	0.00401	0.01754	0.03554	0.03590	0.03590
d2			-0.00143	0.00970	0.00390	0.02150	0.04321	0.04364	0.04364
d3				0.00259	0.00456	0.04120	0.08325	0.08409	0.08409
d4					-0.00132	0.08018	0.16167	0.16315	0.16315
d5						0.19501	0.34509	0.34725	0.34725
d6							0.79051	0.79285	0.79285
d7								0.99765	0.99765
d8									1.00000

10. Преобразователь плотности распределения отсчетов АЦП

Для формирования последовательности случайных бит мы можем выбрать в качестве первичных последовательностей разряды АЦП, имеющие наименьшие значения взаимнокорреляционной функции при n = 0. Например, по данным таблицы 3, это могут быть разряды d2, d3, d4, и d5.

Существует метод получения первичных последовательностей с очень хорошей взаимнокорреляционной функцией из отсчетов АЦП. Метод заключается в преобразовании произвольного распределения вероятности отсчетов случайной величины в равномерное распределение.

Преобразование выполняется при помощи Таблицы Равномерного Преобразования (ТРП), формируемой следующим образом.

По большому числу 2^N отсчетов M-разрядного АЦП накапливается гистограмма из 2^M элементов. Номер элемента гистограммы - это значение выхода АЦП, а накапливается в элементе число отсчетов с соответствующим значением, появившихся на выходе АЦП.

Далее строится функция распределения из 2^M элементов путем последовательного накопления суммы элементов гистограммы. Таблица ТРП размером 2^M х Q заполняется значениями функция распределения, усеченными до Q разрядов.

Вероятность появления каждого из значений выхода Qt будет одинакова при неизменном распределении отсчетов АЦП. В свою очередь, если отсчеты сигнала на входе АЦП независимы, то отдельные разряды q_i выхода Qt будут также независимыми.

Ниже приведен псевдокод алгоритма формирования таблицы Qt :

G:array[1..2^M]of integer;

Qt:array[1..2^M]of byte;

for i=1 to 2^M do G[i]:=0;

for i=1 to 2^N do inc(G[ADC]);

P=0;

for i=1 to 2^M do

P=P+G[i];

Qt[i]=(P >> (N-Q))& 2^Q-1;

end for;

Например, для M = 10, N = 24 и Q = 8 в таблице 4 приведены значения взаимнокорреляционной функции при n = 0 после преобразования распределения отсчетов АЦП в равномерное распределение.

Таблица 4. Значения взаимнокорреляционной функции после преобразования распределения

Выходной разряд ТРП	q1	q2	q3	q4	q5	q6	q7
q0	-0.00450	0.00082	-0.00087	-0.00048	0.00045	-0.00215	0.00189
q1		-0.00120	0.00130	-0.00281	-0.00213	-0.00041	0.00075
q2			0.00011	0.00049	0.00055	-0.00003	-0.00046
q3				-0.00024	-0.00075	-0.00028	-0.00008
q4					0.00058	0.00020	0.00069
q5						0.00046	-0.00012
q6							-0.00006

12. Декоррелятор

Несмотря на достаточно малые значения корреляции между разрядами выхода таблицы ТРП, они превышают значения 0,0005625, которое соответствует порогу P-значения для = 0.01. По этой причине требуется выравнивание статистических характеристик первичной последовательности или декорреляция.

Статистические характеристики, неотличимые от идеальных, дает умножение или деление последовательности на некоторый полином. В частности, деление на неприводимый полином осуществляют скремблеры, широко применяемые в технике связи, например скремблер, соответствующий рекомендации ITU-T V.34 с полиномом 1+х⁵+х²³. Аппаратная реализация скремблера достаточно проста - это сдвигающий регистр, последовательный вход которого складывается по модулю 2 с 5-м и 23-м разрядами регистра.

При умножении на полином (которому соответствует дескремблер) с целью декорреляции последовательности, полином не обязательно должен быть неприводимым, достаточно, чтобы расстояния (задержки) между суммируемыми разрядами были некратными.

На рисунке 6 приведен пример структуры формирователя случайной последовательности с декоррелятором, в котором по модулю 2 суммируются выходные разряды ТРП, как минимум один из которых пропущен через Т-триггер, а остальные задержаны на линиях задержки ЛЗ1, ЛЗ2, и ЛЗ3 с отводами от разрядов 5, 13, 32; 7, 19, 40 и 11, 27, 49 соответственно.



Рисунок 6 - Формирователь случайной последовательности - декоррелятор

13. Контроль параметров и статистических характеристик

Для предотвращения возможной неправильной работы ГИСЧ требуется контролировать следующие объекты в его составе:

– Источники питания;

– Тракт усиления и преобразования шумового сигнала;

– Тракт формирования случайной последовательности;

– Интерфейс с потребителем случайных чисел.

Источники питания

При отклонении напряжения любого источника питания в составе аппаратуры ГИСЧ от номинального на величину, превышающую допустимую, гипотеза H₀ отвергается и, если отклонение устойчиво, ГИСЧ переводится в состояние неисправного оборудования, подлежащего ремонту со всеми последующими этапами тестирования. Если отклонение кратковременное и одиночное, то ГИСЧ переводится в состояние теста включения, а определенный объем случайных данных бракуется. Если тесты включения успешны, то гипотеза H₀ подтверждается и ГИСЧ может продолжать работу. Если сбой повторяется на периоде времени, менее заданного, то требуется исследование и устранение причины сбоя. Во всех случаях определенный сгенерированный объем случайных данных, по возможности, не должен быть применен. Технически такой контроль выполняется допусковыми схемами контроля на основе компараторов, выходы которых фиксируются в регистре состояния ГИСЧ.

Далее будем понимать, что такой порядок действий применим не только при контроле напряжений источников питания, но и для контроля состояния всех объектов, описываемых далее.

Тракт усиления и преобразования шумового сигнала

В идеале требуется подтверждение двух гипотез о шумовом сигнале: о нормальном распределении отсчетов и о равномерной спектральной плотности мощности. Удобней всего контролировать выходные отсчеты АЦП, вычисляя на определенном интервале времени соответствующие оценки и сравнивая их с граничными значениями.

Например, для проверки нормальности распределения можно вычислять гистограмму с небольшим числом интервалов и контролировать попадание значений гистограммы в соответствующие доверительные интервалы. Аналогично равномерность спектральной плотности мощности можно оценивать по небольшому числу коэффициентов Фурье, попадающих в доверительный интервал.

Так как данные оценки являются статистическими, то выход значения оценки за границы доверительного интервала возможен с определенной вероятностью и, в отличие от случая контроля источников питания, не является признаком ухудшения качества функционирования. Далее этот вопрос будет уточнен при обсуждении частоты дискретизации оценок.

14. Тракт формирования случайной последовательности

В этом тракте необходим контроль статистических характеристик как первичных последовательностей, так и выходной случайной последовательности.

Для первичных последовательностей допустимы некоторое смещение и отклонение других статистик от идеальных, главное, чтобы такая последовательность не вырождалась в явно неслучайную.

Исходя из этого, достаточно задать границы интервала (a₁; a₂), в который с вероятностью должно попадать количество нулей (единиц) в случайной последовательности длиной n:

;

.

Например, для значений = 0.9999 и n = 32 получим: и . Соответственно, количество нулей (или единиц) в контролируемой последовательности длиной 32 бита будет лежать в пределах [5; 27] с вероятностью 0.9999. В этом случае вероятность «ложной тревоги» 1 - = 0.0001, то есть один раз на 320000 бит.

Для выходной случайной последовательности необходимы достаточно «сильные» тесты, например, тесты, рекомендованные Федеральным Стандартом Обработки Информации FIPS PUB 140-2 для криптографических модулей [1] (вариант редакции от 10.10.2001 до 03.12.2002, пункт 4.2.2).

Набор тестов, рекомендованный FIPS для проверки качества выходной последовательности генераторов случайных последовательностей при включении питания, содержит следующие проверки:

– монобитовою проверку;

– проверку покера;

– проверку серий;

– проверку длинных серий.

Для проведения тестов необходимо сформировать из битового потока массив из 20000 бит.

Монобитовая проверка

Монобитовая проверка заключается в подсчете всех единиц в массиве из 20000 бит. Полученное значение должно быть не менее 9725 и не более 10275.

Проверка покера

Проверка покера заключается в подсчете количества появлений 16 возможных 4 битовых чисел, которые последовательно выбираются из проверяемого битового потока. Количество появлений каждого 4-х битового числа обозначим через f(i), где i = 0..15. Вычисляется выражение:

.

Проверка считается пройденной, если 2.16 < X < 46.17.

Проверка серий

Серия определяется, как последовательность подряд идущих одинаковых бит в проверяемом битовом потоке. Проверка серий заключается в подсчете количества появлений одинаковых длин серий отдельно для нулей и единиц. Все серии длиной 6 и более рассматриваются как серии длиной 6. Проверка считается пройденной, если количество появлений каждой серии лежит в пределах, заданных в таблице 5.

Таблица 5

Длина серии	Требуемый Интервал
1	2315 - 2685
2	1114 - 1386
3	527 - 723
4	240 - 384
5	103 - 209
6+	103 - 209

Проверка длинных серий

Длинная серия определяется, как серия длиной 26 или более бит (нулей или единиц). Проверка длинных серий считается пройденной, если в проверяемом битовом потоке не обнаружено длинных серий.

Интерфейс с потребителем случайных чисел

Тип интерфейса определяется конкретным потребителем случайных чисел: внутри криптографического оборудования это могут быть простейшие интерфейсы типа SPI. Для связи с внешним оборудованием, таким, как накопители или компьютер, обычно применяют интерфейсы USB, SATA, PCI (PCI-Express), а также другие, определяемые конкретными требованиями.

Единственным контролируемым параметром для интерфейса с потребителем является достоверность передачи данных, которую можно проверять известными методами. Например, случайные данные и служебную информацию можно оформлять блоками фиксированной длины с подсчетом контрольного кода CRC-32 и его последующей проверкой в приемнике.

15. Частота дискретизации при оценке вероятности подтверждения гипотез

Оценка вероятности подтверждения гипотезы может рассматриваться как случайная величина, значение которой определяют в некоторые заданные моменты времени. В более широком смысле - это результат дискретизации непрерывного случайного процесса с определенной частотой дискретизации f_s.

Если вычисляемая оценка обладает свойством сходимости, то есть, чем больше интервал времени или число событий, на которых производится усреднение, тем меньше ошибка оценки, то при выборе f_s необходимо разрешать компромисс между задержкой в получении оценки и ее достоверностью.

Значение f_s для различных процессов может существенно отличаться, например, оценка исправности источников питания и качества шумового сигнала может производиться с периодом в 1 секунду, а оценка допустимых отклонений параметров генератора шума за счет старения элементов - один раз в год.

15. Число испытаний при оценке вероятности подтверждения гипотез

Обычно рассматривают доверительный интервал

,

который определяет нижнюю p₁ и верхнюю p₂ границы интервала, внутри которого с вероятностью будет находиться вероятность p некоторого события. Например, если это событие - «отказ», и мы проводим некоторое число испытаний n, во время которых «отказ» не наблюдался, то p₁ = 0 и нам требуется определить число испытаний, достаточное для p < p₂ с вероятностью .

Приближенно n определяется как [4]:

.

Например, n = 460 для = 0.99 и p₂ = 0.01 и n = 6700 для = 0.999 и p₂ = 0.001. Последняя запись означает: «чтобы гарантировать с вероятностью 99.9%, что вероятность отказа менее 0.1%, необходимо не менее 6700 испытаний, при которых не будет ни одного отказа».

Под отказом может пониматься не обязательно выход ГСЧ из строя, а и отклонение некоторого параметра ГСЧ в течение определенного времени на величину, больше заданной, или факт искажения генерируемых случайных чисел при передаче их в память компьютера или иные события, критичные для процесса генерации случайных чисел.

Таким образом, тестирование ГСЧ на отказ сводится к определению отказов, заданию гарантированной вероятности и вероятности отказа и выполнению требуемого числа испытаний. При этом необходимо понимать, что задавая = 0.999, мы допускаем, что в 0.1% испытаний результат может оказаться неудовлетворительным.

Примерный проект ГИСЧ

Структура

На основе общих требований, рассмотренных выше, приведем конкретный проект ГИСЧ со структурой, изображенной на рисунке 7.

Рисунок 7 - Структура проектируемого ГИСЧ

Элементы

Усилитель реализован на ИМС управляемого усилителя AD8330ARQ с подключенным к дифференциальному входу резистором 1 кОм в качестве источника шума. AD8330ARQ имеет следующие основные характеристики: полоса 150 МГц, входное дифференциальное сопротивление 1 кОм (при согласованном подключении источника 1 кОм это дает шумовой сигнал на входе с амплитудой 35 мкВ эфф.). Коэффициент усиления задается параметрами внешних цепей и составляет 63 дБ, что определяет дифференциальный выходной сигнал амплитудой 50 мВ эфф.

Фильтр ВЧ реализован в виде RC цепи 2-го порядка с частотой среза 10 кГц для подавления составляющих фликер-шума.

Применен 10 разрядный АЦП AD9215BRU-65 с частотой дискретизации 50 МГц.

Преобразователь равномерного распределения, формирователь случайной последовательности с декоррелятором (см. рис. 6), интерфейс и подсистема контроля и управления реализованы на ИМС программируемой логики EP3C5T144-8 с конфигурационной памятью типа EPCS4.

Подсистема питания с линейными стабилизаторами и компараторами особенностей не имеет.

16. Функции ГИСЧ

ГИСЧ вырабатывает блоки случайных данных длиной 20000 бит (2500 байт) с темпом 6.25 Мбайт/с и помещает их в двойной буфер (2 х 20000 бит). Узел интерфейса реализует алгоритм буферизации «качели»: пока один буфер заполняется случайными данными, второй считывается потребителем. Блок дополняется проверочным кодом CRC-32.

Подсистема контроля и управления осуществляет контроль питающих напряжений, контроль гистограммы АЦП, контроль спектра АЦП, тестирование первичных последовательностей на число единиц и выходной случайной последовательности тестами FIPS в соответствии с приведенными выше описаниями.

Со стороны интерфейса ГИСЧ представлен регистром данных (чтение), регистром состояния (чтение) и регистром управления (запись). Регистр управления определяет следующие режимы работы ГИСЧ:

– Режим «работа»;

– Тестовый режим чтения первичной последовательности;

– Тестовый режим чтения выхода АЦП.

В режиме «работа», при заполнении половины буфера случайными данными, в регистре состояния устанавливается флаг готовности, флаги компараторов контроля питания (флаг устанавливается при любом кратковременном срабатывании компаратора) и флаги непрохождения тестов гистограммы и спектра АЦП, тестов первичных последовательностей и выходной последовательности. Все флаги сбрасываются при чтении регистра состояния.

В тестовом режиме чтения первичной последовательности вместо выходной последовательности буфер заполняется значениями заданного разряда первичной последовательности для последующего статистического тестирования.

В тестовом режиме чтения выхода АЦП, буфер заполняется отсчетами АЦП (1250 16-ти разрядных слов с распространением знакового разряда АЦП в старшие разряды) для последующего анализа. Если интерфейс не успевает передать блок отсчетов АЦП (100 Мбайт/с), то запись отсчетов в буфер приостанавливается. Такие разрывы допустимы, если сигнал АЦП в дальнейшем подвергается статистической обработке или спектральному анализу.

17. Функции Потребителя

Потребитель устанавливает в регистре управления ГИСЧ требуемый режим, считывает регистр состояния и, обнаружив флаг готовности данных, считывает блок соответствующих данных с CRC, проверяет CRC и использует данные по назначению, например, записывает данные в файл. Перед применением случайных данных потребитель проверяет наличие флагов контроля питания и непрохождения тестов и действует в соответствии со своим алгоритмом обработки ошибок.

Автору известна практика тестирования последовательностей, вырабатываемых ГИСЧ, и отбрасывания части последовательности, если она не удовлетворяет критерию правдоподобия. Оправдываются такие действия тем, что если генератор является не совсем случайным, то есть его статистические характеристики не идеальны, то отбрасывая «плохие» участки последовательности, мы улучшаем ее статистические характеристики. С другой стороны, любой критерий правдоподобия сам является случайной величиной, и факт неудовлетворения его с определенной вероятностью обязательно проявляется на истинно случайной последовательности.

Во всем известной книжке «Криптономикон» [6] в Блечтли-парке бабушки доставали буквы из лотерейного барабана (и возвращали назад), и записывали букву в шифроблокнот. Когда им «казалось», что буква не случайна, они возвращали букву в барабан без записи в шифроблокнот. Это сформировало дырку в случайности, которой враги сумели воспользоваться.

Таким образом, если мы с достаточной вероятностью определили, что наш ГИСЧ является истинно случайным, то мы не имеем права как-либо модифицировать его выходную последовательность, в том числе, удалять по определенным критериям ее участки, поскольку любое правило обработки последовательности вводит в нее статистические зависимости, которых в идеальной последовательности быть не может.

генератор сигнал дискретизация корреляция

Выводы

Для получения действительно случайных чисел, прежде всего, надо проверять не степень случайности этих чисел, а подтверждать Нуль Гипотезу, которая заключатся в утверждении, что генератор является Генератором Истинно Случайных Последовательностей. При подтверждении Нуль Гипотезы мы должны все последовательности, вырабатываемые генератором, считать случайными.

Упрощение подтверждения Нуль Гипотезы достигается ее декомпозицией, то есть одновременным подтверждением множества более простых гипотез. Эти гипотезы необходимо подтверждать на протяжении всего жизненного цикла генератора, от начала проектирования до последнего дня эксплуатации.

В приведенном примере проектирования ГИСЧ продемонстрирована такая декомпозиция и обсуждены, по возможности, решения всех обозримых проблем. По предположению автора, это может оказать существенную помощь специалистам, создающим и эксплуатирующим ГИСЧ с требуемыми характеристиками и высоким качеством генерируемых случайных чисел.

Литература

1. FIPS PUB 140-2. National Institute of Standards and Technology, 2002.

2. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. Special Publication 800-22. Revision 1a. National Institute of Standards and Technology Gaithersburg, MD 0899-8930. Revised: April 2010.

3. IEEE Transactions on Computers, C-19, 1970, pp.1210-1213, H.F. Murry. A General Approach for Generating Natural Random Variables.

4. Вентцель Е.С. Теория вероятностей: Учеб. для вузов. - 6-е изд. стер. - М.: Высш. шк., 1999.- 576 c.

5. “Random Numbers Certified by Bell's Theorem,” S. Pironio, A. Acin, S. Massar, A. Boyer de la Giroday, D.N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T.A. Manning, C. Monroe,

6. Нил Стивенсон. Криптономикон I-II. Астрель, 1999. 708 с.

Размещено на Allbest.ru