Материал: Раздел 3. Криптографические протоколы

15

Раздел 3. Криптографические протоколы.

В традиционных (классических) криптографических системах предпола-

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

Криптография с открытым ключом значительно расширила класс задач, решаемых с помощью криптографических методов [7,8,9]. В результате появилась необходимость в интерактивных, многоразовых двусторонних обменах сообщениями между участниками, которые не всегда доверяют друг другу, в передаче информации между несколькими участниками. Последовательность действий участников обмена информацией, использующих криптографические приемы для решения нетрадиционных задач, называют криптографическими протоколами.

3.1. Системы с открытым распределением ключей для абонентских сетей.

Пусть несколько абонентов A, B, C, договорились об обмене информацией. Они могут выбрать некоторое общее простое число p, такое, что p-1 раскладывается на простые сомножители в первой степени. Число вида N = p₁p₂p₃…p_k называется эвклидовым числом. Каждый из участников выбирает два числа меньших и взаимно простых с p-1 так, чтобы:

a₁a₂ º b₁b₂ º c₁c₂ º 1 mod (p-1).

Пусть абонент A хочет передать сообщение S абоненту B. Он кодирует свое сообщение возведением в степень a₁: S^a1 º S₁ mod p и передает его B. Тот в свою очередь кодирует полученное сообщение возведением в степень b₁ : S₁^b1 º S₂ mod p и возвращает его A. A возводит его в степень a₂ и передает его B: S₂^a2 º S₃ mod p. B возводит его в степень b₂ и читает сообщение. Справедливость результата следует из сравнения: a₁b₁a₂b₂ º 1 mod (p – 1).

Пример. Пусть абоненты A, B и C выбрали число p = 103. Это число простое, причем 103-1 = 102 – эвклидово число, так как представляется в виде произведения простых чисел в первых степенях: 102 = 2*3*17. Каждый из участников выбирает пару секретных ключей:

A: a₁ = 25, a₂ = 49,

B: b₁ = 19 , b₂ = 43,

C: c₁ = 35, c₂ = 35.

Пусть теперь A посылает к B сообщение S = 67. Он возводит его в степень 25 и находит остаток по модулю 103: 67²⁵ º 86 mod 103.

B возводит число 86 в степень b₂ = 19 и отправляет результат к A:

86¹⁹ º 96 mod 103.

A возводит полученное сообщение в степень 49 и передает его B:

96⁴⁹ º 21 mod 103.

B получив сообщение, возводит его в степень 43 и читает исходный текст: 21⁴³ º 67 mod 103. Таким образом, S = 67.

Открытым ключом в этой системе является модуль p. Недостатком такой системы является большое число передач от одного абонента к другому.

2. Банки и вкладчики.

Рассмотрим задачу [ 6 ], в которой вкладчики банка v₁,v₂,…v_k передают шифрованное распоряжение ответственному работнику банка B (банкиру). При этом кроме конфиденциальности должна обеспечиваться узнаваемость вкладчика, чтобы по полученному сообщению банкир B сумел идентифицировать автора сообщения и выполнить именно его распоряжение.

Банкир B выбирает некоторое число N = PQ, где P и Q – большие простые числа. Каждый из вкладчиков v_i (i = 1,2,3,…,k) также выбирают свои значения

n_i = p_iq_i, причем желательно, чтобы N > n_i. Затем как банкир, так и вкладчики находят значения j (N) – банкир и j (n_i) – все вкладчики. После чего каждый выбирает свой открытый ключ E - банкир и e_i – вкладчики из условий:

0 < E < j (N) , ( E, j (N) ) = 1 – банкир и 0 < e_i < j (n_i), (e_i, j (n_i)) = 1 – вкладчики. Затем банкир и вкладчики находят свои секретные ключи D и d_i из сравнений:

ED º 1 mod j (N), 0 < D < j (N) – банкир,

edº 1 mod j (n_i), 0 < d < j (n_i) – вкладчики.

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

B: N, E

v_i: n_i, e_i.

Пусть теперь некоторый вкладчик v_i хочет передать распоряжение m банкиру B. Он шифрует его сначала своим секретным ключом (возводя m в степень d_i по mod n_i, а затем открытым ключом банкира: m₁ º m^d_i mod n_i, m₂ º m₁^E mod N. Сообщение m₂ передается по открытому каналу связи. Банкир, получив сообщение m₂ сначала расшифровывает его своим секретным ключом D, а затем открытым ключом вкладчика v_i. В результате получает:

m₃ º m₂^D mod N, m₄ º m₃^ei mod n_i. При этом m₄ = m, т.е. банкир B расшифровывает переданное ему распоряжение, при этом заодно и идентифицирует (узнает) вкладчика. Это похоже на проверку подписи вкладчика и иногда называется “электронная подпись”. Если вкладчик из открытой телефонной книги узнает, что банкир выбрал число N < n_i, то изменив порядок шифровки получит тот же результат, если банкир также изменит порядок расшифровки.

Пример.

Пусть банкир выбрал простые числа P = 23, Q = 11; вкладчик v: p = 13, q = 7. После чего и банкир и вкладчик вычисляют сначала функции Эйлера: j(23*11) = 220; j (13*7) = 72, затем выбирают открытые и вычисляют секретные ключи, например: E = 71, D = 31; e = 29, d = 5. Открыто публикуются числа: P*Q = 253, p*q = 91, E = 71, e = 29. Секретным ключом банкира является число D = 31, а секретным ключом вкладчика d = 5.

Пусть вкладчик решил дать секретное поручение банкиру в виде числа m = 41. Он шифрует его своим секретным ключом t, а затем открытым ключом банкира S:

41⁵ º 6 mod 91, 6⁷¹ º 94 mod 253. Это сообщение (число 94) по открытому каналу передается банкиру. Банкир расшифровывает сообщение сначала своим секретным ключом D, а затем открытым ключом вкладчика e:

94 ³¹ º 6 mod 253, 6²⁹ º 41 mod 77. Банкир принимает указание вкладчика в виде числа 41.

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

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

Часто для создания кода аутентичности используется алгоритм DSA (цифровая подпись). Последние биты результата используются как код аутентичности. Отличие от шифрования состоит в том, что код аутентичности является необратимым.

Односторонняя функция хэширования получает на вход сообщение М произвольной длины, а на выходе выдает хэш-код постоянной длины. В отличие от MAC функция хэширования не требует секретного ключа. В качестве функции хэширования часто используется SHA-1 [ 4 ].

3.4. Электронные платежи

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

Будем использовать три транзакции: снятие со счета, платеж и депозит.

При расчете электронными деньгами необходимо обеспечить:

- безопасность банка в виде невозможности подделать подпись банка или по набору подлинных банкнот, подписанных банком, создать новую фальшивую банкноту с банковской подписью,

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

Эти, на первый взгляд, парадоксальные требования обеспечиваются с помощью так называемой “затемненной” подписи в соответствии со схемой RSA.

Банк выбирает два простых числа p и q, открытый ключ e и вычисляет свой секретный ключ d из условия: ed ≡ 1 mod j (N = pq), затем открыто публикует N, e и некоторую одностороннюю функцию f: Z_N ® Z_N,

Генерация подписи банка состоит в применении к сообщению m функции дешифрования: s ≡ m^d mod N. В простейшем варианте электронной подписи ключом в d соответствует банкнота достоинством в 1 денежную единицу (рубль, сто рублей, тысяча и т.п.) Для получения нескольких денежных единиц в данном протоколе необходимо каждый раз обращаться в банк. Более сложный протокол обеспечивает получение электронной банкноты произвольного достоинства.

При снятии со счета покупатель выбирает некоторое случайное число nÎ Z_N и вычисляет f(n). Покупатель хочет получить о банка подпись на банкноте, т.е. f(n)^d. Однако если он просто пошлет в банк значение f(n), то нарушится условие неотслеживаемости, так как банк, снимая со счета покупателя сумму , сопоставит покупателю выданную (подписанную банком)

Банкноту. Для устранения этого покупатель выбирает некоторое случайное число r Î Z_N, r ¹ 0, вычисляет f(n)r^e mod N и посылает результат в банк. Банк вычисляет значение f(n)^dr mod N и возвращает его покупателю. Покупатель “снимает” затемняющий множитель r и получает подписанную банкноту в виде ( n, f(n)^d mod N). Этой банкнотой он будет рассчитываться с продавцом.

В транзакции платежа покупатель передает продавцу электронную банкноту ( n, f(n)^d mod N), подлинность которой тот может проверить самостоятельно, вычислив по n значение f(n), а затем проверив условие (f(n)^d )^е mod N) º f(n).

3.5. Аутентификация сообщений

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

Двумя важными задачами аутентификации являются:

- проверка того, что содержимое сообщения не было изменено,

- проверка того, что сообщение прибыло именно из того источника о котором информирует сообщение.

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

1. Аутентификация сообщения с помощью шифрования.

Если у отправителя и получателя имеются секретные ключи, то можно

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

2. Аутентификация сообщений без шифрования.

В ряде случаев само сообщение является открытым, но нужно прове-

рить, не изменялось ли оно. Например, при передаче компьютерных программ по интернету.

В этом случае к сообщению добавляется приставка ( тег ). К сообщению добавляется криптографическая контрольная сумма или код аутентичности сообщения постоянной длины MAC (Message Authentication Code). При этом отправитель А и получатель В используют общий секретный ключ K_AB. Отправитель сообщения вычисляет MAC_M = F (K_AB, M) и посылает сообщение M с приставкой MAC_M. Получатель по сообщению и ключу вычисляет MAC_M и сравнивает его с пришедшим. Если они совпадают, то можно сделать выводы:

а) Сообщение не было изменено,

в) Сообщение пришло из указанного источника,

с) Если в сообщении имеется порядковый номер, то можно утверждать, что порядок отправки сообщений также не нарушен.

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

Пусть p и q – простые числа, причем q делит p - 1. Например, p = 23, q = 11, или p = 59, q = 29. Пусть выбрано g такое, что g^q º 1 mod p. для первого примера g = 2, так как 2¹¹ º 1 mod 23, для второго примера g = 4, так как 4²⁹ º 1 mod 59.

Алиса выбирает некоторое случайное число x из диапазона чисел: {0,1,2,…q-1} и вычисляет ключ y = g^-x mod p, который открыто публикует.

Далее Алиса выбирает случайное число k из множества {0,1,2,…q-1}, вычисляет r = g^k mod p и r отправляет к Бобу.

Боб выбирает некоторый случайный запрос e из множества

{0,1,2,…2^t-1}, где t – некоторое целое и посылает e к Алисе.

Алиса вычисляет s = k + xe mod q и посылает s к Бобу на проверку.

Боб проверяет соотношение: r = g^sy^e mod p и если оно выполняется, принимает доказательство Алисы, что она владеет секретным ключом, в противном случае доказательство отвергается.

Пример. Пусть p = 59, q = 29, тогда можно взять g = 4. Случайное число x, выбираемое Алисой, x = 9, тогда y = 4^-9º 17 mod 59. Число 17 является открытым ключом Алисы.

Далее Алиса выбирает k например, k = 12, вычисляет r = 4¹² º 35 mod 59 и число r = 35 посылается к Бобу. Пусть случайный запрос Боба e = 10, который он посылает к Алисе. Алиса вычисляет: s = 12 + 9*10 mod 29 º 15 mod 29. Число s = 15 посылается к Бобу.

Боб проверяет соотношение: 4¹⁵17¹⁰º 57*12 º 35 mod 59. Поскольку r = 35, то доказательство принимается.

В рассмотренном случае автор только доказывал, что владеет некоторым

секретом.

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

При снятии со счета у банка остается некоторое значение f(n)^d r mod N), которое из-за затемняющего множителя r представляет собой просто случайное число.

Пример.

Пусть банком выбраны простые числа p = 17 и q = 19. Тогда N = 323, j (323) = 288. Открытый ключ выберем, например, в виде e = 11, секретный (вычисленный) ключ d = 131 и односторонняя функция, например, f(x) = x² mod 323.

Публикуются открытые ключи N, e и односторонняя функция f(x).

При снятии со счета покупатель выбирает случайное число, например, n = 25, вычисляет f(25) = 25² º 302 mod 323, выбирает затемняющий множитель, например, r = 20 и вычисляет f(n)r^e mod N, которое в данном случает будет равно 302*20¹¹ mod 323 º 74 mod 323 и посылает в банк число 74. Банк возводит полученное число в степень d = 131 и получает 74¹³¹ º 63 mod 323. Покупатель снимает затемняющий множитель r = 20, решая сравнение 63/20 mod 323 º 310. Таким образом банкнота, подписанная банком имеет вид ( 25, 310). Эта банкнота отправляется продавцу. Если продавец хочет самостоятельно проверить подлинность банкноты, он может вычислить f(25) = 25 ² º 302 mod 323 и затем 310 ¹¹ º 302 mod 323. Совпадение полученных значений свидетельствует о подлинности банкноты. Однако для гарантии того, что эта банкноты не использовалась в других платежах, продавец отправляет ее в банк, который по реестру проверяет, что она впервые используется в платеже и зачисляет одну денежную единицу на счет продавца.