Криптосистемы с открытым ключом доклад
Обновлено: 17.05.2024
Аннотация: Рассматриваются основные понятия, относящиеся к криптографии с открытым ключом, а также способы их использования: шифрование, создание и проверка цифровой подписи, обмен ключа. Рассмотрены алгоритмы RSA и Диффи-Хеллмана.
Основные требования к алгоритмам асимметричного шифрования
Создание алгоритмов асимметричного шифрования является величайшим и, возможно, единственным революционным достижением в истории криптографии.
Алгоритмы шифрования с открытым ключом разрабатывались для того, чтобы решить две наиболее трудные задачи, возникшие при использовании симметричного шифрования .
Первой задачей является распределение ключа . При симметричном шифровании требуется, чтобы обе стороны уже имели общий ключ , который каким-то образом должен быть им заранее передан. Диффи, один из основоположников шифрования с открытым ключом , заметил, что это требование отрицает всю суть криптографии, а именно возможность поддерживать всеобщую секретность при коммуникациях.
Диффи и Хеллман достигли значительных результатов, предложив способ решения обеих задач, который радикально отличается от всех предыдущих подходов к шифрованию.
Сначала рассмотрим общие черты алгоритмов шифрования с открытым ключом и требования к этим алгоритмам. Определим требования, которым должен соответствовать алгоритм , использующий один ключ для шифрования, другой ключ - для дешифрования , и при этом вычислительно невозможно определить дешифрующий ключ , зная только алгоритм шифрования и шифрующий ключ .
Кроме того, некоторые алгоритмы, например RSA , имеют следующую характеристику: каждый из двух ключей может использоваться как для шифрования, так и для дешифрования .
Сначала рассмотрим алгоритмы, обладающие обеими характеристиками, а затем перейдем к алгоритмам открытого ключа , которые не обладают вторым свойством.
При описании симметричного шифрования и шифрования с открытым ключом будем использовать следующую терминологию. Ключ , используемый в симметричном шифровании , будем называть секретным ключом . Два ключа, используемые при шифровании с открытым ключом , будем называть открытым ключом и закрытым ключом . Закрытый ключ держится в секрете, но называть его будем закрытым ключом , а не секретным, чтобы избежать путаницы с ключом, используемым в симметричном шифровании . Закрытый ключ будем обозначать KR , открытый ключ - KU .
Будем предполагать, что все участники имеют доступ к открытым ключам друг друга, а закрытые ключи создаются локально каждым участником и, следовательно, распределяться не должны.
В любое время участник может изменить свой закрытый ключ и опубликовать составляющий пару открытый ключ , заменив им старый открытый ключ .
Диффи и Хеллман описывают требования, которым должен удовлетворять алгоритм шифрования с открытым ключом .
Можно добавить шестое требование, хотя оно не выполняется для всех алгоритмов с открытым ключом :
Это достаточно сильные требования, которые вводят понятие односторонней функции с люком . Односторонней функцией называется такая функция, у которой каждый аргумент имеет единственное обратное значение, при этом вычислить саму функцию легко, а вычислить обратную функцию трудно.
Обычно "легко" означает, что проблема может быть решена за полиномиальное время от длины входа. Таким образом, если длина входа имеет n битов, то время вычисления функции пропорционально n a , где а - фиксированная константа. Таким образом, говорят, что алгоритм принадлежит классу полиномиальных алгоритмов Р. Термин "трудно" означает более сложное понятие. В общем случае будем считать, что проблему решить невозможно, если усилия для ее решения больше полиномиального времени от величины входа. Например, если длина входа n битов, и время вычисления функции пропорционально 2 n , то это считается вычислительно невозможной задачей. К сожалению, тяжело определить, проявляет ли конкретный алгоритм такую сложность. Более того, традиционные представления о вычислительной сложности фокусируются на худшем случае или на среднем случае сложности алгоритма. Это неприемлемо для криптографии, где требуется невозможность инвертировать функцию для всех или почти всех значений входов.
Вернемся к определению односторонней функции с люком , которую, подобно односторонней функции , легко вычислить в одном направлении и трудно вычислить в обратном направлении до тех пор, пока недоступна некоторая дополнительная информация. При наличии этой дополнительной информации инверсию можно вычислить за полиномиальное время. Таким образом, односторонняя функция с люком принадлежит семейству односторонних функций fk таких, что
| Y = fk(X) - легко, если k и Х известны |
| X = fk -1 (Y) - легко, если k и Y известны |
| Х = fk -1 (Y) - трудно, если Y известно, но k неизвестно |
Мы видим, что разработка конкретного алгоритма с открытым ключом зависит от открытия соответствующей односторонней функции с люком .
Криптоанализ алгоритмов с открытым ключом
Как и в случае симметричного шифрования , алгоритм шифрования с открытым ключом уязвим для лобовой атаки. Контрмера стандартная: использовать большие ключи.
Криптосистема с открытым ключом применяет определенные неинвертируемые математические функции . Сложность вычислений таких функций не является линейной от количества битов ключа, а возрастает быстрее, чем ключ. Таким образом, размер ключа должен быть достаточно большим, чтобы сделать лобовую атаку непрактичной, и достаточно маленьким для возможности практического шифрования. На практике размер ключа делают таким, чтобы лобовая атака была непрактичной, но в результате скорость шифрования оказывается достаточно медленной для использования алгоритма в общих целях. Поэтому шифрование с открытым ключом в настоящее время в основном ограничивается приложениями управления ключом и подписи, в которых требуется шифрование небольшого блока данных.
Другая форма атаки состоит в том, чтобы найти способ вычисления закрытого ключа , зная открытый ключ . Невозможно математически доказать, что данная форма атаки исключена для конкретного алгоритма открытого ключа . Таким образом, любой алгоритм, включая широко используемый алгоритм RSA , является подозрительным.
Основные способы использования алгоритмов с открытым ключом
Основными способами использования алгоритмов с открытым ключом являются шифрование/ дешифрование , создание и проверка подписи и обмен ключа.
Шифрование с открытым ключом состоит из следующих шагов:
Создание и проверка подписи состоит из следующих шагов:
До тех пор, пока пользователь или прикладная система надежно хранит свой закрытый ключ , их подписи достоверны.
Обмен ключей: две стороны взаимодействуют для обмена ключом сессии , который в дальнейшем можно использовать в алгоритме симметричного шифрования.
Некоторые алгоритмы можно задействовать тремя способами, в то время как другие могут использоваться одним или двумя способами.
Перечислим наиболее популярные алгоритмы с открытым ключом и возможные способы их применения.
На протяжении многих веков человечество использовало криптографические методы для защиты информации при ее передаче и хранении. Приблизительно к концу XIX в. эти методы стали объектом математического изучения. Отрасль математики, изучающая защиту информации, традиционно называется криптологией [cryptology] и подразделяется на криптографию [cryptography], занимающуюся разработкой новых методов и обоснованием их корректности, и криптоанализ [cryptanalysis], задача которого - интенсивное изучение существующих методов, часто с целью реального раскрытия секретов другой стороны. Криптография и криптоанализ находятся в тесном взаимодействии друг с другом и с практическими нуждами и развиваются параллельно закрытыми правительственными организациями многих государств и международным научным сообществом.
В настоящее время существуют тысячи криптографических систем, реализованных как программно, так и аппаратно. Среди них можно выделить системы, сам криптографический принцип работы которых держится в секрете, как, например, микросхема Clipper, предлагаемая правительством США в качестве криптографического стандарта для телекоммуникаций, и системы, алгоритм которых открыт, а секретной является только определенная, как правило небольшая, порция информации, называемая (секретным) ключом [(secret) key] - к ним относится большинство систем, реализуемых программно и предназначенных для широкого использования. В дальнейшем мы будем рассматривать только системы второго типа.
В системе рассматриваемого типа задача вскрытия системы, то есть нарушения защиты информации без предварительного знания ключа, как правило, теоретически разрешима при наличии у вскрывающей стороны неограниченных вычислительных ресурсов. С математической точки зрения надежность криптографической системы определяется сложностью решения этой задачи с учетом реальных вычислительных ресурсов потенциальной вскрывающей стороны. С организационной точки зрения имеет значение соотношение стоимости потенциального вскрытия и ценности защищаемой информации.
Математическое исследование надежности криптографических систем затруднено отсутствием универсального математического понятия сложности. По этой причине надежность большинства криптографических систем в настоящее время невозможно не только доказать, но даже адекватно сформулировать. Как правило, применение той или иной криптографической системы основано на результатах многолетнего практического криптоанализа систем данного типа, в той или иной степени подкрепленных математическим обоснованием. Это обоснование может сводить задачу раскрытия данной криптосистемы к какой-либо задаче теории чисел или комбинаторики, решение которой считается реально не осуществимым, или, что предпочтительнее, к классу NP-полных задач, сводимость к которому является “эталоном” практической неразрешимости. В то же время, понятие практической неразрешимости для конкретных практических задач не является четко определенным или стабильным, благодаря развитию вычислительной техники и методов криптоанализа.
Криптография с симметричным ключом
Долгое время традиционной криптографической схемой была схема с симметричным ключом [symmetric key, dual key]. В этой схеме имеется один ключ, который участвует в шифровании и дешифровании информации. Шифрующая процедура при помощи ключа производит ряд действий над исходными данными, дешифрующая процедура при помощи того же ключа производит обратные действия над кодом. Дешифрование кода без ключа предполагается практически неосуществимым. Если зашифрованная таким образом информация передается по обычному, т.е. незащищенному, каналу связи, один и тот же ключ должен иметься у отправителя и получателя, вследствие чего возникает необходимость в дополнительном защищенном канале для передачи ключа, повышается уязвимость системы и увеличиваются организационные трудности.
К классу алгоритмов с симметричным ключом относится метод “одноразового блокнота” [one-time pad], заключающийся в побитовом сложении (“гаммировании”) шифруемого текста со случайной последовательностью битов - ключом (см. [S94]). Длина ключа должна совпадать с длиной шифруемого текста и каждый отрезок ключа должен использоваться однократно; в противном случае текст легко поддается несанкционированной расшифровке. При выполнении же этих условий данный метод является единственным методом, теоретически устойчивым против криптоанализа противника с неограниченными вычислительными ресурсами. Несмотря на это, в настоящее время метод “одноразового блокнота” практически не применяется из-за организационных сложностей, связанных с генерацией, передачей и хранением используемых в нем сверхдлинных ключей.
Другим примером схемы с симметричным ключом может служить алгоритм DES (Data Encryption Standard), принятый 23 ноября 1976 г. в качестве официального криптографического стандарта США для защиты некритичной [unclassified] информации (см. [S94], с.219-243). В стандарт было включено положение об обязательной ресертификации (пересмотре) алгоритма каждые пять лет; последняя такая ресертификация состоялась в 1992 г. По мнению экспертов, в связи с определенными успехами в криптоанализе DES и появлением новых методов шифрования с симметричным ключом, алгоритм может не быть ресертифицирован на следующий пятилетний срок. Тем не менее, DES по-прежнему считается криптографически стойким алгоритмом и остается самой распространенной схемой шифрования с симметричным ключом.
Российский стандарт на криптографию с симметричным ключом определен ГОСТ 28147-89 “Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования”, который был введен в действие 1 июля 1990 г. В отличие от DES, стандарт содержит указание на то, что он “по своим возможностям не накладывает ограничений на степень секретности защищаемой информации”. В общих чертах алгоритм ГОСТ 28147 аналогичен DES, но имеется ряд существенных отличий, как, например, длина ключа и трактовка содержимого узлов замены [в схеме DES называемых “S-boxes”]. В то время, как заполнение узлов замены DES оптимизировано с точки зрения криптографической стойкости и явно указано в стандарте, заполнение узлов замены ГОСТ 28147 “является секретным элементом и поставляется в установленном порядке”. Учитывая, что оно в то же время “является долговременным ключевым элементом, общим для сети ЭВМ”, и что “установленный порядок” поставки может не предусматривать криптографическую оптимизацию, этот пункт стандарта представляется одним из его слабых мест, затрудняющим реализацию и не способствующим криптографической стойкости. Однако при задании оптимизированных значений для узлов замены криптографическая стойкость алгоритма сравнима со стойкостью DES.
Криптография с открытым ключом
В 1976 г. У.Диффи и М.Хеллманом [DH76] был предложен новый тип криптографической системы - система с открытым ключом [public key cryptosystem]. В схеме с открытым ключом имеется два ключа, открытый [public] и секретный [private, secret], выбранные таким образом, что их последовательное применение к массиву данных оставляет этот массив без изменений. Шифрующая процедура использует открытый ключ, дешифрующая - секретный. Дешифрование кода без знания секретного ключа практически неосуществимо; в частности, практически неразрешима задача вычисления секретного ключа по известному открытому ключу. Основное преимущество криптографии с открытым ключом - упрощенный механизм обмена ключами. При осуществлении коммуникации по каналу связи передается только открытый ключ, что делает возможным использование для этой цели обычного канала и устраняет потребность в специальном защищенном канале для передачи ключа.
С появлением систем с открытым ключом понятие о защите информации, а вместе с ним функции криптографии значительно расширились. Если раньше основной задачей криптографических систем считалось надежное шифрование информации, в настоящее время область применения криптографии включает также цифровую подпись (аутентификацию), лицензирование, нотаризацию (свидетельствование), распределенное управление, схемы голосования, электронные деньги и многое другое (см. [BFS91], ч.7, [S94], ч.1). Наиболее распространенные функции криптографических систем с открытым ключом - шифрование и цифровая подпись, причем роль цифровой подписи в последнее время возросла по сравнению с традиционным шифрованием: некоторые из систем с открытым ключом поддерживают цифровую подпись, но не поддерживают шифрование.
Цифровая подпись используется для аутентификации текстов, передаваемых по телекоммуникационным каналам. Она аналогична обычной рукописной подписи и обладает ее основными свойствами: удостоверяет, что подписанный текст исходит именно от лица, поставившего подпись, и не дает самому этому лицу возможности отказаться от обязательств, связанных с подписанным текстом. Цифровая подпись представляет собой небольшое количество дополнительной информации, передаваемой вместе с подписываемым текстом. В отличие от шифрования, при формировании подписи используется секретный ключ, а при проверке - открытый.
Из-за особенностей алгоритмов, лежащих в основе систем с открытым ключом, их быстродействие при обработке единичного блока информации обычно в десятки раз меньше, чем быстродействие систем с симметричным ключом на блоке той же длины. Для повышения эффективности систем с открытым ключом часто применяются смешанные методы, реализующие криптографические алгоритмы обоих типов. При шифровании информации выбирается случайный симметричный ключ, вызывается алгоритм с симметричным ключом для шифрования исходного текста. а затем алгоритм с открытым ключом для шифрования симметричного ключа. По коммуникационному каналу передается текст, зашифрованный симметричным ключом, и симметричный ключ, зашифрованный открытым ключом. Для расшифровки действия производятся в обратном порядке: сначала при помощи секретного ключа получателя расшифровывается симметричный ключ, а затем при помощи симметричного ключа - полученный по каналу зашифрованный текст. Для формирования электронной подписи по подписываемому тексту вычисляется его однонаправленная хэш-функция (дайджест) [one-way hash function, digest], представляющая собой один короткий блок информации, характеризующий весь текст в целом; задача восстановления текста по его хэш-функции или подбора другого текста, имеющего ту же хэш-функцию, практически неразрешима. При непосредственном формировании подписи, вместо шифрования секретным ключом каждого блока текста секретный ключ применяется только к хэш-функции; по каналу передается сам текст и сформированная подпись хэш-функции. Для проверки подписи снова вычисляется хэш-функция от полученного по каналу текста, после чего при помощи открытого ключа проверяется, что подпись соответствует именно данному значению хэш-функции. Алгоритмы вычисления однонаправленных хэш-функций, как правило, логически тесно связаны с алгоритмами шифрования с симметричным ключом.
Описанные гибридные методы шифрования и цифровой подписи сочетают в себе эффективность алгоритмов с симметричным ключом и свойство независимости от дополнительных секретных каналов для передачи ключей, присущее алгоритмам с открытым ключом. Криптографическая стойкость конкретного гибридного метода определяется стойкостью слабейшего звена в цепи, состоящей из алгоритмов с симметричным и с открытым ключом, выбранных для его реализации.
Система RSA
В 1978 г. Р.Ривест, А.Шамир и Л.Адлеман [RSA78] создали первую криптосистему с открытым ключом для шифрования и цифровой подписи, получившую название RSA (по первым буквам фамилий авторов). Система описывается в терминах элементарной теории чисел. Ее надежность обуславливается практической неразрешимостью задачи разложения большого натурального числа на простые множители. Современное состояние алгоритмов факторизации (разложения на множители) позволяет решать эту задачу для чисел длиной до 430 бит; исходя из этого, ключ длиной в 512 бит считается надежным для защиты данных на срок до 10 лет, а в 1024 бита - безусловно надежным. Длина подписи в системе RSA совпадает с длиной ключа.
Несмотря на то, что отсутствует математически доказанное сведение задачи раскрытия RSA к задаче разложения на множители, а также задачи разложения на множители к классу NP-полных задач, система выдержала испытание практикой и является признанным стандартом de-facto в промышленной криптографии, а также официальным стандартом ряда международных организаций. С другой стороны, свободное распространение программного обеспечения, основанного на RSA, ограничено тем, что алгоритм RSA защищен в США рядом патентов.
Проект DSS
В 1991 г. в США был опубликован проект федерального стандарта цифровой подписи - DSS (Digital Signature Standard, [DSS91], см. также [S94], с.304-314), описывающий систему цифровой подписи DSA (Digital Signature Algorithm). Одним из основных критериев при создании проекта была его патентная чистота.
Предлагаемый алгоритм DSA, имеет, как и RSA, теоретико-числовой характер, и основан на криптографической системе Эль-Гамаля [E85] в варианте Шнорра [S89]. Его надежность основана на практической неразрешимости определенного частного случая задачи вычисления дискретного логарифма. Современные методы решения этой задачи имеют приблизительно ту же эффективность, что и методы решения задачи факторизации; в связи с этим предлагается использовать ключи длиной от 512 до 1024 бит с теми же характеристиками надежности, что и в системе RSA. Длина подписи в системе DSA меньше, чем в RSA, и составляет 320 бит.
С момента опубликования проект получил много критических отзывов (см., напр., [R92]), многие из которых были учтены при его доработке. Одним из главных аргументов против DSA является то, что, в отличие от общей задачи вычисления дискретного логарифма, ее частный случай, использованный в данной схеме, мало изучен и, возможно, имеет существенно меньшую сложность вскрытия. Кроме того, стандарт не специфицирует способ получения псевдослучайных чисел, используемых при формировании цифровой подписи, и не указывает на то, что этот элемент алгоритма является одним из самых критичных по криптографической стойкости.
Функции DSA ограничены только цифровой подписью, система принципиально не предназначена для шифрования данных. По быстродействию система DSA сравнима с RSA при формировании подписи, но существенно (в 10-40 раз) уступает ей при проверке подписи.
Вместе с проектом DSS опубликован проект стандарта SHS (Secure Hash Standard), описывающий однонаправленную хэш-функцию SHA (Secure Hash Algorithm), рекомендованную для использования вместе с DSA (см. [S94], с.333-336). Хэш-функция SHA является модификацией алгоритма MD4, хорошо известного в криптографической литературе.
Российский стандарт цифровой подписи
В 1993 г. в России были изданы два государственных стандарта “Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма” и “Функция хэширования”, под общим заголовком “Информационная технология. Криптографическая защита информации”.
Стандарт “Процедуры выработки и проверки электронной цифровой подписи. ” во многом схож со своим американским аналогом DSS. Для формирования и проверки цифровой подписи в нем используется тот же алгоритм Эль-Гамаля и Шнорра, что и в DSS, с незначительными модификациями. Имеется две альтернативных длины ключа, 512 и 1024 бит; длина подписи составляет 512 бит.
Для генерации ключей предложен ряд новых алгоритмов. Ключи, получаемые при помощи этих алгоритмов, имеют специальный вид, что потенциально может упростить задачу вскрытия системы по сравнению с DSS. Критика DSS, связанная с недостаточно разработанным теоретическим обоснованием алгоритма, в случае росийского стандарта несколько смягчается тем, что элемент ключа q выбирается более длинным, чем в DSA. Критика. связанная с отсутствием спецификации на способ получения псевдослучайных чисел, остается в силе.
Как и DSS, российский стандарт определяет только алгоритм цифровой подписи, но не шифрования. Быстродействие обоих алгоритмов приблизительно совпадает.
Стандарт “Функция хэширования” предназначен для использования вместе со стандартом “Процедуры выработки и проверки цифровой подписи” и представляет собой оригинальный алгоритм, основанный на методе шифрования с симметричным ключом ГОСТ 28147. Стандарт не содержит криптографического обоснования выбранного алгоритма и не корректирует ГОСТ 28147 в части заполнения узлов замены.
Несмотря на указанные недостатки, система, описанная в российском стандарте, применима во многих областях, особенно для коммерческих приложений.
Программная криптографическая система ТерКрипт
Санкт-петербургским МГП “ТЕРКОМ” разработана криптографическая система ТерКрипт, представляющая собой комплекс программ на языке C стандарта ANSI. Система реализует в полном объеме алгоритмы DES, ГОСТ 28147, RSA, DSS/SHS и российских криптографических стандартов. Алгоритмы реализованы на основе общих процедур теории чисел, использующих современные теоретико-числовые методы для достижения максимальной эффективности. Имеется специальная версия системы, оптимизированная для работы на персональных компьютерах IBM AT 286, 386, 486.
[BFS91] Th.Beth, M.Frisch, G.J. Simmons (eds.) Public-Key Cryptography: State of the Art and Future Directions. E.I.S.S. Workshop - Oberwolfach, Germany, July 1991 - Final Report. Lecture Notes in Computer Science, V.578.
[DH76] W.Diffie, M.Hellman. New Directions in Cryptography. IEEE Trans. Inform. Theory, IT-22, No.6 (1976), pp.644-654.
[DSS92] The Digital Signature Standard Proposed by NIST. CACM, V.35 (1992), No.7, pp.36-40.
Самым слабым звеном при реализации симметричных криптосистем в системах защищенного электронного документооборота, электронных банковских платежей и, особенно, электронной торговли является вопрос распределения ключей.
Для обеспечения обмена конфиденциальной информацией между двумя абонентами телекоммуникационной сети, должен быть сгенерирован ключ (возможно, одним из абонентов), а затем по некоторому защищенному каналу передан другим пользователям (другому абоненту). В качестве средства создания защищенного канала вновь может быть использована некоторая криптосистема.
Наибольшую остроту вопрос распределения и доставки ключей приобретает в случае невозможности заранее описать состав информационно-телекоммуникационной сети.
Для решения этой проблемы на основе результатов, полученных классической и современной алгеброй, были предложены системы с открытым ключом (СОК). В СОК для зашифрования не используются секретные ключи – они необходимы только при расшифровании (рис. 1).
Главным понятием СОК является однонаправленная функция с секретом (one-way trapdoor function). Однонаправленную функцию с секретом : легко вычислить для всех , но очень трудно обратить почти для всех значений из . Однако, если используется некоторая секретная информация , то для всех значений легко вычислить величину, удовлетворяющую условию .
Криптосистемы с открытым ключом, использующие однонаправленные функции с секретом, еще называются асимметричными (asymmetric cryptosystems).
В 1975 году Диффи и Хеллмана в работе, посвященной криптографии с открытым ключом, предложили несколько вариантов построения однонаправленных функций с секретом. Однако эти функции не были строго асимметричными, поэтому вскоре Диффи и Хеллман предложили более удачный вариант: показательную функцию по простому модулю.
Эта функция была использована в широко распространенном криптографическом протоколе – протоколе обмена ключами Диффи-Хеллмана (Diffie-Hellman key exchange protocol).
Ранее, в 1974 году, Меркл (Merkle) изобрел механизм согласования криптографического ключа путем явных асимметричных вычислений, получивших название головоломка Меркла.
Асимметричность головоломки Меркла заключается в том, что ее вычислительная сложность для законных участников протокола согласования ключа и для перехватчиков совершенно разная: легальные участники легко выполняют вычисления, а нелегальные — нет. Головоломка Меркла представляет собой первую эффективную реализацию однонаправленной функции с секретом.
Несмотря на то, что головоломка Меркла не подходит для применения в современных криптографических приложениях, ее влияние на криптосистемы с открытым ключом невозможно переоценить.
В последнее время стало известно, что первую криптосистему с открытым ключом разработал британский математик Кокс (Cocks) еще в 1973 году. Алгоритм Кокса, получивший название алгоритма с несекретным ключом шифрования, использовал сложность разложения целого числа на простые множители и, по существу, совпадал с криптосистемой RSA.
Первоначально алгоритм Кокса был засекречен и только в декабре 1997 года Группа по электронной защите средств связи (Communications Services Electronic Security Group – CESG) его рассекретила.
Несмотря на то, что вначале криптосистемы с открытым ключом были достоянием узкого круга лиц, именно благодаря открытым исследованиям они нашли два важнейших применения для создания алгоритмов цифровой подписи и механизмов обмен секретными ключами через открытые каналы связи.
В настоящее время алгоритмы шифрования с открытым ключом получили широкое распространение в информационных системах.
Так, алгоритм RSA фактически стал стандартом для открытых систем и рекомендован международной организацией по стандартизации ISO, соответствующие приложения лежат в основе электронной коммерции, осуществляемой через Internet.
Суть их состоит в том, что каждым абонентом сети генерируются два ключа, связанные между собой по определенному математическому закону. Один ключ объявляется открытым, а другой закрытым (секретным).
Рис. 1. Криптосистема с открытым ключом
Таким образом, односторонняя функция с секретом, используемая в асимметричной системе, является взаимнооднозначной, но вместе с тем обладает свойствами необратимости.
Необратимость, конечно, понимается не в общепринятом смысле, а как практическая невозможность вычислить обратную функцию, используя современные вычислительные средства за обозримый интервал времени.
Поэтому, чтобы гарантировать надежную защиту информации, к СОК предъявляются два важных и очевидных требования.
1. Преобразование исходного текста должно быть вычислительно нереализуемым (необратимым) и исключать его восстановление на основе открытого ключа.
2. Определение закрытого ключа на основе открытого также должно быть невозможным на современном технологическом уровне. При этом желательна точная нижняя оценка сложности (количества операций) раскрытия шифра.
В основе современных криптосистем с открытым ключом вычислительно необратимые преобразования чаще всего строятся на основе следующих алгоритмических проблем:
– разложение больших чисел на простые множители;
– вычисление логарифма в конечном поле;
– нахождение кратности точки (дискретный логарифм) на эллиптической кривой;
– вычисление корней алгебраических уравнений над кольцами и полями.
Отметим, области применения СОК.
1. Средства шифрования передаваемых и хранимых данных.
2. Средства аутентификации пользователей и проверки целостности данных.
3. Механизмы распределения ключей.
Алгоритмы СОК работают медленее, чем алгоритмы симметричных шифрсистем. Поэтому на практике предпочтительным является комбинированное использование СОК и симметричных систем. При этом СОК используется для создания механизмов распределения ключей, объем которых незначителен, а с помощью симметричных алгоритмов осуществляется шифрование больших информационных потоков.
Наибольшее распространение получили системы с открытым ключом на основе алгоритма RSA, криптосистема Эль-Гамаля и криптосистемы на основе эллиптических кривых.
Криптосистема RSA, разработанная в 1977 году, получила свое название в честь ее создателей: Рона Ривеста, Ади Шамира и Леонарда Эйдельмана.
Разработчики воспользовались тем фактом, что нахождение больших простых чисел в вычислительном отношении осуществляется достаточно просто, но не известен алгоритм, выполняющий за полиномиальное время разложение на простые множители больших чисел.
Доказано (теорема Рабина), что раскрытие шифра RSA эквивалентно нахождению такого разложения. Поэтому для любой длины ключа можно дать (современую практическую) нижнюю оценку числа операций для раскрытия шифра, а с учетом производительности современных компьютеров оценить и необходимое на это время.
Возможность реально оценить защищенность алгоритма RSA стала одной из причин популярности этой СОК на фоне десятков других схем. Поэтому алгоритм RSA используется в банковских компьютерных сетях, особенно для работы с удаленными клиентами (обслуживание кредитных карточек).
В настоящее время алгоритм RSA используется во многих стандартах, среди которых SSL, S-H Т TP, S-MIME, S/WAN, STT и PCT. Кроме того, алгоритм RSA реализуется как в виде самостоятельных криптографических продуктов (PGP), так и в качестве встроенных средств в некоторых приложениях (Интернет‑браузеры от Microsoft и Netscape).
Напомним ряд положений элементарной теории чисел, лежащих в основе этого алгоритма.
Наибольшим общим делителем двух целых чисел и называется наибольшее целое число, которое делит как так и . Обозначения: или НОД. Числа и называются взаимно простыми, если .
Важным фактом является то, что НОД можно выразить с помощью решений диофантового уравнения.
Пусть и . Тогда существуют целые числа являющиеся решением уравнения .
Решение уравнения , при условиях и , можно найти с помощью т.н. расширенного алгоритма Эвклида. Очевидно, достаточно решить уравнение, при положительных и .
Следовательно, для взаимно простых чисел и , можно найти числа , такие, что . Приведем последнее равенство по модулю , получим .
Построенное число называется числом, обратным к по модулю и обозначается через . Такое число в диапазоне является единственным.
Заметим, что по этой причине, множество всех наименьших неотрицательных вычетов, взаимно простых с , при умножении на любой свой элемент , подвергается перестановке: .
Рассмотрим степени числа по модулю , где и взаимно просты.
Пусть . Степени 1,2,…10, числа 2 таковы: 2,4,8,5,10,9,7,3,6,1.
Аналогично, степени числа 3 равны 3,9,5,4,1,3,9,5,4. В каждом случае имеется периодичность. Наименьшая длина периода для числа по модулю называется порядком (показателем, периодом) числа по модулю .
Порядок числа по модулю обозначается .
Порядки чисел по модулю различны. Существуют числа, являющиеся порядком одновременно для всех чисел, взаимно простых с . Одно из них равно значению т.н. функции Эйлера , определяемой как количество чисел в последовательности , взаимно простых с .
Из определения следует, что для простого числа и, кроме того, .
Функция Эйлера является мультипликативной: если , то .
Теорема Эйлера. Если , то .
Доказательство. При теорема верна. Пусть и – все вычеты по модулю , взаимно простые с модулем (по определению, ).
Пусть – один из таких вычетов. Тогда множества и совпадают.
Поэтому . Умножив обе части сравнения на , получим
Из теоремы Эйлера следует малая теорема Ферма: , где – простое, .
Случай можно учесть в выражении .
Существует общая формула для при известном каноническом разложении на степени простых чисел.
Таким образом, если , где неравные простые числа, то .
Для модулей указанного вида можно показать, что если число, взаимно простое с , то отображение : является взаимно однозначным на множестве вычетов по модулю . При этом, , а обратным отображением является : .
В криптосистеме RSA зашифрование блока сообшения производится по формуле , а для расшифрования применяется операция . Таким образом, открытым и секретным ключом криптосистемы являются соответственно и .
Построение ключа при известных легко осуществимо. При наличии соответствующих параметров функции и также легко вычисляются.
Если известны и , но и неизвестны, то представляет собой одностороннюю функцию с секретом.
Построение по заданным и равносильно разложению числа на сомножители. В случае, когда и – достаточно большие простые числа, то разложение практически невозможно. Это и является причиной стойкости криптосистемы RSA.
Рассмотрим принципы организации информационного обмена с использованием системы RSA. Вначале абонент выбирает пару различных простых чисел и . Затем он вычисляет , выбирает случайный вычет , взаимно простой с , и находит .
На общедоступном сервере (сайте) размещается справочная таблица, которая содержит открытые ключи абонентов .
Для передачи криптограммы от абонента к абоненту абонент разбивает открытый текст на блоки и последовательно зашифровывает их с помощью преобразования . Абонент производит расшифрование поблочно, применяя отображение .
Очевидно, для того чтобы найти , достаточно знание сомножителей ,. Для современных технологических возможностей время выполнения наилучших из известных алгоритмов разложения для значений слишком велико.
1. Выберем простые числа: , .
3. Выберем случайное значение , .
5. Вычислим секретный ключ
Для расшифрования возведем каждый блок в степень по модулю 33: , , .
Секретный ключ для учебной системы легко найти перебором. На практике это невыполнимо, т.к. реальный размер модуля (длина битового представления) находится в диапазоне от 512 до 4096 битов.
Основные усилия в ходе практической реализации RSA приходятся на генерацию случайных больших простых чисел.
Есть очевидный путь решения задачи: случайно выбрать большое нечетное число и проверить его делимость на множители в диапазоне .
В случае неуспеха выбираем число и так далее. Однако при больших такой подход неосуществим.
Заметим, что из теории чисел известно, что вероятность того, что наудачу выбранное число порядка будет простым, оценивается как .
Другая проблема – какой длины следует использовать ключи?
Полезно привести длины параметров RSA в битах, установленные и рекомендуемые французскими специалистам для практических приложений.
1. Сомножители RSA – модуля должны выбираться случайно и быть одинаковой длины.
2. Длина секретного ключа должна быть сравнима с размером модуля .
3. Длина открытого ключа должна быть строго более 16 битов.
4. До 2010 года разрешается использовать значения модуля длиной не менее 1536 битов, однако рекомендуется – не менее 2048 битов.
5. С 2010 года по 2020 год разрешается использовать значения модуля длиной не менее 2048 битов.
6. После 2020 года предполагается использовать значения модуля длиной не менее 4096 битов.
Следующий немаловажный аспект реализации RSA – вычислительный. Ведь приходится использовать аппарат арифметики больших чисел.
Следует учитывать, что, по сравнению с тем же алгоритмом DES, для RSA требуется в тысячи и десятки тысяч раз большее время.
В отличие от RSA асимметричная криптосистема Эль-Гамаля основана на проблеме дискретного логарифма.
Соответствующая односторонняя функция является показательной функцией по простому модулю : секретные параметры входят в показатели степеней.
Возведение числа в степень в конечном поле выполняется легко, в то время как восстановление показателя степени по значению функции (то есть нахождение дискретного логарифма) при больших является сложной вычислительной задачей.
В криптосистеме Эль-Гамаля для построения пары асимметричных ключей выбирается большое простое число и два псевдослучайных числа, меньших .
Открытым ключом является тройка чисел .
Затем вычисляются числа – лазейка и – шифртекст. Криптограммой является пара блоков данных .
Для расшифрования достаточно получить сомножитель , что можно сделать с помощью секретного ключа, вычислив значение .
Таким образом, обеспечивается защищенный информационный обмен без предварительной рассылки секретных ключей.
Список используемой литературы
Васильева, И. Н. Криптографические методы защиты информации: учебник и практикум для академического бакалавриата / И. Н. Васильева. — М.: Издательство Юрайт, 2018. — 349 с.
Запечников , С . В . Криптографические методы защиты информации : учебник для академического бакалавриата / С . В . Запечников , О . В . Казарин , А . А . Тарасов . — М . : Издательство Юрайт , 2015 . — 309 с.
Молдовян, II. А. Практикум по криптосистемам с открытым ключом / II. А. Молдовян. — СПб.: БХВ-Петербург, 2007. – 304 с.
, что
| x | легко вычислимо |  |
| ——————————→ | ||
| ←··································· | ||
| сложновычислимо |
По известному " width="" height="" />
довольно просто найти значение " width="" height="" />
, тогда как определение " width="" height="" />
из " width="" height="" />
сложно в смысле теории.
| Имя | (имя_пароль) |
|---|---|
| АЛИСА | РОМАШКА |
| БОБ | НАРЦИСС |
| Имя: | АЛИСА |
|---|---|
| Пароль: | ГЛАДИОЛУС |
Примеры таких криптотекстов:
| Криптотекст 1 | Криптотекст 2 | Криптотекст 3 |
|---|---|---|
| 1235267 | 5643452 | 1235267 |
| 3572651 | 3517289 | 3517289 |
| 4673956 | 4673956 | 4673956 |
| 3517289 | 3572651 | 3572651 |
| 7755628 | 7755628 | 7755628 |
| 5643452 | 1235267 | 5643452 |
| 8492746 | 8492746 | 8492746 |
Чтобы расшифровать текст, достаточно иметь справочник, составленный согласно возрастанию номеров. Этот справочник является лазейкой (секрет, который помогает получить начальный текст), известной только легальным пользователям. Не имея на руках копии справочника, криптоаналитик затратит очень много времени на расшифровку. [2]
Схема шифрования с открытым ключом [ ]
Пусть " width="" height="" />
— пространство ключей, а " width="" height="" />
и " width="" height="" />
— ключи шифрования и расшифрования соответственно. >" width="" height="" />
- функция шифрования для произвольного ключа " width="" height="" />
" width="" height="" />
" width="" height="" />
, такая что:
Научная основа [ ]
Вообще, в основу известных асимметричных криптосистем кладётся одна из сложных математических проблем, которая позволяет строить односторонние функции и функции-лазейки. Например, криптосистемы задачу об укладке рюкзака .
Основные принципы построения криптосистем с открытым ключом [ ]
- Начинаем с трудной задачи Р. Она должна решаться сложно в смысле теории: нет алгоритма, с помощью которого можно было бы перебрать все варианты решения задачи Р за Криптография с несколькими открытыми ключами [ ]
Пусть есть 3 ключа " width="" height="" />
, >" width="" height="" />
, >" width="" height="" />
, распределенные так, как показано в таблице.
| Лицо | Ключ |
|---|---|
| Алиса | |
| Боб | |
| Кэрол | |
| Дэйв | , |
| Эллен | , |
| Франк | , |
Криптоанализ алгоритмов с открытым ключом [ ]
, анализируя его, пытается найти >" width="" height="" />
. Этот процесс упрощается, если криптоаналитик перехватил несколько криптотекстов с, посланных лицом A лицу B.
Большинство криптосистем с открытым ключом основаны на проблеме факторизации больших чисел. К примеру, RSA использует в качестве открытого ключа n произведение двух больших чисел. Сложность взлома такого алгоритма состоит в трудности разложения числа n на множители. Но эту задачу решить реально. И с каждым годом процесс разложения становится все быстрее. Ниже приведены данные разложения на множители с помощью алгоритма "Квадратичное решето".
| Год | Число десятичных разрядов в разложенном числе | Во сколько раз сложнее разложить на множители 512-битовое число |
|---|---|---|
| 1983 | 71 | > 20 000 000 |
| 1985 | 80 | > 2 000 000 |
| 1988 | 90 | 250 000 |
| 1989 | 100 | 30 000 |
| 1993 | 120 | 500 |
| 1994 | 129 | 100 |
Также задачу разложения потенциально можно решить с помощью Алгоритма Шора при использовании достаточно мощного квантового компьютера.
Для многих методов несимметричного шифрования криптостойкость, полученная в результате криптоанализа, существенно отличается от величин, заявляемых разработчиками алгоритмов на основании теоретических оценок. Поэтому во многих странах вопрос применения алгоритмов шифрования данных находится в поле законодательного регулирования. В частности, в России к использованию в государственных и коммерческих организациях разрешены только те программные средства шифрования данных, которые прошли государственную сертификацию в административных органах, в частности, в ФАПСИ, [6]
Читайте также: