Решаем четыре системы сравнений 5 страница

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

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

Во-первых, такая задача может быть решена, если воспользоваться какой-нибудь асимметричной системой. Пусть это будет RSA. Обозначив через Е и D алгоритмы зашифрования и расшифрования соответственно участника Х, легко построить протокол электронной, или цифровой, подписи для пары Алиса-Боб. Именно:

1) Алиса, подписывая сообщение х, вычисляет у = Е (D (х)).

2) Боб, получив у, вычисляет х = Е (D (у)).

Боб, прочитав сообщение х, вправе рассчитывать на то, что оно послано Алисой, ибо применяя общеизвестный алгоритм Е к некоторому тексту, он (уверенный в системе RSA) надеется, что соответствующий открытый текст был преобразован в данный при помощи алгоритма D , известного только Алисе.

Общая схема цифровой подписи – это тройка алгоритмов (G, S, V).

G – полиномиальный вероятностный алгоритм генерирования ключей. С его помощью

каждый из абонентов информационной сети получает в свое распоряжение пару

(К , К ) ключей, где К – открытый ключ, помещаемый в сертифицированный

справочник, а К – соответствующий первому секретный ключ.

S – полиномиальный алгоритм генерирования подписей. На входе (х, К ), где х –

пересылаемое сообщение, алгоритм S выдает подпись s для сообщения х.

V – полиномиальный алгоритм проверки подписи. Если V (K , x, s) = 1, то подпись s

под сообщением х принимается, если же V (K , x, s) = 0, то подпись отвергается. Но

всегда для подписи s, сгенерированной с помощью ключа К для сообщения х,

должно быть V (K , x, s) = 1.

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

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

Выборочное фальсифицирование. Противник способен подделать подпись некоторых сообщений по своему выбору.

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

Слом системы подписи. Противник в состоянии получить секретный ключ.

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

Атака по ключу. Противник знает только открытый ключ К .

Атака по известной подписи. Противник знает пару (х, s), где s – подпись под сообщением х, выработанная при помощи алгоритма S на секретном ключе К .

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

i = 1, …, n получить подпись s под сообщением х , как если бы оно было получено при помощи алгоритма S на секретном ключе К .

Так как подписываемые тексты могут быть весьма объемными, то бывает, что текст разбивается на блоки, и каждый блок подписывается отдельно. Но это тоже не очень удобно. Решает проблему использование хэш-функций. Их еще называют сжимающими. Под хэш-функцией понимаем, как уже говорилось, криптографическую функцию H от сообщения х произвольной длины, которому сопоставляется хэш-код сообщения H (x) фиксированного размера (обычно 128 или 160 бит). Использование хэш-функций в системах электронной подписи сводится к тому, что подписывается не само сообщение, а его хэш-код. Напомним здесь и два важных свойства хэш-функции:

1) Функция H эффективно вычислима для любого сообщения х, но по данному

значению H вычислительно неосуществимо нахождение отвечающего ему

сообщения х.

2) Вычислительно неосуществимо нахождение двух различных сообщений х и х ,

для которых совпадали бы значения H, т. е. H (x ) = H (x ).

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

Так как хэш-функция – это достаточно хитроумный элемент схем цифровой подписи, то приведем простой пример, основанный на системе RSA, как описано выше.

Пусть Алиса посылает следующий текст:

«DON’T EAT SWEETS BEFORE DINNER. ALICE.»

Переведем его в цифровой текст, используя теперь 30-символьный алфавит. Получим:

х = «0314 1329 1926 0400 1926 1822 0404 1918 2601 0405 1417 0426 0308 1313 0417 2826

0011 0802 0428»

Пусть заданы простые числа р = 3767 и q = 4111. Их произведение n = 15486137. Значение функции Эйлера (n) = 15478260. Допустим, Алиса выбрала такую пару ключей: е = 15587, d = 7130903. А ключи Боба таковы: е = 279911, d = 1063031. Тогда Алиса, преобразуя цифровой текст, указанным выше способом сначала получает следующую группу блоков:

D (x) = «10088956 11601866 02974881 14031245 02974881 03932189 10757594

03140428 01665248 00532433 04104532 13938145 02945774 09309208

09681573 07820757 13096773 04367025 08149343».

А затем вычисляет

Е (D (x)) = «08927408 09913251 03078488 10821448 03078488 06990205 09170395

08389990 09031807 04884302 03172873 00695649 07422563 12233388

14578612 15419663 02390840 00904683 03569801»

и посылает полученное Бобу. Боб применяет к указанной строке текста сначала алгоритм D , а к результату - Е . Например, для первого и второго блока будем иметь:

Е (D (08927408)) = E (10088956) = 00000314,

Е (D (09913251)) = E (11601866) = 00001329.

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

Системы цифровой подписи допускают вероятностную модификацию. В вероятностных системах алгоритм S является не детерминированным, а вероятностным. Он продуцирует подпись, которая оказывается случайной величиной. Рассмотрим одну из таких систем – систему ЭльГамала. В ней процедура генерирования ключей такая же, как и в соответствующей криптосистеме. Сохраняя предыдущие обозначения для ключей и открытого текста, опишем кратко алгоритмы подписывания и проверки.

4. Схема электронной подписи ЭльГамала.

Подписывание. Алиса вырабатывает свою подпись S под сообщением М таким образом:

1) выбирает случайное число ;

2) вычисляет ;

3) вычисляет ;

4) вычисляет ;

5) полагает .

Подтверждение подписи. Боб проверяет справедливость сравнения

.

Корректность процедуры вытекает непосредственно из правил построения и . Именно: . Отсюда с использованием теоремы Эйлера получаем:

.

Рассмотрим теперь еще один вероятностный вариант схемы цифровой подписи с модифицированной системой ключей по отношению к системе ЭльГамала..

3. Схема электронной подписи Шнорра. Система была предложена К. Шнорром (Schnorr C. P.). Пусть р – большое простое число и q – простое, делящее р – 1, и пусть g 1 такое, что g = 1. Числа р, q, g не составляют тайны и являются общими для всех абонентов сети. Алиса, между тем, выбирает случайное число a в диапазоне от 1 до q -1 и вычисляет величину h = g (mod p).

Набор ключей Алисы выглядит так:

открытый ключ: h;

секретный ключ: а.

Алгоритм подписывания использует некоторую хэш-функцию H и состоит из следующих шагов:

1)Алиса (подписывающая сторона) выбирает случайное число k от 1 до q -1 и вычисляет r = g (mod p).

2)Алиса вычисляет е = H (rx), где х – подписываемое сообщение, а rx означает результат конкатенации r и х.

3)Алиса вычисляет s = k + аe (mod q) и посылает сообщение х с подписью (e, s) Бобу (проверяющая сторона).

4)Боб вычисляет величину = g h (mod p) и проверяет, выполняется ли равенство e = H ( x). Если выполняется, то подпись принимается, в противном случае – отвергается.

Стойкость системы Шнорра в значительной степени зависит от свойств функции H.

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

5. Схема ECDSA (Elliptic Curve Digest Signature Algorithm). Рассмотрим еще алгоритм ECDSA – алгоритм цифровой подписи на эллиптической кривой, принятый, например, в Германии в качестве государственного стандарта.

Алгоритм генерирования ключей.

1) Выбирают эллиптическую кривую Е, определяемую над . Число точек кривой должно делиться на большое простое число n.

2) Выбирают точку порядка n.

3) Выбирают случайное число .

4) Вычисляют .

5) Секретным ключом объявляют d, открытым – .

Алгоритм формирования подписи под сообщением М.

1) Выбирают случайное число .

2) Вычисляют и полагают . Если , то переходят к шагу 3), иначе, – к шагу 1).

3) Вычисляют .

4) Вычисляют . Если , то переходят к шагу 5), иначе, возвращаются к шагу 1).

5) Подписью под сообщением М полагают пару целых чисел .

Замечание. (i) h (x) – хэш-функция (в указанном стандарте – SHA -1).

(ii) При r = 0 результат вычисления не зависит от d.

(iii) При s = 0 не существует , что необходимо для проверки

подписи.

Алгоритм проверки подписи под сообщением М с помощью открытого ключа

1) Если r и s – целые числа из , то переходят к шагу 2), иначе, подпись отвергается.

2) Вычисляют и .

3) Вычисляют и .

4) Вычисляют и .

5) Подпись полагают верной в том и только в том случае, когда .

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

При наличии надежного посредника можно поступить так. Алиса выбирает случайный бит с, а Боб – случайный бит b. Оба сообщают о своем выборе посреднику, который вычисляет сумму d = с + b (mod 2) и пересылает каждой из сторон результат.

Остановимся на случае, когда надежного посредника нет. Физически процесс можно

представить в следующем виде. Боб выбирает случайный бит b и, записав его на листке бумаги, запирает последний в небольшой сейф, который пересылается Алисе (предполагается, что Алиса не может вскрыть сейф без ключа). Алиса, в свою очередь, выбирает случайный бит c и посылает его Бобу. Боб в ответ посылает Алисе ключ. Оба вычисляют сумму d = b + c (mod 2).

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

1)Алиса выбирает случайное число х из Z , вычисляет y = g (mod p) и посылает у

Бобу.

2) Боб выбирает случайный бит b и случайное число k из Z , вычисляет величину

r = y g (mod p) и посылает r Алисе.

3) Алиса выбирает случайный бит с и посылает его Бобу.

4) Боб посылает Алисе b и k.

5) Алиса проверяет, выполняется ли сравнение r = y g (mod p). Если да, то результатом выполнения протокола будет бит d = b + c (mod 2).

В этом протоколе пустой сейф у Бобу присылает Алиса. Так как k выбирается случайно, то r является случайным элементом группы Z . Поэтому, получая сейф назад с битом b, который теперь обозначен через r, Алиса не может вскрыть его без ключа (если, конечно, она не умеет решать задачу дискретного логарифмирования). Боб тоже не может схитрить, ибо Алиса сверяет содержимое сейфа со значением, присланным открыто.

7. Протокол разделения секрета. Протокол решает задачу коллективного доступа к ресурсу, понимаемого в широком значении слова. Пусть имеются n участников протокола совместно владеющих некоторым ресурсом, доступ к которому обеспечивается знанием определенного «секрета». Секрет может представлять собой какой-то код, последовательность, число и т.д. Требуется организовать доступ к ресурсу путем некоего «распределения» секрета так, чтобы заранее заданные (разрешенные) множества участников могли всегда однозначно восстановить секрет, а прочие (неразрешенные) – нет. И более того, последние не должны получать никакой дополнительной информации о значении секрета. Совокупность разрешенных множеств называют структурой доступа. Здесь рассматривается т.н. пороговая схема разделения секрета. Это значит, что разрешенными множествами участников являются любые множества из t или более элементов. Протокол предложен А. Шамиром (Shamir A.) и состоит в следующем.

Пусть секрет представлен в виде натурального числа s. Выбирают большое простое число р и рассматривают s как элемент поля Z . Полагают а = s и выбирают в Z случайным образом числа а , … а . Пусть

f (x) = x –

многочлен от переменной х с коэффициентами из Z . Участник протокола с номером і, где і = 1, …, n, получает долю секрета – значение s = f (i). Если известны произвольные t значений f (i ), …, f (i ) многочлена, то f (x) однозначно восстанавливается по интерполяционной формуле Лагранжа:

f (x) = ) .

Восстановив f (x), легко найти секрет s = a = f (0). Зная не более t – 1 значения многочлена f (x), невозможно получить никакой информации о значении s, ибо для любого по заданным значениям в точках i , …, i можно указать многочлен f (x) такой, что f (0) = .

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

r = g (mod p), i = 0, …, t -1,

и публикует r , …, r . Участник с номером i, получив свою долю, проверяет равенство

g = r (r ) … (r ) (mod p),

убеждаясь, что s - доля секрета s. Действительно,

r (r ) … (r ) = g g … g = g = g (mod p).

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

Приведем небольшой пример. Пусть выбрано простое число р = 25362569 и g = 3. Пусть секрет представлен числом s = 317054. Число участников протокола n зададим равным 9 и положим t = 6. Таким образом, предполагается, что любые шесть или более участников, соблюдая правила протокола, смогут восстановить секрет. Выберем многочлен степени 5 над полем Z :

f (x) = 317054 + 115312 x + 301241 x + 711483 x + 249872 x + 674258 x .

Дата добавления: 2014-11-16