Кивино гнездо: Закономерные случайности

Dmitry Panasenko написал(а) к All в Sep 11 14:45:12 по местному времени:

=============================================================================
* Forwarded by Dmitry Panasenko (2:5015/115)
* Area : RU.COMPUTERRA (RU.COMPUTERRA)
* From : News Robot, 2:5030/1256 (Понедельник Август 29 2011 18:58)
* To : All
* Subj : Кивино гнездо: Закономерные случайности
=============================================================================

Компьютерра
___________________________________________________________________

Кивино гнездо: Закономерные случайности

Опубликовано: 29.08.2011, 17:05

Автор: Берд Киви

Как известно, генераторы случайных чисел - или rng (от random
Number Generator) - обеспечивают работу криптографии. Иначе
говоря, играют важнейшую роль в безопасности коммуникаций и
защите информации, хранимой в компьютерных устройствах.

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

Конечно же, разработчиками постоянно делаются попытки исправить
эту неприятную ситуацию. И одна из наиболее интересных за
последнее время конструкций для лгенератора случайностей╗ была
представлена в августе этого года корпорацией Intel - на
конференции НOT CНIPS 23, проходившей в Стэнфордском
университете, США.

Инженерам исследовательского центра intel circuit research lab в
г. Хиллсбро, штат Орегон, удалось-таки сконструировать внутри
микросхемы настоящий DRNG или DIGITAL RNG - чисто цифровой (без
аналоговых компонентов) генератор случайных чисел, - используя
исключительно производственные процессы КМОП-технологии.

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

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

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

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

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

Производственные линии для выпуска интегральных микросхем каждые
несколько лет приходится обновлять из-за перехода к более мелким
масштабам упаковки транзисторов. Для цифровых схем
КМОП-технологии этот переход осуществляется довольно просто, а
вот для каждого нового поколения аналоговых схем все оказывается
гораздо сложнее.

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

Это снижение напряжения попутно понижает мощность сигнала - без
перемен в шуме устройства. Иначе говоря, понижается и уровень
отношения сигнала к шуму, а значит, каждая модернизация
неизбежно влечет за собой тщательную переоценку параметров и
комплекс тестирований для RNG. Ясно, что это чрезвычайно
неудобно и обременительно.

Принимая во внимание все эти проблемы, в 2008 году конструкторы
intel всерьез озаботились задачей по созданию такого генератора
случайных чисел, который использовал бы в своей работе
исключительно цифровые элементы схемы. Поначалу задачей полного
избавления генератора случайных битов от аналоговых схем
занимались исследователи Circuit Research Lab в Хиллсбро, а
затем к ним подключились индийские коллеги из исследовательского
центра bangalore design lab.

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

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

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

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

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

Конструктивно весь этот трюк реализован на основе пары
инверторов (элементов схемы, у которых выходной сигнал
противоположен сигналу на входе), циклически подсоединенных друг
к другу, и двух довольно странно подключенных к инверторам
транзисторов. Из-за этой лнелогичной╗ схемы подключения данная
система в каждом такте работы на кратчайшее время подвисает
между двумя своими базовыми состояниями 0 и 1.

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

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

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

А цель конструкторов Intel ставилась так, чтобы построить
систему, которая генерирует не просто чисто случайные, а
лвысококачественные случайные числа╗, совместимые с
общепринятыми криптографическими стандартами. В первую очередь,
с критериями NIST SP800-90 Национального института стандартов и
технологий США, соответствие которым гарантирует выдачу
соответствующего сертификата, а значит, и повсеместное признание
схемы в качестве надежной криптотехнологии.

Чтобы гарантировать высокое качество случайных чисел,
порождаемых новым drng, в intel разработали специальный
трехэтапный процесс генерации. Помимо базовой аппаратной схемы
(первый этап), данный процесс также предусматривает
лкондиционер╗ (второй этап) и псевдослучайный генератор чисел
(заключительный третий этап). В совокупности же вся эта
конструкция получила кодовое наименование BULL MOUNTAIN.

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

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

Третий этап bull mountain объясняется тем, что хотя новая
аппаратная схема генерирует случайные числа из теплового шума
намного быстрее, чем ее предшественники, она все еще не
настолько шустра, чтобы отвечать любым нынешним запросам к
защищенным компьютерным коммуникациям. Поэтому, дабы позволить
BULL MOUNTAIN выдавать случайные числа столь же быстро, как
программные генераторы псевдослучайных последовательностей (но
сохраняя при этом высокое качество подлинно случайных чисел)
конструкторы добавили в схему еще один уровень - PRNG с очень
высокой скоростью лзасева╗.

Этот алгоритм использует 256-битные случайные числа от
кондиционера, чтобы засеивать ими криптографически надежный (на
основе стандарта AES) генератор псевдослучайных чисел,
порождающий последовательности 128-битных чисел. Из одного
256-битного зерна этот псевдослучайный генератор способен
выдавать огромное множество псевдослучайных чисел. Понятно, что
когда такие зерна поступают со скоростью порядка 3 гигагерц,
производительность генератора можно сделать очень большой.

В новых микропроцессорах Intel генератор Bull Mountain будет
доступен программным приложениям через инструкцию RDRAND,
которая уже была представлена программистам-разработчикам
несколько месяцев назад. Первыми процессорами, которые обеспечат
работу RDRAND, станут чипы семейства IVY BRIDGE.

Эти 22-нанометровые микропроцессоры, как ожидается, должны быть
официально представлены в сентябре в рамках конференции
разработчиков Intel Developer Forum. Согласно другой, пока
неофициальной информации, в INTEL намерены объявить о рыночных
поставках новых чипов ivy bridge в начале 2012 года, примерно в
дни январской ярмарки бытовой электроники Consumer Electronics
SНOW.


___________________________________________________________________

Оригинал статьи на http://pda.computerra.ru/?action=article&id=631063

[http://pda.computerra.ru/?action=sec...ion_id=27994]: - Блог "Компьютерры-Онлайн" - Колумнисты - Кивино гнездо

-+-
+ Origin: by_Rain 19/11-2007g. (2:5030/1256)
=============================================================================

Ave(te), All!


Tibi et igni, vale! Dmitry "Dev" Panasenko

---