5_2.htm 5.2. Двухключевые криптографические системы Двухключевые криптографические системы характеризуются на использовании двух ключей: открытого (несекретного) и закрытого (секретного). Особенность двухключевых систем состоит в возможности получения двух разновидностей шифрования в зависимости от вариантов применения открытого и секретного ключей.
Рис. 5.24. Система шифрования с открытым ключом Так, если открытый ключ используется для шифрования, а секретный ключ — для расшифрования, то имеет место система шифрования с открытым ключом. В этом случае каждый владелец открытого ключа может зашифровать текст, а расшифровать его сможет только владелец секретного ключа. Этот способ используется, например, в системах сотовой подвижной связи стандарта GSM. Структурная схема системы шифрования с открытым ключом представлена на рис. 5.24. Процесс шифрования и расшифрования для систем с открытым ключом, проиллюстрированный на рис. 5.24, может быть представлен выражениями: Y=Ez0(X), X=Dzc(Y)=Dzc(Ez0(X)), где Х — открытый текст; Y — зашифрованный текст; Z0 — открытый ключ; Zc — секретный ключ; Ez0 — функция шифрования; Dzc — функция расшифрования. Если же секретный ключ используется для шифрования, а открытый для расшифрования, то имеет место система электронной цифровой подписи (ЭЦП). В данном случае только владелец секретного ключа может правильно зашифровать текст, то есть подписать его, а проверить подпись (расшифровать текст) может любой пользователь, имеющий в своем распоряжении открытый ключ. Реализацию процесса шифрования и расшифрования для системы ЭЦП можно представить с помощью следующих выражений: Y=Ezc(X), X=Dzo(Y)=Dzo(Ezc(X)), где Х — открытый текст; Y — зашифрованный (подписанный) текст; Z — открытый ключ; Z — секретный ключ; Ezc — функция шифрования ЭЦП; Dzo — функция расшифрования ЭЦП. При этом для взаимной однозначности выражений, описывающих процессы шифрования и расшифрования с открытым и секретным ключами, необходимо выполнение условия Ezo Dzc = Ezc Dzo =е, где е — единичное преобразование. Криптографические системы с открытым ключом В криптосистемах с открытым (общедоступным) ключом используются некоторые аналитические преобразования и два различных, но взаимосвязанных друг с другом ключа — один (открытый — доступный любому лицу) для шифрования, другой (секретный — доступный только одному лицу) для дешифрирования. Стойкость криптосистем с открытым ключом определяется вычислительной сложностью алгоритмов. В этом случае предполагается, что даже при наличии всей доступной информации для дешифрирования сообщения оно не сможет быть восстановлено за требуемое время из-за чрезвычайно большого объема необходимых вычислений. В криптосистемах с открытым ключом, в алгоритмах шифрования и расшифрования используются разные ключи, каждый из которых не может быть получен из другого (с приемлемыми затратами). Желательно, чтобы методы шифрования обладали минимум двумя свойствами: • Законный получатель сможет выполнить обратное преобразование и расшифровать сообщение • Злоумышленник или криптоаналитик противника, перехвативший сообщение, не сможет восстановить по нему исходное сообщение без таких затрат времени и средств, которые сделают эту работу нецелесообразной. Один ключ используется для шифрования, другой — для расшифрования. Односторонние функции не могут быть непосредственно использованы в качестве криптосистемы, так как даже законный получатель не сможет расшифровать полученное сообщение. Односторонняя функция должна иметь «потайную дверь (лазейку)», то есть должен существовать эффективный способ ее вычисления в обоих направлениях, при этом знание прямого преобразования не позволяет легко найти обратное преобразование. Двухключевые системы (рис. 5.25), в основном, используют блочные методы шифрования и основаны на применении односторонних (необратимых) функций с потайным ходом (лазейкой). Эти функции обладают важным свойством: при заданном значении х относительно просто вычислить значение функции f(x). Однако, если известна функция y=f(x), то для вычисления х очень трудно рассчитать значение обратной функции l/f(y). Односторонние функции с потайной дверью (лазейкой) являются теоретической основой криптосистем с открытым ключом. Примером подобной функции является перемножение простых чисел (простое число, как известно из школьной программы, — это целое число, которое делится без остатка только на единицу и на само себя). Например, сравнительно несложно перемножить два простых 100-значных числа, однако для разложения на множители получившегося 200-значного числа потребуется десятки лет непрерывной работы мощного компьютера. Примером криптоалгоритма на основе умножения простых чисел является широко известный алгоритм RSA (Райвест, Шамир, Адлеман). Криптостойкость алгоритма RSA находится в прямой зависимости от сложности разложения простых чисел на множители. Вычисление ключей в таких системах осуществляется получателем сообщений, который оставляет у себя тот ключ, который он будет потом использовать для расшифрования, то есть секретный ключ. Другой ключ — открытый, он высылает отправителю сообщений любым доступным способом, не опасаясь его огласки. Используя этот открытый ключ, любой пользователь может зашифровать свой открытый текст и послать его получателю, который сформировал данный открытый ключ (рис. 5.26). Все используемые алгоритмы этого процесса являются общедоступными. Особенность этого метода заключается в том, что функции шифрования и расшифрования являются обратимыми только тогда, когда они обеспечиваются с помощью строго определенной пары ключей (открытого и секретного), причем открытый ключ должен представлять собой необратимую функцию от секретного ключа.
Рис. 5.26. Пример реализации системы с открытым ключом
В результате исследований односторонних (необратимых) функций с использованием решений определенных классов математических задач появились следующие направления в построении двухключевых криптографических алгоритмов: • Умножение простых чисел • Дискретное возведение в степень • Задача об укладке (упаковки) рюкзака (ранца) • Использование кодовых конструкций, исправляющих ошибки. Недостатком этих систем является то, что в системах с открытым ключом, также как и в блочных шифрах, необходим большой размер шифруемого блока, хотя, возможно, и не больше чем в алгоритме DES. А это препятствует, наряду с низкой скоростью шифрования, использованию алгоритмов с открытым ключом в потоковых шифрах. На настоящий момент высокоэффективные системы с открытым ключом рока не найдены. Почти повсеместно принято ограничение использования криптосистем с открытым ключом — только для управления ключами и цифровой подписи. Метод возведения в степень Известно несколько методов шифрования, разработанных на основе дискретного возведения в степень. Наиболее распространенным из них является метод дискретного возведения в степень в конечных полях. К ним относятся криптоалгоритмы Диффи-Хелмана (DH) и Месси-Омура. Задача дискретного возведения в степень в аддитивной абелевой группе положена в основу построения алгоритмов на алгеброических кривых. Идея криптографии с открытым ключом тесно связана с идеей односторонних функций. По заданному аргументу х легко вычислить значение функции f(x), тогда как определение х из f(x) трудновычислимо. Здесь «трудно-вычислимость» понимается в смысле теории сложности. Ситуация изображена на рис. 5.27. Мы говорим о f(x), как о функции. Определение х из f(x) трудновычислимо только для криптоаналитика. Законный получатель информации имеет подходящую лазейку. Далее такие односторонние функции будем называть криптографическими. Упомянем по этому поводу, что ни одного примера криптографической односторонней функции не известно. Зато существует много криптографических функций f(x), таких, что: • Легко вычислить f(x) из х • Определение х из f(x), вероятно, будет трудновычислимым.
С точки зрения криптографии с открытым ключом вполне подходят функции, удовлетворяющие этим двум требованиям. В типичных криптосистемах с открытым ключом только прямой криптоанализ основан на вычислении х из f(x). Могут существовать и другие, более гениальные криптоанали-тические методы, избегающие этого вычисления. Таким образом, криптоаналитик может достичь успеха даже в том случае, когда доказано, что нахождение х из f(x) трудновычислимо. Функция f(x) будет односторонней, если перевод х в f(x) легок, а обратный перевод из f(x) в х трудновычислим. Второе требование часто заменяется более слабым условием: обратный перевод, вероятно, будет трудновычислимым. Можно выделить две основные группы методов криптографической защиты информации с открытым ключом, использующих ту или иную одностороннюю функцию с «потайной лазейкой». В качестве такой функции может быть использовано модульное возведение в степень с фиксированным показателем степени m и модулем n: . f(x)=xmmod n ( ) Эффективный алгоритм для обратной операции — извлечения корня m-ой степени по модулю п для произвольных тип неизвестен. Это так называемая проблема дискретного логарифмирования для больших чисел. Один из методов использует эффективный алгоритм извлечения корня при известном разложении числа п на простые множители. Это и позволяет отнести функцию вида f(x) к классу односторонних функций с «потайной лазейкой». Метод укладки (упаковки) рюкзака (ранца) Реализацией задачи об укладке рюкзака является криптоалгоритм Мер-кле и Хелмана. Рассмотрим этот криптоалгоритм на примере. Пусть задан набор чисел (а1,а2,...аn)=А, состоящий из n различных положительных целых чисел и еще одно положительное целое число k. Задачей является нахождение таких чисел а1, если это возможно, сумма которых равна числу k. В простейшем случае это число k указывает размер рюкзака, а каждое из чисел а; указывает размер предмета, который может быть упакован в рюкзак. Задачей является нахождение такого набора предметов, чтобы рюкзак был полностью заполнен. В качестве примера возьмем число k=3231 и набор из 10 целых чисел а1,..., 43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523. Заметим, что число k получается при сложении только некоторых чисел а:
Рис. 5.28. Метод укладки рюкзака 3231 = 129+ 473 + 903 + 561 + 1165 Таким образом, сложив эти числа, мы нашли решение, то есть заполнили рюкзак. Ситуация наглядно проиллюстрирована на рис. 5.28. В принципе решение всегда может быть найдено полным перебором подмножеств А и проверкой, какая из сумм равна числу k. В нашем случае это означает перебор 210=1024 подмножеств (включая при этом и пустое множество). Это вполне осуществимо. Но что будет, если существует несколько сотен чисел а1.? В нашем примере n=10, чтобы не усложнять положение и расчеты. В реальных условиях пример будет иметь, скажем, 300 чисел а. Суть здесь в том, что неизвестны алгоритмы, имеющие существенно меньшую сложность по сравнению с полным перебором. Поиск правильного решения среди 2300 подмножеств не поддается обработке. Кодовые конструкции Алгоритм преобразований на основе кодовых конструкций с исправлением ошибок различаются по способам маскирования исходного кода. Наиболее известными являются криптоалгоритмы Мак-Элайса, использующие исправляющие ошибки коды Гоппы, Нидеррайгера, Крука, Габидулина и Др. Сравнительные характеристики некоторых известных двухключевых криптоалгоритмов приведены в табл. 5.2. Таблица 5.2. Характеристики двухключевых криптоалгоритмов
Алгоритм Длина ключа, бит Примечание RSA DHE (алгоритм Диффи-Хелмана в версии Эль-Гамаля) DSS до 1 до 4 до 2 Используется для шифрования и формирования ЭЦП Используется для шифрования Используется для формирования ЭЦП Составные криптографические системы Сравнительный анализ показателей эффективности используемых в настоящее время криптографических систем показывает, что алгоритм шифрования двухключевых систем значительно медленнее классического алгоритма с секретным ключом. В то же время шифрование сообщений с открытым ключом обладает рядом преимуществ, которые невозможно реализовать в одноключевых системах. Данное обстоятельство побудило многих специалистов по криптографии к поиску криптосистем, сочетающих в себе достоинства как одноключевых, так и двухключевых систем. В 1991 году американский криптолог Ф. Зиммерманн предложил использовать так называемые составные криптографические системы, основанные на совместном применении систем с открытым и секретным ключами. В качестве конкретной реализации такого подхода был разработан и опубликован для широкого круга пользователей криптографический алгоритм PGP (Pretty Good Privacy). Принцип работы этого криптоалгоритма показан на рис. 5.29.
Рис. 5.29. Криптоалгоритм PGP Для шифрования открытого текста Х используется качественный и быстрый алгоритм симметричного шифрования с секретным ключом. В качестве секретного ключа применяется случайное число, используемое как сеансовый ключ Z. Кроме того, сеансовый ключ Z шифруется с помощью открытого ключа получателя Z0 при использовании несимметричного шифрования. Зашифрованные текст в виде Y=Ez(X) и сеансовый ключ в виде K=EZ0(Z) отправляются получателю. Процесс расшифрования является обратным по отношению к шифрованию. Секретный ключ получателя Zс используется для восстановления сеансового ключа Z, который, в свою очередь, служит ключом симметричного расшифрования Dz(Y) получаемого текста. Практические разработки криптоалгоритма PGP и последующий анализ его криптостойкости показывают, что он становится все более популярным в мире. Более того, рабочая группа по стандартам Интернета (IETF) рассматривает алгоритм PGP как возможный официальный стандарт этой глобальной сети, который будет рекомендован всем производителям программного обеспечения.