Протокол электронной подписи
- $\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]). Эти угрозы и атаки описываются в соответствующих статьях справочника.Если ограничиться указанным набором угроз и атак, то самая слабая стойкость для протоколов электронной подписи — это стойкость против полного раскрытия на основе атаки с открытым ключом. Легко видеть, что если существуют протоколы электронной подписи, удовлетворяющие даже этому самому слабому условию стойкости, то существуют односторонние функции. Оказывается, что из существования односторонних функций следует существование протоколов электронной подписи, стойких в самом сильном смысле при данном наборе угроз и атак.
- выбирает $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)$ (открытый ключ).
Литература
- [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