Недостатки симметричных криптосистем и принципы асимметричного шифрования

Наряду с вычислительной простотой и интуитивной понятностью симметричных криптосистем, они обладают рядом серьезных недостатков. К основным недостаткам симметричных криптосистем относят проблему распространения симметричных ключей и проблему их хранения [13].

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

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

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

Ключи в асимметричных криптосистемах всегда генерируются парами и состоят из двух частей – открытого ключа (ОК) и секретного ключа (СК).

Ключевая пара
СК	ОК

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

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

Функциональная схема взаимодействия участников асимметричного криптографического обмена представлена на рис. 5.11.

В данной схеме участвует получатель секретного сообщения А и отправитель секретного сообщения B. ОКА – открытый ключ пользователя А, СКА – секретный ключ пользователя А. Ключевая пара (ОКА, СКА) сгенерирована на стороне получателя А, после чего открытый ключ данной пары ОКА отправляется по открытому каналу пользователю B. Предполагается, что злоумышленнику также известен открытый ключ ОКА.

Рис. 5.11. Функциональная схема асимметричной криптосистемы

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

Рис 5.11 отражает только одностороннюю схему взаимодействия в рамках асимметричных криптосистем. Для реализации двустороннего обмена необходима реализация следующих шагов:

1. Пользователь A генерирует ключевую пару (ОК_А,СК_А).

2. Пользователь B генерирует ключевую пару (ОК_B,СК_B).

3. Пользователи A и B должны обменяться своими открытыми ключами. Пользователь А передает свой открытый ключ ОК_А пользователю B, пользователь B передает свой открытый ключ ОК_B пользователю A.

4. Пользователь А шифрует информацию для пользователя B на ключе ОК_B, пользователь B шифрует информацию для пользователя A на ключе ОК_A.

5. Пользователь А дешифрует информацию, присланную ему от пользователя B, на ключе СК_А, пользователь B дешифрует информацию, присланную ему от пользователя A, на ключе СК_B.

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

Рис. 5.12. Схема распределения ОК с использованием центра распределения ключей

В настоящее время все более распространенным подходом к вопросу распределения ключей приобретает подход, основанный на реализации инфраструктуры открытых ключей PKI и удостоверяющих центров (УЦ).

У. Диффи и М. Хеллман сформулировали требования, выполнение которых обеспечивает безопасность асимметричной криптосистемы [29]:

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

2. Отправитель, зная открытый ключ получателя, может легко получить шифротекст.

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

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

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

 

Однонаправленные функции

Концепция асимметричных криптосистем основана на использовании однонаправленных функций.

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

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

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

Целочисленное умножение

Вычисление произведения двух очень больших целых чисел P и Q (N = P * Q) является несложной задачей для ЭВМ. Однако, решение обратной задачи, заключающейся в нахождении делителей P и Q большого числа N (в особенности, когда P и Q – большие простые числа), является практически неразрешимой задачей при больших N. Если N»2⁶⁶⁴ и P» Q, то задача факторизации не разрешима за приемлемое время на современных ЭВМ. Поэтому целочисленное умножение является однонаправленной функцией.

Модульная экспонента

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

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

 

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

Алгоритм RSA был предложен в 1978 году Р.Райвестом, А. Шамиром, А. Адлеманом и был назван по первым буквам фамилий его авторов. Данный алгоритм стал первым алгоритмом шифрования с открытым ключом. Надежность данного алгоритма основывается на трудности факторизации больших чисел и вычисления дискретных логарифмов [13,8].

В криптосистеме RSA открытый ключ ОК, секретный ключ СК, исходное сообщение М и шифротекст С являются целыми числами от 0 до N -1, где N – модуль.

Пусть пользователь А является получателем сообщения, которое ему должен переслать отправитель B.

Пользователь A должен вначале сгенерировать ключевую пару RSA. Это он делает следующим образом.

Алгоритм формирование ключевой пары пользователем А

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

2. Вычисляем модуль . Согласно формуле (4.1) , где - функция Эйлера.

3. Открытый ключ ОК_А выбирается случайно таким образом, чтобы выполнялись следующие условия:

1<ОКA£ , НОД(ОКА, )=1

(5.11)

4. Секретный ключ СК_A находится по сформированному открытому ключу так, что

СКА×ОКАº1 (mod ) или СКА=ОКА^-1 (mod (P-1) × (Q-1))

(5.12)

Пользователь A может легко найти СК_А, используя расширенный алгоритм Евклида, зная числа P и Q, а значит и .

Любой другой пользователь не может зная открытый ключ ОК_А вычислить СК_А, так как ему не известны числа P и Q. Для их нахождения ему потребуется факторизовать известное ему число N, что является вычислительно сложной задачей.

Шифрование и дешифрование сообщений в криптосистеме RSA

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

(5.13)

Обращение данной функции, то есть определение значения M по известным значениям С, ОК_А, N практически не осуществимо при больших N ().

Однако, знание секретного ключа СК_А позволяет обратить данную функцию, то есть решить задачу дешифровки криптограммы C. Для дешифровки криптограммы С необходимо возвести ее в степень секретного ключа пользователя А по модулю N. Таким образом, дешифровка сообщения выполняется в соответствие с формулой (5.14).

(5.14)

Действительно,

В теории чисел известна теорема Эйлера, утверждающая, что если НОД(x, N)=1, то .

Согласно 5.12, СК_А×ОК_Аº1 (mod ), то есть СК_А×ОК_А=k× +1. Таким образом,

Таким образом, показано, что .

Получатель А, который создает ключевую пару (ОК_А,СК_А) защищает два параметра: 1) секретный ключ СК_А; 2) пару чисел P и Q. Рассекречивание данных чисел приводит к тому, что злоумышленник сможет вычислить , а значит и вычислить секретный ключ СК_А согласно (5.12).

Открытыми в криптосистеме RSA являются только значения ОК_А и N.

В настоящее время разработчики криптоалгоритмов с открытым ключом на базе RSA предлагают применять в качестве чисел P,Q,N – числа длиной не менее 200-300 десятичных разрядов.

Пример 5.11

Зашифруем сообщение DAC по алгоритму RSA. Для простоты вычислений будем оперировать с небольшими числами P и Q.

Действия получателя А

1. Выберем P = 5 и Q = 13

2. Модуль

3.

4. В качестве ОК_А необходимо выбрать значение, удовлетворяющее условиям , . Пусть ОК_А = 5.

5. Необходимо найти СК_А, такой что . Это СК_А =29. Действительно, .

6. Отправляем пользователю B пару чисел (N= 65, ОК_А =5)

Действия отправителя B

1. Представим отправляемое сообщение в виде последовательности целых чисел от 0 до 64. Присвоим букве А номер 1, букве B – 2, С – 3, D – 4. Тогда открытый текст DAC запишется в виде последовательности чисел 413, то есть M₁ =4, M₂ =1, M₃ =3.

2. Сформируем шифротекст по формуле 5.13:

,

,

.

3. Пользователь B отправляет A криптограмму C₁, C₂, C₃ =49, 1, 48.

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

1. Раскрываем шифротекст по формуле 5.14:

,

,

.

Таким образом, восстановлено исходное сообщение M₁ =4=D, M₂ =1=A, M₃ =3=C. Исходное сообщение – DAC.