Алгоритм Шора
Что такое Алгоритм Шора?
Алгоритм ШораКвантовый алгоритм, факторизующий большие целые числа и вычисляющий дискретные логарифмы за полиномиальное время; на достаточно мощном квантовом компьютере он взламывает RSA, Diffie-Hellman и криптографию на эллиптических кривых.
Алгоритм Шора, опубликованный Питером Шором в 1994 году, решает задачи факторизации целых чисел и дискретного логарифмирования за полиномиальное время на отказоустойчивом квантовом компьютере. Именно эти задачи лежат в основе практически всех современных систем с открытым ключом: RSA, Diffie-Hellman, DSA и ECDSA. Существующее квантовое оборудование пока не способно факторизовать криптографически значимые ключи, однако серьёзные оценки показывают, что нескольких тысяч устойчивых логических кубитов будет достаточно для взлома RSA-2048. Эта перспектива и стала причиной запуска NIST-программы стандартизации PQC, а также опасений по поводу атак типа «собрать сейчас — расшифровать потом».
● Примеры
- 01
Используется как теоретический ориентир при оценке сроков квантовой угрозы для RSA-2048 и ECC P-256.
- 02
Обосновывает переход с классических асимметричных примитивов на решёточные KEM, например CRYSTALS-Kyber.
● Частые вопросы
Что такое Алгоритм Шора?
Квантовый алгоритм, факторизующий большие целые числа и вычисляющий дискретные логарифмы за полиномиальное время; на достаточно мощном квантовом компьютере он взламывает RSA, Diffie-Hellman и криптографию на эллиптических кривых. Относится к категории Криптография в кибербезопасности.
Что означает Алгоритм Шора?
Квантовый алгоритм, факторизующий большие целые числа и вычисляющий дискретные логарифмы за полиномиальное время; на достаточно мощном квантовом компьютере он взламывает RSA, Diffie-Hellman и криптографию на эллиптических кривых.
Как работает Алгоритм Шора?
Алгоритм Шора, опубликованный Питером Шором в 1994 году, решает задачи факторизации целых чисел и дискретного логарифмирования за полиномиальное время на отказоустойчивом квантовом компьютере. Именно эти задачи лежат в основе практически всех современных систем с открытым ключом: RSA, Diffie-Hellman, DSA и ECDSA. Существующее квантовое оборудование пока не способно факторизовать криптографически значимые ключи, однако серьёзные оценки показывают, что нескольких тысяч устойчивых логических кубитов будет достаточно для взлома RSA-2048. Эта перспектива и стала причиной запуска NIST-программы стандартизации PQC, а также опасений по поводу атак типа «собрать сейчас — расшифровать потом».
Как защититься от Алгоритм Шора?
Защита от Алгоритм Шора обычно сочетает технические меры и операционные практики, как описано в определении выше.
Какие есть другие названия Алгоритм Шора?
Распространённые альтернативные названия: Алгоритм факторизации Шора.
● Связанные термины
- cryptography№ 846
Постквантовая криптография
Классические криптографические алгоритмы, спроектированные так, чтобы оставаться стойкими к атакам как классических, так и крупномасштабных квантовых компьютеров.
- cryptography№ 890
Квантовая криптография
Криптография, использующая свойства квантовой механики — обычно фотонов — для достижения гарантий безопасности, недостижимых при чисто классической связи.
- cryptography№ 951
Алгоритм RSA
Алгоритм с открытым ключом Ривеста, Шамира и Адлемана (1977), безопасность которого опирается на трудность факторизации произведения двух больших простых чисел.
- cryptography№ 454
Алгоритм Гровера
Квантовый алгоритм поиска, находящий помеченный элемент в неструктурированной базе из N записей примерно за sqrt(N) шагов, что даёт квадратичное ускорение против симметричных шифров и хеш-функций.
- cryptography№ 732
Стандартизация PQC в NIST
Многолетний процесс NIST по отбору и стандартизации постквантовых криптоалгоритмов; первые три стандарта — FIPS 203, 204 и 205 — опубликованы в августе 2024 года.
- cryptography№ 253
CRYSTALS-Kyber
Решёточный механизм инкапсуляции ключа, стандартизированный NIST в августе 2024 года как FIPS 203 (ML-KEM); предназначен для замены ключевого обмена RSA и Diffie-Hellman в постквантовую эпоху.