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



Квантовые компьютеры не могут взломать схемы, надежность которых основана на сложности нахождения коллизий.

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

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

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

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

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

Читайте также:  SQL-инъекция в McAfee ePolicy Orchestrator

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


Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

12 + семь =

наверх