В криптографии размер ключа или длина ключа относится к числу бит в ключе, используемом криптографическим алгоритмом (например, шифром ) .
Длина ключа определяет верхнюю границу безопасности алгоритма (т. е. логарифмическую меру самой быстрой известной атаки на алгоритм), поскольку безопасность всех алгоритмов может быть нарушена атаками методом перебора . В идеале нижняя граница безопасности алгоритма по замыслу равна длине ключа (т. е. замысел алгоритма не снижает степень безопасности, присущую длине ключа).
Большинство алгоритмов с симметричным ключом разработаны так, чтобы иметь безопасность, равную длине их ключа. Однако после проектирования может быть обнаружена новая атака. Например, Triple DES был разработан с 168-битным ключом, но теперь известна атака со сложностью 2 112 (т. е. Triple DES теперь имеет только 112 бит безопасности, и из 168 бит в ключе атака сделала 56 «неэффективными» для безопасности). Тем не менее, пока безопасность (понимаемая как «количество усилий, которые потребуются для получения доступа») достаточна для конкретного приложения, то не имеет значения, совпадают ли длина ключа и безопасность. Это важно для алгоритмов с асимметричным ключом , потому что не известно ни одного такого алгоритма, который удовлетворял бы этому свойству; эллиптическая кривая криптографии подходит ближе всего с эффективной безопасностью примерно в половину длины ее ключа.
Ключи используются для управления работой шифра, так что только правильный ключ может преобразовать зашифрованный текст ( шифротекст ) в открытый текст . Все широко используемые шифры основаны на общеизвестных алгоритмах или имеют открытый исходный код , и поэтому только сложность получения ключа определяет безопасность системы, при условии отсутствия аналитической атаки (т. е. «структурной слабости» в используемых алгоритмах или протоколах), и предполагая, что ключ недоступен иным образом (например, путем кражи, вымогательства или компрометации компьютерных систем). Широко распространенное представление о том, что безопасность системы должна зависеть только от ключа, было явно сформулировано Огюстом Керкхоффсом (в 1880-х годах) и Клодом Шенноном (в 1940-х годах); эти утверждения известны как принцип Керкхоффса и максима Шеннона соответственно.
Следовательно, ключ должен быть достаточно большим, чтобы атака методом грубой силы (возможная против любого алгоритма шифрования) была неосуществимой, т. е. заняла бы слишком много времени и/или потребовала бы слишком много памяти для выполнения. Работа Шеннона по теории информации показала, что для достижения так называемой « совершенной секретности » длина ключа должна быть по крайней мере такой же большой, как и сообщение, и использоваться только один раз (этот алгоритм называется одноразовым блокнотом ). В свете этого, а также практической сложности управления такими длинными ключами, современная криптографическая практика отказалась от понятия совершенной секретности как требования к шифрованию и вместо этого сосредоточилась на вычислительной безопасности , при которой вычислительные требования взлома зашифрованного текста должны быть невыполнимы для злоумышленника.
Системы шифрования часто группируются в семейства. Обычные семейства включают симметричные системы (например, AES ) и асимметричные системы (например, RSA и криптография на эллиптических кривых [ECC]). Они могут быть сгруппированы в соответствии с центральным используемым алгоритмом (например, ECC и шифры Фейстеля ). Поскольку каждый из них имеет разный уровень криптографической сложности, обычно используются разные размеры ключей для одного и того же уровня безопасности в зависимости от используемого алгоритма. Например, безопасность, доступная с 1024-битным ключом, использующим асимметричный RSA, считается примерно равной по безопасности 80-битному ключу в симметричном алгоритме. [1]
Фактическая степень безопасности, достигаемая с течением времени, меняется по мере того, как становятся доступными более мощные вычислительные мощности и более мощные математические аналитические методы. По этой причине криптологи склонны обращать внимание на индикаторы, указывающие на то, что алгоритм или длина ключа демонстрируют признаки потенциальной уязвимости, чтобы перейти к более длинным размерам ключей или более сложным алгоритмам. Например, по состоянию на май 2007 года [обновлять]1039-битное целое число было факторизовано с помощью специального числового поля с использованием 400 компьютеров в течение 11 месяцев. [2] Факторизованное число имело особую форму; специальное числовое поле сито не может использоваться на ключах RSA. Вычисление примерно эквивалентно взлому 700-битного ключа RSA. Однако это может быть предварительным предупреждением о том, что 1024-битные ключи RSA, используемые в безопасной онлайн-торговле, следует прекратить , поскольку они могут стать взламываемыми в обозримом будущем. Профессор криптографии Арьен Ленстра заметил, что «в прошлый раз нам потребовалось девять лет, чтобы перейти от специального к неспециальному, трудно разлагаемому числу», а на вопрос о том, мертвы ли 1024-битные ключи RSA, он сказал: «Ответ на этот вопрос — безусловно да». [3]
Атака Logjam 2015 года выявила дополнительные опасности при использовании обмена ключами Диффи-Хеллмана, когда используются только один или несколько общих простых модулей размером 1024 бита или меньше. Эта практика, довольно распространенная в то время, позволяет скомпрометировать большие объемы коммуникаций за счет атаки на небольшое количество простых чисел. [4] [5]
Даже если симметричный шифр в настоящее время не поддается взлому путем использования структурных слабостей в его алгоритме, может оказаться возможным перебрать все пространство ключей с помощью так называемой атаки методом грубой силы. Поскольку более длинные симметричные ключи требуют экспоненциально больше работы для поиска методом грубой силы, достаточно длинный симметричный ключ делает эту линию атаки непрактичной.
При длине ключа n бит существует 2 n возможных ключей. Это число растет очень быстро с увеличением n . Большое количество операций (2 128 ), необходимых для перебора всех возможных 128-битных ключей, широко считается недостижимым для традиционных цифровых вычислительных технологий в обозримом будущем. [6] Однако квантовый компьютер, способный запустить алгоритм Гровера, сможет искать возможные ключи более эффективно. Если квантовый компьютер подходящего размера уменьшит 128-битный ключ до 64-битной безопасности, примерно эквивалентной DES . Это одна из причин, по которой AES поддерживает длину ключа 256 бит и более. [a]
Шифр Lucifer компании IBM был выбран в 1974 году в качестве основы для того, что впоследствии стало Стандартом шифрования данных . Длина ключа Lucifer была уменьшена со 128 бит до 56 бит , что, по мнению АНБ и NIST, было достаточным для неправительственной защиты в то время. АНБ располагает крупными вычислительными ресурсами и большим бюджетом; некоторые криптографы, включая Уитфилда Диффи и Мартина Хеллмана, жаловались, что это сделало шифр настолько слабым, что компьютеры АНБ смогли бы взломать ключ DES за день с помощью параллельных вычислений методом перебора . АНБ оспорило это, заявив, что перебор DES займет у них «примерно 91 год». [7]
Однако к концу 90-х годов стало ясно, что DES можно взломать за несколько дней с помощью специально разработанного оборудования, которое может быть приобретено крупной корпорацией или правительством. [8] [9] В книге Cracking DES (O'Reilly and Associates) рассказывается об успешной возможности взлома 56-битного DES в 1998 году с помощью атаки методом грубой силы, организованной группой по защите прав киберпреступников с ограниченными ресурсами; см. EFF DES cracker . Еще до этой демонстрации 56 бит считалось недостаточной длиной для ключей симметричного алгоритма общего назначения. Из-за этого DES был заменен в большинстве приложений безопасности на Triple DES , который имеет 112 бит безопасности при использовании 168-битных ключей (тройной ключ). [1]
Опубликованный в 2001 году Расширенный стандарт шифрования использует ключи размером 128, 192 или 256 бит. Многие наблюдатели считают, что 128 бит достаточно для обозримого будущего симметричных алгоритмов качества AES , пока не станут доступны квантовые компьютеры . [ необходима цитата ] Однако с 2015 года Агентство национальной безопасности США выпустило руководство о том, что оно планирует перейти на устойчивые к квантовым вычислениям алгоритмы и теперь требует 256-битные ключи AES для данных, классифицированных до Совершенно секретно . [10]
В 2003 году Национальный институт стандартов и технологий США ( NIST) предложил поэтапно отказаться от 80-битных ключей к 2015 году. В 2005 году 80-битные ключи были разрешены только до 2010 года. [11]
С 2015 года руководство NIST гласит, что «использование ключей, которые обеспечивают менее 112 бит стойкости для согласования ключей, теперь запрещено». Одобренные NIST симметричные алгоритмы шифрования включают Triple DES с тремя ключами и AES . Одобрения для Triple DES с двумя ключами и Skipjack были отозваны в 2015 году; алгоритм Skipjack от АНБ , используемый в его программе Fortezza, использует 80-битные ключи. [1]
Эффективность криптосистем с открытым ключом зависит от сложности (вычислительной и теоретической) решения некоторых математических задач, таких как факторизация целых чисел . Решение этих задач требует много времени, но обычно быстрее, чем перебор всех возможных ключей методом грубой силы. Таким образом, асимметричные ключи должны быть длиннее для эквивалентной устойчивости к атакам, чем ключи симметричного алгоритма. Предполагается, что наиболее распространенные методы будут слабы против достаточно мощных квантовых компьютеров в будущем.
С 2015 года NIST рекомендует использовать ключи длиной не менее 2048 бит для RSA [12], что является обновлением общепринятой рекомендации о минимальной длине ключа в 1024 бита, принятой по крайней мере с 2002 года. [13]
1024-битные ключи RSA эквивалентны по прочности 80-битным симметричным ключам, 2048-битные ключи RSA эквивалентны 112-битным симметричным ключам, 3072-битные ключи RSA эквивалентны 128-битным симметричным ключам, а 15360-битные ключи RSA эквивалентны 256-битным симметричным ключам. [14] В 2003 году RSA Security заявила, что 1024-битные ключи, вероятно, станут взламываемыми где-то между 2006 и 2010 годами, в то время как 2048-битные ключи будут достаточны до 2030 года. [15] По состоянию на 2020 год [обновлять]самым большим публично известным взломанным ключом RSA является RSA-250 с 829 битами. [16]
Конечно-полевой алгоритм Диффи-Хеллмана имеет примерно такую же прочность ключа, как и RSA для тех же размеров ключей. Фактор работы для взлома Диффи-Хеллмана основан на задаче дискретного логарифмирования , которая связана с задачей факторизации целых чисел, на которой основана прочность RSA. Таким образом, 2048-битный ключ Диффи-Хеллмана имеет примерно такую же прочность, как 2048-битный ключ RSA.
Криптография на основе эллиптических кривых (ECC) — это альтернативный набор асимметричных алгоритмов, который является эквивалентно безопасным с более короткими ключами, требуя всего лишь примерно вдвое больше бит, чем эквивалентный симметричный алгоритм. 256-битный ключ Диффи–Хеллмана на основе эллиптических кривых (ECDH) имеет примерно такой же коэффициент безопасности, как и 128-битный ключ AES . [12] Сообщение, зашифрованное с помощью алгоритма эллиптического ключа с использованием ключа длиной 109 бит, было взломано в 2004 году. [17]
Ранее АНБ рекомендовало 256-битный ECC для защиты секретной информации вплоть до уровня СЕКРЕТНО и 384-битный для СОВЕРШЕННО СЕКРЕТНО; [10] В 2015 году агентство объявило о планах перехода к квантово-устойчивым алгоритмам к 2024 году, а до тех пор рекомендует 384-битный для всей секретной информации. [18]
Две наиболее известные атаки квантовых вычислений основаны на алгоритме Шора и алгоритме Гровера . Из этих двух алгоритм Шора представляет больший риск для текущих систем безопасности.
Широко распространено мнение, что производные алгоритма Шора эффективны против всех основных алгоритмов с открытым ключом, включая RSA , Диффи-Хеллмана и эллиптической кривой . По словам профессора Жиля Брассара , эксперта в области квантовых вычислений: «Время, необходимое для факторизации целого числа RSA, того же порядка, что и время, необходимое для использования того же целого числа в качестве модуля для одного шифрования RSA. Другими словами, для взлома RSA на квантовом компьютере (вплоть до мультипликативной константы) требуется не больше времени, чем для его законного использования на классическом компьютере». Общее мнение заключается в том, что эти алгоритмы с открытым ключом небезопасны при любом размере ключа, если станут доступны достаточно большие квантовые компьютеры, способные запустить алгоритм Шора. Последствием этой атаки является то, что все данные, зашифрованные с использованием современных систем безопасности на основе стандартов, таких как вездесущий SSL, используемый для защиты электронной коммерции и интернет-банкинга, и SSH, используемый для защиты доступа к конфиденциальным вычислительным системам, находятся под угрозой. Зашифрованные данные, защищенные с помощью алгоритмов с открытым ключом, могут быть заархивированы и могут быть взломаны позднее, что обычно называется ретроактивным/ретроспективным дешифрованием или « собрать сейчас, расшифровать позже ».
Широко распространены предположения , что распространенные симметричные шифры (такие как AES или Twofish ) и устойчивые к коллизиям хэш-функции (такие как SHA ) обеспечивают большую безопасность от известных атак квантовых вычислений. Они широко считаются наиболее уязвимыми для алгоритма Гровера . Беннетт, Бернстайн, Брассар и Вазирани доказали в 1996 году, что поиск ключа методом перебора на квантовом компьютере не может быть быстрее, чем примерно 2 n /2 вызовов базового криптографического алгоритма, по сравнению с примерно 2 n в классическом случае. [19] Таким образом, при наличии больших квантовых компьютеров n -битный ключ может обеспечить по крайней мере n /2 бит безопасности. Квантовый перебор легко преодолевается путем удвоения длины ключа, что имеет небольшие дополнительные вычислительные затраты при обычном использовании. Это означает, что для достижения 128-битного рейтинга безопасности против квантового компьютера требуется как минимум 256-битный симметричный ключ. Как упоминалось выше, в 2015 году АНБ объявило о планах перехода на квантово-устойчивые алгоритмы. [10]
В своем отчете «Часто задаваемые вопросы по квантовым вычислениям» за 2016 год АНБ подтвердило:
«Достаточно большой квантовый компьютер, если он будет построен, будет способен подорвать все широко распространенные алгоритмы открытого ключа, используемые для установления ключей и цифровых подписей. [...] Общепризнано, что квантовые вычислительные методы гораздо менее эффективны против симметричных алгоритмов, чем против широко используемых в настоящее время алгоритмов открытого ключа. В то время как криптография открытого ключа требует изменений в фундаментальной конструкции для защиты от потенциального будущего квантового компьютера, симметричные алгоритмы ключа считаются безопасными при условии использования достаточно большого размера ключа. [...] Алгоритмы открытого ключа ( RSA , Диффи-Хеллмана , [Эллиптическая кривая Диффи-Хеллмана] ECDH и [Алгоритм цифровой подписи на эллиптической кривой] ECDSA ) все уязвимы для атак достаточно большого квантового компьютера. [...] Хотя было предложено несколько интересных квантово-устойчивых алгоритмов открытого ключа за пределами АНБ, ничего из них не было стандартизировано NIST , и АНБ в настоящее время не определяет никаких коммерческих стандартов квантовой устойчивости. АНБ ожидает, что NIST будет играть ведущую роль в усилиях по разработке широко принятого стандартизированного набора квантово-устойчивых алгоритмов. [...] Учитывая уровень интереса в криптографическом сообществе, мы надеемся, что в следующем десятилетии квантово-устойчивые алгоритмы станут широко доступны. [...] Алгоритмы AES-256 и SHA-384 симметричны и считаются защищенными от атак со стороны большого квантового компьютера». [20]
В пресс-релизе 2022 года АНБ сообщило:
«Криптографически релевантный квантовый компьютер (CRQC) будет иметь потенциал для взлома систем с открытым ключом (иногда называемых асимметричной криптографией), которые используются сегодня. Учитывая зарубежные достижения в области квантовых вычислений, сейчас самое время спланировать, подготовить и заложить в бюджет переход к [квантовоустойчивым] алгоритмам QR, чтобы гарантировать постоянную защиту [национальных систем безопасности] NSS и связанных с ними активов в случае, если CRQC станет достижимой реальностью». [21]
С сентября 2022 года АНБ переходит от коммерческого набора алгоритмов национальной безопасности (теперь именуемого CNSA 1.0), первоначально запущенного в январе 2016 года, к коммерческому набору алгоритмов национальной безопасности 2.0 (CNSA 2.0), оба варианта кратко описаны ниже: [22] [b]
CNSA 2.0
CNSA 1.0