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

Введение

 

Начало асимметричным  шифрам было положено в работе «Новые направления в современной криптографии»  Уитфилда Диффи и Мартина Хеллмана, опубликованной в 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. Как средства для распределения ключей.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

Пусть 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 = [log2(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.

Пример 2. Установим р=3, q=7. Тогда n=р·q=21.

Выбираем d как 5. Из формулы (e·5) mod 12=1 вычисляем e=17. Открытый ключ 17, 21, секретный - 5, 21. Зашифруем последовательность «2345»:

C(2)= 217 mod 21 =11

C(3)= 317 mod 21= 12

C(4)= 417 mod 21= 16

C(5)= 517 mod 21= 17

Криптотекст - 11 12 16 17.

Проверим расшифровкой: 

M(2)= 115 mod 21= 2

M(3)= 125 mod 21= 3

M(4)= 165 mod 21= 4

M(5)= 175 mod 21= 5

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

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

Компания RSA регулярно проводит конкурсы на взлом собственных (и не только собственных) шифров. Предыдущие конкурсы выиграла организация Distributed.net, являющаяся Интернет - сообществом добровольцев.

Участники Distributed.net загружают к  себе на ПК небольшую программу - клиент, которая подсоединяется к центральному серверу и получает кусочек данных для вычислений. Затем все данные загружаются на центральный сервер, и клиент получает следующий блок исходной информации. И так происходит до тех пор, пока все комбинации не будут перебраны. Пользователи, участники системы, объединяются в команды, а на сайте ведется рейтинг как команд, так и стран.

Например, участвующей в конкурсе по взлому RC5-64 (блочный шифр компании RSA, использующий ключ длиной 64 бита) организации Distributed.net удалось осуществить взлом  через пять лет (1757 дней) работы. За это  время в проекте участвовали 327 856 пользователей и было перебрано 15 268 315 356 922 380 288 вариантов ключа. Выяснилось, что была (не без юмора) зашифрована  фраза «some things are better left unread» («некоторые вещи лучше оставлять непрочтенными»).

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Криптосистема Эль-Гамаля

 

Криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема была предложена Тахером Эль-Гамалем в 1984 году. Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию.

Генерация ключей

Генерируется случайное  простое число  P длины  n битов.

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


Выбирается случайное целое число  x такое, что


Вычисляется

Открытым ключом является тройка              , закрытым ключом — число x.


Шифрование

Сообщение  M шифруется следующим образом:

  1. Выбирается сессионный ключ — случайное целое число k такое, что
  2. Вычисляются числа                             и
  3. Пара чисел            является шифротекстом.

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

Зная закрытый ключ x, исходное сообщение можно вычислить из шифротекста (a, b) по формуле:

При этом нетрудно проверить, что                                                  и поэтому 


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


.


 

 

 

 

 

 

 

 

 

 

 

Рис. 2 Схема шифрования Эль-Гамаля

 

Пример 1.

Шифрование 

  1. Допустим что нужно зашифровать сообщение M = 5.
  2. Произведем генерацию ключей:
  • пусть                           . Выберем             - случайное целое число  ;

такое, что ;          

  • вычислим ;
  • итак, открытым является тройка                             , а закрытым ключом является число ;
  1. Выбираем случайное целое число k такое, что 1 < k < (p−1).                   Пусть k = 9.

Вычисляем число  .

Вычисляем число .

Полученная пара                     является шифротекстом.


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

  1. Необходимо получить сообщение   M = 5 по известному шифротексту и закрытому ключу ;
  2. Вычисляем M по формуле:
  3. Получили исходное сообщение .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Криптосистемы на основе эллиптических уравнений

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

 

y2 = x3 + ax + b,

 

Для точек на кривой довольно легко вводится операция сложения, которая играет ту же роль, что и операция умножения  в криптосистемах RSA и Эль-Гамаля.

В реальных криптосистемах на базе эллиптических  уравнений используется уравнение

 

y2 = x3 + ax + b mod p,

 

где р - простое.

Проблема  дискретного логарифма на эллиптической  кривой состоит в следующем: дана точка G на эллиптической кривой порядка r (количество точек на кривой) и другая точка Y на этой же кривой. Нужно найти единственную точку x такую, что Y = xG.

 

 

 

 

 

 

 

Библиографический список

 

  1. Аветисян, Д.О. Проблемы информационного поиска: Эффективность, автоматическое кодирование, поисковые стратегии / Д. О. Аветисян. - М.: Финансы и статистика, 1981. - 208 с.
  2. Аршинов, М.Н. Коды и математика / М.Н. Аршинов.- М.: Наука, 1983. - 231 с.
  3. Герасименко, В.А. Защита информации в автоматизированных системах обработки данных / В.А. Герасименко.- М.: Энергоатомиздат, 1994.
  4. Расторгуев, С.П. Программные методы защиты информации в компьютерах и сетях / С. П. Расторгуев. -М.: Яхтсмен. - 1993. - 188 с.
  5. Спесивцев, А.В. Защита информации в персональных ЭВМ / А.В. Спесивцев. - М.: Радио и связь, МП "ВЕСТА", 1978.
  6. Шеннон, К. Работы по теории информации и кибернетике / К. Шеннон. - М.: Иностранная литература, 1963.

 


Криптосистемы открытого шифрования 📙 Контрольная → 🆔 81593

Криптосистемы открытого шифрования 📙 Контрольная → 🆔 81593

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