Случайные числа и кибер-безопасность

dice-bowe830

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

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

Профессор компьютерных наук Дэвид Цукерман (David Zuckerman), вместе со студентом выпускником Эшаном Чатопадхе (Eshan Chatopadhyay) представят исследование, посвященное их методу, в июне 2016 года, на ежегодном Симпозиуме по Теории Вычислений (STOC). Это событие — главная теоретическая научная конференция, проводимая Ассоциацией Компьютерной Техники. Право участвовать в ней выдается после жесткого процесса проверки проектов кандидатов на наличие ошибок а также высокой значимости их открытия для развития науки. Их проект, наряду с двумя другими участниками, получит Премию STOC «Best Paper Award».

«Это проблема, к которой я возвращался снова и снова на протяжении более чем 20 лет, – говорит проф. Цукерман, – У меня просто мурашки по коже от того, что я наконец нашел решение».

В прошлом году Чатопадхе и Цукерман опубликовали черновик, описывающий их метод, на одном из Интернет форумов. В области более склонной к мелким, последовательным улучшениям, научное сообщество отметило прорыв в виде данного метода, сравнивая его с другими, теперь уже морально устаревшими. Одед Голдрейх (Oded Goldreich), профессор компьютерных наук в Израильском университете Вейсманна, отметил, что даже если это не самое существенное открытие последнего времени, оно как минимум «оправдает знатную ночную вечеринку».

«Когда я услышал про этот метод, я не мог заснуть, – говорит Йел Калай (Yael Kalai), младший исследователь по криптографии в Microsoft Research New England, занимавшийся экстракторами случайности. – Я был так поражен. Я не мог поверить в это. Я побежал в (онлайн) архив поглядеть на черновик. Это действительно шедевральная вещь».

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

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

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

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

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

«Один из распространенных случаев, когда шифрование употребляется неверно, состоит в использовании слабых случайностей, – говорит Цукерман. – В таком смысле, делая высококачественное шифрование более доступным, наши методы могут улучшить безопасность».

Их черновик показывает, как сгенерировать всего одно по-настоящему случайное число, эквивалентное броску монеты, однако бывший студент Цукермана, Ксин Ли (Xin Li), уже ранее демонстрировал способ увеличения количества генерируемых этим методом случайных чисел.

Веб-сайт, на котором Цукерман и Чатопадхе опубликовали свою работу прошлым летом, называется Электронное Обсуждение Вычислительной Сложности (Electronic Colloquium on Computational Complexity). Он позволяет исследователям делиться своей работой и получать обратную связь перед публикацией финальных версий в журналах или на научных конференциях. Ученые и математики внимательно рассматривали новую публикацию, оставляя комментарии и даже расширяя метод, делая его еще более мощным.

Источник: news.utexas.edu



Categories: Безопасность, Криптоанархизм, Криптография, Сервисы, Стандарты, Теория, Технологии

Tags: , ,

2 replies

  1. так что за магия с помощью которой две последовательности псевдослучайных чисел превращаются в невероятно случайные числа?

Trackbacks

  1. Случайные числа и кибер-безопасность | NewsAggregator

Поделитесь своими мыслями

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s