Добрый день.

Схем ГСЧ много и многие доступны в интернете. Хотелось бы обратиться к знающим людям - какую схему ГСЧ вы посоветуете, как наиболее стабильную? Задача для ГСЧ тривиальна - генерация пароля (с помощью микроконтроллера). Слышал, что есть схемы ГСЧ, сертифицированные ФСБ, и не такие уж и секретные. Может кто и поделится.

Спасибо.

1. Хеш-функция вроде SHA. Вы подаете ей на вход некую фразу, она на ее основе генерит отпечаток, который можно использовать, как пароль. Даже зная пароль, получить исходную фразу невозможно.

2. Последовательный регистр с обратными связями. См. Хоровица и Хилла. Или аналоговый генератор на шумовом диоде или шумящем стабилитроне.

3. Огромное множество самых различных алгоритмов. См. второй том Дональда Кнута.

4. Задача эта, если серьезно к ней подойти, потрясающе сложна и обширна. Для интереса можете почитать Фергюссона и Шнайера "Практическая криптография" ...

делал такую как тут http://www.cryptography.com/public/pdf/IntelRNG.pdf 4.2 Dual Oscillator, на выборке ~15МБ прошла тесты на случайность числа.

...произвольную выборку каждой 3-й буквы 2-го абзаца из любого тома хранения библиотеки им. В.И.Ленина... Манускрипт Войнича не взломают никогда. А любая схема (не аналоговая) только ждет своего часа...


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

Вот как раз аналоговую схему ГСЧ я и замышляю реализовать на плате(источник шума+усилитель+микроконтроллер для обработки). Кто подскажет, где можно посмотреть использующиеся в настоящее время схемы для ГСЧ (на шумящем стабилитроне и тп)?

Первый же ответ Google на запрос "noise generator diode":

http://pdfserv.maxim-ic.com/en/an/AN3469.pdf

stm32F2, stm32f4 - имеют встроенный генератор случайных чисел как раз для этих целей

Сгенерированный пароль в Вашем случае должен быть случайным, проще говоря знание первой части пароля не несет никакой информации о второй части.
Можно использовать конечно регистр, но тут проблема возникает в начальном его заполнении+генерация пароля в нем детерминирована и описывается математически
Следовательно остается шумовой диод НО проблема в использовании диода в том, что надо грамотно его настроить и реализовать минимальные тесты для того чтобы исключить период времени выхода в рабочую точку из периода генерации символов пароля. Как вариант предлагается взять существующее схемотехнические решение дабы избежать косяков в железе и реализоваться свои тесты.В нете есть софт для тестирования выходных последовательностей датчика, проблема лишь в том что далеко не каждый железячник способен оценить качество последовательности спаяной им фиговины. Все зависит от задачи и от цены информации закрытой этим паролем готовые решения с чипами(кот в мешке) для серьезных задач не рекомендуется.

Терморектальный криптоанализ проверенное временем решение вскрытия хороших паролей

Если хотите сами попробовать что-то вроде "шумящего диода", то могу порекомендовать найти МК с встроенным АЦП и
встроенным термодатчиком. Младший разряд АЦП, подключенный к нему (с небольшой обработкой) и будет у Вас "ГСЧ".

реккурентные последовательности (коды Хеммигна) и сложение по модулю 2 дает абсолютно случайные числа , сертифицировано КГБ еще в 50-х годах прошлого столетия;
кстати всех с днем ВЧК-КГБ-ФСБ

Можно использовать как программную, так и аппаратную генерацию.
1. Программная генерация. Бытует мнение, что такой подход это моветон и использовать его для криптографии нельзя, поскольку программно генерируемые числа обычно имеют псевдослучайную природу. Однако если мы будем использовать для инициализации таких псевдослучайных ГСЧ числа с высокой энтропией, то на выходе ГСЧ уже будет нечто похожее на случайную последовательность, без приставки "псевдо". Мера случайности полученной последовательности определяется при помощи статистических тестов, например NIST.
Итак, для программной генерации случайных чисел делаем следующее:
A. Берем псевдослучайный ГСЧ, например регистр сдвига с линейной обратной связью Его можно реализовывать как программно, так и аппаратно, схем в инете куча, таблиц с описанием примитивных многочленов тоже навалом (можно посмотреть хотя бы в ссылках к приведенной выше статье на вики).
Б. Берем откуда-то число с некоторой энтропией (неопределенностью). В качестве такого числа можно взять, например, младшие биты системного времени, а если в микроконтроллере системных часов нет - то содержимое таймера-счетчика. Поскольку числа вы будете генерить в произвольные моменты времени, полученное таким образом число претендует на случайность.
В. Инициализируем полученным выше числом ваш псевдослучайный ГСЧ , например рассмотренный регистр сдвига с линейной ОС. И гоняем этот регистр некоторое количество тактов, которое может определятся содержимым другого таймера. То, что получилось в результате берем в виде случайного числа.
Г. Последовательность сгенерированных случайных чисел проверяем при помощи статистического теста, если полученная мера случайности устраивает - пользуетемся созданным генератором.
2. Аппаратная генерация Выше уже предлагали схему измерения шума полупроводникового диода, а я предложу цифровую схему, которую Intel использует для аппаратной генерации случайных чисел в процессорах микроархитектуры IVY BRIDGE. Вот ссылки на статьи в которых описывается такой генератор: 1, 2, 3
В двух словах суть предложенного в Intel подхода сводится к следующему. Если ввести бистабильную ячейку (RS триггер) в метастабильное состояние, то под воздействием тепловых шумов RS триггер случайно перейдет либо в 0, либо в 1. Распределение полученных случайных чисел, как я понимаю, будет такое же, как и у теплового шума. Чтобы перевести триггер в метастабильное состояние, необходимо подать одинаковое напряжение на входы R и S. Это может быть либо R=S=0 (для RS триггера в базисе И-НЕ), либо R=S=1 (для RS триггера в базисе ИЛИ-НЕ). Допустим мы работаем с триггером в базисе ИЛИ-НЕ и подали на его входы две единицы. На прямом и инверсном выходах тригера появятся логические нули. Далее, когда мы подадим на входы два нуля вместо двух единиц, прямой выход триггера случайно перейдет либо в 0, либо в 1. Нужно только, чтобы напряжения на R и S входах переходили из 1 в 0 одновременно. Если это требование нарушить, энтропия существенно снизиться. Эту проблему можно решать добавлением к RS триггеру отрицательной обратной связи, что и сделала Intel в своей разработке. Более детально механизм работы данного ГСЧ и его статистические тесты рассмотрены в приведенных выше статьях.