События

Квантовый компьютер бесполезен для поиска коллизий хеш-функций

Квантовый компьютер бесполезен для поиска коллизий хеш-функций

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

Квантовые алгоритмы эффективно решают проблемы факторинга и дискретных логарифмов. На классических компьютерах такие задачи решить достаточно сложно, поэтому криптосистема RSA и алгоритм Диффи-Хеллмана считаются надежными. Все используемые на сегодняшний день криптографические схемы подписи, надежность которых основана на факторинге и вычислении дискретного логарифма, могут быть взломаны при помощи квантового компьютера, однако пока таких машин не существует. Даже если квантовый компьютер будет построен, он окажется бесполезен для поиска коллизий хеш-функций (H) или подбора пар определенных сообщений (M1, M2), таких как H(M1)=H(M2). Таким образом, квантовые компьютеры не могут взломать схемы, надежность которых основана на сложности нахождения коллизий, например, SPHINCS или XMSS.

Эксперт приводит ряд ключевых техник, используемых данными схемами: одноразовые схемы подписей, дерево хешей (дерево Меркла) и многоразовые схемы подписей.

Одноразовые алгоритмы позволяют получать устойчивые к взлому подписи даже в случае неимоверного увеличения вычислительной мощности компьютера (например, при использовании квантового компьютера).

Самая большая проблема одноразовых схем подписей - передача открытого ключа. Ральф Меркл (Ralph Charles Merkle) предложил криптосистему, где один открытый ключ можно использовать для множества сообщений. Схема подписи Меркла объединяет в себе схему одноразовой подписи (либо Лампорта, либо Винтерница) с деревом Меркла, что позволяет подписать одним ключом несколько сообщений, не создавая риск для их безопасности.

Дерево Меркла представляет собой математическую структуру, хеширующую различные наборы данных в один компактный хеш: корень Меркла. Базовая идея схемы достаточно проста - это обычное дерево (структура данных), в узлах которого находятся хеши, полученные по данным дочерних узлов. При использовании хеш-дерева верификаторам подписей потребуется хранить только корень хеша (обычно его размер составляет 256 бит), вместо всех открытых ключей, отмечает эксперт.

Автор: Сергей Куприянов
4.02.2017 (13:59)
Пройди тест и узнай об этом!
Информер новостей
Расширение для Google Chrome
Пишите нам

Редакция: info@alterprogs.ru

Реклама: adv@alterprogs.ru

Все права защищены © 2010-2019

"Alterprogs.ru" - технологии будущего

Контакты  | Карта сайта

Использование любых материалов, размещенных на сайте, разрешается при условии ссылки на alterprogs.ru. Для интернет-изданий - обязательна прямая открытая для поисковых систем гиперссылка. Ссылка должна быть размещена в независимости от полного либо частичного использования материалов. Материалы в рубрике "Новости партнеров" публикуются на правах рекламы.