23 February 2010

Новый алгоритм ГСЧ на замену /dev/random

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

Немецкие исследователи Бернард Фечнер (университет Хагена) и Андре Остерлох (BTC AG) заявили о прорыве в методах генерации случайных чисел. Они разработали алгоритм, который обеспечивает дискретное равномерное распределение до 20 раз лучше существующих методов. К работе прилагаются результаты тестов по сравнению качества случайных чисел, генерируемых разными методами.

Разработанный немцами ГСЧ считывает последовательность битов из памяти (метастабильное состояние) и по таблице меняет местами 0 и 1. Таблица — это дополнительный уровень случайности, который позволяет на порядок повысить качество случайных чисел. Специфика метода (считывание из памяти) обеспечивает максимально возможную скорость работы алгоритма. Он не только качественнее, но и на порядок быстрее, чем алгоритм LFSR плюс счётчик тактов процессора — такая связка используется в стандартной программе /dev/random, которая идёт в комплекте с Unix.

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

Результаты своей работы Бернард Фечнер и Андре Остерлох опубликовали в журнале International Journal of Critical Computer-Based Systems. [A meta-level true random number generator. Int. J. Critical Computer-Based Systems, 2010, 1, 267-279, PDF]

via ScienceDaily
Tags:ГСЧгенератор случайных чиселслучайностьэнтропия
Hubs: Cryptography
+47
3.7k 17
Comments 64
Popular right now
Top of the last 24 hours