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

Страницы работы

8 страниц (Word-файл)

Содержание работы

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

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

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

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

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

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

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

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

 и

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

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

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

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

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

.

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

.

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

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

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

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

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

  – просто

 – сложно.

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

2.  Алгоритм RSA

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

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

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

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

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

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

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

1. ,

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

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

или  .

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

Похожие материалы

Информация о работе

Тип:
Конспекты лекций
Размер файла:
244 Kb
Скачали:
0