Криптография с открытым ключом - Public-key cryptography

Непредсказуемое (обычно большое и случайное ) число используется для начала генерации приемлемой пары ключей, подходящей для использования алгоритмом асимметричного ключа.
В схеме шифрования с асимметричным ключом любой может зашифровать сообщения с помощью открытого ключа, но только владелец парного закрытого ключа может расшифровать такое сообщение. Безопасность системы зависит от секретности закрытого ключа, который не должен становиться известным никому.
В схеме обмена ключами Диффи-Хеллмана каждая сторона генерирует пару открытого / закрытого ключей и распределяет открытый ключ пары. После получения аутентичной (nb, это критически важно) копии открытых ключей друг друга Алиса и Боб могут вычислить общий секрет в автономном режиме. Общий секрет может использоваться, например, как ключ для симметричного шифра, который, по существу, во всех случаях будет намного быстрее.
В этом примере сообщение имеет цифровую подпись , но не зашифровано. 1) Алиса подписывает сообщение своим закрытым ключом. 2) Боб может проверить, что Алиса отправила сообщение и что сообщение не было изменено.

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

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

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

Алгоритмы открытого ключа - это фундаментальные примитивы безопасности в современных криптосистемах , включая приложения и протоколы, которые обеспечивают гарантию конфиденциальности, подлинности и неотвратимости электронных сообщений и хранилищ данных. Они лежат в основе множества Интернет-стандартов, таких как Transport Layer Security (TLS) , S / MIME , PGP и GPG . Некоторые алгоритмы открытого ключа обеспечивают распределение ключей и секретность (например, обмен ключами Диффи – Хеллмана ), некоторые предоставляют цифровые подписи (например, алгоритм цифровой подписи ), а некоторые обеспечивают и то, и другое (например, RSA ). По сравнению с симметричным шифрованием асимметричное шифрование работает гораздо медленнее, чем хорошее симметричное шифрование, слишком медленно для многих целей. Современные криптосистемы (такие как TLS , Secure Shell ) используют как симметричное шифрование, так и асимметричное шифрование, часто с использованием асимметричного шифрования для безопасного обмена секретным ключом, который затем используется для симметричного шифрования.

Описание

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

Напротив, в системе открытых ключей открытые ключи могут распространяться широко и открыто, и только соответствующие частные ключи должны храниться в секрете их владельцем.

Двумя наиболее известными способами использования криптографии с открытым ключом являются:

  • Шифрование с открытым ключом , при котором сообщение шифруется открытым ключом предполагаемого получателя. Для правильно выбранных и используемых алгоритмов сообщения на практике не могут быть расшифрованы кем-либо, кто не обладает соответствующим закрытым ключом, который, таким образом, считается владельцем этого ключа и, следовательно, лицом, связанным с открытым ключом. Это можно использовать для обеспечения конфиденциальности сообщения.
  • Цифровые подписи , в которых сообщение подписано закрытым ключом отправителя и может быть проверено любым, у кого есть доступ к открытому ключу отправителя. Эта проверка доказывает, что отправитель имел доступ к закрытому ключу и, следовательно, весьма вероятно, что это лицо, связанное с открытым ключом. Это также гарантирует, что сообщение не было подделано, поскольку подпись математически привязана к сообщению, из которого она изначально была сделана, и проверка не удастся практически для любого другого сообщения, независимо от того, насколько оно похоже на исходное сообщение.

Одним из важных вопросов является уверенность / доказательство того, что конкретный открытый ключ является подлинным, т. Е. Что он правильный и принадлежит заявленному физическому или юридическому лицу и не был подделан или заменен какой-либо (возможно, злонамеренной) третьей стороной. Есть несколько возможных подходов, в том числе:

Инфраструктура открытого ключа (PKI), в которых один или несколько третьих сторонах - известные как сертификат власти - УДОСТОВЕРЯЕТСЯ собственность ключевых пар. TLS полагается на это. Это означает, что все участники доверяют системе PKI (программное обеспечение, оборудование и управление).

« Сеть доверия », которая децентрализует аутентификацию с использованием индивидуальных подтверждений ссылок между пользователем и открытым ключом, принадлежащим этому пользователю. PGP использует этот подход в дополнение к поиску в системе доменных имен (DNS). Система DKIM для цифровой подписи электронных писем также использует этот подход.

Приложения

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

Еще одно применение в криптографии с открытым ключом - это цифровая подпись . Схемы цифровой подписи могут использоваться для аутентификации отправителя .

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

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

Гибридные криптосистемы

Поскольку алгоритмы с асимметричным ключом почти всегда требуют больших вычислительных ресурсов, чем симметричные, для шифрования и обмена симметричным ключом обычно используется открытый / частный алгоритм обмена асимметричным ключом , который затем используется криптографией с симметричным ключом для передачи данных с использованием теперь общий симметричный ключ для алгоритма шифрования с симметричным ключом. PGP , SSH и семейство схем SSL / TLS используют эту процедуру; поэтому они называются гибридными криптосистемами . Первоначальный обмен ключами на основе асимметричной криптографии для совместного использования сгенерированного сервером симметричного ключа от сервера к клиенту имеет то преимущество, что не требует предварительного обмена симметричным ключом вручную, например, на распечатанной бумаге или дисках, перевозимых курьером, в то время как обеспечение более высокой пропускной способности данных криптографии с симметричным ключом по сравнению с криптографией с асимметричным ключом для оставшейся части общего соединения.

Недостатки

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

Алгоритмы

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

Были обнаружены серьезные недостатки для нескольких ранее многообещающих алгоритмов с асимметричным ключом. Алгоритм «ранец упаковки» был установлен, небезопасными после разработки новой атаки. Как и все криптографические функции, реализации с открытым ключом могут быть уязвимы для атак по побочным каналам, которые используют утечку информации для упрощения поиска секретного ключа. Часто они не зависят от используемого алгоритма. Ведутся исследования как для обнаружения новых атак, так и для защиты от них.

Изменение публичных ключей

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

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

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

В некоторых продвинутых атаках типа «злоумышленник посередине» одна сторона коммуникации будет видеть исходные данные, а другая - вредоносный вариант. Асимметричные атаки типа «злоумышленник посередине» могут помешать пользователям понять, что их соединение скомпрометировано. Это остается так, даже если известно, что данные одного пользователя скомпрометированы, потому что данные выглядят нормально для другого пользователя. Это может привести к запутанным разногласиям между пользователями, например, "это должно быть на вашей стороне!" когда ни один пользователь не виноват. Следовательно, атаки типа «злоумышленник посередине» можно полностью предотвратить только в том случае, если инфраструктура связи физически контролируется одной или обеими сторонами; например, по проводному маршруту в собственном здании отправителя. Таким образом, открытые ключи легче изменить, когда оборудование связи, используемое отправителем, находится под контролем злоумышленника.

Инфраструктура открытого ключа

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

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

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

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

Примеры

Примеры хорошо зарекомендовавших себя техник асимметричного ключа для различных целей:

Примеры алгоритмов с асимметричным ключом, которые еще не получили широкого распространения, включают:

Примеры известных, но небезопасных алгоритмов асимметричного ключа включают:

Примеры протоколов, использующих алгоритмы с асимметричным ключом, включают:

История

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

Предвкушение

В своей книге 1874 г. Принципы науки , Уильям Стэнли Джевонс писал:

Сможет ли читатель сказать, какие два числа, умноженные вместе, дадут число 8616460799 ? Думаю, вряд ли кто-нибудь, кроме меня, когда-нибудь узнает.

Здесь он описал связь односторонних функций с криптографией и продолжил обсуждение конкретно проблемы факторизации, используемой для создания функции лазейки . В июле 1996 года математик Соломон В. Голомб сказал: «Джевонс предвидел ключевую особенность алгоритма RSA для криптографии с открытым ключом, хотя он определенно не изобрел концепцию криптографии с открытым ключом».

Секретное открытие

В 1970 году Джеймс Х. Эллис , британский шифровальщик из штаб-квартиры правительства Великобритании (GCHQ), задумал возможность «несекретного шифрования» (теперь называемого криптографией с открытым ключом), но не нашел способа реализовать его. В 1973 году его коллега Клиффорд Кокс внедрил то, что стало известно как алгоритм шифрования RSA , дав практический метод «несекретного шифрования», а в 1974 году другой математик и криптограф GCHQ, Малкольм Дж. Уильямсон , разработал то, что теперь известно как Обмен ключами Диффи – Хеллмана . Схема также была передана в Агентство национальной безопасности США . Обе организации имели военную направленность, и в любом случае были доступны лишь ограниченные вычислительные мощности; потенциал криптографии с открытым ключом остался нереализованным ни одной из организаций:

Я счел его наиболее важным для использования в военных целях ... если вы можете поделиться своим ключом быстро и в электронном виде, у вас будет большое преимущество перед противником. Только в конце эволюции от Бернерс-Ли, разработавшей открытую интернет-архитектуру для CERN , ее адаптации и принятия для Arpanet ... криптография с открытым ключом полностью реализовала свой потенциал.

- Ральф Бенджамин

Эти открытия не были публично признаны в течение 27 лет, пока исследование не было рассекречено британским правительством в 1997 году.

Публичное открытие

В 1976 году Уитфилд Диффи и Мартин Хеллман опубликовали криптосистему с асимметричным ключом, которые под влиянием работы Ральфа Меркла по распределению открытых ключей раскрыли метод согласования открытых ключей. Этот метод обмена ключами, который использует возведение в степень в конечном поле , стал известен как обмен ключами Диффи – Хеллмана . Это был первый опубликованный практический метод установления общего секретного ключа по аутентифицированному (но не конфиденциальному) каналу связи без использования предварительного общего секрета. «Техника согласования открытых ключей» Меркла стала известна как «Пазлы Меркла» , была изобретена в 1974 году и опубликована только в 1978 году.

В 1977 году Рон Ривест , Ади Шамир и Леонард Адлеман независимо друг от друга изобрели обобщение схемы Кокса, работавших тогда в Массачусетском технологическом институте . Последние авторы опубликовали свою работу в 1978 году Мартин Гарднер «s Scientific American колонке, и алгоритм стал известен , как RSA , с их инициалами. RSA использует возведение в степень по модулю произведения двух очень больших простых чисел для шифрования и дешифрования, выполняя как шифрование с открытым ключом, так и цифровые подписи с открытым ключом. Его безопасность связана с чрезвычайной трудностью факторизации больших целых чисел , проблемой, для которой не существует известной эффективной общей техники (хотя разложение на простые множители может быть получено с помощью атак грубой силы; это тем труднее, чем больше простые множители). Описание алгоритма было опубликовано в колонке « Математические игры» в августовском выпуске журнала Scientific American за 1977 год .

С 1970-х годов было разработано большое количество разнообразных методов шифрования, цифровой подписи, согласования ключей и других методов, включая криптосистему Рабина , шифрование Эль-Гамаля , DSA и криптографию на основе эллиптических кривых .

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

Примечания

использованная литература

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