# Signature Algorithms: RSA and DSA

## Motivation§

Until now, we have focused on cryptosystems that are used in encrypting and decrypting messages. With signature algorithms, we can post a message publicly along with a digital signature that certifies the authenticity of the message.

## Hashing Algorithms§

One-way hash function

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*.

## RSA Signature Algorithm§

The RSA signature algorithm works very similiarly to the cryptosystem.

RSA Signature

**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.

Typically, we use a hashing function on the message and find the signature of the hash, instead of the whole message. The onus is on the verifier to use the same hashing algorithm and compute the hash of the message, then verifying that the signature matches this hash.

## Digital Signature Algorithm (DSA)§

The Digital Signature Algorithm is an alternative to the RSA signature algorithm, and one of its key benefits is that it is generally faster. Like Diffie-Hellman and Elgama, DSA relies on the difficulty of the DLP rather than factorization.

DSA

**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.

By choosing our $q$ such that $\text{ord}_p(g) = q$ strengthens the DSA. We’ve discussed Shank’s Baby-Step Giant-Step algorithm to solve the DLP when the order of a group element is a prime. It takes $\mathcal{O}(N)$ memory, where $N \sim \sqrt{q}$, so using the smallest recommended bit-size $q$ of $160$, we can expect around $2^{80}$ bytes of memory to solve using Shank’s.