2
$\begingroup$

I just read the Wikipedia page on the Digital Signature Algorithm here:

https://en.wikipedia.org/wiki/Digital_Signature_Algorithm

Is the signing algorithm explained on the page the one that is used by most Certificate Authorities to sign TLS certificates? And is the verification algorithm explained on the page the one that is used by most web browsers to verify the CA signature of the TLS certificate received from a server?

I will summarize what I understand based on the wiki article above and overlay my knowledge of TLS certificates.

The Certificate Authority goes through these steps to sign a TLS certificate for the organization AcmeCorp (ignoring the concepts of intermediate certificates):

  1. Select a hash algorithm $H()$ (e.g., something from the SHA-2 family) and select or generate several other arbitrary constants labeled as $p$, $q$, and $g$. The $H()$, $p$, $q$, and $g$ are all publicly disclosed.
  2. Generate a private key $x$ and a public key $y$ based on some of the details from point 1. Then publicly disclose the public key $y$ to all parties (You can find $y$ in root certificates that come bundled with your operating system). Keep the private key $x$ confidential.
  3. Assume the CA wants to create a TLS certificate for the domain acmecorp.com. Let's call the contents of the TLS certificate the variable $m$. The signature made for the TLS certificate will be composed of $r$ and $s$. Where $r = (g^k \mod p) \mod q$ and $s = (k^{-1}(H(m) + xr)) \mod q$ and $k$ is a random number from $\{1...q-1\}$.
  4. The CA gives the $m$, $r$, and $s$ to AcmeCorp acmecorp.com.

Firefox goes through these steps to validate the CA signature of the TLS Certificate:

  1. Firefox visits https://acmecorp.com.
  2. https://acmecorp.com gives Firefox $m$, $r$, $s$, and which $H()$ to use.
  3. Firefox computes $v = (g^{u_1} * y^{u_2} \mod p) \mod q$, where $u_1$ and $u_2$ are computed from $r$, $w$, $q$, and $m$ (reminder that these 4 values are publicly disclosed).
  4. Firefox validates the signature by evaluating $v=r$. If $v \neq r$, then the signature is invalid.

So my questions are:

  • Can someone correct mistakes in my understanding?
  • I mentioned in step 3 $s = (k^{-1}(H(m) + xr)) \mod 1$. I'm not a mathematician, but at first glance, it seems like $x$ is easy to derive from $s$ because $x$ isn't an argument within the $H()$ algorithm. I'm just under the impression (because I don't have a math background) that hashing with the $H()$ is what helps keep the original value of $x$ private, and that other mathematical operations described in the algorithm might not be computationally strong enough to protect $x$?
$\endgroup$
1
  • 1
    $\begingroup$ Digital Signature Algorithm (DSA) is not a generic term for a digital signature. It's a particular kind of digital signature, that is seldom used in TLS certificates nowadays at least. What's actually used is more likely to be ECDSA (an elliptic curve evolution of DSA), or EdDSA (another elliptic curve signature), or RSA-SSA-PKCS1-v1_5. $\endgroup$
    – fgrieu
    Commented Jun 24 at 15:29

1 Answer 1

4
$\begingroup$

Is the signing algorithm explained on the page the one that is used by most Certificate Authorities to sign TLS certificates?

Is the signing algorithm explained on the page the one that is used by most Certificate Authorities to sign TLS certificates?

No, the Digital Signature Algorithm (DSA) is not commonly used by Certificate Authorities (CAs) for signing TLS certificates anymore. While DSA is based on the discrete logarithm problem (DLP) and uses finite field calculations, it has largely been replaced by more efficient and secure algorithms.

One of the most prevalent alternatives is the Elliptic Curve Digital Signature Algorithm (ECDSA), which uses elliptic curves over either prime fields ($\text{F}_p$) or binary fields ($\text{F}_{2^m}$). ECDSA creates smaller and more efficient signatures compared to DSA, making it a preferred choice for modern cryptographic applications, including TLS certificates.

Select a hash algorithm H() (eg. something from SHA-2 family) and select or generate several other arbitrary constants labelled as p, q and g. The H(), p, q and g are all publicly disclosed.

No, the keys are not related to the hash algorithm. You can use the same key pair using different hash algorithms to create digital signatures. And most of the time the parameters are selected and indicated using a named set of parameters. Those named set of parameters are indicated in the protocol using an OID rather than as a string though.

Generate a private key x and a public key y based on some of the details from point 1. Then publicly disclose the public key y to all parties (You can find y in root certificates that come bundled with your operating system). Keep the private key x confidential.

Again, no. In principle the signing key is specific to the CA certificate, which is generated well in advance using the same techniques, but using a CA Policy Document (CP). The parameters that the CA uses to sign certificates may be different from the parameters used for the user's key pair.

The signature made for the TLS certificate will be the composed of r and s. Where r = (g^k mod p) mod q and s = (k^-1(H(m) + xr)) mod 1 and k is a random number from {1...q-1}

Yes, that's a general description of (EC)DSA. There are some inaccuracies though:

  • Modular Inverse: The equation for $s$ uses the modular inverse of $k$ modulo $q$, not modulo 1.
  • Modulo $q$: The entire calculation for $s$ is done modulo $q$, not modulo 1.

https://acmecorp.com gives FireFox m, r, s and which H() to use.

No. The parameters are tied to and indicated within the certificates, usually as an OID, as indicated.

FireFox validates the signature by evaluating v=r. If v!=r, then signature is invalid.

Yes, again, that's just the description of DSA.

... hashing with the $\text{H}()$ is what helps keep the original value of $x$ private, and that other mathematical operations described in the algorithm might not be computationally strong enough to protect $x$?

No, it is the randomization using $k$ that protects the private key $x$ in the algorithm. The hash function is used to compress the message into a fixed-size value. If the randomization is not performed correctly, it can result in leaking the private key. For ECDSA, this issue led to the leakage of Sony's signing keys used for PlayStation content, allowing hackers to bypass security.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.