Выпуск #9/2018
Тимошин Сергей Александрович, Нуйкин Андрей Валерьевич, Ролдугина Жанна Игоревна
Разработка и особенности использования аппаратного генератора случайных чисел в составе защищенных систем на кристалле
Разработка и особенности использования аппаратного генератора случайных чисел в составе защищенных систем на кристалле
Просмотры: 2702
УДК 621.373.5
DOI: 10.22184/1993-8578.2018.82.321.326
DOI: 10.22184/1993-8578.2018.82.321.326
В настоящее время генераторы случайных чисел широко используются в микроэлектронных устройствах для различных задач, среди которых создание криптографических ключей для защищенной передачи данных. В связи с тем, что они выполняют такую важную функцию в устройствах, необходимо, чтобы элементы реализуемой генератором последовательности чисел были независимы друг от друга, а также имели равномерное распределение.
Данные условия наиболее точно выполняются для аппаратных генераторов случайных чисел. На сегодняшний день одними из самых защищенных интегральных микросхем, в составе которых используется аппаратный генератор случайных чисел, являются платежные и идентификационные микропроцессорные смарт-карты со встроенной энергонезависимой памятью [1, 2, 3].
Работа аппаратных генераторов случайных чисел основывается на измерении параметров физического процесса, которые хаотически изменяются во времени. Процесс может описываться либо классической, либо квантовой физикой. Вероятностная природа квантовой физики наиболее подходит в качестве основы для создания подобного прибора. Однако данные системы в настоящее время подходят лишь для тех областей, где истинность случайных чисел важна настолько, что компенсирует все материальные и интеллектуальные затраты на производство данных устройств [4].
В тех случаях, когда требуется широкое практическое применение, обращаются к классической физике с макроскопическими системами. Среди них для генерации случайных чисел наблюдаются такие эффекты: отслеживание тепловых шумов в резисторе, фазовое дрожание в кольцевых генераторах и т. д. Подобные устройства более просты в реализации и не требуют особой технологии, однако некоторые факторы, например, температура, могут повлиять на качество сгенерированной последовательности.
Разработанный блок генератора случайных чисел предназначен для формирования случайной последовательности логических состояний на выходе блока. Требования по напряжению питания соответствуют требованиям, предъявляемым цифровыми блоками. Ток потребления пропорционален тактовой частоте (3,5 мкА при 10 МГц). Предельная тактовая частота 100 МГц. На рис. 1 представлено символьное обозначение разработанного блока генератора случайных чисел.
С выхода генератора out_rndgen снимается последовательность случайных чисел. С помощью входа sel_rndgen осуществляется выбор схемы генератора случайных чисел, вход en_rndgen представляет собой вход разрешения работы генератора случайных чисел, на вход clk_rndgen поступает тактовый сигнал. На рис. 2 представлена временная диаграмма работы генератора случайных чисел, на которой продемонстрирована работа генератора при включенном и отключенном разрешающем сигнале с входа en_rndgen с временем включения схемы t0.
Ток потребления данного блока генератора случайных чисел составляет не более 300 мкА, а время включения составляет не более 1 мкс. В рамках работы была произведена оптимизация схемы блока генератора случайных чисел по току потребления и занимаемой площади.
В лаборатории отдела разработки интегральных схем АО «НИИМЭ» было проведено исследование генераторов случайной последовательности в составе экспериментальных образцов и в составе конечных изделий. Данное исследование заключалось в определении степени работоспособности генераторов случайной последовательности и сравнении работоспособности исходного и оптимизированного генератора случайной последовательности.
Для проведения измерений использовалось следующее оборудование: источник питания — GwInstek GPD-73303S, генератор/анализатор сигналов — Lecroy ArbStudio 1104, плата для прототипирования на основе ПЛИС Xilinx Virtex-4.
При помощи генератора/анализатора сигналов — Lecroy ArbStudio 1104 были собраны последовательности данных с выхода генератора случайной последовательности длиной 62500 байт.
Существенной проблемой аппаратных генераторов случайных чисел является наличие отклонений и корреляций в сгенерированной последовательности. Сами процессы могут быть случайными, но проблемы могут возникнуть в процессе измерений. В связи с этим возникает необходимость в коррекции полученной последовательности случайных чисел для повышения энтропии, при которой вероятности появления логического нуля и единицы приблизительно равны. Существует большое количество методов коррекции для улучшения качества последовательности. В работе применялась коррекция с помощью преобразования фон Неймана. Принцип данного преобразования состоит в разбиении исходной последовательности на пары бит с последующим выбором только тех пар, где соседние значения различны, пары с одинаковыми значениями отбрасываются. Для выбранных пар в выходную последовательность назначаются конечные значения. На рис. 3 приведен пример такого преобразования. В данном примере паре «10» назначается значение «1», а для пары «01» назначается значение «0», пары «00» и «11» удаляются из последовательности.
По итогам преобразования фон Неймана последовательность значительно сокращается, а ее статистические свойства приближаются к свойствам, присущим случайным последовательностям.
Для экспресс-оценки качества данных последовательность была исследована по нескольким параметрам. Одним из наиболее показательных критериев случайных последовательностей является вероятность появления логических «0» и «1» в последовательности, которая в идеальном случае равна 50 %. Следующим критерием являлась степень сокращения длины последовательности при проведении преобразования фон Неймана, которая характеризует равномерность распределения значений в последовательности. Также в качестве критерия была выбрана степень сжатия архиватором последовательности после преобразования фон Неймана. Значение степени сжатия отображает отсутствие либо наличие закономерностей, обнаруженных архиватором. В случайной последовательности закономерностей быть не должно, поэтому размер сжатых файлов должен быть не меньше исходных. Так как в каждой сложной цифровой микросхеме присутствуют генераторы тактового сигнала или тактовый сигнал подается извне, для анализа возможности влияния тактового сигнала на качество генерируемой случайной последовательности в тестовый кристалл был включен генератор тактовой частоты.
Были протестированы случайные последовательности, полученные с разработанных генераторов: исходного и оптимизированного. Анализ результатов производился по девяти выборкам значений. После проведения преобразования фон Неймана исходные последовательности уменьшились в 4–5 раз.
Двоичные файлы случайных чисел до сжатия имели следующие размеры: исходная последовательность — 62 500 байт; последовательность, полученная после преобразования фон Неймана — 12 500 байт. Сжатие данных производилось с помощью программы 7z при следующих настройках: формат архива — zip, уровень сжатия — ультра, метод сжатия — Deflate, размер словаря 32 КБ, размер слова — 128.
При отключенном генераторе тактовой частоты средний размер исходной последовательности после сжатия составляет 59458 байта, что составляет 95 % от исходного размера. Для последовательности, полученной после преобразования фон Неймана, это число составляет 12245 байта (98 %).
При включенном генераторе тактовой частоты средний размер исходной последовательности после сжатия составляет 61754 байта (98,8 %), для последовательности, полученной после преобразования фон Неймана, это число составляет 12648 байта (101,2 %).
Средний размер оптимизированной последовательности после сжатия при отключенном генераторе тактовой частоты составляет 60866 байта (99,5 %), для последовательности, полученной после преобразования фон Неймана, это число составляет 12633 байта (101,1 %).
Средний размер оптимизированной последовательности после сжатия при включенном генераторе тактовой частоты составляет 62216 байта (98,8 %), для последовательности, полученной после преобразования фон Неймана, это число составляет 12631 байта (101 %).
На рис. 4 представлены размеры файлов сжатых последовательностей, полученных с исходного и оптимизированного блоков генератора случайных чисел, при отключенном и включенном генераторе тактовой частоты. Для наглядности также отображен размер исходной последовательности.
На рис. 5 представлены размеры файлов сжатых последовательностей после коррекции, полученных с исходного и оптимизированного блоков генератора случайных чисел, при отключенном и включенном генераторе тактовой частоты. Для наглядности также отображен размер исходной последовательности.
На рис. 6 представлено соотношение логических нулей и единиц при отключенном генераторе тактовой частоты для исходной и оптимизированной последовательностей.
На рис. 7 представлено соотношение логических нулей и единиц при включенном генераторе тактовой частоты для исходной и оптимизированной последовательностей.
По результатам исследования было установлено, что влияние генератора тактовой частоты не ухудшает статистические свойства сгенерированной случайной последовательности.
Для более точного определения качества полученных случайных чисел проводятся различные статистические тесты. Из самых обобщенных соображений можно выделить два класса критериев: эмпирические критерии, при использовании которых вычисляются некоторые статистики от групп случайных чисел; и теоретические критерии, для которых анализ последовательности чисел производится теоретико-числовыми методами, над рекуррентными правилами, образующими случайные числа [5].
В настоящее время существует большое количество программных средств для проверки качества случайных чисел. Для определения случайных чисел Национальным институтом стандартов и технологий (NIST) были разработаны 15 тестов. Эти тесты основаны на различных статистических свойствах, присущих только случайным последовательностям. Еще одним известным набором тестов для анализа случайных последовательностей является пакет diehard, который считается одним из наиболее строгих существующих наборов тестов. В данной работе для проверки свойств последовательности применялись тесты из пакета dieharder. Пакет содержит 114 тестов, включая тесты diehard, NIST и прочие тесты. Автор утверждает невозможность прохождения всех тестов. Были протестированы как исходный, так и оптимизированный генераторы на технологиях 180 нм и 90 нм.
Входными данными для тестирования могут быть как выход программного генератора, так и входной файл с выборкой случайных чисел. Пакет dieharder очень требователен к объему входных данных, поэтому для проведения анализа были собраны большие объемы выборок. Опытным путем установлено, что необходимый минимум входных данных для большинства тестов составляет около 512 мегабайт. Для каждого тестового образца были собраны такие объемы случайных данных. Для двух образцов дополнительно было собрано по одному пакету объемом 1 гигабайт. Результат прохождения тестов dieharder для 1 ГБ данных аналогичен объему пакета 512 мегабайт. Исходная последовательность прошла малое количество тестов (2–3 из 114). Повышение энтропии методом фон Неймана привело к сокращению выборки в 12–14 раз (до 35–42 Мбайт) и к повышению количества проходимых тестов до 25–30 из 114.
Для проведения дальнейшего анализа было решено зашифровать файлы случайных чисел посредством алгоритма DES в режиме электронной кодовой книги (ECB) с ключами «0». В результате получаемые последовательности успешно прошли 106–110 тестов из 114. Таким образом, в качестве наиболее эффективного метода улучшения статистических свойств случайной последовательности было выбрано шифрование файлов.
Авторы считают, что в данной работе новыми являются следующие положения и результаты. Коррекция фон Неймана может быть использована только для оценки годности генератора случайных чисел в составе изделия, критерием оценки является сокращение выборки не более чем в 16–18 раз. Для достижения высокого качества случайной последовательности повышение энтропии предлагается проводить при помощи того или иного блока шифрования, имеющегося в составе кристалла. В результате работы были спроектированы и изготовлены образцы изделий с использованием техпроцессов с минимальными топологическими нормами 90 нм и 180 нм [6, 7].
ЛИТЕРАТУРА
1. Красников Г. Я., Горнев Е. С. Развитие полупроводниковой микроэлектроники ОАО «НИИМЭ и Микрон», История отечественной электроники: — М.: 2012. — Т. 1. — С. 539–563.
2. Красников Г. Я., Шелепин Н. А. «Состояние и перспективы развития технологий и элементной базы СБИС с энергонезависимой памятью», Международная научно-техническая конференция с элементами научной школы для молодежи. — М.: Зеленоград, 2010.
3. S.Timoshin, A.Nuykin, A.Kravtsov. Extreme Low Cost Chip for HF RFID tag. 7th Annual IEEE International Conference on RFID, IEEE RFID 2013. Orlando, US — 2013.
4. Ролдугина Ж. И., Нуйкин А. В. Влияние времени моделирования на статистическое распределение выходных значений сигнала аппаратного генератора случайного числа // Микроэлектроника и информатика — 2017: сборник статей. — М.: МИЭТ, 2017. — С. 170–176.
5. Слеповичев И. И. Введение в теорию генераторов псевдослучайных чисел. Саарбрюккен: LAP LAMBERT Academic Publishing, 2016. 128 с.
6. Нуйкин А. В., Кравцов А. С. «Разработка и внедрение кристаллов для смарт-карт на российском и международном рынках на основе решений АО «НИИМЭ» // Электронная техника. Серия 3. Микроэлектроника. — 2016. — № 1(161). — С. 4–8.
7. Нуйкин А. В., Кравцов А. С. «Перспективы развития систем радиочастотной идентификации на основе карт памяти и микропроцессорных карт», Международная конференция «Микроэлектроника 2015». Крым, Алушта — 2015.
Данные условия наиболее точно выполняются для аппаратных генераторов случайных чисел. На сегодняшний день одними из самых защищенных интегральных микросхем, в составе которых используется аппаратный генератор случайных чисел, являются платежные и идентификационные микропроцессорные смарт-карты со встроенной энергонезависимой памятью [1, 2, 3].
Работа аппаратных генераторов случайных чисел основывается на измерении параметров физического процесса, которые хаотически изменяются во времени. Процесс может описываться либо классической, либо квантовой физикой. Вероятностная природа квантовой физики наиболее подходит в качестве основы для создания подобного прибора. Однако данные системы в настоящее время подходят лишь для тех областей, где истинность случайных чисел важна настолько, что компенсирует все материальные и интеллектуальные затраты на производство данных устройств [4].
В тех случаях, когда требуется широкое практическое применение, обращаются к классической физике с макроскопическими системами. Среди них для генерации случайных чисел наблюдаются такие эффекты: отслеживание тепловых шумов в резисторе, фазовое дрожание в кольцевых генераторах и т. д. Подобные устройства более просты в реализации и не требуют особой технологии, однако некоторые факторы, например, температура, могут повлиять на качество сгенерированной последовательности.
Разработанный блок генератора случайных чисел предназначен для формирования случайной последовательности логических состояний на выходе блока. Требования по напряжению питания соответствуют требованиям, предъявляемым цифровыми блоками. Ток потребления пропорционален тактовой частоте (3,5 мкА при 10 МГц). Предельная тактовая частота 100 МГц. На рис. 1 представлено символьное обозначение разработанного блока генератора случайных чисел.
С выхода генератора out_rndgen снимается последовательность случайных чисел. С помощью входа sel_rndgen осуществляется выбор схемы генератора случайных чисел, вход en_rndgen представляет собой вход разрешения работы генератора случайных чисел, на вход clk_rndgen поступает тактовый сигнал. На рис. 2 представлена временная диаграмма работы генератора случайных чисел, на которой продемонстрирована работа генератора при включенном и отключенном разрешающем сигнале с входа en_rndgen с временем включения схемы t0.
Ток потребления данного блока генератора случайных чисел составляет не более 300 мкА, а время включения составляет не более 1 мкс. В рамках работы была произведена оптимизация схемы блока генератора случайных чисел по току потребления и занимаемой площади.
В лаборатории отдела разработки интегральных схем АО «НИИМЭ» было проведено исследование генераторов случайной последовательности в составе экспериментальных образцов и в составе конечных изделий. Данное исследование заключалось в определении степени работоспособности генераторов случайной последовательности и сравнении работоспособности исходного и оптимизированного генератора случайной последовательности.
Для проведения измерений использовалось следующее оборудование: источник питания — GwInstek GPD-73303S, генератор/анализатор сигналов — Lecroy ArbStudio 1104, плата для прототипирования на основе ПЛИС Xilinx Virtex-4.
При помощи генератора/анализатора сигналов — Lecroy ArbStudio 1104 были собраны последовательности данных с выхода генератора случайной последовательности длиной 62500 байт.
Существенной проблемой аппаратных генераторов случайных чисел является наличие отклонений и корреляций в сгенерированной последовательности. Сами процессы могут быть случайными, но проблемы могут возникнуть в процессе измерений. В связи с этим возникает необходимость в коррекции полученной последовательности случайных чисел для повышения энтропии, при которой вероятности появления логического нуля и единицы приблизительно равны. Существует большое количество методов коррекции для улучшения качества последовательности. В работе применялась коррекция с помощью преобразования фон Неймана. Принцип данного преобразования состоит в разбиении исходной последовательности на пары бит с последующим выбором только тех пар, где соседние значения различны, пары с одинаковыми значениями отбрасываются. Для выбранных пар в выходную последовательность назначаются конечные значения. На рис. 3 приведен пример такого преобразования. В данном примере паре «10» назначается значение «1», а для пары «01» назначается значение «0», пары «00» и «11» удаляются из последовательности.
По итогам преобразования фон Неймана последовательность значительно сокращается, а ее статистические свойства приближаются к свойствам, присущим случайным последовательностям.
Для экспресс-оценки качества данных последовательность была исследована по нескольким параметрам. Одним из наиболее показательных критериев случайных последовательностей является вероятность появления логических «0» и «1» в последовательности, которая в идеальном случае равна 50 %. Следующим критерием являлась степень сокращения длины последовательности при проведении преобразования фон Неймана, которая характеризует равномерность распределения значений в последовательности. Также в качестве критерия была выбрана степень сжатия архиватором последовательности после преобразования фон Неймана. Значение степени сжатия отображает отсутствие либо наличие закономерностей, обнаруженных архиватором. В случайной последовательности закономерностей быть не должно, поэтому размер сжатых файлов должен быть не меньше исходных. Так как в каждой сложной цифровой микросхеме присутствуют генераторы тактового сигнала или тактовый сигнал подается извне, для анализа возможности влияния тактового сигнала на качество генерируемой случайной последовательности в тестовый кристалл был включен генератор тактовой частоты.
Были протестированы случайные последовательности, полученные с разработанных генераторов: исходного и оптимизированного. Анализ результатов производился по девяти выборкам значений. После проведения преобразования фон Неймана исходные последовательности уменьшились в 4–5 раз.
Двоичные файлы случайных чисел до сжатия имели следующие размеры: исходная последовательность — 62 500 байт; последовательность, полученная после преобразования фон Неймана — 12 500 байт. Сжатие данных производилось с помощью программы 7z при следующих настройках: формат архива — zip, уровень сжатия — ультра, метод сжатия — Deflate, размер словаря 32 КБ, размер слова — 128.
При отключенном генераторе тактовой частоты средний размер исходной последовательности после сжатия составляет 59458 байта, что составляет 95 % от исходного размера. Для последовательности, полученной после преобразования фон Неймана, это число составляет 12245 байта (98 %).
При включенном генераторе тактовой частоты средний размер исходной последовательности после сжатия составляет 61754 байта (98,8 %), для последовательности, полученной после преобразования фон Неймана, это число составляет 12648 байта (101,2 %).
Средний размер оптимизированной последовательности после сжатия при отключенном генераторе тактовой частоты составляет 60866 байта (99,5 %), для последовательности, полученной после преобразования фон Неймана, это число составляет 12633 байта (101,1 %).
Средний размер оптимизированной последовательности после сжатия при включенном генераторе тактовой частоты составляет 62216 байта (98,8 %), для последовательности, полученной после преобразования фон Неймана, это число составляет 12631 байта (101 %).
На рис. 4 представлены размеры файлов сжатых последовательностей, полученных с исходного и оптимизированного блоков генератора случайных чисел, при отключенном и включенном генераторе тактовой частоты. Для наглядности также отображен размер исходной последовательности.
На рис. 5 представлены размеры файлов сжатых последовательностей после коррекции, полученных с исходного и оптимизированного блоков генератора случайных чисел, при отключенном и включенном генераторе тактовой частоты. Для наглядности также отображен размер исходной последовательности.
На рис. 6 представлено соотношение логических нулей и единиц при отключенном генераторе тактовой частоты для исходной и оптимизированной последовательностей.
На рис. 7 представлено соотношение логических нулей и единиц при включенном генераторе тактовой частоты для исходной и оптимизированной последовательностей.
По результатам исследования было установлено, что влияние генератора тактовой частоты не ухудшает статистические свойства сгенерированной случайной последовательности.
Для более точного определения качества полученных случайных чисел проводятся различные статистические тесты. Из самых обобщенных соображений можно выделить два класса критериев: эмпирические критерии, при использовании которых вычисляются некоторые статистики от групп случайных чисел; и теоретические критерии, для которых анализ последовательности чисел производится теоретико-числовыми методами, над рекуррентными правилами, образующими случайные числа [5].
В настоящее время существует большое количество программных средств для проверки качества случайных чисел. Для определения случайных чисел Национальным институтом стандартов и технологий (NIST) были разработаны 15 тестов. Эти тесты основаны на различных статистических свойствах, присущих только случайным последовательностям. Еще одним известным набором тестов для анализа случайных последовательностей является пакет diehard, который считается одним из наиболее строгих существующих наборов тестов. В данной работе для проверки свойств последовательности применялись тесты из пакета dieharder. Пакет содержит 114 тестов, включая тесты diehard, NIST и прочие тесты. Автор утверждает невозможность прохождения всех тестов. Были протестированы как исходный, так и оптимизированный генераторы на технологиях 180 нм и 90 нм.
Входными данными для тестирования могут быть как выход программного генератора, так и входной файл с выборкой случайных чисел. Пакет dieharder очень требователен к объему входных данных, поэтому для проведения анализа были собраны большие объемы выборок. Опытным путем установлено, что необходимый минимум входных данных для большинства тестов составляет около 512 мегабайт. Для каждого тестового образца были собраны такие объемы случайных данных. Для двух образцов дополнительно было собрано по одному пакету объемом 1 гигабайт. Результат прохождения тестов dieharder для 1 ГБ данных аналогичен объему пакета 512 мегабайт. Исходная последовательность прошла малое количество тестов (2–3 из 114). Повышение энтропии методом фон Неймана привело к сокращению выборки в 12–14 раз (до 35–42 Мбайт) и к повышению количества проходимых тестов до 25–30 из 114.
Для проведения дальнейшего анализа было решено зашифровать файлы случайных чисел посредством алгоритма DES в режиме электронной кодовой книги (ECB) с ключами «0». В результате получаемые последовательности успешно прошли 106–110 тестов из 114. Таким образом, в качестве наиболее эффективного метода улучшения статистических свойств случайной последовательности было выбрано шифрование файлов.
Авторы считают, что в данной работе новыми являются следующие положения и результаты. Коррекция фон Неймана может быть использована только для оценки годности генератора случайных чисел в составе изделия, критерием оценки является сокращение выборки не более чем в 16–18 раз. Для достижения высокого качества случайной последовательности повышение энтропии предлагается проводить при помощи того или иного блока шифрования, имеющегося в составе кристалла. В результате работы были спроектированы и изготовлены образцы изделий с использованием техпроцессов с минимальными топологическими нормами 90 нм и 180 нм [6, 7].
ЛИТЕРАТУРА
1. Красников Г. Я., Горнев Е. С. Развитие полупроводниковой микроэлектроники ОАО «НИИМЭ и Микрон», История отечественной электроники: — М.: 2012. — Т. 1. — С. 539–563.
2. Красников Г. Я., Шелепин Н. А. «Состояние и перспективы развития технологий и элементной базы СБИС с энергонезависимой памятью», Международная научно-техническая конференция с элементами научной школы для молодежи. — М.: Зеленоград, 2010.
3. S.Timoshin, A.Nuykin, A.Kravtsov. Extreme Low Cost Chip for HF RFID tag. 7th Annual IEEE International Conference on RFID, IEEE RFID 2013. Orlando, US — 2013.
4. Ролдугина Ж. И., Нуйкин А. В. Влияние времени моделирования на статистическое распределение выходных значений сигнала аппаратного генератора случайного числа // Микроэлектроника и информатика — 2017: сборник статей. — М.: МИЭТ, 2017. — С. 170–176.
5. Слеповичев И. И. Введение в теорию генераторов псевдослучайных чисел. Саарбрюккен: LAP LAMBERT Academic Publishing, 2016. 128 с.
6. Нуйкин А. В., Кравцов А. С. «Разработка и внедрение кристаллов для смарт-карт на российском и международном рынках на основе решений АО «НИИМЭ» // Электронная техника. Серия 3. Микроэлектроника. — 2016. — № 1(161). — С. 4–8.
7. Нуйкин А. В., Кравцов А. С. «Перспективы развития систем радиочастотной идентификации на основе карт памяти и микропроцессорных карт», Международная конференция «Микроэлектроника 2015». Крым, Алушта — 2015.
Отзывы читателей