Учёные из университета Техаса предложили новый метод генерации случайных чисел, который позволяет комбинировать две относительно некачественные последовательности случайных чисел и получать качественный результат. Открытие может иметь далекоидущие последствия в области криптографии.
Исследования в этой области ведутся не одно десятилетие, но специалисты полагают, что в данном случае был совершён прорыв. До сих пор функции, которые генерируют качественные случайные последовательности на основе пары менее качественных, нуждались в более качественном «сырье».
Научная работа, описывающая новый метод, была опубликована в марте, а в июне её авторы, Дэвид Цукерман и Ишан Чаттопадхья, расскажут о своём открытии на симпозиуме по теории алгоритмов, которую проводит международная Ассоциация вычислительной техники (ACM).
В работе Цукермана и Чаттопадхьи предложена функция, принимающая случайные последовательности на n бит из двух источников со значениями мин-энтропии не менее logCn для достаточно большого значения C и выдающая случайный бит с ошибкой n−Ω(1). Лучший метод, известный ранее, требовал более качественных источников с мин-энтропией 0,499n.
«Мы продемонстрировали, что если у вас есть два низкокачественных источника случайных чисел, — а источники невысокого качества куда проще найти, — и они независимы друг от друга и не коррелируют между собой, то их можно комбинировать и получить случайное число высокого качества», — объясняет Цукерман в издании Threat Post.
Работа Цукермана и Чаттопадхьи рассматривает генерацию случайных чисел с теоретической точки зрения, но в перспективе их идеи способны найти практические применения в криптографии, социологии, а также в моделировании климата и других сложных сред.
Недостаточное качество источника случайных чисел делает уязвимой полагающуюся на него криптографическую систему. Документы Сноудена свидетельствуют о том, что спецслужбы уже используют предсказуемые генераторы случайных чисел в качестве лазейки, позволяющей обойти криптозащиту.
