stringtranslate.com

Размер ключа

В криптографии размер ключа или длина ключа относится к количеству битов в ключе, используемом криптографическим алгоритмом (например, шифром ).

Длина ключа определяет верхнюю границу безопасности алгоритма (т. е. логарифмическую меру самой быстрой известной атаки на алгоритм), поскольку безопасность всех алгоритмов может быть нарушена атаками методом перебора . В идеале нижняя граница безопасности алгоритма по замыслу равна длине ключа (то есть конструкция алгоритма не умаляет степень безопасности, присущую длине ключа).

Большинство алгоритмов с симметричным ключом спроектированы таким образом, чтобы обеспечить безопасность, равную длине ключа. Однако после проектирования может быть обнаружена новая атака. Например, Triple DES был разработан с учетом 168-битного ключа, но теперь известна атака сложности 2 112 (т. е. Triple DES теперь имеет только 112 бит безопасности, а из 168 бит ключа атака обработала 56 бит). «неэффективно» с точки зрения безопасности). Тем не менее, пока безопасность (понимаемая как «количество усилий, необходимых для получения доступа») достаточна для конкретного приложения, не имеет значения, совпадают ли длина ключа и безопасность. Это важно для алгоритмов с асимметричным ключом , поскольку неизвестно, чтобы такой алгоритм удовлетворял этому свойству; Криптография на основе эллиптических кривых наиболее близка к ней с эффективной безопасностью, равной примерно половине длины ключа.

Значение

Ключи используются для управления работой шифра, так что только правильный ключ может преобразовать зашифрованный текст ( зашифрованный текст ) в открытый текст . Все широко используемые шифры основаны на общеизвестных алгоритмах или имеют открытый исходный код , поэтому только сложность получения ключа определяет безопасность системы при условии отсутствия аналитической атаки (т.е. «структурной слабости» в алгоритмах). или используемые протоколы) и при условии, что ключ недоступен иным образом (например, в результате кражи, вымогательства или взлома компьютерных систем). Широко распространенное представление о том, что безопасность системы должна зависеть только от ключа, было явно сформулировано Огюстом Керкхоффсом (в 1880-х годах) и Клодом Шенноном (в 1940-х годах); эти утверждения известны как принцип Керкхоффса и максима Шеннона соответственно.

Поэтому ключ должен быть достаточно большим, чтобы атака методом перебора (возможная против любого алгоритма шифрования) была невозможна – т. е. заняла бы слишком много времени и/или потребовала бы слишком много памяти для выполнения. Работа Шеннона по теории информации показала, что для достижения так называемой « совершенной секретности » длина ключа должна быть не меньше длины сообщения и использоваться только один раз (этот алгоритм называется одноразовым блокнотом ). В свете этого, а также практической сложности управления такими длинными ключами, современная криптографическая практика отказалась от понятия совершенной секретности как требования шифрования и вместо этого сосредоточилась на вычислительной безопасности , согласно которой вычислительные требования для взлома зашифрованного текста должны быть соблюдены. невозможно для злоумышленника.

Размер ключа и система шифрования

Системы шифрования часто группируются в семейства. Общие семейства включают симметричные системы (например, AES ) и асимметричные системы (например, RSA и Elliptic-curve_cryptography ). Их можно сгруппировать в соответствии с используемым центральным алгоритмом (например, криптография на основе эллиптических кривых и шифры Фейстеля ). Поскольку каждый из них имеет разный уровень криптографической сложности, обычно для одного и того же уровня безопасности используются разные размеры ключей , в зависимости от используемого алгоритма. Например, безопасность, доступная при использовании 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) — это альтернативный набор асимметричных алгоритмов, который одинаково безопасен с более короткими ключами и требует лишь примерно вдвое больше битов, чем эквивалентный симметричный алгоритм. [12] 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]

По данным АНБ:

«Достаточно большой квантовый компьютер, если он будет построен, будет способен подорвать все широко распространенные алгоритмы с открытым ключом, используемые для создания ключей и цифровых подписей. ... Принято считать, что методы квантовых вычислений гораздо менее эффективны против симметричных алгоритмов, чем против Современные широко используемые алгоритмы с открытым ключом. Хотя криптография с открытым ключом требует изменений в фундаментальной конструкции для защиты от потенциального будущего квантового компьютера, алгоритмы с симметричным ключом считаются безопасными при условии, что используется достаточно большой размер ключа. ... В долгосрочной перспективе АНБ надеется на NIST , чтобы определить широко распространенный, стандартизированный набор коммерческих алгоритмов с открытым ключом, которые не уязвимы для квантовых атак».

По состоянию на 2016 год пакет коммерческих алгоритмов национальной безопасности АНБ включает в себя: [20]

Смотрите также

Примечания

  1. ^ Дополнительную информацию см. в обсуждении взаимосвязи между длиной ключей и атаками квантовых вычислений внизу этой страницы.

Рекомендации

  1. ^ abc Баркер, Элейн; Рогинский, Аллен (март 2019 г.). «Переходы: Рекомендации по переходу к использованию криптографических алгоритмов и длины ключей, NIST SP-800-131A, ред. 2» (PDF) . Nvlpubs.nist.gov . Проверено 11 февраля 2023 г.
  2. ^ «Исследователь: 1024-битного шифрования RSA недостаточно». Мир ПК . 23 мая 2007 г. Проверено 24 сентября 2016 г.
  3. ^ Ченг, Жаки (23 мая 2007 г.). «Исследователи: взлом 307-значного ключа ставит под угрозу 1024-битный RSA». Арс Техника . Проверено 24 сентября 2016 г.
  4. ^ «Слабый Диффи-Хеллман и атака затора». сайт слабыйdh.org . 20 мая 2015 г.
  5. ^ Адриан, Дэвид; Бхаргаван, Картикеян; Дурумерик, Закир; Годри, Пьеррик; Грин, Мэтью; Халдерман, Дж. Алекс; Хенингер, Надя; Спринголл, Дрю; Томе, Эммануэль; Валента, Люк; ВандерСлот, Бенджамин; Вустроу, Эрик; Занелла-Бегелен, Сантьяго; Циммерманн, Пол (октябрь 2015 г.). Несовершенная прямая секретность: как Диффи-Хеллман терпит неудачу на практике (PDF) . 22-я конференция ACM по компьютерной и коммуникационной безопасности (CCS '15). Денвер, Колорадо. Архивировано (PDF) оригиналом 10 октября 2022 г.
  6. ^ «Насколько безопасен AES от атак методом перебора?». ЭЭ Таймс . Проверено 24 сентября 2016 г.
  7. ^ "Запись и стенограмма встречи DES Stanford-NBS-NSA" . Жаба.com . Архивировано из оригинала 3 мая 2012 г. Проверено 24 сентября 2016 г.
  8. ^ Блейз, Мэтт ; Диффи, Уайтфилд ; Ривест, Рональд Л .; Шнайер, Брюс ; Симомура, Цутому ; Томпсон, Эрик; Винер, Майкл (январь 1996 г.). «Минимальная длина ключей для симметричных шифров для обеспечения адекватной коммерческой безопасности». Укрепить . Проверено 14 октября 2011 г.
  9. ^ Сильная криптография. Глобальная волна перемен, Информационный доклад Института Катона, №. 51, Арнольд Г. Рейнхольд, 1999 г.
  10. ^ abc "Криптография АНБ Suite B" . Национальное Агенство Безопасности . 15 января 2009 г. Архивировано из оригинала 7 февраля 2009 г. Проверено 24 сентября 2016 г.
  11. ^ Баркер, Элейн; Баркер, Уильям; Берр, Уильям; Полк, Уильям; Смид, Майлз (1 августа 2005 г.). «Специальная публикация NIST 800-57, часть 1, рекомендации по управлению ключами: общие сведения» (PDF) . Национальный институт стандартов и технологий . Таблица 4, с. 66. дои :10.6028/NIST.SP.800-57p1. Архивировано (PDF) из оригинала 13 декабря 2016 г. Проверено 8 января 2019 г. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
  12. ^ abc Баркер, Элейн; Данг, Куинь (22 января 2015 г.). «Специальная публикация NIST 800-57, часть 3, редакция 1: Рекомендации по управлению ключами: Руководство по управлению ключами для конкретных приложений» (PDF) . Национальный институт стандартов и технологий : 12. doi : 10.6028/NIST.SP.800-57pt3r1. Архивировано (PDF) из оригинала 26 февраля 2015 г. Проверено 24 ноября 2017 г. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
  13. ^ «Анализ безопасности симметричных и асимметричных ключей на основе затрат». Лаборатории РСА . Архивировано из оригинала 13 января 2017 г. Проверено 24 сентября 2016 г.
  14. ^ Баркер, Элейн (май 2020 г.). «Специальная публикация NIST 800-57, часть 1, редакция 4: Рекомендации по управлению ключами: общие сведения» (PDF) . Национальный институт стандартов и технологий : 53. doi : 10.6028/NIST.SP.800-57pt1r5. S2CID  243189598. Архивировано (PDF) из оригинала 9 мая 2020 г. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
  15. ^ Калиски, Берт (6 мая 2003 г.). «Размер ключа TWIRL и RSA». Лаборатории РСА . Архивировано из оригинала 17 апреля 2017 г. Проверено 24 ноября 2017 г.
  16. ^ Циммерманн, Пол (28 февраля 2020 г.). «Факторизация RSA-250». Cado-nfs-обсудить. Архивировано из оригинала 28 февраля 2020 г. Проверено 12 июля 2020 г.
  17. ^ «Certicom объявляет победителя конкурса криптографии на эллиптических кривых» . Certicom Corp., 27 апреля 2004 г. Архивировано из оригинала 27 сентября 2016 г. Проверено 24 сентября 2016 г.
  18. ^ "Коммерческий набор алгоритмов национальной безопасности" . Национальное Агенство Безопасности . 09.08.2015 . Проверено 12 июля 2020 г.
  19. ^ Беннетт Ч., Бернштейн Э., Брассар Г., Вазирани У., Сильные и слабые стороны квантовых вычислений . SIAM Journal on Computing 26 (5): 1510–1523 (1997).
  20. ^ Коммерческий набор алгоритмов национальной безопасности и часто задаваемые вопросы по квантовым вычислениям Агентство национальной безопасности США, январь 2016 г.

Общий

Внешние ссылки