ПЗ – 2. Двухключевые системы защиты информации. Математическая модель и особенности построения НКГС

ПЗ – 2.  Двухключевые системы защиты информации

1.         Математическая модель и особенности построения НКГС

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

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

Структурная схема асимметричной КГС представлены на рис. 1.

Особенности асимметричных КГС:

1) К_О  и Е передаются по открытому каналу (известны криптоаналитику противника);

2) алгоритмы зашифрования (Ш) и расшифрования (РШ)

 и

являются открытыми.

3) стойкость АКГС определяется секретностью ключа К_С.

Требования У. Диффи и М. Хеллмана к АКГС.

1. Вычисление пары ключей (К_О, К_С) получателем Б на основе неких начальных условий просто.

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

.

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

.

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

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

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

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

1. Целочисленное умножение  факторизация больших чисел.

  – просто

 – сложно.

  и    для разложения числа  операций.

2. Модульная экспонента – дискретный логарифм.

Пусть А и N – целые и определенно множество  Z_N = {0, 1, 2, …, N-1}.

Модульная экспонента с основанием А по mod N есть

и   , где  –  х целое, такое что 1 £ х £ N-1.

Значение  легко вычислимо, а задача обращения функции     –  задача нахождения дискретного логарифма. Эта задача формулируется так: для известных А, N и y найти целое x, такое что

.

При целых А и  решение задачи потребует 10²⁶ операций, что на 10³ больше, чем при факторизации чисел.

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

Однонаправленная функция с потайным ходом (лазейкой).

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

Пример: модульная экспонента с фиксированной модулем и показателем степени. Переменное основание модульной экспоненты используется для указания значения М или Е.

Наиболее известными КГС с открытым ключом являются:

- рюкзачная криптосистема (khapsack crypto system);

- криптосистема RSA;

- криптосистема Эль-Гамаля (EGCS – El Gamal);

- криптосистема, основанная на свойствах эллиптических кривых – ECCS (Elliptik Curre cryptosystem).

2.  Алгоритм RSA

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

Алгоритм был предложен в 1978 году Р. Райвестом (R. Rivest), А. Шамиром (А. Shamir) и А. Адлеманом (A. Adleman), являющихся сотрудниками Массачусетского технологического института, США.

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

В криптосистеме на основе алгоритма RSA открытый ключ К_О, секретный ключ К_С, открытое сообщение М и криптограмма Е принадлежат множеству целых чисел, образующих (поле Галуа GFCN)

Z_N = {0, 1, 2, …, N-1}, где N – модуль, причем

, где P и Q – большие простые числа, которые выбираются случайно, хранятся в тайне и относительно близки друг к другу.

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

1. ,  ,

2. , где   – функция Эйлера, указывающая количество положительных целых чисел в интервале от 1 до N, которые взаимно просты с N, т.е. НОД (а, N)=1, аÎ(1, 2, …, N-1). Одновременно открытый ключ К_О и  должны быть взаимно просты.

Далее вычисляется секретный ключ К_С

или  .

Для этого получатель применяет расширенный алгоритм Евклида, так как ему известна пара простых чисел (P, Q), что позволяет легко вычислить .