4. Digital Signatures with Schnorr

Discrete Logarithm Problem (DLP)

https://youtu.be/NmM9HA2MQGI?si=U4u5dM-dk2gz6UdO

The Discrete Logarithm Problem (DLP) is a mathematical problem that forms the basis for several important cryptographic systems. In essence, DLP involves finding the power to which a base must be raised to obtain a given element within a finite group.

Formally, let G be a cyclic group generated by an element g of order n. Given two elements h ∈ G and g ∈ G, find an integer x such that:

$h \equiv g^x \pmod{n}$

where x is known as the discrete logarithm of h with respect to the base g.

Diffie-Hellman Key Exchange (DHKE)

One of the earliest and most influential cryptographic protocols based on DLP is the Diffie-Hellman Key Exchange (DHKE). This protocol enables two parties, traditionally referred to as Alice and Bob, to establish a shared secret key over an insecure communication channel without actually exchanging the key itself.

Here's how it works:

1. Public values: Both parties agree on a common modulus p and a generator g.
2. Private values: Each party chooses a private exponent x_A and x_B, respectively.
3. Shared secrets: They calculate their respective shares of the secret key using the formula $K_A \equiv g^{x_A \cdot x_B} \pmod{p}$.
4. Exchange shares: They exchange these calculated shares publicly.
5. Calculate final key: Upon receiving each other's share, both parties compute the final shared secret key $K \equiv g^{x_A \cdot x_B} \pmod{p}$.

This protocol provides perfect forward secrecy, ensuring that even if one of the parties' long-term private exponents becomes compromised at some point in time, previously established session keys will remain unaffected.

ElGamal Encryption

Taher ElGamal introduced his eponymous encryption system in 1985, which is an asymmetric encryption algorithm used to provide confidentiality. Building upon the principles outlined above, ElGamal encryption allows users to encrypt messages securely under the assumption that computing discrete logs remains computationally hard.

Steps:

1. Key Generation: Choose a random integer $(x)$ from $[1, p - 2]$. Compute $y = g^x \pmod{p}$.
2. Encryption:
   • Message m: Represent the message m as an element of G
   • Random Integer: Select a random integer k from $[1, p-2]$
   • Ciphertext: Compute $c_1 = g^k \pmod{p}$ and $c_2 = mc \cdot y^k \pmod{p}$
3. Decryption: Compute $m = c_2 \cdot (c_1^{x})^{-1} \pmod{p}$.

ElGamal Digital Signatures

ElGamal signatures provide a method for verifying the authenticity and integrity of a message.

Steps:

1. Key Generation: Choose a random integer x from $[1, p - 2]$. Compute $y = g^x \pmod{p}$.
2. Signing:
   • Message m: Hash the message m to get H(m).
   • Random Integer: Select a random integer k from $[1, p-2]$ such that $\gcd(k,p - 1) = 1$
   • Compute Signature: $r = g^k \pmod{p}$ and $s = k^{-1}(H(m) - x \cdot r) \pmod{(p - 1)}$
3. Verification: Verify that $g^{H(m)} \equiv y^r \cdot r^s \pmod{p}$.

These DLP-based schemes form the basis of many secure communication protocols in modern cryptography. They leverage the computational difficulty of solving the discrete logarithm problem to provide security guarantees. However, they also have some limitations:

• Computational complexity: The security of these algorithms relies on the difficulty of solving the DLP, which can be computationally expensive for large key sizes.
• Key size: Larger key sizes are often necessary to maintain a desired level of security, which may increase computational requirements.

Despite these challenges, DLP-based public-key cryptography remains an important and widely used category in modern cryptographic systems.