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

Два месяца назад преподаватель информатики Давид Цукерман (David Zuckerman) и магистрант Ешан Чаттопадхьяй (Eshan Chattopadhyay) опубликовали научную статью и теперь представят свой метод достоверной генерации псевдослучайных чисел на июньской конференции ACM по теории вычислений (Symposium on Theory of Computing, STOC). Эта работа чисто теоретическая, однако в перспективе, по убеждению Цукермана, она может повлечь ряд практических усовершенствований в криптографии, методике научно-исследовательских опросов и способах изучения других сложных сред, таких как климат.

«Мы показали, что при наличии двух источников случайных чисел низкого качества, которые обычно легче раздобыть, — двух независимых источников, никак не связанных между собой, их можно в какой-то мере объединить и получить истинно случайное число, — заявил Цукерман. — Попытки получить такой результат уже были, однако прежние методики никогда не опирались на источники столь низкого качества, требуя несколько более высокий уровень».

Технические подробности нового метода были представлены в статье «Explicit Two-Source Extractors and Resilient Functions» («Явное извлечение на основе двух источников и отказоустойчивые функции»). Университетские исследователи привнесли стойкие функции в новый алгоритм, используя опыт своих предшественников, и достигли поворотной вехи в истории теоретической информатики. Новое достижение уже пущено в ход: один из коллег техасцев, Синь Ли (Xin Li), использовал их результаты для создания последовательностей из множественных случайных чисел.

«Глобальный прогресс обычно бывает пошаговым, с несколькими промежуточными этапами, — полагает Цукерман. — Нам же удалось добиться успеха сразу на нескольких направлениях, именно поэтому все так взволнованы».

Работа техасцев была оценена по достоинству в академических кругах по всему миру. Так, Одед Голдрайх (Oded Goldreich), известный криптограф-теоретик, преподающий информатику в израильском институте Вейцмана, отозвался о ней как о «фантастическом результате«.

«Было бы здорово увидеть какой-нибудь конкретный экстрактор с двумя источниками с минимальной энтропией меньше 0,5, не говоря уже о том, чтобы побить энтропию в 0,499 у Бургейна, – написал Голдрайх на институтском сайте. – Работать с любой постоянной минимальной энтропией – настоящее удовольствие (см. A Challenge from the mid-1980s), а чтобы пойти дальше, и бессонных ночей не жалко».

Докторант Массачусетского технологического института Генри Юэнь (Henry Yuen) назвал работу техасских исследователей «потрясающей». «Если результат корректен, то я бы назвал это прорывом в теоретической информатике», – пишет Юэнь в блоге MIT.

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

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

«Я возвращался к этой проблеме снова и снова в течение более 20 лет, — признался Цукерман. — Теперь я в полном восторге от того, что все-таки ее решил».

Категории: Аналитика, Главное, Кибероборона