Алгоритмы асимметричного шифрования

Обсуждение криптоанализа

Можно определить четыре возможных подхода для криптоанализа алгоритма RSA:

Лобовая атака: перебрать все возможные закрытые ключи.

Разложить n на два простых сомножителя. Это даст возможность вычислить φ(n)=(p–1)•(q–1) и d=e–1 (mod φ(n)).

Определить φ(n) непосредственно, без начального определения р и q. Это также даст возможность определить d=e–1(mod φ(n)).

Определить d непосредственно, без начального определения φ(n).

Защита от лобовой атаки для RSA и ему подобных алгоритмов состоит в использовании большой длины ключа. Таким образом, чем больше битов в е и d, тем лучше. Однако, так как вычисления, связанные с возведением в степень, необходимы как при создании ключей, так и при шифровании / расшифровании, чем больше размер ключа, тем медленнее работает система.

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

$$L (n) = esqrt ^{(lnn \cdot ln (lnn))}$$

Пока не разработаны лучшие алгоритмы разложения числа на простые множители, можно считать, что величина n от 100 до 200 цифр в настоящее время является достаточно безопасной. На современном этапе считается, что число из 100 цифр может быть разложено на множители за время порядка двух недель. Для дорогих конфигураций (т.е. порядка $10 млн) число из 150 цифр может быть разложено приблизительно за год. Разложение числа из 200 цифр находится за пределами вычислительных возможностей. Например, даже если вычислительный уровень в 10¹² операций в секунду достижим, что выше возможностей современных технологий, то потребуется свыше 10 лет для разложения на множители числа из 200 цифр с использованием существующих алгоритмов.

Для известных в настоящее время алгоритмов задача определения φ(n) по данным е и n, по крайней мере сопоставима по времени с задачей разложения числа на множители.

Для того чтобы избежать выбора значения n, которое могло бы легко раскладываться на сомножители, на р и q должно быть наложено много дополнительных ограничений:

р и q должны друг от друга отличаться по длине только несколькими цифрами. Таким образом, оба значения р и q должны быть от 1075 до 10100.

Оба числа (р – 1) и (q – 1) должны содержать большой простой сомножитель.

НОД(p–1, q–1) должен быть маленьким.

Алгоритм Диффи-Хеллмана

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

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

Алгоритм основан на трудности вычислений дискретных логарифмов. Дискретный логарифм определяется следующим образом. Вводится понятие примитивного корня простого числа Q как числа, чьи степени создают все целые от 1 до Q–1. Это означает, что если А является примитивным корнем простого числа Q, тогда числа

$$A (mod\; Q), A2 (mod\; Q), . . . , AQ – 1 (mod\; Q)$$

являются различными и состоят из целых от 1 до Q–1 возможно с некоторыми перестановками.

В этом случае для любого целого B<Q и примитивного корня A простого числа Q можно найти единственную экспоненту Х, такую, что

$$Y = A^Х (mod\; Q), где 0 \leq X \leq (Q – 1)$$

Экспонента X называется дискретным логарифмом, или индексом Y, по основанию A (mod Q). Это обозначается как

$$ind_{A, Q} (Y)$$

Теперь опишем алгоритм обмена ключей Диффи-Хеллмана.

Общеизвестные элементы

Q - Простое число

A - A<Q и A является примитивным корнем Q

Предполагается, что существуют два известных всем числа: простое число Q и целое A, которое является примитивным корнем Q.

Создание пары ключей пользователем I

Выбор случайного числа Хi - закрытый ключ

$$X_i< Q$$

Вычисление числа Yi - открытый ключ

$$Y_i = A^{Xi} (mod \; Q)$$

Создание открытого ключа пользователем J

Выбор случайного числа Хj - закрытый ключ

$$X_j< Q$$

Вычисление случайного числа Yj - открытый ключ

$$Y_j = A^{Xj} (mod \; Q)$$

Теперь предположим, что пользователи I и J хотят обменяться ключом для алгоритма симметричного шифрования. Пользователь I выбирает случайное число Хi< Q и вычисляет Yi = AXi (mod Q). Аналогично пользователь J независимо выбирает случайное целое число Хj< Q и вычисляет Yj= AXj (mod Q).

Пользователи I и J обмениваются открытыми ключами Yi и Yj

Каждая сторона держит значение Х в секрете и делает значение Y доступным для другой стороны.

Создание общего секретного ключа пользователем I

$$K = (Y_j)^{ Xi }(mod\; Q)$$

Создание общего секретного ключа пользователем J

$$K = (Y_i)^{ Xj }(mod\; Q)$$

Теперь пользователь I вычисляет ключ К = (Yj)Xi (mod Q), и пользователь J вычисляет ключК = (Yi)Xj (mod Q). В результате оба получат одно и то же значение:

$$K = (Y_j)^{Xi} (mod\; Q)\\ = (A^{X_j} mod\; Q)^{Xi} (mod\; Q)\\ =(A^{X_j})^{X_i} (mod\; Q) \\ = A^{X_jX_i} (mod\; Q)\\ = (A^{X_i})^{X_j} (mod\; Q)\\ = (A^{X_i} mod\; Q)^{X_j} (mod\; Q)\\ = (Y_i)^{X_j} (mod\; Q)$$

по правилам модульной арифметики

Таким образом, две стороны обменялись секретным ключом. Так как Хi и Хj являются закрытыми, противник может получить только следующие значения: Q, A, Yi и Yj. Для вычисления общего ключа атакующий должен взломать дискретный логарифм, т.е. вычислить

$$X_j = ind _{A,Q} (Y_j)$$

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

Следует заметить, что данный алгоритм уязвим для атак типа "man-in-the-middle". Если противник может осуществить активную атаку, т.е. имеет возможность не только перехватывать сообщения, но и заменять их другими, он может перехватить открытые ключи участников Yi и Yj, создать свою пару открытого и закрытого ключа (Xоп, Yоп)и послать каждому из участников свой открытый ключ. После этого каждый участник вычислит ключ, который будет общим с противником, а не с другим участником. Если нет аутентификации хотя бы одной из сторон внешним по отношению к алгоритму Диффи-Хеллмана способом, то участники не смогут обнаружить подобную подмену.

Стандарт цифровой подписи DSS

Национальный институт стандартов и технологии США (NIST) разработал федеральный стандарт цифровой подписи DSS. Для создания цифро-вой подписи используется алгоритм DSA (Digital Signature Algorithm). В качестве хэш-алгоритма стандарт предусматривает использование алго-ритма SHA-1 (Secure Hash Algorithm). DSS первоначально был предложен в 1991 году и пересмотрен в 1993 году в ответ на публикации, касающиеся безопасности его схемы.

Подход DSS

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

Рассмотрим отличия цифровых подписей, создаваемых DSS, от цифровых подписей, создаваемых такими алгоритмами как RSA.

(рис 4.4) Создание и проверка подписи с помощью алгоритма RSA (рис 4.5) Создание и проверка подписи с помощью стандарта DSS

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

В DSS также используется сильная хэш-функция. Хэш-код является входом функции подписи вместе со случайным числом k, созданным для этой конкретной подписи. Функция подписи также зависит от закрытого ключа отправителя KRА и множества параметров, известных всем участникам. Можно считать, что это множество состоит из глобального открытого ключа KU_G. Результатом является подпись, состоящая из двух компонент, обозначаемых какS и R.

Для проверки подписи получатель также создает хэш-код полученного сообщения. Этот хэш-код вместе с подписью является входом в функцию верификации. Функция верификации зависит от глобального открытого ключа KU_G и от открытого ключа отправителя KU_А. Выходом функции верификации является значение, которое должно равняться компоненте R подписи, если подпись корректна. Функция подписи такова, что только отправитель, знающий закрытый ключ, может создать корректную подпись.

Теперь рассмотрим детали алгоритма, используемого в DSS.

Алгоритм цифровой подписи DSS

DSS основан на трудности вычисления дискретных логарифмов и базируется на схеме, определенной ElGamal и Schnorr.

Общие компоненты группы пользователей

Существует три параметра, которые являются открытыми и могут быть общими для большой группы пользователей.

160-битное простое число q, т.е. 2159< q < 2160.

Простое число р длиной между 512 и 1024 битами должно быть таким, чтобы q делилось на (р – 1), т.е. 2L-1< p < 2L, где 512 < L < 1024 и (p-1)/q является целым.

g = h(p-1)/q (mod p), где h является целым между 1 и (р-1), и g должно быть больше единицы.

Зная эти значения, отправитель выбирает закрытый ключ и создает открытый ключ.

Закрытый ключ отправителя

Закрытый ключ х должен быть числом между 1 и (q-1)и должен быть выбран случайно или псевдослучайно.

x - случайное или псевдослучайное целое, 0 < x < q

Открытый ключ отправителя

Открытый ключ вычисляется следующим образом:

$$у = g^x (mod \;p)$$

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

Случайное число, уникальное для каждой подписи.

k - случайное или псевдослучайное целое, 0<k<q, уникальное для каждого подписывания.

Подписывание

Для создания подписи отправитель вычисляет две величины, r и s, которые являются функцией от компонент открытого ключа (p, q, g), закрытого ключа пользователя х, хэш-кода сообщения Н(М) и целого k, которое должно быть создано случайно или псевдослучайно и должно быть уникальным при каждом подписывании.

$$r = g^k ((mod\; p) mod\; q)\\ s = (k^{-1}\cdot (H (M) + x\cdotr)) (mod\; q)$$

Подпись равна (r, s).

Проверка подписи

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

$$w = s^{-1} (mod\; q)\\ u1 = (H (M)\cdot w) (mod\; q)\\ u2 = r\cdot w\; mod\; q\\ v = ((g^{u1}\cdot y^{u2}) (mod \;p)) (mod \;q)$$

Подпись корректна, если v = r

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

Лемма 1. Для любого целого t, если

$$g = h^{(p-1)/q}(mod \;p)\\ то\; g^t (mod \; p) = g^{t mod\; q}(mod\; p)$$

По теореме Ферма, так как h является взаимнопростым с p, то

$$h^{p-1}(mod\; p) = 1.$$

Следовательно, для любого неотрицательного целого n

$$g^{nq}(mod p) = (h^{(p-1)/q}(mod\; p))^{nq}(mod\; p)\\ = h^{((p-1)/q) nq}(mod\; p)\\ = h^{(p-1)n}(mod\; p)\\ = ((h^{(p-1)}(mod p))^n) (mod \;p)\\ = 1^n(mod\; p) = 1$$

Таким образом, для неотрицательных целых n и z мы имеем

$$g^{nq+z} (mod \;p) = (g^{nq \cdot gz)}(mod \;p)\\ = (((g^{nq}(mod p)) \cdot (g^z(mod \; p ))) (mod \;p)\\ = g^z(mod \;p)$$

Любое неотрицательное целое t может быть представлено единственным способом как t = nq + z, где n и z являются неотрицательными целыми и 0<z<q. Таким образом z = t (mod q).

Лемма 2. Для неотрицательных чисел a и b: g(a mod q + b mod q)(mod p) = g(a+b) mod q(mod p).

По лемме 1 мы имеем

$$g^{(a mod \;q + b mod \;q)}(mod\; p) = g^{(a mod \;q + b mod\; q) mod \;q(mod\; p)\\ = g^{(a + b) mod\; q}(mod\; p)$$

Лемма 3. y(rw) mod q(mod p) = g(xrw) mod q(mod p)

По определению y = gx(mod p). Тогда:

$$y^{(rw) mod q}(mod\; p) = (g^{x}(mod\; p))^{(rw) mod q}(mod\; p)\\ = g^{x ((rw)\; mod \; q)}(mod\; p)\; - \;по\; правилам \;модульной\; арифметики\\ = g^{(x\; ((rw\; mod \;q)))\; mod\; q}(mod p)\; -\; по\; лемме \;1\\ = g^{(xrw)\; mod\; q}(mod\; p)$$

Лемма 4. ((H(M) + x•r) • w) (mod q) = k

По определению s = (k-1• (H(M) + x•r)) (mod q). Кроме того, так как q является простым, любое неотрицательное целое меньшее q имеет мультипликативную инверсию. Т.е. (k •k-1) (mod q = 1). Тогда:

$$(k\cdot s) (mod\; q)= (k \cdot (k^{-1}\cdot (H(M) + x\cdot r)) (mod\; q)) (mod\; q)\\ = (k \cdot (k^{-1}(H(M) + x\cdotr))) (mod\; q)\\ = ((k \cdot k^{-1}) (mod \;q) \cdot ((H(M) + x\cdot r) (mod\; q) (mod\; q)\\ = (H(M) + x\cdot r) (mod\; q)$$

По определению w = s-1(mod q), следовательно, (w•s) (mod q)=1. Следовательно:

$$((H(M) + x\cdot r) w) (mod\; q) = ((H(M) + x\cdot r) (mod \;q) \cdot w (mod \;q)) (mod q)\\ = ((k \cdot s) (mod\; q) \cdot w (mod \;q)) (mod\; q)\\ = (k\cdot w\cdot s) (mod\; q)\\ = (k (mod\; q) \cdot (w \cdot s) (mod \; q))) (mod \; q)\\ = k (mod\; q)$$

Так как 0 < k < q, то k (mod q) = k.

Теорема. Используя введенные выше определения для v и r, докажем, что v=r.

$$v= ((g^{u1}\cdot y^{u2}) (mod \;p)) (mod \;q)\\ = (g^{(H(M) w) (mod \;q)} \cdot y^{(rw) (mod\; q))} (mod \;p)) (mod \;q)\\ = (g^{(H(M) w) (mod\; q)} \cdot g^{(xrw)(mod\; q))} (mod \;p)) (mod \;q)\\ = (g^{(H(M) w) (mod\; q) + (xrw) (mod\; q))} (mod \;p)) (mod \;q)\\ = (g^{(H(M) w + xrw)(mod\; q))} (mod \;p)) (mod \;q)\\ = (g^{w (H(M) + xr) mod \;q)} (mod \;p)) (mod \;q)\\ = (g^k(mod\; p))\; (mod\; q)\\ = r$$

Отечественный стандарт цифровой подписи ГОСТ 3410

В отечественном стандарте ГОСТ 3410, принятом в 1994 году, исполь-зуется алгоритм, аналогичный алгоритму, реализованному в стандарте DSS. Оба алгоритма относятся к семейству алгоритмов ElGamal.

В стандарте ГОСТ 3410 используется хэш-функция ГОСТ 3411, которая создает хэш-код длиной 256 бит. Это во многом обуславливает требования к выбираемым простым числам p и q:

р должно быть простым числом в диапазоне 2509 < p < 2512 либо 21020 < p < 21024

q должно быть простым числом в диапазоне 2254 < q < 2256

q также должно быть делителем (р-1).

Аналогично выбирается и параметр g. При этом требуется, чтобы gq(mod p ) = 1.

В соответствии с теоремой Ферма это эквивалентно условию в DSS, что g = h(p-1)/q(mod p).

Закрытым ключом является произвольное число х

$$0 < x < q$$

Открытым ключом является число y

$$y = g^x(mod\; p)$$

Для создания подписи выбирается случайное число k

$$0 < k < q$$

Подпись состоит из двух чисел (r, s), вычисляемых по следующим формулам:

$$r = (g^k \;mod\; p) mod\; q\\ s = (kH(M) + xr) mod\; q$$

Еще раз обратим внимание на отличия DSS и ГОСТ 3410.

Используются разные хэш-функции: в ГОСТ 3410 применяется отечественный стандарт на хэш-функции ГОСТ 3411, в DSS используется SHA-1, которые имеют разную длину хэш-кода. Отсюда и разные требования на длину простого числа q: в ГОСТ 3410 длина q должна быть от 254 бит до 256 бит, а в DSS длина q должна быть от 159 бит до 160 бит.

По-разному вычисляется компонента s подписи. В ГОСТ 3410 компонента s вычисляется по формуле

$$s = (k \cdot H(M) + x \cdot r) (mod\; q)$$

В DSS компонента s вычисляется по формуле

$$s = (k^{-1} \cdot (H(M) + x\cdot r)) (mod \;q)$$

Последнее отличие приводит к соответствующим отличиям в формулах для проверки подписи.

Получатель вычисляет

$$w = H(M)^{-1} (mod\; q)\\ u1 = w \cdot s (mod\; q)\\ u2 = (q-r) \cdot w (mod \;q)\\ v = ((g^{u1}\cdot y^{u2}) mod\; p) (mod\; q)$$

Подпись корректна, если v = r.

Структура обоих алгоритмов довольно интересна. Заметим, что значение r совсем не зависит от сообщения. Вместо этого r есть функция от k и трех общих компонент открытого ключа. Мультипликативная инверсия k(mod p)(в случае DSS) или само значение k (в случае ГОСТ 4310) подается в функцию, которая, кроме того, в качестве входа имеет хэш-код сообщения и закрытый ключ пользователя. Эта функция такова, что получатель может вычислить r, используя входное сообщение, подпись, открытый ключ пользователя и общий открытый ключ.

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

Другое важное замечание заключается в том, что экспоненциальные вычисления при создании подписи необходимы только для gk(mod p). Так как это значение от подписываемого сообщения не зависит, оно может быть вычислено заранее. Пользователь может заранее просчитать некоторое количество значений r и использовать их по мере необходимости для подписи документов. Еще одна задача состоит в определении мультипликативной инверсии k-1 (в случае DSS). Эти значения также могут быть вычислены заранее.

Подписи, созданные с использованием стандартов ГОСТ 3410 или DSS, называются рандомизированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будут создаваться разные значения подписи (r,s), поскольку каждый раз будет использоваться новое значение k. Подписи, созданные с применением алгоритма RSA, называются детерминированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будет создаваться одна и та же подпись.

Криптография с использованием эллиптических кривых

Математические понятия

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

В общем случае уравнение эллиптической кривой Е имеет вид:

$$y^2+ axy + by = x^3+ cx^2+ dx + e$$

В качестве примера рассмотрим эллиптическую кривую Е, уравнение которой имеет вид:

$$y^2+ y = x^3– x^2$$

На этой кривой лежат только четыре точки, координаты которых являются целыми числами. Это точки

А (0, 0), В (1, -1), С (1, 0) и D (0, -1)

(рис 4.6) Пример эллиптической кривой с четырьмя точками

Для определения операции сложения двух точек на эллиптической кривой сделаем следующие предположения:

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

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

Если три точки эллиптической кривой лежат на прямой линии, то их сумма есть О.

(рис 4.7) Сложение точек на эллиптической кривой

Введем следующие правила сложения точек на эллиптической кривой:

Точка О выступает в роли нулевого элемента. Так, О = –О, и для любой точки Р на эллиптической кривой Р + О = Р.

Вертикальная линия пересекает кривую в двух точках с одной и той же координатой х S=(x,y) и T=(x,-y). Эта прямая пересекает кривую и в бесконечно удаленной точке. Поэтому Р1 + Р2+ О = О и Р1 = –Р2.

Чтобы сложить две точки P и Q с разными координатами х, следует провести через эти точки прямую и найти точку пересечения ее с эллиптической кривой. Если прямая не является касательной к кривой в точках P или Q, то существует только одна такая точка, обозначим ее S. Согласно нашему предположению

P + Q + S = О

Следовательно,

P + Q = –S или

P + Q = T

Если прямая является касательной к кривой в какой-либо из точек P или Q, то в этом случае следует положить S=P или S=Q соответственно.

Чтобы удвоить точку Q, следует провести касательную в точке Q и найти другую точку пересечения S с эллиптической кривой. Тогда Q + Q = 2?Q = -S.

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

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

$$y^2= x^3+ ax + b (mod\; p)$$

Такую кривую будем обозначать Ep(a,b). При этом числа а и b должны быть меньше р и должны удовлетворять условию $$4a^3+ 27b^2(mod\; p) \ne 0$$. Множество точек на эллиптической кривой вычисляется следующим образом.

Для каждого такого значения х, что $$0 \leq х \leq р$$, вычисляется $$x^3+ ax + b(mod\; p)$$.

Для каждого из полученных таким образом значений выясняется, имеет ли это значение целочисленный квадратный корень. Если нет, то в Ep (a,b) нет точек с этим значением х. Если целочисленный корень существует, имеется два значения y, равные этим значениям квадратного корня. Исключением является случай, когда y равен нулю. Эти значения (x,y) и будут точками Ep(a,b).

Алгоритм цифровой подписи на основе эллиптических кривых ECDSA

Создание ключей:

Выбирается эллиптическая кривая Ep(a,b). Число точек на ней должно делиться на большое целое n.

Выбирается точка Р ∈ Ep(a,b).

Выбирается случайное число d ∈ [1,n-1].

Вычисляется Q = d×P.

Закрытым ключом является d, открытым ключом (E, P, n, Q).

Создание подписи:

Выбирается случайное число k ∈ [1,n-1].

Вычисляется k×P = (x1, y1) и r = x1 (mod n). Проверяется, чтобы r не было равно нулю, так как в этом случае подпись не будет зависеть от закрытого ключа. Если r = 0, то выбирается другое случайное число k.

Вычисляется

$$k^{-1}\; mod\; n$$

Вычисляется

$$s = k^{-1}\cdot (Н(M) + d\cdot r) (mod\; n)$$

Проверяется, чтобы s не было равно нулю, так как в этом случае необходимого для проверки подписи числа s-1(mod n) не существует. Если s=0, то выбирается другое случайное число k.

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

Проверка подписи:

Проверяется, что целые числа r и s принадлежат диапазону чисел [0,n-1]. В противном случае результат проверки отрицательный, и подпись отвергается.

Вычисляется

$$w = s^{-1}(mod \; n) \;и\; H(M)$$

Вычисляется

$$u1 = H(M) \cdot w (mod \;n)\\ u2 = r \cdot w (mod \;n)$$

Вычисляется

$$u_1\times P + u_2\times Q = (x_0, y_0)\\ v = x_0 (mod\; n)$$

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

Инфраструктура Открытого Ключа

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

Сначала рассмотрим уязвимости, связанные с открытым ключом, и необходимость создания Инфраструктуры Открытого Ключа (Public Key Infrastructure - PKI). Затем определим ключевые термины, используемые в Инфраструктуре Открытого Ключа.

Одним из требований к алгоритмам цифровой подписи является требование, чтобы было вычислительно невозможно, зная открытый ключ KU, определить закрытый ключ KR. Казалось бы, открытый ключ KU можно распространять по небезопасным сетям и хранить в небезопасных репози-торях. Но при этом следует помнить, что при использовании цифровой подписи необходимо быть уверенным, что субъект, с которым осуществляется взаимодействие с использованием алгоритма открытого ключа, является собственником соответствующего закрытого ключа. В противном случае возможна атака, когда оппонент заменяет открытый ключ законного участника своим открытым ключом, оставив при этом идентификатор законного участника без изменения. Это позволит ему создавать подписи от имени законного участника и читать зашифрованные сообщения, послан-ные законному участнику, используя для этого свой закрытый ключ, соответствующий подмененному открытому ключу. Для предотвращения такой ситуации следует использовать сертификаты, которые являются структу-рами данных, связывающими открытый ключ с субъектом. Для связывания необходимо наличие доверенного сертификационного центра (Certification Authority – СА), который проверяет идентификацию субъекта и подписы-вает его открытый ключ и некоторую дополнительную информацию своим закрытым ключом.

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

Основным понятием Инфраструктуры Открытого Ключа является понятие сертификата.

Сертификат участника, созданный СА, имеет следующие характеристики:

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

Никто другой, кроме данного сертификационного центра, не может модифицировать сертификат без обнаружения этого проверяющей стороной.

Мы будем рассматривать сертификаты Х.509, хотя существует доста-точно много сертификатов других форматов.

Стандарт Х.509 первоначально являлся частью стандарта Х.500 и описывал основные требования к аутентификации в Каталогах Х.500. Но Х.509 используется не только в контексте сервиса Каталога Х.500. Сертификаты, определяемые данным стандартом, используются практически всеми программными продуктами, относящимися к обеспечению сетевой безопасности.

Стандарты ITU-TX.509 и ISO/IEC 9594-8, которые впервые были опубликованы в 1988 году как часть рекомендаций Х.500 Директории, определили формат сертификата Х.509. Формат сертификата в стандарте 1988 года называется форматом версии 1 (v1). Стандарт Х.500 был пересмотрен в 1993 году, в результате чего было добавлено несколько новых полей в формат сертификата Х.509, который был назван форматом версии 2 (v2).

Опыт реализации первой и второй версий говорит о том, что форматы сертификата v1 и v2 имеют ряд недостатков. Самое важное, что для хранения различной информации требуется больше полей. В результате ISO/IEC, ITU-T и ANSI X9 разработали формат сертификата Х.509 версии 3 (v3). Формат v3 расширяет формат v2, обеспечивая возможность добавления дополнительных полей расширения. Конкретные типы полей расширения могут быть определены в стандартах или определены и зарегистрированы любой организацией или сообществом. В 1996 году стандартизация базового формата v3 была завершена.

Стандарт ISO/IEC, ITU-T и ANSI X9 являются очень общими, чтобы применять их на практике. Для того чтобы разрабатывать интероперабельные реализации, использующие сертификаты Х.509 v3, необходимо четко специфицировать формат сертификата Х.509 v3. Специалисты IETF разработали профиль сертификата X.509 v3 и опубликовали его в RFC 3280.

Основные элементы сертификата представлеы в таблице 1.8.

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

$$СА << A >>$$

- сертификат пользователя А, выданный сертификационным центром СА.

СА подписывает сертификат своим закрытым ключом. Если соответствующий открытый ключ известен проверяющей стороне, то она может проверить, что сертификат, подписанный СА, действителен.

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

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

Таблица 4.1

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

Теперь предположим, что А получил сертификат от уполномоченного органа СА₁, и В получил сертификат от уполномоченного органа СА₂. Если А не знает безопасным способом открытый ключ СА₂, то сертификат В, выданный СА₂, для него бесполезен. А может прочитать сертификат В, но не в состоянии проверить подпись. Тем не менее, если два СА могут безопасно обмениваться своими открытыми ключами, возможна следующая процедура для получения А открытого ключа В.

1. А получает сертификат СА₂, подписанный СА₁. Так как А знает открытый ключ СА₁ надежным способом, А может получить открытый ключ СА₂ из данного сертификата и проверить его с помощью подписи СА₁ в сертификате.

2. Затем А получает сертификат В, подписанный СА₂. Так как А теперь имеет открытый ключ СА₂ надежным способом, А может проверить подпись и безопасно получить открытый ключ В.

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

$$СА_1<< СА_2>> СА_2<< B>>$$

Аналогично В может получить открытый ключ А с помощью такой же цепочки:

$$СА2<< СА1 >> СА1<< А>>$$

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

$$СА_1<< СА_2>> СА_2 << СА_3>> . . . СА_N<< B >>$$

В этом случае каждая пара СА в цепочке (СА_i , СА_i+1 ) должна создать сертификаты друг для друга.

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

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

Х.509 определяет следующий способ отмены сертификата. Предполагается, что каждый СА периодически выпускает подписанную структуру данных, называемую списком отмененных сертификатом (Certificate Revo-cation List – CRL). CRL является помеченным временем списком, который подписан СА или специальным выпускающим CRL и в котором перечис-лены отмененные на текущий момент сертификаты с неистекшим периодом действительности, указанным в сертификате. Данный список становится свободно доступен в открытом репозитории. Каждый отмененный сертификат идентифицируется в CRL своим серийным номером. Когда использующая сертификат система получает сертификат, эта система не только проверяет подпись сертификата и действительность, но также полу-чает свежий CRL и проверяет, не находится ли в этом CRL серийный номер сертификата. Понятие "свежий" может зависеть от локальной политики, но обычно означает самый последний выпущенный CRL. Новый CRL выпускается регулярно (например, каждый час, день или неделю). При получении уведомления об отмене запись добавляется в CRL.

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

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

Как и формат сертификата Х.509 v3, для того, чтобы обеспечить интероперабельность реализаций различных производителей, необходимо иметь строгий формат Х.509 CRLv2. Существуют также специальные про-токолы и соответствующие им форматы сообщений, поддерживающих on-line оповещения об отмене. On-line методы оповещения об отмене могут применяться в некоторых окружениях как альтернатива CRL. On-line проверка отмены может существенно уменьшить промежуток между отправ-кой сообщения об отмене и получением этой информации проверяющей стороной. После того как СА получает сообщение об отмене, любой запрос к on-line сервису будет корректно отображать действительность сертификата. Однако эти методы навязывают новые требования безопасности: проверяющая сторона должна доверять on-line сервису действительности, в то время как репозиторий не обязательно должен быть доверяемым.

В Инфраструктуре Открытого Ключа используются следующие термины и понятия.

Public Key Infrastructure (PKI)– инфраструктура открытого ключа – это множество аппаратуры, ПО, людей, политик и процедур, необходимых для создания, управления, хранения, распределения и отмены сертифика-тов, основанных на криптографии с открытым ключом.

End Entity (ЕЕ)– конечный участник, для которого выпущен данный сертификат. Важно заметить, что здесь под конечными участниками подразумеваются не только люди и используемые ими приложения, но также и исключительно сами приложения (например, для безопасности уровня IP).

Certificate Authority (CA)– сертификационный или удостоверяющий центр – это уполномоченный орган, который создает и подписывает сертификаты открытого ключа. Дополнительно СА может создавать пары закрытый/открытый ключ для конечного участника. Важно заметить, что СА отвечает за сертификаты открытого ключа в течение всего времени их жизни, а не только в момент выпуска.

Public Key Certificate (PKC)– сертификат открытого ключа или просто сертификат – это структура данных, содержащая открытый ключ конечного участника и другую информацию, которая подписана закрытым ключом СА, выпустившим данный сертификат.

Registration Authority (RA)– регистрационный центр - необязательный участник, ответственный за выполнение некоторых административных задач, необходимых для регистрации конечных участников. Такими задачами могут быть: подтверждение идентификации конечного участника; проверка значений, которые будут указаны в создаваемом сертификате; проверка, знает ли конечный участник закрытый ключ, соответствующий открытому ключу, указанному в сертификате. Заметим, что RA сам также является конечным участником.

Причины, по которым могут создаваться RA, разделяют на технические и организационные. К техническим относятся следующие причины:

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

Не все конечные участники могут иметь возможность опубликовать свои сертификаты; для этого может использоваться RA.

RA может иметь возможность выпускать подписанные запро-ы отмены от имени конечного участника, тогда как конечный участник не всегда имеет возможность сделать это (например, если пара ключей потеряна).

Организационные причины для использования RA следующие:

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

Наличие RА может уменьшить число необходимых СA.

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

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

Выпускающий CRL- необязательный компонент, которому СА делегирует функции опубликования списков отмененных сертификатов.

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

Certificate Practice Statement (CPS)– утверждение об используемой практике, в соответствии с которой сотрудники сертификационного центра выпускают сертификаты открытого ключа.

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

Root CA – СА, которому непосредственно доверяет конечный участник; это означает безопасное получение открытого ключа корневого СА, требующее некоторых внешних по отношению к PKI шагов. Этот термин не означает, что корневой СА обязательно должен быть вершиной иерархии. Заметим, что термин "доверенный якорь" имеет то же значение, что и корневой СА в данном случае.

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

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

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

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

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

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

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