Section 5.4 DSA and Elliptic Curve DSA
The Digital Signature Algorithm is a system that takes advantage of the existence of cyclic subgroups of smaller order in \(\F_p\text{.}\) Choosing a large prime \(p\) will keep the core discrete log problem intractable using contemporary methods like the index calculus, while finding a much smaller subgroup keeps the computation and storage requirements reasonable for users. (That is, while \(p\) might be on the order of \(2^{2048}\text{,}\) the subgroup used for the verification is on the order of \(q \sim 2^{512}\text{,}\) for example.)
Algorithm 5.4.1. Digital Signature Algorithm (DSA).
- (public parameters) Sam chooses a large primes \(p, q\) satisfying \(p \equiv 1 \bmod p\) and an element \(g\) of order \(q\) modulo \(p\text{.}\)
- (private) Sam chooses a private key \(1 \lt a \lt q-1\) and computes \(A = g^a\text{.}\)
- (public) Sam publishes \(p,q, g, A\text{.}\)
- (private) Sam wishes to sign a document \(D\) where \(1 \leq D \lt q\text{.}\) She picks a random element \(1 \lt k \lt q\text{.}\) She computes\begin{equation*} S_1 = g^k \bmod q, \hspace{.5cm} S_2 = (D - aS_1)k\inv \bmod q. \end{equation*}Her signature is the pair \(D^{sig} = (S_1, S_2)\text{.}\)
- (private) Vera receives the document \(D\text{,}\) the signature \(D^{sig}\) and the public signing key \(p,q, g, A\text{.}\) She wants to verify that the document comes from Sam.
- (private) Vera computes the verification constants\begin{equation*} V_1 = D S_1\inv,\hspace{.5cm} V_2 = S_1 S_2\inv \end{equation*}
- Vera's verification question is:\begin{equation} \text{Is } (g^{V_1}A^{V_2}\bmod p) \bmod q= S_1 \text{?}\label{eq-dsa}\tag{5.4.1} \end{equation}
As is the running theme with elliptic curves, the DSA is easily implemented with elliptic curves in place of the finite field \(\F_p\text{.}\) The advantage is that the ONLY way currently known to attack the discrete log problem in robust elliptic curves is with exponential routines. The Digital Signature Algorithm with elliptic curves is called ECDSA and is in common usage. One of the more surprising applications is in the realm of cryptocurrecy, to be discussed in a sequel section.
Algorithm 5.4.2. Elliptic Curve Digital Signature Algorithm (ECDSA).
- (public parameters) Sam chooses an elliptic curve over a finite field \(E(\F_p)\) and a point \(G \in E(\F_p)\) of large prime order \(q\text{.}\)
- (private) Sam chooses a private key \(1 \lt a \lt q-1\) and computes \(A = sG\text{.}\)
- (public) Sam publishes \(p,q, G, A\text{.}\)
- (private) Sam wishes to sign a document \(D\) where \(1 \leq D \lt q\text{.}\) She picks a random element \(1 \lt k \lt q\text{.}\) She computes\begin{equation*} kG = (x_k, y_k) \end{equation*}and then sets\begin{equation*} s_1 = x_k, \hspace{.5cm} s_2 = (D + ax_k)k\inv \bmod q. \end{equation*}Her signature is the pair \(D^{sig} = (s_1, s_2)\text{.}\)
- (private) Vera receives the document \(D\text{,}\) the signature \(D^{sig}\) and the public signing key \(p,q, G, A\text{.}\) She wants to verify that the document comes from Sam.
- (private) Vera computes the verification constants\begin{equation*} v_1 = D s_2\inv,\hspace{.5cm} v_2 = x s_2\inv \end{equation*}
- Vera's verification question is:\begin{equation} \text{Is } (v_1 G + v_2 A) \bmod q = x \text{?}\label{eq-ecdsa}\tag{5.4.2} \end{equation}