Teoria_chisel_i_kriptozashita

3)это значение отсылается участнику А;

4)участник А вычисляет

РО = dАPВ

5)и отсылает полученную точку В;

6)умножая полученную точку на свой секретный ключ расшифро-

вания dВ , участник В получает точку Рm , соответствующую сооб-

щению m участника А:

Рm = dВPО .

Вычисляя РО, участникАснимаетдействиесвоегоключашифрования:

РО = dАPВ = dА(еВРА) = dА(еВ(еАРm )) = еВ(dА(еАРm )) = еВРm .

Следовательно, участник В получает

dВPО = dВ(dАРm ) = Рm .

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

7.3. Протокол распределения ключей Менезеса-Кью-Ванстона (MQV-протокол)

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

Для предотвращения действий активного криптоаналитика необходима аутентификация кратковременных ключей, например, еАР и еВР в

протоколе Месси-Омуры. Для этого используется открытое опубликование ключей dАР и dВР . При этом постороннее лицо не в состоянии стать по-

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

61

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

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

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

Вобоих случаях используется двоякая трактовка координат точек эллиптической кривой: а) как элементов расширения поля, над которым строится кривая; б) как кодов целых чисел.

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

Участники А и В располагают точкой Р эллиптической кривой по-

рядка n, над которой осуществляются все вычисления. Кроме того, они знают долговременные и кратковременные ключи друг друга:

1) ключи участника В известны участнику А

QВ = dВР = (аВ,bВ), RВ = kВР = (хВ, уВ) ;

2) ключи участника А известны участнику В

QА = dАР = (аА,bА), RА = kАР = (хА, уА) .

7.4. Протокол Эль Гамаля для криптосистемы с использованием эллиптических кривых

В случае криптосистемы RSA использование протокола Эль Гамаля выглядит следующим образом. Выбирается простое число n и случайные числа р < n и q < n . Открытым ключом является тройка

(n, p, pq modn = у) , а q используется в качестве секретного ключа.

Для шифрования открытого текста m необходимо вычислить а ≡ pk (mod n), b(m) ≡ ( уk m)(modn), где k — случайное взаимно простое с n число. Шифртекстом является пара а, b(m). Очевидно, что для

расшифровки требуется вычислить m = (b(m) / aq ) mod n .

62

Модификация протокола Эль Гамаля, использующая мультипликативную группу эллиптической кривой, выглядит следующим образом.

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

Абоненты криптосистемы А и В уже совершили обмен частями ключа kАQ и kВQ по протоколу Диффи-Хеллмана. Теперь абонент А, же-

лающий переслать В сообщение М, должен выбрать секретное число l и отправить другому абоненту пару точек эллиптической кривой

Е= (lQ, M +l(kВQ)). Для расшифровки полученного сообщения абонент

Ввычисляет Т = kВ(lQ)(l(kВQ)). Очевидно, что М = М +l(kВQ) −T . Следует обратить внимание на то, что точка lQ выполняет функцию

суммы шифра и, следовательно, одна и та же точка Q не должна исполь-

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

7.5. Обоснование протоколов с использованием модулярной арифметики

Распределение ключей.

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

На первом этапе участники А и В, используя свои секретные данные kА,dА и kВ, dВ , вычисляют числа

sА = (kА + хАаАdА) mod n , sВ = (kВ + хВаВdВ) mod n .

На втором этапе они вычисляют точки эллиптической кривой

U А = RВ + хВаВQВ,

UВ = RА + хАаАQА.

На третьем этапе они вычисляют точку эллиптической кривой

W = sАU А, W = sВUВ.

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

63

Для участника А

sАU А = ((kА + xАaАdА) mod n)(RВ + xВaВQВ) =

=((kА + xАaАdА) mod n)(kВP + xВaВdВP) =

=((kА + xАaАdА) mod n)(kВ + xВaВdВ)P =

=((kА + xАaАdА)(kВ + xВaВdВ) mod n) P.

Для участника В

sВUВ = ((kВ + xВaВdВ) mod n)(RА + xАaАQА) =

=((kВ + xВaВdВ) mod n)(kАP + xАaАdАP) =

=((kВ + xВaВdВ) mod n)(kА + xАaАdА)P =

=(((kВ + xВaВdВ)(kА + xАaАdА)) mod n) P.

Врассмотренной интерпретации протокола модулярная арифметика

сочетается с арифметикой эллиптических кривых.

Рассмотрим интерпретацию, когда модулярная арифметика не используется и числа sА, sВ заранее не вычисляются.

Участник А может вычислить точку U А эллиптической кривой, выполнив умножение точки QВ на константу аВ и константу хВ , а затем сложить полученную точку с RВ . Аналогичным образом участник В вычисляет точку UВ.

Для получения точки W участники А и В, имея в виду, что надо умножить полученные точки на константы sА и sВ , могут проделать это по следующему алгоритму (описывается для стороны А):

3)складываются две точки эллиптической кривой, полученные в пп. 1) и 2).

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

64

8.Цифровая подпись

8.1Стандарт DSS, алгоритм DSA

В1991 г. Правительственный национальный институт стандартов и технологий США утвердил стандарт цифровой подписи DSS (Digital Signature Standard), основанный на специальном алгоритме цифровой подписи DSА (Digital Signature Algorithm) для использования в правительственных

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

Дляинициализациикаждыйпользовательдолжен проделатьследующее:

1)выбрать простое число q, не менее 150 бит, используя для этого генератор случайных чисел и тесты на простоту;

2)аналогичным образом выбрать второе простое число р, не менее 500 бит, причем делителем р – 1 является q;

3)выбрать образующий элемент α единственной циклической подгруппы группы Fр порядка q, которое находится вычислением

α ≡ g(р−1)q (mod p) для случайно выбранного целого числа g (если в результате вычислений получается целое, отличное от единицы, то α будет образующим элементом);

4) определить случайное число а 0,q в качестве секретного ключа

и образовать открытый ключ у ≡αа(mod p) .

Теперь пользователь может подписывать сообщения. Сначала он

r ≡ (αk mod p)(mod q) . В заключение пользователь находит целое s такое, что s ≡ (k–1 [h(m) + ar])(mod q) . Подпись этого пользователя m образуется парой чисел (r, s) по модулю q.

Чтобы проверить подпись, противоположная сторона, получив аутентифицированный открытый ключ от первого пользователя ( р,q,α, у) , должна выполнить следующие действия :

1)проверить, выполняются ли условия (0 < r < q) и (0 < s < q) , а если нет, то отклонить подпись;

2)вычислить w≡ s–1(mod q) и h(m) ;

3)найти u1 ≡ (s−1h)(mod q) и u2 ≡ (rw)(mod q);

4)вычислить v ≡ ((αu1 уu2 ) mod p)(mod q);

5)принять подпись, если v = r , и отклонить в противоположном случае.

65

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

Алгоритм ESDSA — аналог DSA для эллиптических кривых. Для простоты будем рассматривать эллиптические кривые над полем Fр .

Пусть Е — эллиптическая кривая, определенная над полем Fр , и пусть Р — точка простого порядка q кривой Е(Fр) . Эта кривая и точка на

ней являются системными параметрами. Используемые простые числа р и q примерно одного порядка. Каждый пользователь выбирает случайное число а в интервале 1 < a < q −1 и вычисляет свой открытый ключ по формуле Q = aP . Он публикуется при сохранении числа а в качестве сек-

ретного ключа пользователя.

Протокол ESDSA для вычисления цифровой подписи. Чтобы под-

писать свое сообщение, пользователь проделывает следующее:

1)выбирает случайное целое число k 1,q −1;

2)вычисляет kP = (x1, y1) и r ≡ x1(mod q) ( х1 0, p −1 с дальнейшим приведением по модулю q). Если r ≡ 0(mod q), то выбирают новое случайное число k 1,q −1;

3)определяет k−1 modq ;

4)вычисляет s ≡ (k-1[h(m) + xr])(modq), где h(m) — хэширован-

ное посылаемое сообщение m. Если s = 0, то значения s−1 mod q , требуемого по п. 3) для верификации подписи не существует, откуда необходимо возвращение к п. 1);

5) подписью для сообщения m является пара чисел (r, s) .

ESDSA для верификации подписи. Чтобы проверить подпись источника сообщения, пользователь проделывает следующее:

1)получает авторизированную копию открытого ключа Q источника сообщения;

2)проверяет принадлежность чисел (r, s) интервалу (1,q −1);

3)вычисляет w≡ s–1(mod q) и h(m) ;

4)находит u1 ≡ (s−1h)(mod q) и u2 ≡ (rw)(mod q) ;

5)вычисляет (х0 , у0 ) = u1P +u2Q , v ≡ х0 (mod q) ;

6)принимает подпись, если v = r , и отклонить в противоположном случае.

66

Основное различие между ECDSA и DSA состоит в способе образования r . DSA вычисляет r как случайную степень αk mod p, приведенную по модулю q , которое должно принадлежать интервалу (1,q −1).

ECDSA формирует целое r взятием абсциссы точки kP и приведением ее по модулю q .

Для получения того же уровня секретности, что и в случае применения DSA, параметр q должен быть 160-битовым.

Вместо использования Е и Р в качестве глобальных системных параметров, можно фиксировать только поле Fр для всех пользователей и

позволить каждому пользователю выбирать собственную эллиптическую кривую Е и точку Р Е(Fр) . В этом случае определенное уравнение

кривой Е, координаты точки Р, а также порядок q этой точки Р должны быть включены в открытый ключ пользователя. Если поле Fр фиксирова-

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

ромное число вариантов выбора эллиптической кривой над полем Fр .

8.2. Обобщенная схема цифровой подписи Эль Гамаля

Обобщенная схема электронной подписи Эль Гамаля работает в любой абелевой группе.

Для работы по данной схеме каждому участнику необходимо:

1)выбрать подходящую циклическую группу G порядка n и её образующий элемент α ;

2) выбрать случайное целое число а 1, n −1 и вычислить элемент

у=αа mod n ;

3)сформировать открытый ключ (α, у) на основе секретного ключа а.

Для формирования подписи, сопровождающей документ m, участник А должен выполнить следующие действия:

1) выбрать случайное секретное число k 1, n −1, взаимно простое с n , (k, n) =1;

2)вычислить элемент r =αk mod n ;

3)найти k −1 mod n;

4)вычислить хэш-функции h(m) и h(r);

5)найти s = k −1[h(m) −ah(r)]mod n;

67

6) цифровой подписью является пара (r, s) .

Для проверки цифровой подписи участника А на документе m участник В должен проделать следующие действия:

1)получить авторизированную версию открытого ключа участника А (α, у) ;

2)вычислить хэш-функции h(m) и h(r);

3)найти v1 = ( уh(r) rs ) mod n ;

4)вычислить v2 =αh(m) mod n;

5)принять подпись, если v1 = v2 и отклонить ее в противоположном

случае.

Генерация подписи требует вычислений, как в группе G , так и в группе Zn , в то же время проверка подписи связана с вычислениями

только в группе G .

Рассмотренный алгоритм наиболее удачно может быть реализован при использовании в качестве группы G последовательность точек эллип-

тической кривой над конечным полем Fq . Проблема дискретного лога-

рифмирования в этой группе гораздо сложнее, чем в мультипликативной группе конечного поля Fq . Отсюда следует, что q может иметь меньшую

размерность, чем в случае имплементации в группе Fq .

8.3. Схема цифровой подписи Эль Гамаля с возвратом сообщения

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

Пространством сообщений здесь является М = Z р , где р — простое

число. В качестве пространства подготовленных к подписанию сообщений МS используется декартово произведение МS = Z р ×Zq , где q — про-

стое число, которое является делителем ( р−1). Пусть R — инъекция из пространства сообщений М в пространство подписанных сообщений МS . Например, значение R(m) может быть представлено как

(m,m mod q) . Через R−1 обозначается отображение из образа функции R

68

в ее область определения: R−1 : Im(R) → М . Например,

R−1(m,m mod q) = m .

Алгоритм генерации ключа тот же, что и в алгоритме DSA, с тем отличием, что размеры р и q могут быть одного порядка.

Алгоритм генерации подписи на сообщение m следующий: 1) вычисление m = R(m);

2) выбор случайного секретного числа k 1,q −1 и вычисление

r≡α−k (mod p);

3)вычисление е ≡ (m~r)(mod p) ;

4)определение s ≡ (ae +k)(mod q);

5)объявление пары (е, s) как подпись сообщения m. Алгоритм верификации подписи следующий:

1)получение авторизированной копии открытого ключа источника сообщения;

2)прием сообщения при условиях 0 < е< р и 0 < s < р и отклонение при невыполнении этих условий;

3)вычисление v ≡ (αs у−е)(mod p)и m~ ≡ (ve)(mod p) ;

4)отклонение подписи при условии, что m~ M R , и прием при невыполнении этого условия;

Доказательство корректности алгоритма.

Алгоритм генерации подписи осуществляется по следующей схеме

v ≡αs у−е ≡αs−ae ≡αk (mod p).

Таким образом,

8.4. Цифровая подпись с использованием точек эллиптической кривой

Пусть е = h(m) — значение хэш-функции для документа m, и пусть

Е — точка из группы точек эллиптической кривой, Р — базовая точка открытого ключа, n — порядок этой точки, s –– секретный ключ участника А, подписывающего документ. Открытым ключом участника А является точка Q = sP .

Алгоритм генерации подписи следующий:

1) участник А образует случайную строку k и вычисляет

69

R= kP ;

2)используя целочисленную абсциссу х точки R , участник А вычисляет

с≡ (х+е)(mod n) ,

d ≡ (k −sc)(mod n).

Пара (с, d) является подписью для документа m, для которого h(m) = e.

Для проверки того, что h(m) является корректным хэш-значением,

выполняется следующий алгоритм: 1) вычисляется

R′ = dP + cQ ;

2) используя абсциссу R′, вычисляется

е′ ≡ (с− х′)(mod n);

3) совпадение последнего значения с хэш-значением h(m) подтверждает положительный результат проверки.

9. Модели атаки нарушителя

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

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

При анализе надежности систем безопасности возникают две задачи:

1.Проверить безопасность данной системы относительно некоторой модели нарушителя.

2.Для данной системы найти максимальную модель, относительно которой она является безопасной (существует доказательство

безопасности).

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

1.Вычислительные (тип вычислительной модели, ее производительность, объем памяти и др.).

70