Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Статьи / asymmetr.doc
Скачиваний:
51
Добавлен:
01.05.2014
Размер:
100.86 Кб
Скачать

4. Асимметричные криптографические системы

4.1 Алгоритм RSA (R.L Rivest, A.Shamir, L.Alderman)

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

4.3 Криптографические системы на основе эллиптических алгоритмов

4.1 Алгоритм RSA (R.L Rivest, A.Shamir, L.Alderman)

Не­смот­ря на до­воль­но боль­шое чис­ло раз­лич­ных асимметричных криптографических систем, наиболее популярна - криптосистема RSA, разработанная в 1977 году и по­лу­чив­шая на­зва­ние в честь ее соз­да­те­лей: Рона Ри­ве­ста, Ади Ша­ми­ра и Леонарда Эй­дель­ма­на.

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

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

В настоящее время алгоритм RSA используется во многих стандартах, среди которых SSL, S-HHTP, S-MIME, S/WAN, STT и PCT.

Согласно известной из теории чисел теоремы Эйлера для любых взаимно простых чисел M и n , где M< n , выполняется соотношение

Mj(n) = 1 (mod n).

В качестве числа M будем брать исходное сообщение, которое необходимо подписать или зашифровать. Условие взаимной простоты чисел M и n обеспечим тем, что будем выбирать число n , равное произведению двух больших простых множителей. В этом случае вероятность того, что случайное сообщение не будет взаимно простым с модулем, является пренебрежимо малым. В качестве одностороннего преобразования будем использовать возведение в степень по модулю простого числа. При некотором значении этой степени e будем иметь функцию шифрования E , которая преобразует исходное сообщение M в криптограмму C = D(M) = Me mod n. Параметр e будем полагать общедоступным (открытым, публичным). По известному значению S при известных n и e вычислительно сложно найти M.

В качестве потайного хода, соответствующей односторонней функции шифрования Me mod n , будем использовать также возведение в степень, но с другим значением степени. Новое значение степени d необходимо выбрать таким, чтобы функция дешифрования D(C) = Cd mod n была обратной по отношению к E(M) = Me (mod n), т.е. должно выполняться условие

M = D[E(M)] = (Me)d = Med (mod n).

Из этого соотношения следует: ed = 1 (mod j(n)). Таким образом, две процедуры возведения в степень по модулю n будут взаимно обратными, если произведение степеней равно единице по модулю функции Эйлера от числа n. Параметр d является ключом к потайному входу, поэтому он является секретным. Теперь задача состоит в выборе необходимых значений степеней e и d. Очевидно, что первоначально необходимо установить значение функции Эйлера от модуля n. Легко заметить, что для любого простого числа p имеем j(p) = p-1. Поскольку мы выбрали n = pq, где оба множителя являются простыми числами, то, используя свойство мультипликативности функции Эйлера, получаем:

j(n) = j(pq) = j(p)j(q) = (p-1)(q-1).

Еще Евклиду было известно, что если целые числа e и m удовлетворяют условиям 0 < e < m и НОД(m, e) = 1, то существует единственное d , удовлетворяющее условиям 0 < d < m и de = 1 (mod m), и кроме того d может быть вычислено с помощью расширенного алгоритма Евклида.

Переходим к следующей схеме функционирования криптосистемы RSA.

  1. Каждый пользователь выбирает два больших, не равных между собой, простых числа p и q, находит их произведение n = pq и вычисляет значение j(n) = (p-1)(q-1). (Одно из требований к выбору p и q заключается в том, что по крайней мере одно из чисел p-1 или q-1 должно иметь один большой простой множитель. Размер модуля n должен быть не менее 512 бит. Для ответственных применений системы RSA рекомендуемая длина модуля составляет 1024 бит.)

  2. Затем выбирается целое число e такое, что e < j( n) и НОД(e, j( n)) = 1 и вычисляется d, удовлетворяющее условию

ed = 1 (mod j( n)).

  1. Секретным ключом является тройка чисел p, q, d, которая держится в секрете. (На самом деле хранить в секрете достаточно только число d, поскольку простые числа p и q нужны только на этапе формирования модуля n и вычисления d. После этого числа p и q могут быть уничтожены.)

  2. Пара чисел n, e является открытым ключом, который предоставляется всем абонентам криптосистемы RSA.

  3. Процедура подписывания сообщения M – это возведение числа M в степень d по mod n:

S = Md (mod n).

Число S есть цифровая подпись, которую может выработать только владелец секретного ключа.

  1. Процедура проверки подписи S , соответствующей сообщению M, - это возведение числа S в целую степень e по mod n:

M¢ = Se (mod n).

Если M¢ = M , то сообщение M признается подписанным пользователем, который предоставил ранее открытый ключ e. Видно, что

Se = (Md)e = Mde = Mj(n)Q+1 = Mj(n)QM= (Mj(n))QM = 1QM (mod n),

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

Стойкость криптосистемы RSA основана на сложности разложения модуля на два больших простых множителя. До настоящего времени не найдены практически реализуемые общие способы решения этой задачи при длине модуля 512 бит и более. Однако, для частных видов простых чисел p и q сложность этой задачи резко понижается, поэтому в криптосистеме RSA необходимо выполнить ряд специальных тестов при генерации секретного ключа. Другой особенностью системы RSA является ее мультипликативность:

E(M1,M2) = E(M1) E(M2) (mod n),

что позволяет нарушителю на основе двух подписанных сообщений сформировать подпись третьего сообщения, которое равно M3 = M1M2 (mod n). Поскольку M3 в подавляющем большинстве случаев не будет представлять собой какого-либо осмысленного текста, то наличие этой особенности не является недостатком. В системе RSA необходимо учитывать также следующую возможность. Выбрав произвольное значение S, можно вычислить значение M¢ = Se , т.е. произвольное значение можно представить как подпись некоторого сообщения. В таких случаях используют следующую схему.

  1. К сообщению T , которое необходимо подписать и передать по открытому каналу, присоединяется заранее условленный двоичный вектор V длиной v= 64 бит:

M ® T | V .

  1. Вырабатывается подпись для сообщения M:

S = Md (mod n).

  1. Значение S направляется приемной стороне.

  2. Приемная сторона по значению S вычисляет значения

M¢ = Se (mod n), V¢ = M¢ mod 2v,

T¢ = M¢ div 2v.

Если V¢ равно условленному значению, т.е. если выполняется условие V¢ = V, то принимается решение, что сообщение T¢ подписано владельцем секретного ключа, соответствующего открытому ключу, с помощью которого выполнялась проверка подписи. (Вероятность того, что случайное сообщение может быть принято за подписанное, равна 2-v.)

Полезным свойством рассматриваемой системы открытого шифрования является то, что при шифровании сообщения двумя и более пользователями дешифрующие процедуры можно выполнить в произвольном порядке. Например, пусть C = E1[E2(M)], тогда D1[D2(S)] = D2[D1(S)] = M. Это свойство используется в протоколе слепой подписи и в системах тайного электронного голосования.

Таким образом, секретный ключ служит для подписывания сообщений, открытый ключ – для проверки подписи. Для того, чтобы послать секретное сообщение некоторому абоненту A , любой пользователь может воспользоваться открытым ключом абонента A и сформировать криптограмму C = EA(M). По значению C восстановить сообщение M может только абонент A , который знает секретный ключ, соответствующий открытому ключу, с помощью которого была сформирована криптограмма. В криптосистеме RSA генерация подписи совпадает с процедурой дешифрования, а проверка подписи – с процедурой шифрования.

Рассмотрим небольшой пример, иллюстрирующий применение алгоритма RSA.

Пример Зашифруем сообщение “САВ”. Для простоты будем использовать маленькие числа (на практике применяются гораздо большие).

  1. Выберем p=3 и q=11.

  2. Определим n=3*11=33.

  3. Найдем (p-1)(q-1)=20. Следовательно, в качестве d, взаимно простое с 20, например, d=3.

  4. Выберем число е. В качестве такого числа может быть взято любое число, для которого удовлетворяется соотношение (е*3) (mod 20) = 1, например 7.

  5. Представим шифруемое сообщение как последовательность целых чисел с помощью отображения: А®1, В®2, С®3. Тогда сообщение принимает вид (3,1,2). Зашифруем сообщение с помощью ключа {7,33}.

ШТ1 = (37) (mod 33) = 2187 (mod 33) = 9,

ШТ2 = (17) (mod 33) = 1 (mod 33) = 1,

ШТ3 = (27) (mod 33) = 128 (mod 33) = 29.

  1. Расшифруем полученное зашифрованное сообщение (9,1,29) на основе закрытого ключа {3,33}:

ИТ1 = (93) (mod 33) = 729 (mod 33) = 3,

ИТ2= (13) (mod 33) = 1 (mod 33) = 1,

ИТ3 = (293) (mod 33) = 24389 (mod 33) = 2.

Итак, в реальных системах алгоритм RSA реализуется следующим образом: каждый пользователь выбирает два больших простых числа, и в соответствии с описанным выше алгоритмом выбирает два простых числа e и d. Как результат умножения первых двух чисел (p и q) устанавливается n.

{e,n} образует открытый ключ, а {d,n} - закрытый (хотя можно взять и наоборот).

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

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

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

4.1.1 Практическая реализация RSA

В настоящее время алгоритм RSAактивно реализуется как в виде самостоятельных криптографических продуктов (Например, в нашумевшей программеPGP), так и в качестве встроенных средств в популярных приложениях ( в браузерах Интернет отMicrosoftиNetscape).

Важная проблема практической реализации - генерация больших простых чисел. Решение задачи «в лоб» - генерация случайного большого числа n(нечетного) и проверка его делимости на множители от 3 вплоть доn0.5. В случае неуспеха следует взятьn+2 и так далее ( В теории чисел показано, что вероятность того, что число порядкаnбудет простым составляет 1/lnn).

В принципе в качестве pиqможно использовать «почти» простые числа, то есть числа для которых вероятность того, что они простые, стремится к 1. Но в случае, если использовано составное число, а не простое, криптостойкостьRSAпадает. Имеются неплохие алгоритмы, которые позволяют генерировать «почти» простые числа с уровнем доверия 2-100.

Другая проблема - ключи какой длины следует использовать?

Для прак­ти­че­ской реа­ли­за­ции ал­го­рит­мов RSA по­лез­но знать оцен­ки тру­до­ем­ко­сти раз­ло­же­ния про­стых чи­сел раз­лич­ной дли­ны, сде­лан­ные Шроппелем.

log10 n

Число операций

Примечания

50

1.4*1010

Раскрываем на суперкомпьютерах

100

2.3*1015

На пределе современных технологий

200

1.2*1023

За пре­де­ла­ми со­вре­мен­ных тех­но­ло­гий

400

2.7*1034

Тре­бу­ет су­ще­ст­вен­ных из­ме­не­ний в тех­но­ло­гии

800

1.3*1051

Не раскрываем

В кон­це 1995 го­да уда­лось прак­ти­че­ски реа­ли­зо­вать рас­кры­тие шиф­ра RSA для 500-знач­но­го клю­ча. Для это­го с по­мо­щью се­ти Ин­тер­нет бы­ло за­дей­ст­во­ва­но 1600 ком­пь­ю­те­ров.

Сами авторы RSAрекомендуют использовать следующие размеры модуляn:

768 бит - для частных лиц;

1024 бит - для коммерческой информации;

2048 бит - для особо секретной информации. ( Данные оценки сделаны с учетом развития вычислительной техники вплоть до 2004 года.)

Третий немаловажный аспект реализации RSA - вычислительный. Ведь приходится использовать аппарат длинной арифметики. Если используется ключ длиной k бит, то для операций по открытому ключу требуется О(k2) операций, по закрытому ключу - О(k3) операций, а для генерации новых ключей требуется О(k4) операций.

Криптографический пакет BSAFE 3.0 (RSA D.S.) на компьютере Pentium-90 осуществляет шифрование со скоростью 21.6 Кбит/c для 512-битного ключа и со скоростью 7.4 Кбит/c для 1024 битного. Самая «быстрая» аппаратная реализация обеспечивает скорости в 60 раз больше.

По сравнению с тем же алгоритмом DES, RSA требует в тысячи и десятки тысяч раз большее время.

Соседние файлы в папке Статьи