Алгоритм Гровера
Что такое Алгоритм Гровера?
Алгоритм ГровераКвантовый алгоритм поиска, находящий помеченный элемент в неструктурированной базе из N записей примерно за sqrt(N) шагов, что даёт квадратичное ускорение против симметричных шифров и хеш-функций.
Алгоритм Гровера, предложенный Лавом Гровером в 1996 году, находит помеченный вход чёрного ящика за O(sqrt(N)) запросов вместо классических O(N). Применительно к криптографии он вдвое снижает фактический уровень безопасности симметричных примитивов и хеш-функций: у AES-128 эффективная стойкость падает примерно до 64 бит, а сопротивление SHA-256 поиску прообраза — приблизительно до 128 бит. Стандартная мера — удвоить длину ключей и хешей: переход на AES-256 и SHA-384 или SHA-512 сохраняет комфортный запас даже при атаках типа Гровера. В отличие от алгоритма Шора, сам по себе Гровер не взламывает криптографию с открытым ключом.
● Примеры
- 01
Используется в рекомендациях NIST для сравнения постквантовой стойкости AES-128 и AES-256.
- 02
Приводится как обоснование перехода HMAC и KDF на 256-битные и более длинные значения.
● Частые вопросы
Что такое Алгоритм Гровера?
Квантовый алгоритм поиска, находящий помеченный элемент в неструктурированной базе из N записей примерно за sqrt(N) шагов, что даёт квадратичное ускорение против симметричных шифров и хеш-функций. Относится к категории Криптография в кибербезопасности.
Что означает Алгоритм Гровера?
Квантовый алгоритм поиска, находящий помеченный элемент в неструктурированной базе из N записей примерно за sqrt(N) шагов, что даёт квадратичное ускорение против симметричных шифров и хеш-функций.
Как работает Алгоритм Гровера?
Алгоритм Гровера, предложенный Лавом Гровером в 1996 году, находит помеченный вход чёрного ящика за O(sqrt(N)) запросов вместо классических O(N). Применительно к криптографии он вдвое снижает фактический уровень безопасности симметричных примитивов и хеш-функций: у AES-128 эффективная стойкость падает примерно до 64 бит, а сопротивление SHA-256 поиску прообраза — приблизительно до 128 бит. Стандартная мера — удвоить длину ключей и хешей: переход на AES-256 и SHA-384 или SHA-512 сохраняет комфортный запас даже при атаках типа Гровера. В отличие от алгоритма Шора, сам по себе Гровер не взламывает криптографию с открытым ключом.
Как защититься от Алгоритм Гровера?
Защита от Алгоритм Гровера обычно сочетает технические меры и операционные практики, как описано в определении выше.
Какие есть другие названия Алгоритм Гровера?
Распространённые альтернативные названия: Поиск Гровера.
● Связанные термины
- cryptography№ 846
Постквантовая криптография
Классические криптографические алгоритмы, спроектированные так, чтобы оставаться стойкими к атакам как классических, так и крупномасштабных квантовых компьютеров.
- cryptography№ 020
AES (Advanced Encryption Standard)
Стандартизированный NIST блочный шифр с длиной блока 128 бит и ключами 128, 192 или 256 бит, разработанный Дамоном и Раймном; основной симметричный шифр в мире.
- cryptography№ 247
Криптографическая хеш-функция
Детерминированная односторонняя функция, отображающая входные данные произвольной длины в дайджест фиксированной длины и устойчивая к коллизиям, первообразам и вторым первообразам.
- cryptography№ 1036
Алгоритм Шора
Квантовый алгоритм, факторизующий большие целые числа и вычисляющий дискретные логарифмы за полиномиальное время; на достаточно мощном квантовом компьютере он взламывает RSA, Diffie-Hellman и криптографию на эллиптических кривых.
- cryptography№ 1121
Симметричное шифрование
Схема шифрования, в которой один и тот же секретный ключ используется и для шифрования, и для расшифрования; обеспечивает высокую скорость и стойкую конфиденциальность при безопасном обмене ключом.
- cryptography№ 890
Квантовая криптография
Криптография, использующая свойства квантовой механики — обычно фотонов — для достижения гарантий безопасности, недостижимых при чисто классической связи.