Одна из проблем, которая осталась неразрешенной в традиционной криптографии, -распространение секретных ключей

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

Поэтому американские математики Диффи, Хеллман и Меркле разработали в 1976 г. концепцию открытого ключа и асимметричного шифрования.

Шифры с открытым ключом

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

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

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

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

• «что знают двое, знает свинья» - наличие единственной копии ключа уменьшает возможности его утраты и позволяет установить чёткую персональную ответственность за сохранение тайны;

• наличие двух ключей позволяет использовать данную шифровальную систему в двух режимах -секретная связь и цифровая подпись.

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

НАУЧНАЯ ОСНОВА

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Е_в: М ® С,