Криптосистема Райвеста - Шамира – Адлемана (система RSA) на основе возведения в степень в кольце вычетов

М.И. Рожков

МЕТОДЫ ЗАЩИТЫ ИНФОРМАЦИИ НА ОСНОВЕ НЕСИММЕТРИЧНЫХ КРИПТОСИСТЕМ

(курс лекций для студентов МГИЭМ)

1. ПРИНЦИПЫ ПОСТРОЕНИЯ КРИПТОСИСТЕМ

С “ОТКРЫТЫМ КЛЮЧОМ”

Пусть имеется множество K = {k} пользователей (абонентов), которые могут обмениваться сообщениями из множества M = {m} по “незащищенным” каналам связи. Незащищенность каналов понимается в том смысле, что к ним могут подключаться любые посторонние абоненты. При этом проходящая по каналу связи информация может этими посторонними абонентами искажаться, перехватываться, переадресовываться и т.п.

Традиционный способ сохранения точности и конфиденциальности передаваемой информации в этих условиях заключается в шифровании данной информации. Для этого пользователи снабжаются секретными криптоалгоритмами E_ij, i,j Î K, E_ij : M ® M, то есть обратимыми отображениями множества в себя, и когда пользователь i желает передать пользователю j сообщение “m”, то он вычисляет y = E_ij(m) и направляет значение “y” по адресу j. На приемном конце для восстановления сообщения “m” к сообщению “y” применяют отображение E_ij ^-1.

Принципиальные сложности здесь возникают на этапах “согласованного” обмена между абонентами криптоалгоритмами E_ij и E_ij^-1, замены криптоалгоритмов на новые, расширения круга пользователей.

Весьма оригинальные пути решения этих трудностей предложили в 1976 году Диффи и Хеллман. Для организации секретной связи они предложили идею системы открытого шифрования (СОШ), суть которой заключается в следующем.

Рассматриваются семейства алгоритмов {E_k}, kÎK и {D_k }, kÎK, E_k : M ® M , D_k : M ® M такие, что

1) при любом kÎK отображение D_k обратно к E_k , то есть при любом mÎM

D_k(E_k(m)) = m;

2) при любых k и mÎM величины E_k(m) и D_k(m) вычисляются “достаточно легко”;

3) при любом k “достаточно сложно” при известном E_k найти D_k;

4) пары отображений E_k, D_k возможно генерировать сравнительно просто;

5) при любом k и случайно выбранном mÎM сложно найти “m” при известном E_k(m).

При наличии таких семейств отображений {E_k}, {D_k}, kÎK, при организации системы связи алгоритмы шифрования E_k помещаются в общедоступный справочник, а обратные к ним алгоритмы D_k хранятся абонентами в секрете (абонент номер i хранит в секрете алгоритм D_i ).

Тогда, чтобы передать сообщение mÎM от абонента i к абоненту j абонент i берет из справочника алгоритм шифрования E_j, вычисляет y = E_j(m) и посылает результат абоненту j.

Получив сообщение “y”, абонент j восстанавливает первоначальное сообщение “m” с помощью секретного алгоритма D_j :

D_j(y) = D_j (E_j(m)) = m.

Одновременно данная система допускает и возможность электронной подписи сообщений. В этом случае вместе с сообщением “m” абонент i передает D_i(m)=s, что и является собственно подписью для сообщения “m”.

На приемном конце критерием правильности подписи служит равенство E_i(s)=m, при этом алгоритм E_i берется из открытого справочника.

Криптографические качества такой СОШ основаны на сложности решения двух задач:

Задача 1. При известном отображении E_k: M®M найти обратное к нему отображение D_k: M ® M.

Задача 2. При заданных E_k: M®M и y=E_k(m) найти сообщение mÎM.

СОШ называют также несимметричными криптосистемами или

криптосистемами с двумя ключами.

Отображения (функции) E_kсо свойствами 5) называют также однонаправленными (такой термин означает, что значение функции при любом заданном аргументе вычисляется “легко”, в то время как по заданному значению функции нахождение аргумента - “трудная задача”).

На практике отображения E_k, D_k следует выбирать таким образом, чтобы задачи 1,2 были эквивалентны в вычислительном смысле известным трудным задачам в области математики.

Кроме изложенной выше СОШ Диффи и Хеллман предложили также систему открытого распределения ключей (СОРК), суть которой можно изложить следующим образом.

Пусть имеется функция от двух переменных ¦: X´X®X, обладающая следующими свойствами:

а) при любых a, x Î X значение ¦(a,x) легко вычисляется;

б) при любых a, x, y Î X справедливо равенство

¦ ( ¦(a,x), y) = ¦ ( ¦(a,y), x);

в) по значениям ¦(a,x) и ¦(a,y) при неизвестных x, y (аргумент “a” при этом может считаться известным) трудно найти значение ¦(¦(a,x), y).

При наличии такой функции ¦ система распределения ключей реализуется даже таким образом. Функция ¦ и фиксированный элемент aÎX помещаются в общедоступный справочник. Для выработки общего секретного ключа абоненты i и j генерируют случайным образом соответственно элементы x и y, сохраняя их в секрете на время выработки общего секретного ключа. Далее они обмениваются значениями ¦(a,x) и ¦(a,y). После чего вырабатывают общий секретный ключ по схеме :

k = ¦(¦(a,y), x) = ¦(¦(a,x), y),

пользуясь свойством б) функции ¦.

Если в изложенной ранее СОШ принципиально важная роль отводилась свойству однонаправленности функций E_k , то в данном случае аналогичная роль отводится однонаправленности функций ¦(a,x) по аргументу “x”.

Что касается конкретных однонаправленных функций, задача “обращения” которых относилась бы к известным трудным задачам вычислительной математики и которые, следовательно, можно было бы использовать в СОШ и СОРК, то Диффи и Хеллман предложили использовать функцию возведения в степень в конечном поле.

Пусть GF(q) - конечное поле из q элементов, a - примитивный элемент поля GF(q), X = {0,1,...,q-2}, ¦: X®GF(q), ¦(x) = a^x, то есть в качестве однонаправленной функции ¦ рассматривается функция возведения в натуральную степень примитивного элемента конечного поля. Задача обращения такой функции, т.е. решения уравнения a^x = b при заданных a,b известна в математике как “проблема логарифмирования в конечном поле”.

Тогда базовый протокол открытого распределения ключей состоит в следующем. Полагаем, что поле GF(q) и примитивный элемент a - общеизвестны.

Участник A выбирает секретный ключ x(A), а участник B - секретный ключ x(B), x(A),x(B)Î{1,2,…,q-1}. Затем A вычисляет y_A = a^x(A) и посылает абоненту B.

Аналогичным образом B вычисляет y_B = a^x(B) и результат посылает абоненту A.

Тогда абоненты A и B образуют общий секретный ключ k_AB следующим образом

k_AB = a^x(A)x(B)= (y_A)^x(B)= (y_B)^x(A).

Отметим, что до сих пор нет доказательства того, что сложность раскрытия этой системы не может быть меньше сложности решения задачи дискретного логарифмирования в поле GF(q).

Отметим также, что число q-1 должно иметь по крайней мере один большой делитель. В противном случае задача дискретного логарифмирования в поле GF(q) решается легко.

Серьезным недостатком изложенного базового протокола СОРК является возможность атаки «злоумышленник в середине», суть которой состоит в следующем. Злоумышленник выбирает числа z(A) и z(B), затем подменяет в канале связи сообщения a^x(A) и a^x(B) на a^z(A) и a^z(B) соответственно. Далее он формирует ключи k₁=a^x(A)z(B) и k₂=a^x(B)z(A) для связи с пользователями A и B соответственно.

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

Для устранения данного недостатка базового протокола был предложен протокол MTI (Т.Мацумото, И.Такашима, Х.Имаи, см [10]), в котором пользователи имеют открытые ключи и используют модифицированный алгоритм выработки общего ключа.

Итак, пользователи A и B имеют секретные ключи a и b соответственно и публикуют свои открытые ключи z_A=a^a, z_B=a^b , a - примитивный элемент поля GF(q).

Для выработки общего ключа k они генерируют случайные числа соответственно x(A) и x(B), 1£x(A),x(B)£q-2, и обмениваются сообщениями : A®B: a^x(A), B®A: a^x(B).

При этом искомый общий ключ находится по формуле

k= (a^x(B))^a×(z_B)^x(A) = (a^x(A))^b×(z_A)^x(B) =a^x(A)b+x(B)a .

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

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

СИСТЕМЫ ОТКРЫТОГО ШИФРОВАНИЯ

Криптосистема Райвеста - Шамира – Адлемана (система RSA) на основе возведения в степень в кольце вычетов

Пусть n = pq, где p, q - различные простые большие числа, M = Z_n - кольцо вычетов по модулю n, j(n) = (p-1)(q-1) - функция Эйлера, e, d - целые числа такие, что

ed º 1 (mod j(n)) .

Тогда алгоритм зашифрования E сообщения mÎM заключается в возведении в степень e в кольце Z_n , т.е.

E(m) = m^e (mod n).

Одновременно алгоритм расшифрования D=E^-1 заключается в возведении шифрованного текста c= E(m) в степень d:

c^d=m (mod n).

Таким образом, в данной системе в открытый справочник абонент помещает пару (n,e), которая позволяет зашифровать любое сообщение.

В секрете же абонент держит число d, что позволяет расшифровать сообщения только ему. Кроме того, секретными должны быть и числа p, q, ибо при известном разложении числа “n” на простые составляющие нахождение секретного “d” не составляет труда с помощью алгоритма Евклида. При этом после вычисления пары e, d абонент может информацию о числах p и q просто стереть.

Итак, однонаправленная функция, лежащая в основе RSA - системы, представляет собой возведение в степень e в кольце Z_n. Обращение такой функции, т.е. нахождение целого d такого, что

ed º 1 (mod j(n)) ,

является “сложной” задачей, эквивалентной задаче разложения числа “n” на простые множители p и q.

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

2.1.1. Утверждение. Пусть n = pq, где p, q - различные простые числа, j(n) = (p-1)(q-1) - функция Эйлера, e, d - целые числа такие, что

ed º 1 (mod j(n)) .

Тогда доля любого mÎZ_n справедливо равенство:

m^ed=m (mod n).

Доказательство. Так как кольцо Z_n изоморфно прямой сумме полей Z_p и Z_q, то достаточно доказать, что для заданного простого числа p при любом mÎZ_p верно равенство:

m^ed=m (mod p).

Без потери общности можно полагать, что m¹0 (mod p), и рассматриваемое равенство приводится к эквивалентному виду

m^ed^-1=1 (mod p).

Учитывая, что ed º 1 (mod j(n)), для некоторого целого k получаем

ed-1=k×j(n)=k×(p-1)(q-1).

Отсюда, с учетом малой теоремы Ферма

m^ed^-1=(m^p-1)^k^×^(q-1)=1 (mod p).

На этом доказательство завершено.

Рекомендуется, в частности, выбирать параметры системы RSA такими, чтобы

d>n^1/4;

число p+1 имеет большой простой делитель;

число p-1 имеет большой простой делитель s такой, что число s-1 также обладает большим простым делителем.

Дата добавления: 2019-02-12; просмотров: 304; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 3 4 5 6 7 Следующая ⇒

Мы поможем в написании ваших работ!