Асимметричные криптосистемы шифрования

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

¨ открытый ключ К: используется для шифрования информации, вычисляется из секретного ключа k;

¨ секретный ключ k: используется для расшифрования информации, зашифрованной с помощью парного ему открытого ключа К.

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

Асимметричные системы называют еще двухключевыми криптографическими системами или криптосистемами с открытым ключом.

Обобщенная схема асимметричной криптосистемы шифрования с открытым ключом показана на рис. 4.18.

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

Рис. 4.18. Обобщенная схема асимметричной криптосистемы шифрования

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

Процесс передачи зашифрованной информации в асимметричной криптосистеме осуществляется следующим образом:

1. Подготовительный этап:

– абонент В генерирует пару ключей: секретный ключ k_B и открытый ключ К_B;

–открытый ключ К_B посылается абоненту А и остальным абонентам (или делается доступным, например, на разделяемом ресурсе).

2. Использование – обмен информацией между абонентами А и В:

– абонент А зашифровывает сообщение с помощью открытого ключа К_B абонента В и отправляет шифртекст абоненту B;

– абонент В расшифровывает сообщение с помощью своего секретного ключа k_B. Никто другой (в том числе абонент А) не может расшифровать данное сообщение, так как не имеет секретного ключа абонента В. Защита информации в асимметричной криптосистеме основана на секретности ключа k_B получателя сообщения.

Асимметричные криптосистемы обладают следующими характерными особенностями:

1. Открытый ключ К_B и криптограмма С могут быть отправлены по незащищенным каналам, то есть противнику известны К_B и С.

2. Алгоритмы шифрования и расшифрования Е_B: М ® С, D_B: С ® М являются открытыми.

Безопасность асимметричной криптосистемы обеспечивает выполнение следующих требований:

1. Вычисление пары ключей (К_B, k_B) получателем В на основе начального условия должно быть простым.

2. Отправитель А, зная открытый ключ К_B и сообщение М, может легко вычислить криптограмму

(4.8)

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

(4.9)

4. Противник, зная открытый ключ К_B, при попытке вычислить секретный ключ k_B наталкивается на непреодолимую вычислительную проблему.

5. Противник, зная пару (К_B, С), при попытке вычислить исходное сообщение М наталкивается на непреодолимую вычислительную проблему.

Концепция асимметричных криптографических систем с открытым ключом основана на применении однонаправленных функций. Неформально однонаправленную функцию можно определить следующим об разом. Пусть X и Y – некоторые произвольные множества. Функция f: X ® Y является однонаправленной, если для всех х Î X можно легко вычислить функцию , где у Î Y. В то же время для большинства у Î Y достаточно сложно получить значение х Î X, такое, что (при этом полагают, что существует по крайней мере одно такое значение х).

Основным критерием отнесения функции f к классу однонаправленных функций является отсутствие эффективных алгоритмов обратного преобразования Y ® X.

Примером однонаправленной функции является целочисленное умножение. Прямая задача – вычисление произведения двух очень больших целых чисел Р и Q, то есть нахождение значения N = Р ´ Q является относительно несложной задачей для компьютера.

Обратная задача – факторизация, или разложение на множители большого целого числа, то есть нахождение делителей Р и Q большого целого числа N = Р ´ Q, – является практически неразрешимой при достаточно больших значениях N. По современным оценкам теории чисел, при целом и Р = Q для разложение числа N потребуется около 10²³ операций, то есть задача практически неразрешима для современных компьютеров.

Вторым важным классом функций, используемых при построении криптосистем с открытым ключом, являются однонаправленные функции с секретом. Функция f: X ® Y относится к классу однонаправленных функций с секретом в том случае, если она является однонаправленной и, кроме того, возможно эффективное вычисление обратной функции, если известен секрет (секретное число, строка или другая информация, ассоциирующаяся с данной функцией). В качестве примера однонаправленной функции с секретом можно указать используемую в криптосистеме RSA модульную экспоненту с фиксированными модулем и показателем степени. Переменное основание модульной экспоненты используется для представления числового значения сообщения М либо криптограммы С.

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

Асимметричные криптографические системы обладают следующими важными преимуществами перед симметричными криптосистемами:

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

¨ исчезает квадратическая зависимость числа ключей от числа пользователей; в асимметричной криптосистеме количество используемых ключей связано с количеством абонентов линейной зависимостью (в системе из N пользователей используются 2´N ключей), а не квадратичной, как в симметричных системах;

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

Асимметричные криптосистемы имеют следующие недостатки:

¨ на настоящий момент нет математического доказательства необратимости используемых в асимметричных алгоритмах функций;

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

¨ необходимо защищать открытые ключи от подмены.

Последнее рассмотрим более подробно. Предположим, на компьютере абонента А хранится открытый ключ К_B абонента В. Злоумышленник п имеет доступ к открытым ключам, хранящимся у абонента А. Он генерирует свою пару ключей К_п и k_n и подменяет у абонента А открытый ключ К_B абонента В на свой открытый ключ К_п. Для того чтобы отправить некую информацию абоненту В, абонент А зашифровывает ее на ключе К_п, думая, что это ключ К_B. Соответственно, это сообщение не сможет прочитать абонент В, но зато легко расшифрует и прочитает абонент п. От подмены открытых ключей спасает процедура сертификации открытых ключей.

Алгоритм шифрования RSA

Криптоалгоритм RSA был разработан в 1978 году тремя авторами: Р. Райвестом (Rivest), A. Шамиром (Shamir) и Л. Эйдельманом (Adleman). Алгоритм получил свое название по первым буквам фамилий его авторов. Алгоритм RSA стал первым алгоритмом с открытым ключом, который может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи.

Надежность алгоритма RSА основывается на трудности факторизации больших чисел и вычисления дискретных логарифмов в конечном поле.

В алгоритме RSA открытый ключ К_B, секретный ключ k_B, сообщение М и криптограмма С принадлежат множеству целых чисел

, (4.10)

где N – модуль:

. (4.11)

Здесь Р и Q – случайные большие простые числа. Для обеспечения максимальной безопасности выбирают Р и Q равной длины и хранят их в секрете.

Множество с операциями сложения и умножения по модулю N образует арифметику по модулю N.

Открытый ключ К_B выбирают случайным образом так, чтобы выполнялись условия

, (4.12)

. (4.13)

где – функция Эйлера.

Функция Эйлера указывает количество положительных целых чисел в интервале от 1 до N, которые взаимно просты с N.

Условие (4.13) означает, что открытый ключ К_B и функция Эйлера должны быть взаимно простыми.

Далее, используя расширенный алгоритм Евклида, вычисляют секретный ключ k_B, такой, что

(4.14)

или

. (4.15)

Это можно осуществить, так как получатель В знает пару простых чисел (Р, Q) и может легко найти . Заметим, что k_B и N должны быть взаимно простыми.

Открытый ключ К_B используют для шифрования данных, а секретный ключ k_B – для расшифрования.

Процедура шифрования определяет криптограмму С через пару (открытый ключ К_B, сообщение М) в соответствии со следующей формулой:

. (4.16)

В качестве алгоритма быстрого вычисления значения С используют ряд последовательных возведений в квадрат целого М и умножений на М с приведением по модулю N.

Расшифрование криптограммы С выполняют, используя пару (секретный ключ k_B, криптограмма С) по следующей формуле:

. (4.17)

Процедуры шифрования и расшифрования в алгоритме RSA. Предположим, что пользователь А хочет передать пользователю В сообщение в зашифрованном виде, используя алгоритм RSA. В таком случае пользователь А выступает в роли отправителя сообщения, а пользователь В – в роли получателя. Криптосистему RSA должен сформировать получатель сообщения, то есть пользователь В.

Пользователи В и А должны выполнить следующие действия:

1. Пользователь В выбирает два произвольных больших простых числа Р и Q.

2. Пользователь В вычисляет значение модуля .

3. Пользователь В вычисляет функцию Эйлера

и выбирает случайным образом значение открытого ключа К_B с учетом выполнения условий

.

4. Пользователь В вычисляет значение секретного ключа k_B, используя расширенный алгоритм Евклида при решении сравнения

.

5. Пользователь В пересылает пользователю А пару чисел (N, К_B) по незащищенному каналу.

Если пользователь А хочет передать пользователю В сообщение М, он выполнить следующие действия:

6. Пользователь А разбивает исходный открытый текст М на блоки, каждый из которых может быть представлен в виде числа

.

7. Пользователь А шифрует текст, представленный в виде последовательности чисел , по формуле

и отправляет криптограмму

пользователю В.

8. Пользователь В расшифровывает принятую криптограмму

используя секретный ключ k_B, по формуле

.

В результате будет получена последовательность чисел , которые представляют собой исходное сообщение М. При практической реализации алгоритма RSA необходимо иметь возможность без существенных затрат генерировать большие простые числа, уметь оперативно вычислять значения ключей К_B и k_B.

Пример: Шифрование сообщения CAB. Для простоты вычислений будут использоваться небольшие числа. На практике применяются очень большие числа (длиной 250÷300 десятичных разрядов).

Действия пользователя В:

1. Выбирает Р = 3 и Q = 11.

2. Вычисляет модуль .

3. Вычисляет значение функции Эйлера для N = 33:

.

Выбирает в качестве открытого ключа К_B произвольное число с учетом выполнения условий

т.е. ключ должен быть взаимно простым с (целым числом, которое не имеет общих делителей с – 3, 7, 9 и т.д.). Пусть .

4. Вычисляет значение секретного ключа k_B, используя расширенный алгоритм Евклида при решении сравнения

;

;

Решение дает .

5. Пересылает пользователю А пару чисел (N = 33, К_B = 7).

Действия пользователя А:

6. Представляет шифруемое сообщение как последовательность целых чисел в диапазоне 0...32. Пусть буква А представляется как число 1, буква В – как число 2, буква С – как число 3. Тогда сообщение CAB можно представить как последовательность чисел 312, то есть М₁ = 3, М₂ = 1, М₃ = 2.

7. Шифрует текст, представленный в виде последовательности чисел М₁, М₂ и М₃ используя ключ К_B = 7 и N = 33, по формуле

.

Получает

,

,

.

Отправляет пользователю В криптограмму

С₁, С₂, С₃ = 9, 1, 29.

Действия пользователя В:

8. Расшифровывает принятую криптограмму С₁, С₂, С₃ используя секретный ключ k_B = 3, по формуле

.

Получает

,

,

.

Таким образом, восстановлено исходное сообщение: CAB

Криптоалгоритм RSA всесторонне исследован и признан стойким при достаточной длине ключей. В настоящее время длина ключа 1024 бит считается приемлемым вариантом. Некоторые авторы утверждают, что с ростом мощности процессоров криптоалгоритм RSA потеряет стойкость к атаке полного перебора. Однако увеличение мощности процессоров позволит применить более длинные ключи, что повышает стойкость RSА. Следует отметить, что алгоритм RSА можно применять как для шифрования сообщений, так и для электронной цифровой подписи.

Нетрудно видеть, что в асимметричной криптосистеме RSA количество ис­пользуемых ключей связано с количеством абонентов линейной зависимостью (в системе из N пользователей используются 2 ´ N ключей), а не квадратичной, как в симметричных системах.

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