Квантовый компьютер убьёт шифрование AES-128? Математика говорит: для этого нужно больше машин, чем атомов во Вселенной
NewsMakerПараллелизация ломает алгоритм Гровера — и все забыли об этом.
AES-128 - один из базовых механизмов шифрования, который защищает данные в интернете и внутри сервисов. Когда браузер открывает сайт по HTTPS, когда мессенджер шифрует переписку или система хранит пароли и токены, часто в основе лежит именно этот алгоритм. Он берет данные и «перемешивает» их с помощью ключа длиной 128 бит. Без этого ключа исходный текст восстановить нельзя: остается только перебирать все возможные варианты, а их 2^128, то есть число с 38 нулями. Даже при огромных вычислительных мощностях такой перебор занимает астрономическое время.
На фоне разговоров о квантовых компьютерах вокруг AES-128 закрепилась упрощенная формула: как только появятся достаточно мощные квантовые машины, защита «сожмется» вдвое и станет сопоставима с 64 битами. Из этого делают прямой вывод, что алгоритм почти потеряет смысл. Криптограф Филиппо Валсорда разбирает этот тезис и показывает, где именно ломается логика.
Основанием для такого страха стал алгоритм Гровера. Он ускоряет поиск по неструктурированному набору данных и теоретически снижает число шагов при переборе ключей. В пересказах часто остается только одно: вместо 2^128 операций якобы нужно примерно 2^64. Но такой пересчет игнорирует, как устроена реальная атака и какие ограничения возникают при попытке реализовать ее на практике.
Обычный перебор на классических компьютерах хорошо делится на части. Если задача требует проверить миллиарды вариантов, ее можно раздать тысячам машин, и каждая возьмет свою долю. Чем больше ресурсов, тем быстрее падает общее время. Алгоритм Гровера ведет себя иначе. Он требует длинного последовательного вычисления, где шаги зависят друг от друга. Попытка «разрезать» задачу и распараллелить ее резко снижает выигрыш от квантового ускорения.
AES-128 - один из базовых механизмов шифрования, который защищает данные в интернете и внутри сервисов. Когда браузер открывает сайт по HTTPS, когда мессенджер шифрует переписку или система хранит пароли и токены, часто в основе лежит именно этот алгоритм. Он берет данные и «перемешивает» их с помощью ключа длиной 128 бит. Без этого ключа исходный текст восстановить нельзя: остается только перебирать все возможные варианты, а их 2^128, то есть число с 38 нулями. Даже при огромных вычислительных мощностях такой перебор занимает астрономическое время.
На фоне разговоров о квантовых компьютерах вокруг AES-128 закрепилась упрощенная формула: как только появятся достаточно мощные квантовые машины, защита «сожмется» вдвое и станет сопоставима с 64 битами. Из этого делают прямой вывод, что алгоритм почти потеряет смысл. Криптограф Филиппо Валсорда разбирает этот тезис и показывает, где именно ломается логика.
Основанием для такого страха стал алгоритм Гровера. Он ускоряет поиск по неструктурированному набору данных и теоретически снижает число шагов при переборе ключей. В пересказах часто остается только одно: вместо 2^128 операций якобы нужно примерно 2^64. Но такой пересчет игнорирует, как устроена реальная атака и какие ограничения возникают при попытке реализовать ее на практике.
Обычный перебор на классических компьютерах хорошо делится на части. Если задача требует проверить миллиарды вариантов, ее можно раздать тысячам машин, и каждая возьмет свою долю. Чем больше ресурсов, тем быстрее падает общее время. Алгоритм Гровера ведет себя иначе. Он требует длинного последовательного вычисления, где шаги зависят друг от друга. Попытка «разрезать» задачу и распараллелить ее резко снижает выигрыш от квантового ускорения.