Протокол электронной подписи

electronic signature protocol

Связанные статьи: протокол электронно-цифровой подписи (словарь)

Определение 1 протокол электронной подписи; см. также [1]

Предположим, что каждому числу $n\in\mathbb N$ (играющему роль параметра стойкости) поставлено в соответствие множество $M_n\subseteq\{0,1\}^*$, называемое пространством сообщений при данном $n$. Протоколом электронной подписи называется тройка полиномиальных вероятностных алгоритмов $(\mathcal G,\mathcal S,\mathcal V)$, называемых алгоритмами генерации ключей, генерации подписей и проверки подписей соответственно, таких, что

$\mathop{\mathrm{supp}}\mathcal G(1^n)\subseteq\{0,1\}^*\times\{0,1\}^*$ для любого $n\in\mathbb N$;

при всех $m\in M_n$, $(s,v)\in\mathop{\mathrm{supp}}\mathcal G(1^n)$ ($n\in\mathbb N$) всегда выполняется равенство $\mathcal V(1^n,v,m,\mathcal S(1^n,s,m))=1$.

Схема применения протокола электронной подписи из определения 1 может выглядеть следующим образом. Пусть $n\in\mathbb N$ — параметр стойкости. Подписывающий генерирует $(s,v)\leftarrow\mathcal G(1^n)$ (см. условие 1 определения 1). В этой паре $s$ служит для генерации подписей, а $v$ — для их проверки. Поэтому $s$ хранится подписывающим в секрете, а $v$ публикуется. Подписью для произвольного сообщения $m\in M_n$, вычисляемой подписывающим, является выходное значение алгоритма $\mathcal S$ на входе $(1^n,s,m)$. Алгоритм $\mathcal V$ служит для проверки подписей. А именно, $w\in\{0,1\}^*$ называется допустимой подписью для сообщения $m\in M_n$ относительно открытого ключа $v$, если всегда выполняется равенство $\mathcal V(1^n,v,m,w)=1$ (означающее, что подпись принята). Таким образом, условие 2 определения 1 означает, что если $(s,v)\in\mathop{\mathrm{supp}}\mathcal G(1^n)$, то подпись для произвольного сообщения, сгенерированная алгоритмом $\mathcal S$ с использованием секретного ключа $s$, является допустимой для этого сообщения относительно открытого ключа $v$.

Вообще говоря, для применения протоколов электронной подписи на практике необходимо наличие процедуры арбитража, позволяющей разрешать споры между участниками. Например, предположим, что некий подписывающий, имеющий открытый ключ $v$, отказывается признать своей подпись $w$ для сообщения $m$. В этом случае процедура арбитража может заключаться в следующем. Арбитр требует от подписывающего предъявить секретный ключ $s$ и строки случайных битов $r$ и $r’$, использованные при генерации пары $(s,v)$ алгоритмом $\mathcal G$ и подписи $w$ алгоритмом $\mathcal S$ соответственно. Если подписывающий отказывается это сделать, то арбитр признает подпись подлинной. В противном случае подпись признается подлинной тогда и только тогда, когда $(s,v)=\mathcal G(1^n;r)$ и $w=\mathcal S(1^n,s,m;r’)$.

Стойкость протоколов электронной подписи определяется, естественно, против конкретной угрозы на основе конкретной атаки. Иногда стойкость имеет место лишь в случае, когда число сообщений, подписываемых с использованием одного и того же секретного ключа, ограничено сверху некоторым числом, зависящим от параметра стойкости $n$ (см., в частности, пример 3 ниже). Перечислим основные угрозы и атаки (в порядке возрастания силы) для протоколов электронной подписи (см. также [2]). Эти угрозы и атаки описываются в соответствующих статьях справочника.

Угрозы: экзистенциальная подделка, селективная подделка, универсальная подделка, полное раскрытие.

Атаки: с открытым ключом, с известными сообщениями, простая с выбором сообщений, направленная с выбором сообщений, адаптивная с выбором сообщений.

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

Теорема 2 см. также [3], [1]

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

Пример 3 протокол Лампорта; см. также [4], [1], [5]

Пусть $f$ — произвольная односторонняя функция. Выберем произвольное число $n\in\mathbb N$, играющее роль параметра стойкости. Пространством сообщений $M_n$ является множество $\{0,1\}^{k(n)}$, где $k$ — произвольный наперед заданный полиномиальный параметр. Алгоритм генерации ключей $\mathcal G$ на входе $1^n$

выбирает $s_i^b\in_{\mathfrak U}\{0,1\}^n$ и вычисляет $v_i^b=f(s_i^b)$ для каждых $i\in\{1,\dots,k(n)\}$ и $b\in\{0,1\}$;

возвращает на выходе $(s,v)$, где $s=\left(\left.s_i^b\,\right|\, i\in\{1,\dots,k(n)\},\, b\in\{0,1\}\right)$ (секретный ключ) и $v=\left(\left.v_i^b\,\right|\, i\in\{1,\dots,k(n)\},\, b\in\{0,1\}\right)$ (открытый ключ).

Алгоритм генерации подписи $\mathcal S$ на входе $(1^n,s,m)$, где $s=\left(\left.s_i^b\,\right|\, i\in\{1,\dots,k(n)\},\, b\in\{0,1\}\right)$, $s_i^b\in\{0,1\}^n$ и $m\in\{0,1\}^{k(n)}$, выдает в качестве подписи для сообщения $m$ набор \[ \left(s_1^{m_{[1]}},\dots,s_{k(n)}^{m_{[k(n)]}}\right). \] Наконец, алгоритм проверки подписей $\mathcal V$ на входе $(1^n,v,m,w)$, где $v=\left(\left.v_i^b\,\right|\, i\in\{1,\dots,k(n)\},\, b\in\{0,1\}\right)$ и $m\in\{0,1\}^{k(n)}$, принимает $w$ в качестве подписи для сообщения $m$, если и только если $w=\left(w_1,\dots,w_{k(n)}\right)$, $w_i\in\{0,1\}^n$ и $f(w_i)=v_i^{m_{[i]}}$ для всех $i\in\{1,\dots,k(n)\}$. Легко видеть, что тройка $(\mathcal G,\mathcal S,\mathcal V)$ построенных выше алгоритмов образует протокол электронной подписи, стойкий против экзистенциальной подделки на основе частного случая направленной атаки с выбором сообщений, в котором противник может получить подпись только для одного сообщения. Эту атаку можно считать также частным случаем адаптивной атаки с выбором сообщений, в котором противник может обратиться к оракулу, возвращающему допустимые подписи, только один раз. В то же время если противник получил допустимые подписи для каких либо сообщений $m,m’\in\{0,1\}^{k(n)}$ таких, что $m_{[i]}\ne m_{[i]}’$ при всех $i\in\{1,\dots,k(n)\}$, то он может осуществить угрозу полного раскрытия. Таким образом, данный протокол является стойким только тогда, когда с использованием одного и того же секретного ключа подписывается лишь одно сообщение. Отметим, что построенный в настоящем примере протокол используется для построения протоколов электронной подписи, допускающих подписывание многих сообщений с использованием одного и того же секретного ключа (см., например, [6], [3]).

Литература

[1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
[2] Goldwasser, S. and Micali, S. and Rivest, R. L. «A digital signature scheme secure against adaptive chosen-message attacks» 1988
[3] Rompel, J. «One-way functions are necessary and sufficient for secure signatures» 1990
[4] Lamport, L. «Constructing digital signatures from one-way functions» 1979
[5] Luby, M. «Pseudorandomness and cryptographic applications» 1996
[6] Naor, M. and Yung, M. «Universal one-way hash functions and their cryptographic applications» 1989

Математическая криптография

Протокол электронной подписи

Литература