Криптосистемы открытого шифрования

Введение

 

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

В 1977 году учёными Рональдом  Ривестом (Ronald Linn Rivest), Ади Шамиром (Adi Shamir) и Леонардом Адлеманом (Leonard Adleman) из Массачусетского Технологического Института (MIT) был разработан алгоритм шифрования, основанный на проблеме о  разложении на множители. Система была названа по первым буквам их фамилий (RSA — Rivest, Shamir, Adleman). Эта же система  была изобретена Клиффордом Коксом (Clifford Cocks) в 1973 году, работавшим в центре правительственной  связи (GCHQ). Но эта работа хранилась  лишь во внутренних документах центра, поэтому о её существовании было не известно до 1977 года. RSA стал первым алгоритмом, пригодным и для шифрования, и для цифровой подписи.

 

 

 

 

Криптографическая система

 

Криптографическая система - семейство преобразований шифра  и совокупность ключей (т.е алгоритм + ключи). Само по себе описание алгоритма  не является криптосистемой. Только дополненное  схемами распределения и управления ключами оно становится системой.

Современные криптосистемы  классифицируют следующим образом:

 

 

 

Асимметричные криптосистемы (системы открытого шифрования - о.ш., с открытым ключом и т.д. - public key systems) - смысл данных криптосистем состоит в том, что для зашифрования и расшифрования используются разные преобразования.

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

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

 

 

 

 

 

 

 

 

     

 

 

 

 

Рис. 1 Простейшая модель криптосистемы  с открытым ключом

 

Таким образом, пропадает  проблема передачи секретного ключа (как  у симметричных систем). Однако, несмотря на все свои преимущества, эти криптосистемы  достаточно трудоемки и медлительны. Стойкость асимметричных криптосистем базируется, в основном,  на алгоритмической  трудности решить за приемлемое время какую-либо задачу. Если злоумышленнику удастся построить такой алгоритм, то дискредитирована будет вся система и все сообщения, зашифрованные с помощью этой системы. В этом состоит главная опасность асимметричных криптосистем в отличие от симметричных.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Идея криптосистемы  с открытым ключом

 

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

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

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

Поэтому чтобы гарантировать надежную защиту информации, к системам с открытым ключом (СОК) предъявляются два важных и очевидных требования:

1. Преобразование  исходного текста должно быть  необратимым и исключать его  восстановление на основе открытого  ключа.

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

Алгоритмы шифрования с открытым ключом получили широкое распространение в современных информационных системах. Так, алгоритм RSA стал мировым стандартом.

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

1. Разложение больших чисел на простые множители.
2. Вычисление логарифма в конечном поле.
3. Вычисление корней алгебраических уравнений.

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

1. Как самостоятельные средства защиты передаваемых и хранимых данных.

2. Как средства для распределения ключей.

3. Средства аутентификации пользователей.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Схема шифрования с открытым ключом

 

Пусть K — пространство ключей, а e и d — ключи шифрования и расшифрования соответственно. Ee — функция шифрования для произвольного ключа eK, такая что:

 

Ee(m) = c

 

Здесь cC, где C — пространство шифротекстов, а mM, где M — пространство сообщений.

Dd — функция расшифрования, с помощью которой можно найти исходное сообщение m, зная шифротекст c :

 

Dd(c) = m

 

{Ee: eK} — набор шифрования, а {Dd: dK} — соответствующий набор для расшифрования. Каждая пара (E,D) имеет свойство: зная Ee, невозможно решить уравнение Ee(m) = c, то есть для данного произвольного шифротекста cC, невозможно найти сообщение mM. Это значит, что по данному e невозможно определить соответствующий ключ расшифрования d. Ee является односторонней функцией, а d — лазейкой.

Ниже показана схема передачи информации лицом А лицу В. Они  могут быть как физическими лицами, так и организациями и так  далее. Но для более лёгкого восприятия принято участников передачи отождествлять  с людьми, чаще всего именуемыми Алиса и Боб. Участника, который  стремится перехватить и расшифровать сообщения Алисы и Боба, чаще всего  называют Евой.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Боб выбирает пару (e,d) и шлёт ключ шифрования e (открытый ключ) Алисе по открытому каналу, а ключ расшифрования d (закрытый ключ) защищён и секретен (он не должен передаваться по открытому каналу).
2. Чтобы послать сообщение m Бобу, Алиса применяет функцию шифрования, определённую открытым ключом e: Ee(m) = c, c — полученный шифротекст.
3. Боб расшифровывает шифротекст c, применяя обратное преобразование Dd, однозначно определённое значением d.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Криптоанализ  алгоритмов с открытым ключом

 

Казалось бы, что криптосистема  с открытым ключом — идеальная  система, не требующая безопасного  канала для передачи ключа шифрования. Это подразумевало бы, что два  легальных пользователя могли бы общаться по открытому каналу, не встречаясь, чтобы обменяться ключами. К сожалению, это не так. Рисунок иллюстрирует, как Ева, выполняющая роль активного  перехватчика, может захватить систему (расшифровать сообщение, предназначенное  Бобу) без взламывания системы  шифрования.

 

 

 

 

 

 

 

 

 

 

 

В этой модели Ева перехватывает  открытый ключ e, посланный Бобом Алисе. Затем создает пару ключей e' и d', «маскируется» под Боба, посылая Алисе открытый ключ e', который, как думает Алиса, открытый ключ, посланный ей Бобом. Ева перехватывает зашифрованные сообщения от Алисы к Бобу, расшифровывает их с помощью секретного ключа d', заново зашифровывает открытым ключом e Боба и отправляет сообщение Бобу. Таким образом, никто из участников не догадывается, что есть третье лицо, которое может как просто перехватить сообщение m, так и подменить его на ложное сообщение m'. Это подчеркивает необходимость аутентификации открытых ключей.

Еще одна форма атаки —  вычисление закрытого ключа, зная открытый (рисунок ниже). Криптоаналитик знает  алгоритм шифрования Ee, анализируя его, пытается найти Dd. Этот процесс упрощается, если криптоаналитик перехватил несколько криптотекстов с, посланных лицом A лицу B.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Криптосистема открытого  шифрования RSA

 

Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исследователями - математиками Рональдом Ривестом (R.Rivest), Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах. Алгоритм RSA основан на свойствах простых чисел (причем очень больших). Простыми называются такие числа, которые не имеют делителей, кроме самих себя и единицы. А взаимно простыми называются числа, не имеющие общих делителей, кроме 1.

Первым этапом любого асимметричного алгоритма является создание пары ключей: открытого и закрытого и распространение  открытого ключа "по всему миру".

Для начала выберем два очень  больших простых числа (большие  исходные числа нужны для построения больших криптостойких ключей). Определим  параметр n как результат перемножения двух простых чисел р и q. Выберем большое случайное число и назовем его d, причем оно должно быть взаимно простым с результатом умножения (р - 1)·(q - 1). Отыщем такое число e, для которого верно соотношение

(e·d) mod ((р -1)·(q -1)) = 1

Открытым ключом является пара чисел e и n, а закрытым - d и n.

Отправитель разбивает свое сообщение  на блоки, равные k = [log₂(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.

При шифровании исходный текст рассматривается  как числовой ряд, и над каждым его числом мы совершаем операцию

C(i)= (M(i)^e) mod n.

Их  можно спокойно передавать по открытому  каналу, поскольку операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название «логарифмирование в конечном поле» и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа d и n, то по C(i) прочесть исходные сообщения M(i) он не может никак, кроме как полным перебором.

В результате получается последовательность C(i), которая и составит криптотекст.

Дешифрование информации происходит по формуле 

 

M(i) = (C(i)^d ) mod n.

 

Как видите, расшифровка предполагает знание секретного ключа.

Как видим, результат совпал.

Пример 1. Для иллюстрации своего метода Ривест, Шамир и Адлеман записали английскую фразу:

The magic words are squeamish ossifrage.

Сначала они стандартным  образом  (a=01, b=02, …, z=26, пробел=00) записали её в виде целого числа

x=2008050013010709030023151804190001180500191721051309190800151919090618010705  (76 цифр), а затем зашифровали при помощи отображения

e

y= f(x)=x                (mod N )

при

e=9007

и

N=1438162575788886766932577997614661200218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541   (127 цифр).

В результате получили зашифрованный  текст:

f(x)=96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154

(128 цифр).

Текст f(x) и числа N, e были опубликованы, причём дополнительно сообщалось, что N=pq, где p и q – простые числа, записываемые соответственно 64 и 65 десятичными знаками. Тому, кто дешифрует сообщение F(x) была обещана награда в $100.

Эта история завершилась  спустя 17 лет в 1994 г., когда D. Atkins, M. Graff, A.K. Lenstra и P.S. Leyand  сообщили о дешифровании фразы f(x).

Числа p и q  при этом оказались равными:

 

p=3490529510847650949147849619903898133417764638493387843990820577 (64 цифры)

q=32769132993266709549961988190834461413177642967992942539798288533 (65 цифр)

 

В работе, возглавлявшейся  четырьмя названными авторами проекта, после теоретической подготовки на заключительном этапе длительностью  в 220 дней принимали участие около 600 человек и примерно 1600 компьютеров, объединённых сетью Internet. Премия в $100 была передана в Free Sofware Foundation.