АРХИВ СТАТЕЙ ЖУРНАЛА «МОЙ КОМПЬЮТЕР» ЗА 2002 ГОД

Открытый ключ к закрытой информации

• Все журналы \ Номер 12/183 `2002 от 25.03.2002 \ Открытый ключ к закрытой информации

Роман БРЕЧКО rbrechko@ukr.net

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

Концепция открытого ключа

Основной проблемой, с которой соприкасалась классическая криптография, являлась проблема передачи шифрующего ключа. В чем же суть этой проблемы? Так вот, поскольку современная криптография полагает, что шифрующий ключ нужно постоянно менять, то для этого следует иметь надежный канал связи для передачи ключа. Казалось бы, что ничего страшного в этом нет. Да, действительно, все хорошо, если передачу ключа нужно осуществить в пределах одного города. Ну а если ключ надо передать в другую страну? Вот здесь-то и начинают возникать проблемы (тем более, что передачу ключа нужно проводить довольно-таки часто). Отсутствием этих препятствий и характеризуется концепция открытого ключа, развитая в 1976 году американскими математиками Диффи, Гелманом и Меркле.

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

Для начала отошлем к понятиям классической криптографии, в первую очередь к ключу К, который использовался при шифровании и почти во всех случаях при дешифровке. Зная шифрующий ключ К, легко можно получить дешифрующий ключ К1. Процесс получения криптотекста С с открытого текста М с помощью алгоритма Е и используя ключ К запишем в следующем виде: С=ЕК(М). Соответственно, процесс дешифровки выполняется по правилу М=DK1(C), где D — алгоритм дешифровки. Во всех классических криптосистемах дешифрующий ключ легко находится, если известен шифрующий. В криптосистемах же с открытым ключом дешифрующий ключ К1 из ключа К вывести очень непросто — в принципе, практически невозможно.

Общую схему шифрования с открытым ключом можно подать в следующем виде (рис. 1).

Криптосистемы с открытым ключом должны включать в себя следующие понятия:

• Алфавит А, в котором записываются открытые тексты, а также алфавит В — для отображения криптотекстов.

• Алгоритм генерирования ключей — это полиномиальный вероятностный алгоритм, который, получая значение параметра k (определяет параметр надежности), выдает пару ключей К и К1. Они называются соответственно открытым и тайным ключами.

• Полиномиальный детерминированный алгоритм шифрования Е, который, получая на входе открытый текст М и ключ К, дает на выходе криптотекст С: С=ЕК(М).

• Полиномиальный детерминированный алгоритм дешифрования D, который, имея криптотекст С и тайный ключ К1, выдает открытый текст М: М=DK1(C).

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

Теперь покажем преимущества этой концепции над классической. Для этого представим себе коммуникационную сеть (например, Интернет), которой пользуется n абонентов. Естественно, что каждая пара абонентов может иметь свои секреты и хочет общаться по сети тайно от других абонентов. Несложно подсчитать, что n абонентов образуют n(n-1)/2 пар. Именно такое количество ключей будет востребовано, если будет использоваться классический подход. В то же время концепция открытого ключа позволяет использовать сеть более оптимально. Каждый абонент самостоятельно формирует пару ключей (Кi, Ki1), где i — номер абонента в сети. После этого всем оглашается множество открытых ключей {К1, К2, …, Кn}, а каждый второй элемент из пары ключей сохраняется в тайне. Таким образом, если первый абонент хочет послать секретное сообщение второму абоненту, то он должен будет использовать алгоритм Е с ключом К2. Полученный криптотекст не сможет никто прочитать, кроме второго абонента, потому что только у него имеется тайный ключ К21. Стало быть, тайна общения будет сохранена с использованием всего лишь n ключей. Как видите, концепция открытого ключа оптимальней, к тому же может обеспечить легкую смену ключей.

В общих чертах с концепцией открытого ключа вроде бы уже разобрались, поэтому приступим к описанию конкретных криптосистем. Поскольку об одной из наиболее популярных в этой концепции криптографических систем, а именно RSA, на страницах МК (№ 170-171, статья «Чтоб никто не догадался») уже рассказывалось, уделяться ей внимание мы не будем.

Криптосистема Рабина

Описание этой системы начнем с генерирования ключей. Итак, нужно выбрать два разных больших простых числа p и q. Следует отметить, что большими будем считать числа разрядностью не менее 200 бит. Также напомним, что простыми называются числа, которые не имеют делителей, кроме единицы и самого себя. Итак, далее считаем произведение: n=p*q. Открытым ключом будем считать число n, а тайным ключом будут числа p и q.

Процесс шифрования осуществляется блоками. Для этого шифруемый текст нужно записать в цифровой форме и разбить на блоки так, чтобы каждый блок не превышал n. Цифровая форма текста будет представлять каждый символ в виде числа, не превышающего n — например, каждой букве алфавита можно сопоставить ее порядковый номер. Далее к каждому блоку применяем процедуру Сi=Е(Мi)=Mi mod n. Блоки Сi будут образовывать криптотекст.

Теперь рассмотрим процесс дешифровки. Если Е(М)=С, то блок М будет корнем квадратным числа С по модулю n. Напомним, что корнем квадратным числа х по модулю n называется число y, для которого выполняется соотношение: y = (x^2) mod n. При условии, что числа С и n будут взаимнопростыми, мы получим ровно четыре таких корня. Существуют алгоритмы для нахождения этих корней, но для их успешного применения следует знать тайный ключ, т. е. числа р и q. Именно процедура нахождения квадратного корня и используется при дешифровке по системе Рабина. После дешифровки из четырех полученных корней выбирается один, которому будет соответствовать осмысленная текстовая информация. Казалось бы, все хорошо, но что делать, если нужно передать цифровую информацию? В этом случае вместе с криптотекстом следует передавать дополнительную незашифрованную информацию, хотя для передачи цифровой информации я рекомендовал бы использовать какую-нибудь другую криптосистему. Кроме этого следует отметить, что если числа С и n не будут взаимнопростыми, то конкурирующая организация может получить тайный ключ, т. е. факторизировать число n. Поэтому шифруемый текст такого типа нужно исключать.

Надежность криптосистемы Рабина состоит в том, что задача нахождения квадратного корня по модулю n = p*q не менее тяжела, чем факторизация числа n = p*q.

Пример 1.

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

Для начала сгенерируем открытый и тайный ключи. Выберем р = 7, q = 11, тогда n = p*q = 77. Итак, n = 77 будет открытым ключом, а р = 7 и q = 11 — тайным.

Пускай нам нужно зашифровать слово «Да». Представим его в цифровом виде, присвоив каждой букве ее порядковый номер в алфавите. Тогда получим, что М = 51. Зашифровываем: С = (51^2) mod 77 = 2601 mod 77 = 60. А теперь расшифровываем. Для этого найдем квадратные корни числа 60 по модулю 77. Это будут числа 26, 37, 40, 51. Как видим, лишь последнему числу будет соответствовать нормальная текстовая информация (слово «Да»).

Вероятностное шифрование

Одной из разновидностей криптосистем с открытым ключом является вероятностное шифрование, разработанное Шафи Гольвассером и Сильвио Минелли. Его суть состоит в том, чтобы алгоритм шифрования Е подчинить вероятностным моделям. В чем же преимущества такого подхода? Для примера, в системе RSA не «маскируются» 0 и 1. Так вот, эту проблему успешно решают вероятностные алгоритмы, поскольку они ставят в соответствие открытому тексту М не просто криптотекст С, а некоторый элемент из множества криптотекстов СМ. При этом каждый элемент этого множества выбирается с некоторой вероятностью. Другими словами, для любого открытого текста М результат работы алгоритма Е будет случайной величиной. Может показаться, что в этом случае дешифровать информацию будет невозможно. Спешу обрадовать вас, это совсем не так. Для того чтобы сделать возможной дешифровку, нужно, чтобы для разных открытых текстов М1 и М2 множества СМ1 и СМ2 не пересекались. Также хочется сказать, что вероятностные алгоритмы шифрования являются более надежными, нежели детерминированные, которые описаны выше. Ну а теперь приступим к рассмотрению некоторых вероятностных криптосистем.

Вероятностное шифрование на основе RSA-функций

Генерирование ключей проводится так же, как и в криптосистеме RSA, т. е. открытым ключом будет пара чисел е и n, а тайным — число d.

Перед тем, как приступить к процессу шифрования, зашифровываемый текст нужно представить в двоичном виде. Это можно сделать аналогично тому, как это делается в криптосистеме Рабина, только вместо представлений символов в десятичной системе исчисления в данном случае нужно воспользоваться двоичной системой исчисления. Итак, двоичное сообщение М=m1m2…mk, где mi = {0, 1}, переводится в криптотекст С=с1с2…сk с помощью следующей процедуры:

• если mi = 0, то выбирается случайное четное число хi<n; если же mi = 1, то выбирается случайное нечетное число хi<n;

• считаем сi = (xi^e) mod n.

Полученные сi и будут составлять криптотекст.

Процесс дешифровки будет выглядеть так же просто. Итак, выведение битов открытого текста из элементов криптотекста производится по следующему правилу: mi = 0, если (сi^d) mod n будет четным числом; mi = 1, если (сi^d) mod n будет нечетным числом.

Надежность этой криптосистемы базируется на надежности системы RSA.

Пример 2.

Генерируем ключи: р = 3, q = 7, d = 5 — тайный ключ; n = p*q = 21, e = 17 — открытый ключ.

Чтобы не утруждаться, будем шифровать букву «Д». Для этого представим ее в шестибитном двоичном виде: 000101. Нам нужно четыре случайных четных числа и два нечетных. Пускай ими будут 4, 2, 8, 2 и 3, 5 соответственно. Зашифровываем: с1 = c5 = (4^17) mod 21 = 16, c2 = (2^17) mod 21 = 11, c3 = (8^17) mod 21 = 08, c4 = (3^17) mod 21 = 12, c6 = (5^17) mod 21 = 17. Таким образом, криптотекст будет иметь вид: С = 161108121617.

Теперь попробуем дешифровать этот криптотекст. Для этого считаем: (16^5) mod 21 = 4, (11^5) mod 21 = 2, (8^5) mod 21 = 8, (12^5) mod 21 = 3, (17^5) mod 21 = 5. Используя приведенный выше алгоритм, получим: m1 = m2 = m3 = m5 = 0, m4 = m6 = 1. Из этого имеем М = 000101.

Криптосистема Эль Гамала

Традиционно начнем с генерирования открытого и тайного ключей. Итак, выбирается большое простое число р, а также число g, причем 1<g<p-1. Числа р и g не являются тайными и пребывают во всеобщем пользовании. Каждый абонент сети выбирает случайное число a (1<a<p-1) и считает h = g^a mod p. Открытый ключ будут составлять числа p, g и h, а тайный — число а.

Шифрование в криптосистеме Эль Гамала осуществляется блоками (разбивка на блоки выполняется аналогично системе Рабина). Открытый текст М преобразовывают в криптотекст С таким путем:

• выбирается случайное число r (1<r<p-1);

• считаем С=(С1, С2), где С1 = (g^r) mod p, C2 = (M*h^r) mod p.

Таким образом, пара чисел (С1, С2) будет определять криптотекст.

Для расшифровки криптотекста С используем формулу: М = (С2*((С1)^a)^(-1)) mod p.

Как видим, идея этой криптосистемы довольно-таки проста. Открытый текст М преобразовываем к виду С2, и вместе с ним пересылается подсказка С1.

Пример 3.

Выбираем р = 23, g = 5, а = 6. Находим h = (5^6) mod 23 = 8. Отсюда имеем: р = 23, g = 5, h = 8 — открытый ключ; а = 6 — тайный ключ.

Зашифровывать будем букву «Ё» (опять-таки для простоты). Запишем ее цифровое представление: М = 7. Выбираем r = 10 и находим С1 = (5^10) mod 23 = 9, C2 = (7*8^10) mod 23 = 21. Запишем криптотекст: С = (9; 21).

Несложно проверить, что М = (21*(9^6)^(-1)) mod 23 = 7.

Выводы

Конечно, в данной статье приведены не все известные на сегодняшний день криптосистемы, которые базируются на концепции открытого ключа. За бортом осталась криптосистема Блюма-Гольвассера, алгоритм вероятностного шифрования на основе квадратичности и ряд других изобретений.

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

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

Идёт загрузка...

Данную страницу никто не комментировал. Вы можете стать первым.

Ваше имя:
Ваша почта:
Комментарий:
Введите символы или вычислите пример: * Обновить