Криптография с открытым ключом

2.11.1. Вычислительно сложные алгоритмы и задачи

Обычно "легко" означает, что проблема может быть решена за полиномиальное время от длины входа. Таким образом, если длина входа имеет n битов, то время вычисления функции пропорционально n**a, где а - фиксированная константа. В этом случае говорят, что алгоритм принадлежит классу полиномиальных алгоритмов Р. Термин "трудно" означает более сложное понятие. В общем случае будем считать, что проблему решить невозможно, если усилия для ее решения больше полиномиального времени от величины входа. Например, если длина входа n битов, и время вычисления функции пропорционально a**n, где а - фиксированная константа, то алгоритм принадлежит к классу экспоненциально сложных алгоритмов и это считается вычислительно невозможной задачей. К сожалению, тяжело определить, проявляет ли конкретный алгоритм такую сложность. Более того, традиционные представления о вычислительной сложности фокусируются на худшем случае или на среднем случае сложности алгоритма. Это неприемлемо для криптографии, где требуется невозможность вычисления функции для всех или почти всех значений входов.

2.11.3. Сведения из теории чисел

  1. Если (а · b) (a · c) mod n, то b c mod n, если а и n взаимнопростые, т.е НОД(a, n) = 1.
  2. Обозначим Zp - все числа, взаимнопростые с p и меньшие p. Если p - простое, то Zp - это все остатки. Обозначим w-1 такое число, что w · w-1 1 mod p.

Тогда w Zp z: w · z 1 mod p

  1. Определим функцию Эйлера следующим образом: Φ(n) - число положительных чисел, меньших n и взаимнопростых с n. Если p - простое, то Φ(р) = p-1.

Если p и q - простые, то Φ(p · q) = (p-1) · (q-1).

  1. Теорема Ферма.

an-1 1 mod n, если n - простое.

  1. Теорема Эйлера.

aΦ(n) 1 mod n для всех взаимнопростых a и n, т.е. НОД(а,n) = 1.

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

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

Общие требования к алгоритмам шифрования с открытым ключом (открытое шифрование).

Закрытый (секретный) ключ будем обозначать KR, открытый ключ - KU.

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

Модель шифрования с открытым ключом приведена на рис.7.1.

Рис.7.1. Модель шифрсистемы с открытым ключом

Диффи и Хеллман сформулировали общие требования, которым должен удовлетворять алгоритм шифрования с открытым ключом:

  1. Вычислительно легко создавать пару (открытый ключ KU , закрытый ключ KR).
  2. Вычислительно легко, имея открытый ключ и незашифрованное сообщение М, создать соответствующий зашифрованное сообщение:
С = ЕKU(М)
  1. Вычислительно легко расшифровать сообщение, используя закрытый ключ:
М = DKR(C) = DKR(EKU(M))
  1. Вычислительно невозможно (сложно), зная открытый ключ KU, определить закрытый ключ KR.
  2. Вычислительно невозможно (сложно), зная открытый ключ KU и зашифрованное сообщение С, восстановить исходное сообщение М.
  3. Вычислительно невозможно (сложно), зная открытый ключ KU, открытое сообщение и зашифрованное сообщение С восстановить секретный ключ KR.

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

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

Y = f(X) – легко

X = f-1(Y) - трудно

Примеры

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

Y = fk(X) – легко для любого X, даже если k неизвестно

X = fk-1(Y) – легко для любого Y, если k известно

Х = fk-1(Y) - трудно, если Y известно, но k неизвестно

Тогда проблема открытого шифрования решается следующим образом.

Открытым ключом зашифрования KU служит сама fk(X) с неизвестным k.

Секретным ключом расшифрования KR служит секретный параметр k.

Зашифрование

С = fk(М)

Расшифрование

М = fk-1(М)

Безопасность системы обеспечивается тем, что никто, кроме законного получателя, не знает секретного параметра k.

Криптостойкость системы обеспечивается вычислительной сложность определения М при известных С и fk(М), но неизвестном k (или установления k).

Таким образом разработка конкретного алгоритма с открытым ключом зависит от открытия соответствующей односторонней функции с лазейкой.

Два главных фактора, влияющих на стойкость асимметричных криптосистем:

- выбор однонаправленной функции с лазейкой;

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

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

Первый из них – это задача факторизации целых чисел и различные её варианты.

Второй – это задача дискретного логарифмирования и производные от неё задачи

Схемой открытого шифрования (или, другими словами, асимметричной схемой шифрования) AE=(K,E,D) называется совокупность трёх алгоритмов:

1) алгоритма генерации ключей K=(KU, KR);

2) алгоритма зашифрования E;

3) алгоритма расшифрования D.

и состоит из следующих шагов:

  1. Генерация пары ключей (KU, KR)

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

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

  1. Зашифрование

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

  1. Расшифрование

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

Если пользователь (конечная система) надежно хранит свой закрытый ключ, никто не сможет восстановить передаваемые сообщения.