В криптографии размер ключа или длина ключа относится к количеству битов в ключе , используемом криптографическим алгоритмом (например, шифром ).
Длина ключа определяет верхнюю границу безопасности алгоритма (т. е. логарифмическую меру самой быстрой известной атаки на алгоритм), поскольку безопасность всех алгоритмов может быть нарушена атаками методом перебора . В идеале нижняя граница безопасности алгоритма по замыслу равна длине ключа (то есть конструкция алгоритма не умаляет степень безопасности, присущую длине ключа).
Большинство алгоритмов с симметричным ключом спроектированы таким образом, чтобы обеспечить безопасность, равную длине ключа. Однако после проектирования может быть обнаружена новая атака. Например, 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 . Большое количество операций ( 2128 ), необходимых для перебора всех возможных 128-битных ключей, широко считается недостижимым для традиционных цифровых вычислительных технологий в обозримом будущем. [6] Однако квантовый компьютер , способный запускать алгоритм Гровера, сможет более эффективно искать возможные ключи. Если бы квантовый компьютер подходящего размера сократил бы 128-битный ключ до 64-битного, это примерно эквивалентно DES . Это одна из причин, почему AES поддерживает длину ключей 256 бит и более. [а]
Шифр Люцифер компании IBM был выбран в 1974 году в качестве основы для того, что впоследствии стало стандартом шифрования данных . Длина ключа Люцифера была уменьшена со 128 бит до 56 бит , что, по мнению АНБ и НИСТ, в то время было достаточным для неправительственной защиты. АНБ располагает крупными вычислительными ресурсами и большим бюджетом; некоторые криптографы, в том числе Уитфилд Диффи и Мартин Хеллман, жаловались, что это сделало шифр настолько слабым, что компьютеры АНБ могли взломать ключ DES за день с помощью параллельных вычислений методом грубой силы . АНБ оспорило это, заявив, что на перебор DES у них уйдет «примерно 91 год». [7]
Однако к концу 90-х стало ясно, что DES можно взломать за несколько дней с помощью специально изготовленного оборудования, которое могло быть куплено крупной корпорацией или правительством. [8] [9] В книге «Взлом DES» (O'Reilly and Associates) рассказывается об успешной способности взломать 56-битный DES в 1998 году с помощью грубой атаки, организованной группой по защите гражданских прав в киберпространстве с ограниченными ресурсами; см. взломщик EFF DES . Еще до этой демонстрации длина 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 рекомендует для RSA минимум 2048-битные ключи , [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]
В FAQ по квантовым вычислениям 2016 года АНБ подтвердило:
«Достаточно большой квантовый компьютер, если он будет построен, будет способен подорвать все широко распространенные алгоритмы с открытым ключом, используемые для создания ключей и цифровых подписей. [...] Принято считать, что методы квантовых вычислений гораздо менее эффективны против симметричных алгоритмов. чем по сравнению с ныне широко используемыми алгоритмами с открытым ключом. Хотя криптография с открытым ключом требует изменений в фундаментальной конструкции для защиты от потенциального будущего квантового компьютера, алгоритмы с симметричным ключом считаются безопасными при условии использования достаточно большого размера ключа. Алгоритмы с открытым ключом ( RSA , Диффи-Хеллмана , [Диффи-Хеллмана на эллиптической кривой] ECDH и [Алгоритм цифровой подписи на эллиптической кривой] ECDSA ) уязвимы для атак со стороны достаточно большого квантового компьютера. [...] Хотя. Ряд интересных квантовоустойчивых алгоритмов с открытым ключом был предложен вне АНБ, NIST ничего не стандартизировал , и в настоящее время АНБ не определяет никаких коммерческих квантовоустойчивых стандартов. АНБ ожидает, что NIST будет играть ведущую роль в разработке широко распространенного стандартизированного набора квантовоустойчивых алгоритмов. [...] Учитывая уровень интереса в криптографическом сообществе, мы надеемся, что в следующем десятилетии появятся широко доступные квантовостойкие алгоритмы. [...] Алгоритмы AES-256 и SHA-384 симметричны и считаются безопасными от атак со стороны большого квантового компьютера». [20]
В пресс-релизе 2022 года АНБ уведомило:
«Криптоаналитически значимый квантовый компьютер (CRQC) будет иметь потенциал для взлома систем с открытым ключом (иногда называемых асимметричной криптографией), которые используются сегодня. Учитывая зарубежные достижения в области квантовых вычислений, сейчас самое время планировать, готовиться и составлять бюджет. для перехода на [квантово-устойчивые] QR-алгоритмы для обеспечения устойчивой защиты [систем национальной безопасности] НСС и связанных с ними активов в случае, если CRQC станет достижимой реальностью». [21]
С сентября 2022 года АНБ осуществляет переход от пакета коммерческих алгоритмов национальной безопасности (теперь называемого CNSA 1.0), первоначально запущенного в январе 2016 года, к пакету коммерческих алгоритмов национальной безопасности 2.0 (CNSA 2.0), оба из которых кратко изложены ниже: [22] ] [б]
ЦНСА 2.0
ЦНСА 1.0