Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Значение [ править ]

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

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

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

Системы шифрования часто группируются по семействам. Общие семейства включают симметричные системы (например, AES ) и асимметричные системы (например, RSA ); в качестве альтернативы они могут быть сгруппированы в соответствии с используемым центральным алгоритмом (например, криптография на основе эллиптических кривых ).

Поскольку каждый из них имеет разный уровень криптографической сложности, обычно используются ключи разных размеров для одного и того же уровня безопасности в зависимости от используемого алгоритма. Например, безопасность, доступная с 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 бит. См. Обсуждение взаимосвязи между длиной ключа и атаками квантовых вычислений внизу этой страницы для получения дополнительной информации.

Длина ключей симметричного алгоритма [ править ]

Экспортная политика правительства США уже давно ограничивает «силу» криптографии, которая может быть отправлена ​​из страны. В течение многих лет ограничение составляло 40 бит . Сегодня длина ключа в 40 бит не обеспечивает достаточной защиты даже от случайного злоумышленника с одним ПК. В ответ к 2000 году большинство основных ограничений США на использование надежного шифрования были ослаблены. [7] Однако не все правила были отменены, и регистрация шифрования в Бюро промышленности и безопасности США по-прежнему требуется для экспорта «товаров массового потребления, программного обеспечения и компонентов для шифрования с шифрованием, превышающим 64 бита» (75 FR 36494 ).

Шифр Люцифера IBM был выбран в 1974 году в качестве основы для того, что впоследствии стало стандартом шифрования данных . Длина ключа Люцифера была уменьшена со 128 до 56 бит , что, по мнению NSA и NIST, было достаточно. У АНБ есть большие вычислительные ресурсы и большой бюджет; некоторые криптографы, в том числе Уитфилд Диффи и Мартин Хеллман, жаловались, что это сделало шифр настолько слабым, что компьютеры NSA смогли бы взломать ключ DES за день с помощью параллельных вычислений методом грубой силы. АНБ оспорило это, заявив, что на перебор DES у них уйдет примерно 91 год. [8]Однако к концу 90-х стало ясно, что DES можно взломать в течение нескольких дней с помощью специально созданного оборудования, которое может быть куплено крупной корпорацией или государством. [9] [10] В книге « Взлом DES» (O'Reilly and Associates) рассказывается об успешной попытке взломать 56-битный DES в 1998 году с помощью грубой силы, организованной кибернетической группой по защите гражданских прав с ограниченными ресурсами; см. Взломщик EFF DES . Даже до этой демонстрации длина 56 бит считалась недостаточной для ключей симметричного алгоритма ; DES был заменен во многих приложениях тройным DES , который имеет 112-битную защиту при использовании 168-битных ключей (тройной ключ). [11] В 2002 г.Distributed.net и его добровольцы взломали 64-битный ключ RC5 после нескольких лет усилий с использованием около семидесяти тысяч (в основном домашних) компьютеров.

В стандарте Advanced Encryption Standard, опубликованном в 2001 году, используются ключи размером 128, 192 или 256 бит. Многие наблюдатели считают, что 128 бит достаточно в обозримом будущем для симметричных алгоритмов качества AES , пока не станут доступны квантовые компьютеры . [ необходима цитата ] Однако с 2015 года Агентство национальной безопасности США выпустило руководство о том, что оно планирует перейти на алгоритмы, устойчивые к квантовым вычислениям, и теперь требует 256-битных ключей AES для данных, классифицируемых до Совершенно секретно . [12]

В 2003 году Национальный институт стандартов и технологий США ( NIST) предложил отказаться от 80-битных ключей к 2015 году. В 2005 году использование 80-битных ключей было разрешено только до 2010 года [13].

С 2015 года руководство NIST гласит, что «теперь запрещено использование ключей, обеспечивающих уровень безопасности менее 112 бит для согласования ключей». Алгоритмы симметричного шифрования, одобренные NIST, включают тройной DES с тремя ключами и AES . Утверждения для двухклавишных Triple DES и Skipjack были отозваны в 2015 году; NSA полосатый алгоритм «s используется в Фортецце программе использует 80-битные ключи. [11]

Длина ключей асимметричного алгоритма [ править ]

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

С 2015, NIST рекомендует минимум 2048-битных ключей для RSA , [14] обновление к широко принятой рекомендации 1024-битового минимума , так как по меньшей мере , 2002 [15]

1024-битные ключи RSA эквивалентны по силе 80-битным симметричным ключам, 2048-битные ключи RSA - 112-битным симметричным ключам, 3072-битные ключи RSA - 128-битным симметричным ключам и 15360-битные ключи RSA - 256-битным. симметричные ключи. [16] В 2003 году RSA Security заявила, что 1024-битные ключи, вероятно, станут поддающимися взлому в период между 2006 и 2010 годами, в то время как 2048-битные ключи будут достаточными до 2030 года. [17] По состоянию на 2020 год, самый крупный ключ RSA, который, как известно, был взломанный - это RSA-250 с 829 битами. [18]

Алгоритм Диффи-Хеллмана с конечным полем имеет примерно такую ​​же силу ключа, что и RSA, для тех же размеров ключей. Рабочий коэффициент для взлома Диффи-Хеллмана основан на проблеме дискретного логарифмирования , которая связана с проблемой целочисленной факторизации, на которой основана сила RSA. Таким образом, 2048-битный ключ Диффи-Хеллмана имеет примерно такую ​​же стойкость, как 2048-битный ключ RSA.

Криптография на основе эллиптических кривых (ECC) - это альтернативный набор асимметричных алгоритмов, которые эквивалентно безопасны с более короткими ключами, требуя только примерно вдвое больше битов, чем эквивалентный симметричный алгоритм. [14] 256-битный ключ ECDH имеет примерно такой же коэффициент безопасности, как 128-битный ключ AES. [14] Сообщение, зашифрованное с помощью алгоритма эллиптического ключа с использованием 109-битного ключа, было взломано в 2004 году. [19]

Агентство национальной безопасности (NSA) ранее рекомендовало 256-битный ECC для защиты секретной информации до уровня SECRET и 384-битный для TOP SECRET; [12] В 2015 году он объявил о планах перехода на квантово-устойчивые алгоритмы к 2024 году, а до тех пор рекомендует 384-битный код для всей секретной информации. [20]

Влияние атак квантовых вычислений на силу ключа [ править ]

Два наиболее известных квантовых вычислений атаки основаны на алгоритме Шора и алгоритма Гровера . Из этих двух Shor's представляет больший риск для существующих систем безопасности.

Производные алгоритма Шора широко предполагаются как эффективные против всех основных алгоритмов с открытым ключом, включая RSA , алгоритм Диффи-Хеллмана и криптографию на основе эллиптических кривых.. По словам профессора Жиля Брассара, эксперта в области квантовых вычислений: «Время, необходимое для разложения целого числа RSA на множители, совпадает с порядком времени, необходимого для использования того же целого числа в качестве модуля для одного шифрования RSA. Другими словами, это не требует больше времени. пора взломать RSA на квантовом компьютере (с точностью до мультипликативной константы), чем законно использовать его на классическом компьютере ». По общему мнению, эти алгоритмы с открытым ключом небезопасны при любом размере ключа, если станут доступны достаточно большие квантовые компьютеры, способные выполнять алгоритм Шора. Последствия этой атаки заключаются в том, что все данные зашифрованы с использованием современных систем безопасности, основанных на стандартах, таких как вездесущий SSL, используемый для защиты электронной коммерции, интернет-банкинга и SSH.используется для защиты доступа к чувствительным компьютерным системам. Зашифрованные данные, защищенные с помощью алгоритмов с открытым ключом, могут быть заархивированы и впоследствии могут быть повреждены.

Широко распространено мнение, что распространенные симметричные шифры (такие как AES или Twofish ) и хэш-функции, устойчивые к коллизиям (такие как SHA ), обеспечивают большую защиту от известных атак квантовых вычислений. Считается, что они наиболее уязвимы для алгоритма Гровера . Беннет, Бернштейн, Брассард и Вазирани доказали в 1996 году, что поиск ключа методом перебора на квантовом компьютере не может быть быстрее, чем примерно 2 n / 2 вызовов базового криптографического алгоритма, по сравнению с примерно 2 n в классическом случае. [21] Таким образом, при наличии больших квантовых компьютеров n- битный ключ может обеспечить как минимум n/ 2 бита безопасности. Квантовая грубая сила легко подавляется удвоением длины ключа, что требует небольших дополнительных вычислительных затрат при обычном использовании. Это означает, что для достижения 128-битного рейтинга безопасности против квантового компьютера требуется как минимум 256-битный симметричный ключ. Как упоминалось выше, в 2015 году АНБ объявило, что планирует перейти на квантово-устойчивые алгоритмы. [12]

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

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

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

АлгоритмПрименение
RSA 3072-бит или большеСоздание ключа, электронная подпись
Diffie-Hellman (DH) 3072-бит или большеКлючевое учреждение
ECDH с NIST P-384Ключевое учреждение
ECDSA с NIST P-384Цифровая подпись
SHA-384Честность
AES-256Конфиденциальность

См. Также [ править ]

  • Ключевое растяжение

Ссылки [ править ]

  1. ^ Даклин, Пол (2013-05-27). «Анатомия изменения - Google объявляет, что удвоит размер своих ключей SSL - Naked Security» . Sophos . Проверено 24 сентября 2016 .
  2. ^ "Исследователь: 1024-битного шифрования RSA недостаточно" . Мир ПК . 2007-05-23 . Проверено 24 сентября 2016 .
  3. Перейти ↑ Cheng, Jacqui (2007-05-23). «Исследователи: взлом 307-значного ключа подвергает опасности 1024-битный RSA» . Ars Technica . Проверено 24 сентября 2016 .
  4. ^ "Слабый Диффи-Хеллман и тупиковая атака" . weakdh.org . 2015-05-20.
  5. ^ Адриан, Дэвид; Бхаргаван, Картикеян; Дурумерик, Закир; Годри, Пьеррик; Грин, Мэтью; Халдерман, Дж. Алекс; Хенингер, Надя; Спринголл, Дрю; Томе, Эммануэль; Валента, Люк; VanderSloot, Бенджамин; Вустров, Эрик; Занелла-Бегелин, Сантьяго; Циммерманн, Пауль (октябрь 2015 г.). Несовершенная прямая секретность: как на практике терпит неудачу Диффи-Хеллман (PDF) . 22-я конференция ACM по компьютерной и коммуникационной безопасности (CCS '15). Денвер, Колорадо.
  6. ^ "Насколько защищен AES от атак методом грубой силы?" . EE Times . Проверено 24 сентября 2016 .
  7. ^ Маккарти, Джек (2000-04-03). «Правительства ослабляют правила шифрования» . Мир ПК . Архивировано из оригинала на 2012-04-10.
  8. ^ "DES Stanford-NBS-NSA запись встречи и стенограмма" . Toad.com . Архивировано из оригинала на 2012-05-03 . Проверено 24 сентября 2016 .
  9. ^ Blaze, Мэтт ; Диффи, Уайтфилд ; Ривест, Рональд Л .; Шнайер, Брюс ; Шимомура, Цутому ; Томпсон, Эрик; Винер, Майкл (январь 1996). «Минимальная длина ключа для симметричных шифров для обеспечения надлежащей коммерческой безопасности» . Укрепите . Проверено 14 октября 2011 .
  10. ^ Сильная криптография Глобальная волна изменений , Информационный доклад Института Катона № 51, Арнольд Г. Рейнхольд, 1999 г.
  11. ^ Б Баркер, Элейн; Рогинский, Аллен (06.11.2015). «Переходы: Рекомендации по переходу на использование криптографических алгоритмов и длин ключей, NIST SP-800-131A Ред. 1» (PDF) . Nvlpubs.nist.gov . Проверено 24 сентября 2016 .
  12. ^ a b c «Криптография NSA Suite B» . Агентство национальной безопасности . 2009-01-15. Архивировано из оригинала на 2009-02-07 . Проверено 24 сентября 2016 .
  13. ^ Баркер, Элейн; Баркер, Уильям; Берр, Уильям; Полк, Уильям; Смид, Майлз (1 августа 2005 г.). "Специальная публикация NIST 800-57 Часть 1 Рекомендации по управлению ключами: Общие" (PDF) . Национальный институт стандартов и технологий . Таблица 4, стр. 66. DOI : 10,6028 / NIST.SP.800-57p1 . Проверено 8 января 2019 . Цитировать журнал требует |journal=( помощь )
  14. ^ a b c Баркер, Элейн; Данг, Куин (2015-01-22). «Специальная публикация NIST 800-57, часть 3, редакция 1: Рекомендации по управлению ключами: руководство по управлению ключами для конкретных приложений» (PDF) . Национальный институт стандартов и технологий : 12. doi : 10.6028 / NIST.SP.800-57pt3r1 . Проверено 24 ноября 2017 . Цитировать журнал требует |journal=( помощь )
  15. ^ «Анализ безопасности симметричных и асимметричных длин ключей на основе затрат» . RSA Laboratories . Архивировано из оригинала на 2017-01-13 . Проверено 24 сентября 2016 .
  16. ^ Баркер, Элейн (2016-01-28). «Специальная публикация NIST 800-57, часть 1, редакция 4: Рекомендации по управлению ключами: Общие» (PDF) . Национальный институт стандартов и технологий : 53. doi : 10.6028 / NIST.SP.800-57pt1r4 . Цитировать журнал требует |journal=( помощь )
  17. ^ Калиски, Берт (2003-05-06). «Размер ключа TWIRL и RSA» . RSA Laboratories . Архивировано из оригинала на 2017-04-17 . Проверено 24 ноября 2017 .
  18. ^ Циммерман, Пол (2020-02-28). «Факторизация РСА-250» . Кадо-нфс-обсуждение.
  19. ^ «Certicom объявляет победителя конкурса криптографии с эллиптической кривой» . Certicom Corp.27 апреля 2004 г. Архивировано из оригинала на 2016-09-27 . Проверено 24 сентября 2016 .
  20. ^ "Коммерческий набор алгоритмов национальной безопасности" . Агентство национальной безопасности . 2015-08-09 . Проверено 12 июля 2020 .
  21. ^ Беннетт Ч., Бернштейн Э., Брассард Г., Вазирани У., Сильные и слабые стороны квантовых вычислений . SIAM Journal on Computing 26 (5): 1510-1523 (1997).
  22. ^ Коммерческий набор алгоритмов национальной безопасности и часто задаваемые вопросы по квантовым вычислениям Агентство национальной безопасности США, январь 2016 г.
Общий
  • Рекомендации по управлению ключами - Часть 1: общие, Специальная публикация NIST 800-57. Март 2007 г.
  • Blaze, Мэтт; Диффи, Уитфилд; Ривест, Рональд Л .; и другие. «Минимальные длины ключей для симметричных шифров для обеспечения надлежащей коммерческой безопасности». Январь 1996 г.
  • Арьен К. Ленстра, Эрик Р. Верхёль: Выбор размеров криптографических ключей. J. Cryptology 14 (4): 255-293 (2001) - Citeseer link

Внешние ссылки [ править ]

  • www.keylength.com: онлайн-калькулятор длины ключа
  • Статьи, в которых обсуждаются последствия квантовых вычислений
  • Набор средств криптографии NIST
  • Берт Калиски : размеры ключей TWIRL и RSA (май 2003 г.)