Grover’s algorithm

Зато с асимметричной криптографией история куда неприятнее. RSA и ECDH действительно висят на крючке у Shor’s algorithm, и именно поэтому индустрия нервно двигается в сторону постквантовых схем. Но даже там речь не о магии из лабораторного постера: по тексту исходника, нынешние квантовые машины не умеют даже разложить 21 на множители, так что разговоры о тотальном крахе шифрования слегка опережают физику. Grover’s algorithm и пределы ускорения Главная путаница, похоже, растёт из очень удобного для алармизма слова «квантовый». Люди слышат его и автоматически дорисовывают себе экспоненциальный взлёт, хотя Grover’s algorithm даёт лишь квадратный выигрыш по времени поиска. Это неприятно для защитников, но не катастрофа уровня «выключите интернет». Есть и ещё один скучный, но важный момент. Поиск через Grover’s не распараллеливается так, как любят делать обычные вычисления, поэтому нельзя просто раскидать задачу по куче процессоров и получить линейный прирост. Именно здесь реальность ломает самые громкие прогнозы. RSA и ECDH под ударом, AES-128 пока нет Разделение тут простое, хоть и неприятное для маркетинга безопасности. Асимметричные алгоритмы вроде RSA и ECDH уязвимы из-за Shor’s algorithm, а симметричные системы вроде AES-128 и SHA-256 в ближайшей перспективе выглядят куда спокойнее. Именно поэтому обсуждение постквантовой криптографии чаще всего сводится не к паническому «всё сломано», а к более прагматичному вопросу миграции. Мы уже видели этот сюжет раньше, когда очередная технология обещала обнулить старую инфраструктуру, а потом упиралась в стоимость, масштабирование и банальную нехватку железа. Здесь похожая история: угроза есть, но для 128-битных симметричных ключей она не выглядит срочной, если только кто-то не принесёт алгоритм лучше Grover’s. Что пока умеют квантовые компьютеры И вот тут начинается самая приземлённая часть. Если квантовый компьютер не может даже разложить 21, то до сценария «сломаем AES, а потом ещё и весь интернет» ему, мягко говоря, далеко. Поэтому ближайшие годы, скорее всего, пройдут не под знаком немедленного отказа от классического шифрования, а под знаком постепенной подготовки к смене асимметричных алгоритмов. Пока же громкие заявления о гибели 128-битных ключей звучат как типичный технологический фольклор, который опережает железо на несколько эпох. Ирония в том, что именно симметричная криптография, которую обычно забывают в больших дискуссиях, в этой истории чувствует себя заметно увереннее.

Grover’s algorithm

Квантовые компьютеры не угрожают 128-битным ключам