Курс лекций для студентов мгиэм принципы построения криптосистем с "открытым ключом"



страница1/3
Дата20.12.2012
Размер0.74 Mb.
ТипКурс лекций
  1   2   3
М.И. Рожков
МЕТОДЫ ЗАЩИТЫ ИНФОРМАЦИИ НА ОСНОВЕ НЕСИММЕТРИЧНЫХ КРИПТОСИСТЕМ
(курс лекций для студентов МГИЭМ)

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

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


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

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

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

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

Рассматриваются семейства алгоритмов {Ek }, kK и {Dk }, kK, Ek : M M , Dk : M M такие, что

1) при любом kK отображение Dk обратно к Ek , то есть при любом mM

Dk(Ek(m)) = m;

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

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

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

5) при любом k и случайно выбранном mM сложно найти “m” при известном Ek(m).
При наличии таких семейств отображений {Ek}, {Dk}, kK, при организации системы связи алгоритмы шифрования Ek помещаются в общедоступный справочник, а обратные к ним алгоритмы Dk хранятся абонентами в секрете (абонент номер i хранит в секрете алгоритм Di ).

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


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

Dj(y) = Dj (Ej(m)) = m.

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

На приемном конце критерием правильности подписи служит равенство Ei(s)=m, при этом алгоритм Ei берется из открытого справочника.
Криптографические качества такой СОШ основаны на сложности решения двух задач:

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

Задача 2. При заданных Ek: MM и y=Ek(m) найти сообщение mM.
СОШ называют также несимметричными криптосистемами или

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

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

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

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

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

а) при любых 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).
При наличии такой функции система распределения ключей реализуется даже таким образом. Функция и фиксированный элемент aX помещаются в общедоступный справочник. Для выработки общего секретного ключа абоненты i и j генерируют случайным образом соответственно элементы x и y, сохраняя их в секрете на время выработки общего секретного ключа. Далее они обмениваются значениями (a,x) и (a,y). После чего вырабатывают общий секретный ключ по схеме :

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

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

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

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

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

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

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

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

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

kAB = x(A)x(B)= (yA)x(B)= (yB)x(A).

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

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

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

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

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

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

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

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

k= (x(B))a(zB)x(A) = (x(A))b(zA)x(B) =x(A)b+x(B)a .

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

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

2.1. Криптосистема Райвеста - Шамира – Адлемана (система RSA) на основе возведения в степень в кольце вычетов
Пусть n = pq, где p, q - различные простые большие числа, M = Zn - кольцо вычетов по модулю n, (n) = (p-1)(q-1) - функция Эйлера, e, d - целые числа такие, что

ed 1 (mod (n)) .

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

E(m) = me (mod n).

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

cd=m (mod n).

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

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

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

ed 1 (mod (n)) ,

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

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

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

ed 1 (mod (n)) .

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

med=m (mod n).

Доказательство. Так как кольцо Zn изоморфно прямой сумме полей Zp и Zq, то достаточно доказать, что для заданного простого числа p при любом mZp верно равенство:

med=m (mod p).

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

med-1=1 (mod p).

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

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

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

med-1=(mp-1)k(q-1)=1 (mod p).

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

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

d>n1/4;

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

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

2.2. Система открытого шифрования Эль-Гамаля на основе возведения в степень в конечном поле
Пусть Zp – поле вычетов по модулю большого простого числа p. Пусть участник A желает послать участнику B сообщение m, 0mp-1. Для этого A берет случайное число k из интервала от 0 до p-1. Это число k используется для образования ключа K следующим образом:

K = (yB)k mod p, (2.1)

где yB = x(B) (mod p) - открытый ключ абонента B (этот открытый ключ либо хранится в общем файле открытых ключей, либо высылается абонентом B по запросу), x(B) – секретный ключ абонента B.

Шифртекст далее будет состоять из пары (c1, c2), где

c1 = k (mod p), c2 = Km (mod p). (2.2)

Таким образом, размер шифртекста вдвое превосходит размер открытого сообщения. Заметим также, что мультипликативная операция в (2.2) может быть заменена любой другой обратимой операцией, например, сложением: K+m (mod p).

На приемном конце операция расшифрования выполняется в два этапа. На первом этапе вычисляют ключ K, используя секретный ключ x(B):

K = (k )x(B) = (c1)x(B) (mod p).
На втором этапе восстанавливается сообщение “m” путем деления c2 на K.

Отметим, что параметры и p могут быть одними и теми же для всех пользователей. Это приводит к экономии памяти для хранения открытых ключей абонентов (для каждого абонента “i” надо хранить всего один блок ключевой информации “y”).

Если же параметры и p будут свои для каждого пользователя, то это приведет к утроению объема файла, содержащего информацию об открытых ключах абонентов. Однако данный вариант организации связи с точки зрения безопасности связи представляется более надежным.

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

Действительно, пусть

c1,1 = k (mod p), c2,1 = m1 K (mod p),

c1,2 = k mod p, c2,2 = m2 K (mod p).
Тогда
m1 c2,1

= (mod p).

m2 c2,2
Следовательно, сообщение m2 легко восстанавливается при известном m1.

Данная схема открытого шифрования с точки зрения криптографической безопасности эквивалентна схеме распределения ключей Диффи-Хеллмана. Действительно, если открытый текст “m” может быть вычислен по c1, c2 и yB, тогда и K можно вычислить (т.е. раскрыть систему Диффи-Хеллмана).

Попытка же вычислить k или x(B) по c1, c2, yB (даже при известном m) приводит к необходимости решать задачу дискретного логарифмирования.


2.3. Система Меркля – Хеллмана на основе задачи о ранце
Пусть W = {w(1), ... , w(k)} - заданное множество целых чисел и S – их частичная сумма S = w(i1) + ... + w(it), i1< ... t.

Напомним, что задача о ранце состоит в отыскании w(i1),...,w(it) при известных W и S.

Хотя в общем случае эта задача является NP-полной, для некоторых множеств W эта задача решается весьма эффективно. Это имеет место, в частности, когда последовательность W = w(1),w(2), ...,w(k) является супервозрастающей, т.е. при всех i

w(i+1) > w(1) + ... + w(i).

Тогда восстановление w(i1),...,w(it) при заданном S происходит следующим образом:

w(it) - это наибольшее число из W, не превосходящее S,

w(it-1) - наибольшее число, не превосходящее S-w(it) и т.д.

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

Пусть W = {w1, ... , wk} - супервозрастающая последовательность, n = w1 + ... + wk . Выбираем целое M случайным образом из промежутка между n и 2n, а также случайное целое число a{0,1,..,M-1}, взаимно простое с M. Вычисляем b = a-1 (mod M). Выбираем случайную перестановку чисел {1,2,…,k}.

Пусть

vi =aw(i) (mod M), 1 i k.

Набор V = {v1, ... ,vk} помещается в открытый справочник.

Секретным ключом является набор (b, M, W, ).

Открытый текст “m” представляется в двоичной форме вектором длины k:

m = (1, 2, ... , k), i = 0,1.

Тогда шифрованным текстом для сообщения “m” будет число

y = vi(1) + ... + vi(t) ,

где i(1), ... , i(t) - номера единичных координат вектора m = (1, ... , k).

Процесс расшифрования заключается в следующем. Имеем соотношения:

y aw(i(1)) + ... + aw(i(t)) (mod M),

by w(i(1)) + ... + w(i(t)) (mod M).

Так как M > w(i(1)) + w(i(2)) + ... + w(i(t)) , то

by (mod M) = w(i(1)) + w(i(2)) + ... + w(i(t)).

Отсюда, учитывая свойство супервозрастания последовательности W = {w1, w2, ... , wk}, легко восстанавливаются индексы (i(1)), ... , (i(t)), откуда находятся единичные координаты i(1), ... , i(t) открытого сообщения “m”.

Главным достоинством данной СОШ (как и всех систем, основанных на проблеме ранца) является простота процессов зашифрования - расшифрования. Однако, как показано в [8], данная криптосистема может быть эффективно дешифрована.


2.4. Система Мак–Элиса на основе линейного кода, исправляющего заданное число ошибок
Идея данной системы заключается в выборе корректирующего кода, исправляющего определенное число ошибок, для которого существует эффективный алгоритм декодирования. С помощью секретного ключа данный код маскируется под общий линейный код, для которого нет эффективных алгоритмов декодирования.

Общими параметрами в системе Мак-Элиса являются натуральные числа k, n, t. Для получения открытого и соответствущего ему секретного ключа абонентом A проводятся следующие действия.

1. Берется порождающая матрица G=Gkn двоичного (n,k)-линейного кода, исправляющего t ошибок, для которого известен эффективный алгоритм декодирования.

2. Выбирается случайная двоичная невырожденная матрица S=Skk.

3. Выбирается случайная подстановочная матрица P=Pnn.

4. Вычисляется произведение матриц G1=SGP.

Открытым ключом является пара (G1,t), а секретным – тройка (S,G,P)

Для зашифрования сообщения m, предназначенного для абонента A, абонент B выполняет следующие действия:

1) представляет сообщение m в виде двоичного вектора длины k;

2) выбирает случайный двоичный вектор ошибок Z длины n, содержащий t единиц;

3) вычисляет вектор C=mG1+Z и направляет его (в качестве шифрованного текста) абоненту A.

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

1. Вычисляется вектор C1=CP-1.

2. Получает вектор m1, применяя к вектору C1 алгоритм декодирования кода с порождающей матрицей G.

3. Вычисляет вектор исходного сообщения m=m1S-1.

Корректность приведенного алгоритма расшифрования вытекает из следующих соотношений

C1=CP-1=(mG1+Z)P-1=(mSGP+Z)P-1=(mS)G+ZP-1.

А так как вектор ZP-1 имеет не более t единиц, алгоритм декодирует вектор С1 в m1=mS .

В качестве кода в системе Мак-Элиса можно использовать, например, код Гоппы. Известно, что для любого неприводимого многочлена g(x) степени t над полем GF(2m) существует бинарный код (код Гоппы) длины n=2m и размерности kn-mt, исправляющий до t ошибок, для которого имеется эффективный алгоритм декодирования. В настоящее время не известны эффективные алгоритмы дешифрования системы Мак-Элиса, использующей код Гоппы при правильном выборе параметров системы.

Однако рекомендуемые параметры такой системы (n=1024, t=38, k644) приводят к значительному увеличению открытого ключа системы (около 219 бит) и увеличению длины сообщения при шифровании ( примерно в полтора раза). По этой причине данная система не имеет широкого распространения.


3. СИСТЕМЫ ЭЛЕКТРОННОЙ ПОДПИСИ

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

Тогда данный абонент может использовать данную систему для электронной подписи сообщений, направляемых от него абоненту B.

Для этого абонент A вместе с сообщением m Zn направляет

абоненту B также и величину s=md (mod n), которая собственно и является подписью абонента A под собщением “m”.

Для проверки правильности подписи абонент B, получив пару (m, s), проверяет на истинность равенство

se= m (mod n).

Если данное равенство выполняется, то принимается решение о том, что сообщение “m” действительно исходит от абонента A.

Следует отметить, что само сообщение “m” не скрывается, а всего лишь подтверждается (проверяется) то, что данное сообщение действительно исходит от абонента A.

3.2. Схема электронной подписи Рабина
Абонент A генерирует два больших простых числа p и q, pq. Пусть n= pq. Далее абонент A выбирает случайным образом целое число bZn, (b,n) = 1 и помещает пару (n,b) в открытый справочник. Числа же p и q он хранит у себя в секрете.

Пусть также R - некоторое фиксированное множество, h - хэш-функция, отображающая ZnR в Zn. Хэш-функция h также является общеизвестной.

Подписью сообщения mZn объявляется пара (r,x), rR, xZn такая, что справедливо равенство

x(x + b) h(m,r) (mod n).

Абонент A для подписи сообщения mZn выбирает случайным образом rR и вычисляет h(m,r). Далее находятся решения x1, x2 соответственно сравнений вида

x(x + b) h(m, r) (mod p)

и

x(x + b) h(m, r) (mod q).
Пара (x1, x2) с помощью китайской теоремы об остатках позволяет найти решение x сравнения вида

x(x + b) h(m, r) (mod n),

то есть получить подпись (r,x) для сообщения “m”.

Если при выбранном значении rR решения (x1, x2) указанных выше сравнений не существует, то выбирается другое значение r'R и процедура повторяется. Среднее число попыток для получения подписи (при определенных теоретико-вероятностных предположениях о поведении хэш-функции при случайном выборе ее аргументов) составляет 4.
Попытка же найти подпись для сообщения “m” без знания p и q приводит к необходимости решения сравнения

x(x + b) = c (mod n),

что является трудной задачей, сравнимой по сложности (как считается) с задачей разложения числа n.


3.3. Вариант цифровой подписи Шамира
Данная схема цифровой подписи основана на проверке выполнения соотношения вида
se = it(t, m) (mod n), (3.3.1)
где m – сообщение,

(s,t) - цифровая подпись,

i - личный идентификатор пользователя,

n - произведение двух больших простых чисел,

e - большое простое число такое, что (e, (n)) = 1,

- однонаправленная функция.
Параметры n, e и функция выбираются для организуемой сети пользователей специальным центром генерации ключей. Эти параметры являются общими для всех пользователей и хранятся в их личных электронных карточках. Данные параметры не являются секретными, однако факторизация модуля n должна быть известна только центру генерации ключей. Секретным же ключом пользователя “i” является число “g” такое, что

ge = i (mod n).

Числа “g” для пользователей легко могут быть вычислены в центре генерации ключей (так как там известна факторизация модуля n), в то время как посторонний человек в попытке восстановить “g” по известным e, i, n должен будет решить сложную задачу извлечения корня e-й степени в кольце Zn.

Каждое сообщение mZn будет иметь большое число “правильных” подписей (s,t), однако при случайном выборе пары (s,t) вероятность выполнения соотношения (3.3.1) будет очень мала ( n-1). Если же зафиксировать один из параметров цифровой подписи, то попытка нахождения второго параметра подписи из уравнения (3.3.1) наталкивается на необходимость извлечения модулярных корней, что, как считается до настоящего времени, является сложной вычислительной задачей.

Тем не менее, если “g” известно, то имеется простой способ получения подписи для любого сообщения m, даже не имея разложения числа n.

Этот способ заключается в следующем.

Выбираем случайное число r и вычисляем

t = re (mod n).

Тогда проверочное уравнение (3.3.1) будет иметь вид

se = ge re(t, m) (mod n).

Так как (e, (n)) = 1, то общий множитель “e” можно исключить из экспоненты:

s = gr(t, m) ,

что приводит к нахождению параметра “s” и, следовательно, подписи к сообщению “m”.

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

i(k+1)=i(1)i(2)…i(k) (mod n)

следует, что gi(k+1)=gi(1)gi(2)…gi(k) (mod n), где gj – идентификатор пользователя j.

В частности, если идентификаторы пользователей i и j связаны соотношением: j=i2 (mod n), тогда их секретные ключи gi, gj будут удовлетворять аналогичному соотношению: gj=gi2 (mod n). Следовательно, пользователь i из своего секретного ключа сможет восстановить секретный ключ пользователя j.

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

3.4. Схема цифровой подписи Эль-Гамаля
Пусть - примитивный элемент поля Zp вычетов по модулю большого простого числа p. Пусть m - сообщение, которое требуется подписать, 0 m p-1. Полагаем, что у каждого пользователя есть открытый ключ вида

y = x (mod p),

где x – секретный ключ.

Чтобы подписать сообщение пользователь должен быть способен, используя свой секретный ключ x , найти подпись для “m” так, что все другие пользователи могли бы проверить истинность этой подписи, используя открытый ключ y (вместе с общими для всех и p); и, кроме того, без знания секретного x было бы очень сложно подобрать подпись к сообщению “m”.

В качестве подписи для сообщения “m” предлагается использовать пару (r, s), 0 r, s p-1 такую, чтобы выполнялось уравнение

m = yr rs (mod p). (3.4.1)

Процедура подписи будет состоять из следующих трех шагов.
1. Выбирается случайное число k из интервала от 0 до p-1 такое, что

(k, p-1) = 1.

2. Вычисляется

r = k (mod p). (3.4.2)

3. Перепишем уравнение (1) в виде

m = xr ks (mod p). (3.4.3)

Отсюда получим

m = xr + ks (mod p-1). (3.4.4)

Уравнение (3.4.4) разрешимо относительно s, если k выбрано таким, что

(k, p-1) = 1.

Отметим, что число k, выбираемое на шаге 1, нельзя использовать более одного раза.

Некоторые подходы к раскрытию данной схемы цифровой подписи
1. Пусть имеются L подписей {(ri, si), i=1, 2, ... , L} к соответствующим сообщениям (документам) {mi: i=1,2,...,L}. Тогда можно составить “L” линейных уравнений от L+1 неизвестных вида (3.3.4) и пытаться найти “x”.

Если какое-то значение k использовалось дважды, то система может стать практически однозначно разрешимой относительно “x”.

Например, если одно и то же значение k использовалось для подписи сообщений m1 и m2, то будем иметь систему уравнений над кольцом вычетов Zp-1:

m1 = xr + ks1 (mod p-1),

m2 = xr + ks2 (mod p-1).

Вычитая из первого уравнения второе, получим уравнение относительно k:

k(s1-s2)=m1-m2 (mod p-1)

Данное уравнение будет иметь в точности НОД(s1-s2, p-1) решений, которые легко вычисляются.

Далее, подставив найденное значение k в первое из уравнений, получим уравнение относительно секретного ключа x:

xr =m1- ks1 (mod p-1),

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

2. Пусть задано “m”, и будем пытаться найти r,s такие, чтобы проверочное соотношение (3.4.1) выполнялось. Если зафиксировать r случайным образом в виде

r = j mod p,

где j - случайное число, тогда нахождение для выбранного “r” соответствующего ему “s” равносильно решению задачи дискретного логарифмирования в поле GF(p).

Если же сначала зафиксировать s, то для вычисления r необходимо решить уравнение

rs ys = а (mod p),

которое, как считается, решить не проще, чем задачу дискретного логарифмирования в GF(p).

3. Как и другие предлагавшиеся системы цифровой подписи, данная система позволяет легко строить специального вида сообщения вместе с подписями. Пусть, например,

r' = B yC (mod p), s' = -r'/С (mod p-1), m' = -r' B/С (mod p-1).

Тогда нетрудно проверить, что (r', s') является подписью для сообщения m'.
Заключительные замечания

по данной системе цифровой подписи
1. Предложенная схема ЭЦП может работать не только в случае поля GF(p), но и при произвольном конечном поле GF(q). Однако считается, что проблема логарифмирования в простом поле решается труднее, чем в полях GF(pm), m > 1.

2. Сложность логарифмирования в простом поле GF(p) приблизительно такова же, что и сложность разложения на множители числа “n” при log p = log n. Поэтому и криптографические качества схем ЭЦП, основанных на этих математических проблемах, также примерно одинаковые.

3. При вычислении подписи (в соотношении 3.4.1) вместо открытого сообщения m целесообразно использовать его свертку h=H(m) с помощью хэш-функции H. Это защищает от возможности подбора сообщений с известным значением подписи.

4. ЭЦП Эль-Гамаля послужила образцом для построения целого семейства схем подписи в том числе стандартов цифровой подписи США и России. В их основе лежит проверка сравнения

AyB=rC (mod p),

в котором тройка (A,B,C) совпадает с одной из перестановок чисел (m, s, r). Так исходная схема Эль-Гамаля получается при A=m, B=-r, C=s. В стандарте США Digital Signature Standard (DSS) использованы значения A=m, B=r, C=s, а в стандарте ГОСТ Р 3410-2001 A=-m, B=s, C=r.

5. В указанном семействе схем цифровой подписи можно вместо пары (r,s) использовать пару (r (mod q), s (mod q)), где q – простой делитель числа p-1. При этом исходное проверочное равенство заменяется на модифицированное

(AyB (mod p))=rC (mod q).

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

В этой связи представляет интерес задача построения схем ЭЦП на основе симметричных криптографических систем, свободных от подобных недостатков.

Пусть требуется подписать сообщение M=m(1),m(2),…,m(n), m(i){0,1}.

В схеме Диффи-Лампорта подписывающий выполняет следующие действия.

1. Выбирает 2n случайных секретных ключей K={(k10,k11),…,(kn0,kn1)} для используемой им симметричной криптосистемы.

2. Выбирает n пар случайных чисел S={(s10,s11),…,(sn0,sn1)}, sij{0,1}.

3. Вычисляет значения rij=Ek(i,j)(sij), где Ek(i,j)(sij) – алгоритм шифрования сообщения sij на ключе kij.

4. Наборы S={(s10,s11),…,(sn0,sn1)} и R={(r10,r11),…,(rn0,rn1)} помещаются в общедоступный справочник. При этом помещать информацию в такой справочник может только автор подписи.

5. Подпись для сообщения M имеет вид (k1m(1),…,knm(n)).

Критерием правильности подписи является выполнение равенств

rij=Ek(i,j)(sij), j=m(i), i=1,2,…,n.

Одним из недостатков данной схемы является значительный объем цифровой подписи, которая может превышать само подписываемое сообщение. Для его устранения можно хранить единственный секретный ключ k, из которого формировать последовательность K: kij=Ek(i,j), i=1,2,…,n, j=0,1.

Основной же недостаток схемы цифровой подписи Диффи-Лампорта состоит в том, что после проверки подписи часть ключевого множества K становится известной проверяющему. Поэтому данная схема подписи является по существу одноразовой.

Отметим также, что в схеме Диффи-Лампорта нельзя использовать симметричные криптосистемы, «слабые» относительно атаки по известным открытому и шифрованному текстам, например, шифр наложения ключевой гаммы: rij=sij+kij (mod 2). Использование таких криптосистем привело бы к восстановлению ключевой последовательности K={(k10,k11),…,(kn0,kn1)} по известным наборам S={(s10,s11),…,(sn0,sn1)} и R={(r10,r11),…,(rn0,rn1)}.

4. ЛОГАРИФМИРОВАНИЕ В КОНЕЧНЫХ ПОЛЯХ

4.1. Методы логарифмирования для произвольной циклической группы
Мы будем рассматривать задачу логарифмирования применительно к произвольной циклической группе G = порядка G=n, порожденной образующим элементом “g”, т.е. нас интересует решение уравнения

gx = b

при заданных g и b G.

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

Отправной точкой к оценке сложности задачи логарифмирования будет служить
Метод 1 (полное опробование).

Суть данного метода состоит в вычислении таблицы логарифмов для всех элементов группы G, после чего логарифм конкретного элемента bG получается в результате просмотра данной таблицы.

Данный метод требует O(n) операции для вычисления таблицы. Кроме того, необходимо O(n) ячеек памяти для хранения таблицы.
Метод 2 (метод Шенкса).

Данный метод имеет сложность O(nlogn) операций и требует память для хранения O(n) элементов группы. Существо данного метода заключается в следующем.

Пусть : G {1,2,...,n}- некоторое инъективное отображение группы G на множество {1,2,...,n}.

Заметим, что логарифм любого элемента группы G можно записать в виде mq - r, где
m = [n], 0 r m, 0 q m.

Поэтому для вычисления логарифма элемента b G достаточно найти соответствующие q и r.

Построим два множества
S = { (i, (bgi)) , i = 0,...,m}

T = { (i, (gmi)) , i = 0,...,m}.
Произведем сортировку множеств S и T по второй координате и затем найдем s S и t T такие, что у них вторые координаты совпадают.

Это дает нам уравнение

bgr = gmq ,

отсюда

b = g mq-r .

Осталось заметить, что наиболее сложным в данном методе является этап сортировки, который требует O(mlog m) операций.
Метод 3 (метод Полига-Хеллмана-Сильвера).

Назовем целое число y - “гладким”, если оно не имеет простых делителей, превосходящих числа “y”.

Пусть n =pic(i) , p1 < ... < pk, - разложение числа n по степеням различных простых множителей.

Рассмотрим уравнение gx = a при заданных g и a G, G=n.

Идея нахождения логарифма элемента aG будет заключаться в нахождении величины log a (mod pic(i)), i = 1,2,...,k, что с учетом китайской теоремы об остатках будет равносильно нахождению log a (mod n), т.е. решению стоящей задачи.

Для простоты обозначений положим p - простое число такое, что

pc | n и pc+1 не делит n, x = log a (mod pc ). Ясно, что “x” может быть представлено в виде

x = bj pj , 0 bj < p.

Заметим, что log a = x + pc t для некоторого целого t, следовательно,

c-1

nx/p+npc-1t n bj pj-1 nb0/p

an/p = g = g j=0 = g .
Теперь для вычисления b0 мы вычисляем an/p и = gn/p . Далее вычисляем i для i = 0,1,...,p-1 до тех пор, пока не получим равенство i = an/p . Найденное значение i и будет b0 .

Если c > 1, то для нахождения b1 (после того, как b0 найдено) действуем следующим образом.

Пусть h = g-1= gn-1 , b(0)=b0, a1 = ahb(0). Тогда

c-1

n/p2 n bj pj-2 b1

a1 = g j=1 = .
Перебирая i = 0,1,...,p-1, находим i = b1 такое, что

n/p2

i = a1 .
Аналогичным образом находятся и остальные величины среди b0, b1, ... , bc-1.

Сложность вычисления логарифмов данным методом оценивается величиной

O (ci (log n + pi)).

Если же в данном методе использовать и идею метода Шенкса (на этапах, когда ищется i {0,1,...,p-1} такое, что i равно заданному элементу), то сложность будет

O (ci (log n + pi 1/2 log pi)).

Однако при этом потребуется память порядка O(pk1/2) для записи элементов группы.


4.2. Субэкспоненциальные методы логарифмирования в конечных полях (методы Адлемана, “Ватерлоо”, Копперсмита для случая поля GF(2n))

Ниже приведем несколько алгоритмов дискретного логарифмирования, имеющих субэкспоненциальную сложность. При этом мы ограничимся случаем поля GF(2n) (для простоты изложения), хотя некоторые из этих методов справедливы и в более общем случае. Поле GF(2n) мы будем представлять полем многочленов степени n-1 над полем GF(2) по модулю заданного неприводимого многочлена степени “n”

1. Алгоритм Адлемана

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

Вычисляем логарифмы всех неприводимых многочленов степени не более “b”, где b - фиксированное натуральное число, выбираемое в зависимости от поля GF(2n) и являющееся параметром метода.


Часть вторая.

Для нахождения логарифма заданного ненулевого элемента g(x)GF(2n), генерируем случайное целое число “m” и вычисляем (в поле GF(2n))

h(x) = g(x) m (x),

где (x) - образующий многочлен поля GF(2n).

Разложим h(x) на неприводимые множители

h(x) = pie(i)(x).

Если deg pi (x) b при всех i, 1 i t, тогда

log g(x) = e(i) log pi (x) - a (mod 2n-1).

А так как логарифмы элементов pi(x) находятся в базе данных, то задачу вычисления логарифма для данного элемента g(x) можно считать решенной.

Если же не все pi (x) имеют степень b, то выбираем другое целое “m” и повторяем попытку.

Через N(n,b) обозначим число многочленов степени “n” таких, что разложение любого из них на неприводимые факторы содержит только многочлены степени b. Тогда вероятность p(n,b) попадания на элемент из множества N(n,b) при случайном выборе многочлена степени “n” составит

p(n,b) = .

Поэтому при вычислении логарифма конкретного элемента g(x) потребуется в среднем p(n,b)-1 раз использовать
  1   2   3

Похожие:

Курс лекций для студентов мгиэм принципы построения криптосистем с \"открытым ключом\" iconКурс лекций для студентов мгиэм
Пособие предназначено для студентов 2-5 курсов мгиэм, специализирующихся в области защиты информации
Курс лекций для студентов мгиэм принципы построения криптосистем с \"открытым ключом\" iconО перспективах развития асимметричных криптосистем с упрощенной инфраструктурой
Ящее время криптосистемы с открытым ключом получили широкое распространение. Основная проблема при использовании таких криптосистем...
Курс лекций для студентов мгиэм принципы построения криптосистем с \"открытым ключом\" iconПрограмма дисциплины Криптография с открытым ключом Для направления 231000. 62 «Программная инженерия» подготовки бакалавра
Курс является общеуниверситетским факультативом. Курс читается в 3 – 4 модулях учебного года. Количество кредитов – 4
Курс лекций для студентов мгиэм принципы построения криптосистем с \"открытым ключом\" iconКурс лекций для студентов дневного и заочного отделения
Охватывают задачи не на все методы построения линий пересечения поверхностей, а только наиболее распространенные
Курс лекций для студентов мгиэм принципы построения криптосистем с \"открытым ключом\" iconКриптосистема Гольдвассер-Микали Шифрсистема с открытым ключом называется полиномиально секретной
Известно, что шифрсистема с открытым ключом семантически секретна тогда и только тогда, когда она полиномиально секретна
Курс лекций для студентов мгиэм принципы построения криптосистем с \"открытым ключом\" iconКурс лекций для студентов всех форм обучения Махачкала 2008 ббк 71 я 73 Курс лекций по культурологии для студентов всех форм обучения, Махачкала, дгту, 2008. 264 с
Охватывает всю тематику учебной программы этой дисциплины и это позволяет надеяться на то, что для студентов он окажется полезным...
Курс лекций для студентов мгиэм принципы построения криптосистем с \"открытым ключом\" iconКурс лекций по высшей геодезии раздел «теоретическая геодезия»
Курс лекций ведется на кафедре прикладной геодезии и фотограмметрии Полоцкого государственного университета для студентов специальности...
Курс лекций для студентов мгиэм принципы построения криптосистем с \"открытым ключом\" iconКурс лекций для студентов фен нгу (28. 03. 2004)
Название курса: Гидробиология. Курс лекций объемом 32 часа реализуется в рамках программы обучения по специальности «химик-эколог»...
Курс лекций для студентов мгиэм принципы построения криптосистем с \"открытым ключом\" iconКурс лекций по дисциплине «химия» для студентов нехимических специальностей Под общей редакцией
Краткий курс лекций по дисциплине «химия» для студентов нехимических специальностей
Курс лекций для студентов мгиэм принципы построения криптосистем с \"открытым ключом\" iconПрограмма дисциплины методика анализа экранных искусств
Программа предназначена для студентов, углубленно изучающих предметы культурологического цикла и педагогику Курс включает аудиторный...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org