Принципы и методы криптосистемы с открытым ключом

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

Но сама односторонняя функция бесполезна в применении: ею можно зашифровать сообщение, но расшифровать нельзя.

Поэтому криптография с открытым ключом использует односторонние функции с лазейкой.

Лазейка — это некий секрет (инструкция), который помогает расшифровать. То есть существует такой у, что зная f(x), можно вычислить х.

Научная основа

Начало ассиметричным шрифтам было положено в работе «Новые направления в современной криптографии» Уитфилда Диффи и Мартина

Хеллмана, опубликованной в 1976 году. Находясь под влиянием работы Ральфа Меркле о распространении открытого ключа, они предложили метод получения секретных ключей, используя открытый канал. Этот метод экспоненциального обмена ключей, который стал известен как обмен ключами Диффи-Хеллмана, был первым опубликованным практичным методом для установления разделения секретного ключа между заверенными пользователями канала. В 2002 году Хеллман предложил называть данный алгоритм «Диффи — Хеллмана — Меркле», признавая вклад Меркле в изобретение криптографии с открытым ключом. Эта же схема была разработана Малькольмом Вильямсоном в 1970-х, но держалась в секрете до 1997 года. Метод Мерзсле по распространению открытого ключа был изобретён в 1974 году и опубликован в 1978, его также называют загадкой Меркле.

В 1977 году учёными Рональдом Райвестом, Ади Шамиром и Леонардом Адлеманом из Массачусетского Технологического Института был разработан алгоритм шифрования, основанный на проблеме о разложении на множители. Система была названа по первым буквам их фамилий. Эта же система была

изобретена Клиффордом Коксэм в 1973 году, работавшим в центре правительственной связи (GCHQ). Но эта работа хранилась лишь во внутренних документах центра, поэтому о её существовании было не известно до 1977 года. RSА стал первым алгоритмом, пригодным и для шифрования, и для цифровой подписи.

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

3. Основные принципы построения криптосистем с открытым ключом

1. Начинаем с трудной задачи Р.Она должна решаться сложно в смысле теории: нет алгоритма, с помощью которого можно было бы перебрать все варианты решения задачи Рза полиномиальное время относительно размера задачи.

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

3. «Перетасовываем и взбалтываем» Р₁ , чтобы получить задачу Р", совершенно не похожую на первоначальную. Задача Р", по крайней мере, должна выглядеть как оригинальная труднорешаемая задача Р.

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

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

3.1. Концепция криптосистемы с открытым ключом

Эффективными системами криптографической защиты данных являются асимметричные криптосистемы, называемые также криптосистемами с открытым ключом.

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

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

Обобщенная схема асимметричной криптосистемы с открытым ключом показана на рис. 1.

В этой криптосистеме применяют два различных ключа:

К_в – открытый ключ отправителя А;

k_в – секретный ключ получателя В.

Генератор ключей целесообразно располагать на стороне получателя В (чтобы не пересылать секретный ключ k_в по незащищенному каналу). Значения ключей К_в и k_в зависят от начального состояния генератора ключей.

Раскрытие секретного ключа k_в по известному открытому ключу К_в должно быть вычислительно неразрешимой задачей.

Характерные особенности асимметричных криптосистем:

1. Открытый ключ К_викриптограмма С могут быть отправлены по незащищенным каналам, т.е. противнику известны К_виС.

2. Алгоритмы шифрования и расшифрования

Е_в : М ® С,

D_в : С ® М

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

Защита информации в асимметричной криптосистеме основана на секретности ключа k_в.

Рис.1. Обобщенная схема асимметричной криптосистемы с открытым ключом

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

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

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

С = (М) = Е_в (М). (1)

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

М = (С) = D_в(С) = D_в [Е_в(М)]. (2)

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

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

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

С точки зрения представления данных в компьютере оба ключа являются последовательностями символов, используемыми соответствующими программами для:

· шифрования,

· расшифровки,

· снабжения документа электронной цифровой подписью и проверки этой подписи.

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

Закрытый ключабонент долженсохранять в тайне

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

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

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

Например, когда резидент хочет, чтобы агент выслал ему сообщение, то:

1) Резидент генерирует открытый и секретный ключи.

2) Открытый ключ посылает агенту.

3) Агент шифрует этим открытым ключом сообщение и отправляете его резиденту

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

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

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

Пример такой системы — широко известная криптосистема RSA.

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

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

Формально однонаправленную функцию можно определить следующим образом. Пусть X и Y – некоторые произвольные множества.

Функция

f : X ® Y

является однонаправленной, если для всех xÎX можно легко вычислить функцию

y = f (x), где yÎY.

И в то же время для большинства yÎY достаточно сложно получить значение xÎX, такое, что f (x)=y (при этом полагают, что существует по крайней мере одно такое значение x).

Основным критерием отнесения функции f к классу однонаправленных функций является отсутствие эффективных алгоритмов обратного преобразования: Y ® X.

В качестве примера однонаправленной функции рассмотрим целочисленное умножение.

Прямая задача – вычисление произведения двух очень больших целых чисел P и Q, т.е. нахождение значения

N = P*Q

является относительно несложной задачей для ЭВМ.

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

Следующий характерный пример однонаправленной функции – это модульная экспонента с фиксированными основанием и модулем. Пусть A и N – целые числа, такие, что 1£ А < N.

Определим множество Z_N следующим выражением:

Z_N = {0, 1, 2, ..., N –1}.

Тогда модульная экспонента с основанием А по модулю N представляет собой функцию

f_A,N : Z_N ® Z_N,

f_A,N (x) = A^x (mod N),

где X – целое число, 1£ x £ (N –1).

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

Если y = A^x, то естественно записать x = log_A (у).

Поэтому задачу обращения функции f_A,N(x)называютзадачей нахождения дискретного логарифма или задачей дискретного логарифмирования.

Задача дискретного логарифмирования формулируется следующим образом: