Криптосистеми з відкритим ключем.
Эффективными системами криптографической защиты данных являются ассиметричные криптосистемы, называемые также криптосистемами с открытым ключом. В таких системах для зашифрования данных используется один ключ, для расшифрования – другой ключ (отсюда и название – асимметричный). Первый ключ является открытым и может быть опубликован для использования всеми пользователями системы, которые зашифровывают данные. Расшифрование данных с помощью открытого ключа невозможно.
Для расшифрования данных получатель зашифрованной информации использует второй ключ, который является секретным. Разумеется, ключ расшифрования не может быть определен из ключа зашифрования.
Обобщенная схема ассиметричной криптосистемы с открытым ключом показана на рис. В этой криптосистеме применяют два различных ключа: Ко – открытый ключ отправителя А, Кс – секретный ключ получателя В. Генератор ключей целесообразно располагать на стороне получателя В (чтобы не пересылать секретный ключ Кс по незащищенному каналу). Значения ключей Ко и Кс зависят от начального состояния генератора ключей.
Раскрытие секретного ключа Кс по известному открытому ключу Ко должно быть вычислительно неразрешимой задачей.
Характерные особенности асимметричных криптосистем:
- Открытый ключ Ко и криптосистема С могут быть отправлены по незащищенным каналам, т.е. противнику известны Ко и С.
- Алгоритмы шифрования и расшифрования являются открытыми.
Е:МС D:СМ.
Защита информации в асимметричной криптосистеме основана на секретности ключа Кс.
У. Диффи и М. Хеллман сформулировали требования, выполнение которых обеспечивает безопасность асимметричной криптосистемы:
- Вычисление пары ключей (Ко, Кс) получателем В на основе начального условия должно быть простым;
- Отправитель А, зная открытый ключ Ко и сообщение М, может легко вычислить криптограмму С=ЕКо(М)=Е(М)
- Получатель В, используя секретный ключ Кс и криптограмму С, может легко восстановить исходное сообщение М=DКс(С)=D(С)=D[E(М)]
- Противник, зная открытый ключ Ко, при попытке вычислить секретный ключ Кс наталкивается на непреодолимую вычислительную проблему.
- Противник, зная пару (Ко, С), при попытке вычислить исходное сообщение М наталкивается на непреодолимую вычислительную проблему.
Однонаправленные функции.
Концепция асимметричных криптографических систем с открытым ключом основана на применении однонаправленных функций. Неформально однонаправленную функцию можно определить следующим образом.
Пусть X и Y – некоторые произвольные множества. Функция f:XY является однонаправленной, если:
- для всех xX можно легко вычислить функцию y=f(x), где yY;
- для большинства yY достаточно сложно получить значение xX, такое, что f(x)=y (при этом полагают, что существует, по крайней мере, одно такое значение х).
Основным критерием отнесения функции f к классу однонаправленных функций является отсутствие эффективных алгоритмов обратного преобразования YX.
Пример 1. Разложение на множители большого целого числа, т.е. нахождение делителей P и Q большого целого числа N=P*Q. По современным оценкам теории чисел при целом N≈2664 и P≈Q для разложения числа N потребуется около 1023 операций, т.е. задача практически неразрешима на современных ЭВМ.
Пример 2. Модульная экспонента с фиксированными основанием и модулем. Пусть A и N – целые числа, такие, что 1≤А<N. Определим множество ZN: ZN={0,1,2,…,N-1}. Тогда модульная экспонента с основанием А по модулю N представляет собой функцию fА,N=Ax(mod N), где X – целое число, 1≤x≤N-1. Существуют эффективные алгоритмы, позволяющие достаточно быстро вычислить значения функции fА,N(x).
Если y=Ax, то естественно записать x=logA(y). Поэтому задачу обращения функции fА,N(x) называют задачей нахождения дискретного логарифма или задачей дискретного логарифмирования. Алгоритм вычисления дискретного логарифма за приемлемое время пока не найден. Поэтому модульная экспонента считается однонаправленной функцией. По современным оценкам теории чисел при целых числах A≈2664 и N≈2664 решение задачи дискретного логарифмирования потребует около 1026 операций, т.е. в 1000 раз труднее, чем при разложении на множители.
Криптосистема шифрования данных RSA.
Алгоритм RSA предложили в 1978 г. Р. Райвест (Rivest), А. Шамир (Shamir), А. Адлеман (Adleman). RSA стал первым полноценным алгоритмом с открытым ключом, который может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи.
Надежность алгоритма основывается на трудности факторизации больших чисел и трудности вычисления дискретных логарифмов.
Процедуры шифрования и дешифрования в криптосистеме RSA.
Предположим, что пользователь А (отправитель) хочет передать пользователю В (получателю) сообщение в зашифрованном виде. Криптосистему RSA должен сформировать получатель сообщения (чтобы не пересылать секретный ключ Кс по незащищенному каналу).
Пользователь В (подготовка для шифрования):
1. Выбирает два произвольных больших простых числа P и Q.
2. Вычисляет значение модуля N=P*Q.
3. Вычисляет функцию Эйлера φ(N)=(P-1)(Q-1).
4. Выбирает случайным образом значение открытого ключа Ко с учетом выполнения условий: 1<�Ко≤φ(N), НОД(Ко,φ(N))=1.
5. Вычисляет значение секретного ключа Кс, используя расширенный алгоритм Евклида при решении сравнения Кс=Ко-1(mod φ(N)).
6. Пересылает пользователю А пару чисел (N, Ко) по незащищенному каналу.
Пользователь А (шифрование):
7. Разбивает исходное открытое сообщение М на блоки, каждый из которых может быть представлен в виде числа Mi=0, 1, 2, …, N-1
8. Шифрует текст, представленный в виде последовательности Mi по формуле Ci=MiКо(mod N) и отправляет криптограмму С1, С2, С3, …, Сi, …
Пользователь B (дешифрация):
9. Расшифровывает принятую криптограмму, использую секретный ключ Кс, по формуле Mi=CiКс(mod N).
Роль φ(N) в теореме Эйлера:
С=MКо(mod N) и М=DКс(С)=D(С)=D[E(М)]=CiКс(mod N), следовательно (MКо)Кс=М(mod N)= MКоКс.
Если НОД(x,N)=1, то
xφ(N)1(mod N) или xn*φ(N)+1x(mod N), сопоставляя выражения получим:
Ко*Кс=n*φ(N)+1 или, что то же самое Ко*Кс=1(mod φ(N)).
Чтобы алгоритм RSA имел практическую ценность, необходимо иметь возможность без существенных затрат генерировать большие простые числа, уметь оперативно вычислять значения ключей Ко и Кс.
|