For a very brief theory of digital signature schemes and their analysis, click here

Digital signatures are cryptographic mechanisms that provide authentication, integrity, and non-repudiation for digital documents and messages. Unlike handwritten signatures, digital signatures use mathematical algorithms to ensure that a document hasn't been altered and to verify the identity of the signer. They do not, however, provide confidentiality — encrypting the message content itself for privacy requires a separate encryption step in addition to signing.

How Digital Signatures Work

The digital signature process involves three main phases:

1. Hash Generation: $$h = H(m)$$ The original message $m$ is processed through a cryptographic hash function $H$ (such as SHA-1, used in this experiment, or SHA-256 in modern systems) to create a fixed-size digest $h$.

2. Signature Creation: $$s = \text{Sign}_{sk}(h) = h^d \bmod n$$ The hash $h$ is encrypted using the signer's private key $d$ to create the digital signature $s$.

3. Verification:

$$\text{Verify}_{pk}(m, s) = \begin{cases} \text{Valid} & \text{if } H(m) = s^e \bmod n \\ \text{Invalid} & \text{otherwise} \end{cases}$$

Recipients can verify the signature using the signer's public key $e$ to decrypt the signature and compare it with a freshly computed hash.

Why Hashing Is Essential: Hashing before signing is not just a convenience — it is a security requirement.

• Efficiency: RSA operations are computationally expensive. Signing a short, fixed-size hash (e.g., 160 or 256 bits) is far cheaper than signing an arbitrarily long message directly, and lets the scheme handle messages of any size, even those larger than the modulus $n$.
• Security against forgery: If a scheme signs the raw message directly, $s = m^d \bmod n$, RSA's multiplicative structure becomes exploitable. Given two valid signatures $s_1 = m_1^d \bmod n$ and $s_2 = m_2^d \bmod n$, an attacker can compute

$$s_1 \cdot s_2 \bmod n = (m_1 \cdot m_2)^d \bmod n$$

which is a valid forged signature for the message $m_1 m_2 \bmod n$ — without ever knowing the private key $d$. A cryptographic hash function is not multiplicative in this way ($H(m_1) \cdot H(m_2) \bmod n \neq H(m_1 m_2 \bmod n)$ in general), so hashing first breaks this algebraic shortcut and is what makes "sign-the-hash" schemes resistant to this class of existential forgery.

RSA-Based Digital Signatures

RSA (Rivest–Shamir–Adleman) is widely used for digital signatures due to its mathematical foundation:

Key Properties:

• Key Generation: Create a public–private key pair $(e, n)$ and $(d, n)$
• Signing: Encrypt the message hash with the private key: $s = H(m)^d \bmod n$
• Verification: Decrypt the signature with the public key: $H(m) \stackrel{?}{=} s^e \bmod n$

Note: This experiment focuses on RSA-based signatures. This should not be confused with the NIST Digital Signature Algorithm (DSA), a separate, distinct signature scheme based on the discrete logarithm problem rather than integer factorization — DSA is not used in this experiment.

RSA Security Assumption: The security of RSA digital signatures relies on the believed difficulty of the Integer Factorization Problem: $$\text{Given } n = p \times q \text{, find } p \text{ and } q$$

More precisely, forging signatures without $d$ requires solving the RSA problem — computing $e$-th roots modulo $n$ — which is at least as easy as factoring $n$, though whether it is exactly as hard as factoring remains an open question in cryptography.

Trapdoor Function: RSA uses a trapdoor one-way function:

• Easy direction (for anyone): Computing $y = x^e \bmod n$ is efficient using only the public key $(e, n)$.
• Easy direction (with the trapdoor): If you know the private exponent $d$ — the "trapdoor" — recovering $x = y^d \bmod n$ is equally efficient.
• Hard direction (without the trapdoor): Given only $y$, $e$, and $n$, and without knowing $d$ or the factorization of $n$, finding $x$ such that $x^e \equiv y \pmod{n}$ is believed to be computationally infeasible for sufficiently large $n$.

Mathematical Representation

For RSA digital signatures:

Signature Generation: $$s = H(m)^d \bmod n$$

Signature Verification: $$H(m) = s^e \bmod n$$

Where:

• $H(m)$ is the hash of message $m$
• $d$ is the private key exponent
• $e$ is the public key exponent
• $n$ is the modulus ($n = p \times q$ for primes $p$ and $q$)

RSA Key Generation Process:

1. Choose two large prime numbers $p$ and $q$

2. Compute $n = p \times q$

3. Compute Euler's totient function: $\phi(n) = (p-1)(q-1)$

4. Choose public exponent $e$ such that $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$

5. Compute private exponent $d$ such that $d \equiv e^{-1} \pmod{\phi(n)}$

   (Modern implementations, e.g. FIPS 186-5, often use the Carmichael function $\lambda(n) = \text{lcm}(p-1, q-1)$ instead of $\phi(n)$ in this step, since $\lambda(n)$ divides $\phi(n)$ and gives the smallest valid private exponent — but computing $d$ from $\phi(n)$, as taught here, also yields a mathematically valid key.)

Digital Signature Algorithm Steps:

Signing Process:

1. Compute message hash: $h = H(m)$
2. Generate signature: $s = h^d \bmod n$
3. Send $(m, s)$ to verifier

Verification Process:

1. Compute message hash: $h' = H(m)$
2. Decrypt signature: $h'' = s^e \bmod n$
3. Verify: signature is valid if $h' = h''$

Security Properties

Digital signatures provide three key security properties:

1. Authentication: Verifies the identity of the message sender
2. Integrity: Ensures the message hasn't been modified
3. Non-repudiation: Prevents the sender from denying they signed the message

Does not provide — Confidentiality: A digital signature does not hide the message. $m$ travels alongside $s$ in plain form, so anyone who intercepts $(m, s)$ can read $m$ regardless of whether they verify the signature. Achieving confidentiality requires separately encrypting $m$ (e.g., with the recipient's public key) in addition to signing it.

Key Size Considerations

The security of RSA digital signatures depends on key size and computational complexity. Let $k$ denote the bit-length of the modulus $n$ (i.e., a "$k$-bit key"). Approximate security levels, following the widely cited NIST SP 800-57 equivalences to symmetric-key strength, are:

Key Size ($k$)	Approx. Security Level	Status	Use Case
512-bit	$\approx 2^{50}$ operations	Broken in practice (factored publicly since 1999)	Educational demonstration only
1024-bit	$\approx 2^{80}$ operations	Deprecated by NIST for federal use since 2013	Legacy systems only
2048-bit	$\approx 2^{112}$ operations	Currently recommended minimum	Production use
3072-bit	$\approx 2^{128}$ operations	Recommended for long-term security (beyond 2030)	High-value, long-lived data
4096-bit	$\approx 2^{150}$ operations (approx.)	High security, not an official NIST tier	High-value applications

Security Growth (Advanced / Optional Reading): The best known classical algorithm for factoring the RSA modulus $N$ (the actual large integer, not its bit-length) is the General Number Field Sieve (GNFS), with heuristic sub-exponential running time:

$$L_N[1/3, c] = \exp\Big((c + o(1))\,(\ln N)^{1/3}(\ln \ln N)^{2/3}\Big), \qquad c = \left(\frac{64}{9}\right)^{1/3} \approx 1.923$$

Here $\ln$ is the natural logarithm and $N = n$ is the modulus itself. This grows faster than any polynomial in $\log N$ (the bit-length), which is why increasing key size rapidly increases factoring cost — but it is still sub-exponential, unlike the fully exponential $2^{56}$ brute-force cost of a symmetric cipher like DES with a comparable key length. This classical hardness assumption would also be broken by a sufficiently large quantum computer running Shor's algorithm, which factors integers in polynomial time — a key reason post-quantum signature schemes are being standardized for future use.

Performance vs Security Trade-off:

• Signature time: $O(k^3)$ for a $k$-bit modulus, using schoolbook modular exponentiation (faster with optimized multiplication algorithms)
• Verification time: Typically faster than signing, due to the small public exponent $e$ (often $e = 65537 = 2^{16} + 1$)
• Key generation time: Increases significantly with key size due to the cost of primality testing for larger $p$ and $q$