Оффлайн
- Регистрация
- 19.09.18
- Сообщения
- 154
- Реакции
- 79
- Репутация
- 1
Всем привет. Разберу тему, вокруг которой много путаницы — почему одни виды шифрования считаются устойчивыми к квантовым компьютерам, а другие нет, хотя оба используют серьёзную математику и оба массово применяются прямо сейчас.
Два принципиально разных типа шифрования
Прежде чем говорить о квантовой угрозе, важно понимать, что AES и RSA решают разные задачи и построены на разной математике.
AES — симметричный алгоритм. Один и тот же ключ используется и для шифрования, и для расшифровки. Именно AES шифрует твой диск через LUKS, файлы через VeraCrypt, сам трафик внутри VPN-туннеля.
RSA — асимметричный алгоритм. Пара ключей: публичный, который можно раздавать всем, и приватный, который остаётся только у владельца. RSA обычно не шифрует сами данные напрямую — он используется для обмена ключами и для цифровых подписей, после чего дальнейшее шифрование делает уже симметричный алгоритм вроде AES.
Почему RSA уязвим для квантовых компьютеров
RSA держится на одной конкретной математической сложности — трудности разложения очень больших чисел на простые множители. Обычному компьютеру на это требуются годы или столетия, в зависимости от размера ключа, и именно эта неразрешимая на практике задача и защищает RSA.
Но в 1994 году математик Питер Шор опубликовал алгоритм, который специально решает именно эту задачу — разложение чисел на множители — экспоненциально быстрее на квантовом компьютере, чем на обычном. Алгоритм Шора не теоретическая абстракция, а конкретный, математически доказанный метод. Проблема лишь в том, что пока не существует квантового компьютера с достаточным количеством стабильных кубитов, чтобы реально применить его к ключам того размера, что используются сейчас.
Но сама природа уязвимости в том, что RSA держится ровно на одной математической проблеме, и для этой конкретной проблемы уже существует готовый квантовый алгоритм взлома. Вопрос не "если", а "когда" появится железо, способное его выполнить.
Почему AES устроен принципиально иначе
AES не основан на факторизации чисел или на какой-либо другой задаче, для которой есть специализированный квантовый алгоритм вроде алгоритма Шора. AES — это симметричный шифр, устройство которого сводится к перебору возможных ключей методом грубой силы, если не находить более умных путей взлома.
Для симметричных алгоритмов единственный известный квантовый метод ускорения перебора — это алгоритм Гровера, опубликованный в 1996 году. Но в отличие от алгоритма Шора, который даёт экспоненциальное ускорение (взлом становится качественно, на порядки быстрее), алгоритм Гровера даёт лишь квадратичное ускорение.
Что значит "квадратичное ускорение" на практике
Если AES-256 обычному компьютеру требуется перебрать в среднем половину от 2 в степени 256 комбинаций ключа, то алгоритм Гровера на квантовом компьютере сократит эту работу до примерно 2 в степени 128 операций — что эквивалентно по сложности обычному брутфорсу AES-128.
А AES-128 сам по себе всё ещё считается практически невзламываемым методом полного перебора даже без всякой квантовой угрозы — количество операций настолько огромно, что это остаётся вычислительно неосуществимым на обозримое будущее даже теоретически, с любым мыслимым количеством обычных или квантовых процессоров, объединённых вместе.
То есть AES-256 после появления мощных квантовых компьютеров не станет "взломанным" — он просто эффективно "просядет" до уровня надёжности AES-128, который сам по себе остаётся достаточно сильным.
Итоговая разница простыми словами
RSA уязвим, потому что квантовый алгоритм Шора атакует именно ту математическую структуру, на которой построен RSA — и делает это экспоненциально быстрее.
AES устойчив, потому что для симметричных шифров существует только алгоритм Гровера, дающий лишь квадратичное, а не экспоненциальное ускорение — и даже с этим ускорением AES-256 сохраняет практическую защиту, эквивалентную нынешнему AES-128.
Что это значит практически прямо сейчас
Данные, зашифрованные через LUKS или VeraCrypt с AES-256, остаются защищены даже в гипотетическом мире с работающими крупномасштабными квантовыми компьютерами.
А вот всё, что построено на RSA — обмен ключами в старых версиях TLS, часть PGP-инфраструктуры, цифровые подписи многих сервисов — потенциально уязвимо, когда (и если) появится достаточно мощное квантовое железо.
Что уже делают в индустрии на опережение
NIST в 2024 году финализировал новые стандарты постквантовой криптографии — алгоритмы вроде CRYSTALS-Kyber для обмена ключами и CRYSTALS-Dilithium для цифровых подписей, построенные на математических задачах, для которых пока не существует известного эффективного квантового алгоритма взлома, в отличие от факторизации чисел у RSA.
Signal уже добавил постквантовый компонент в свой протокол обмена ключами. WireGuard-сообщество работает над интеграцией постквантовой защиты через проекты вроде Rosenpass.
Итог
Не всё шифрование одинаково устойчиво к квантовым компьютерам — разница не в силе алгоритма как таковой, а в том, атакует ли конкретный известный квантовый метод именно ту математическую структуру, на которой алгоритм построен. AES-256 в этом смысле оказался архитектурно удачным ещё до того, как кто-либо всерьёз думал о квантовых компьютерах — а RSA, наоборот, строится на именно той проблеме, для которой алгоритм взлома уже существует математически, просто пока не хватает железа для его практического применения.
Интересно услышать, кто уже смотрел в сторону постквантовых алгоритмов на практике — переходили ли на что-то конкретное, или пока это остаётся в основном теорией на будущее.
Два принципиально разных типа шифрования
Прежде чем говорить о квантовой угрозе, важно понимать, что AES и RSA решают разные задачи и построены на разной математике.
AES — симметричный алгоритм. Один и тот же ключ используется и для шифрования, и для расшифровки. Именно AES шифрует твой диск через LUKS, файлы через VeraCrypt, сам трафик внутри VPN-туннеля.
RSA — асимметричный алгоритм. Пара ключей: публичный, который можно раздавать всем, и приватный, который остаётся только у владельца. RSA обычно не шифрует сами данные напрямую — он используется для обмена ключами и для цифровых подписей, после чего дальнейшее шифрование делает уже симметричный алгоритм вроде AES.
Почему RSA уязвим для квантовых компьютеров
RSA держится на одной конкретной математической сложности — трудности разложения очень больших чисел на простые множители. Обычному компьютеру на это требуются годы или столетия, в зависимости от размера ключа, и именно эта неразрешимая на практике задача и защищает RSA.
Но в 1994 году математик Питер Шор опубликовал алгоритм, который специально решает именно эту задачу — разложение чисел на множители — экспоненциально быстрее на квантовом компьютере, чем на обычном. Алгоритм Шора не теоретическая абстракция, а конкретный, математически доказанный метод. Проблема лишь в том, что пока не существует квантового компьютера с достаточным количеством стабильных кубитов, чтобы реально применить его к ключам того размера, что используются сейчас.
Но сама природа уязвимости в том, что RSA держится ровно на одной математической проблеме, и для этой конкретной проблемы уже существует готовый квантовый алгоритм взлома. Вопрос не "если", а "когда" появится железо, способное его выполнить.
Почему AES устроен принципиально иначе
AES не основан на факторизации чисел или на какой-либо другой задаче, для которой есть специализированный квантовый алгоритм вроде алгоритма Шора. AES — это симметричный шифр, устройство которого сводится к перебору возможных ключей методом грубой силы, если не находить более умных путей взлома.
Для симметричных алгоритмов единственный известный квантовый метод ускорения перебора — это алгоритм Гровера, опубликованный в 1996 году. Но в отличие от алгоритма Шора, который даёт экспоненциальное ускорение (взлом становится качественно, на порядки быстрее), алгоритм Гровера даёт лишь квадратичное ускорение.
Что значит "квадратичное ускорение" на практике
Если AES-256 обычному компьютеру требуется перебрать в среднем половину от 2 в степени 256 комбинаций ключа, то алгоритм Гровера на квантовом компьютере сократит эту работу до примерно 2 в степени 128 операций — что эквивалентно по сложности обычному брутфорсу AES-128.
А AES-128 сам по себе всё ещё считается практически невзламываемым методом полного перебора даже без всякой квантовой угрозы — количество операций настолько огромно, что это остаётся вычислительно неосуществимым на обозримое будущее даже теоретически, с любым мыслимым количеством обычных или квантовых процессоров, объединённых вместе.
То есть AES-256 после появления мощных квантовых компьютеров не станет "взломанным" — он просто эффективно "просядет" до уровня надёжности AES-128, который сам по себе остаётся достаточно сильным.
Итоговая разница простыми словами
RSA уязвим, потому что квантовый алгоритм Шора атакует именно ту математическую структуру, на которой построен RSA — и делает это экспоненциально быстрее.
AES устойчив, потому что для симметричных шифров существует только алгоритм Гровера, дающий лишь квадратичное, а не экспоненциальное ускорение — и даже с этим ускорением AES-256 сохраняет практическую защиту, эквивалентную нынешнему AES-128.
Что это значит практически прямо сейчас
Данные, зашифрованные через LUKS или VeraCrypt с AES-256, остаются защищены даже в гипотетическом мире с работающими крупномасштабными квантовыми компьютерами.
А вот всё, что построено на RSA — обмен ключами в старых версиях TLS, часть PGP-инфраструктуры, цифровые подписи многих сервисов — потенциально уязвимо, когда (и если) появится достаточно мощное квантовое железо.
Что уже делают в индустрии на опережение
NIST в 2024 году финализировал новые стандарты постквантовой криптографии — алгоритмы вроде CRYSTALS-Kyber для обмена ключами и CRYSTALS-Dilithium для цифровых подписей, построенные на математических задачах, для которых пока не существует известного эффективного квантового алгоритма взлома, в отличие от факторизации чисел у RSA.
Signal уже добавил постквантовый компонент в свой протокол обмена ключами. WireGuard-сообщество работает над интеграцией постквантовой защиты через проекты вроде Rosenpass.
Итог
Не всё шифрование одинаково устойчиво к квантовым компьютерам — разница не в силе алгоритма как таковой, а в том, атакует ли конкретный известный квантовый метод именно ту математическую структуру, на которой алгоритм построен. AES-256 в этом смысле оказался архитектурно удачным ещё до того, как кто-либо всерьёз думал о квантовых компьютерах — а RSA, наоборот, строится на именно той проблеме, для которой алгоритм взлома уже существует математически, просто пока не хватает железа для его практического применения.
Интересно услышать, кто уже смотрел в сторону постквантовых алгоритмов на практике — переходили ли на что-то конкретное, или пока это остаётся в основном теорией на будущее.