Signature Algorithms: RSA and DSA

A hash function takes an input and generates an output that is typically more efficient, i.e. smaller.

$$H(x) : \mathbb{N} \to \mathbb{N}$$

A hash function does not need to be a bijective function, but for a given input $x$ it must be difficult to construct a $y$ such that $H(x) = H(y)$. The function must also be difficult to reconstruct the input $x$ given the output $H(x)$.

If two inputs map to the same output, we call this a hash collision.

Signing: Suppose Samantha wants to sign a message $g$ with an RSA signature. Then, Samantha chooses two large primes $p, q$ such that $m = pq$, and she chooses a $k$ such that $(k, \varphi(m)) = 1$. Next, she computes the multiplicative inverse of $k$, $\overline{k}$. Now she computes the signaure of her message by computing

$$s \equiv g^{\overline{k}} \pmod{m},$$

she then makes public the signature $s$, the message $g$, and the values $k$ and $m$.

Verifying: If Victor wants to validate the authenticity of Samantha's message, all he has to do is compute

$$s' \equiv s^{k} \pmod{m}$$

if $s' \equiv_m g$, then Victor can be assured that the message is authentic.

Signing: Suppose Samantha wants to sign a message $m$ with DSA. First, Samantha computes the hash of the document $D$. Then, she chooses two large primes $p, q$ such that $q \gt D$, $p \sim k$ (i.e. $p$ is a $k$-bit prime), and $q \sim l$ for $(k, l)$ in $(1024, 160)$, $(2048, 224)$, $(2048, 256)$, $(3072, 256)$[^1]. The primes $p, q$ must also satisfy the following congruence

$$p \equiv 1 \pmod{q} \iff q \vert (p-1).$$

Samantha also chooses an element $g \in \mathbb{F}_p$ such that $\text{ord}_p(g) = q$. Given a primitive root $g_1 \in \mathbb{F}_p$, she can choose $g \equiv_p g_1^{(p-1)/q}$.

Next, Samantha chooses a secret $a$ and computes $A \equiv_p g^a$. Her public signature is composed of the $4$-tuple $(p, q, g, A)$. Samantha then chooses a random element $k \in [1\dots q]$ and computes

$$\begin{align*} S_1 &\equiv \left(g^k \pmod{p}\right) \pmod{q}\\\\ S_2 &\equiv \left(D + aS_1\right)k^{-1} \pmod{q}. \end{align*}$$

Finally, Samantha's signature is given by the pair $(S_1, S_2)$.

Verifying: Victor begins by computing the values

$$\begin{align*} V_1 = DS_2^{-1} \pmod{q}\\ V_2 = S_1S_2^{-1} \pmod{q}. \end{align*}$$

Next, Victor checks the following congruence

$$\left(g^{V_1}A^{V_2}\pmod{p}\right) \pmod{q} \equiv S_1.$$

If the congruence holds, the message is certified to be authentic.