0
$\begingroup$

From the Wikipedia page for DSA(Digital Signature Algorithm) we have the following private/public key generation:

  1. Choose an integer x randomly from [1, q-1]
  2. Compute y := g^x mod p
  3. x is the private key, y is the public key

My question is: How are we sure that there does not exist z != x from [1, q-1], such that y = g^x mod p = g^z mod p and as a result, obtaining the same public key for different (z and x) private keys

$\endgroup$

1 Answer 1

2
$\begingroup$

How are we sure that there does not exist z != x from [1, q-1], such that y = g^x mod p = g^z mod p and as a result, obtaining the same public key for different (z and x) private keys

We're sure about this because $g$ has order $q$, that is, $g^a \ne 1$ for any $a$ not a multiple of $q$ (and $g^q = 1$). And, if $z, x$ had the same public key, that is, if $g^z = g^x$, then $g^{z-x} = 1$, and so $z-x$ must be a multiple of $q$. Because we assume that $0 < z,x < q$, the only way this can be is if $z = x$, that is, they're the same private key. QED.

$\endgroup$
2
  • $\begingroup$ How can we prove that if g^z = g^x then g^(z-x) = 1? $\endgroup$ Oct 22, 2022 at 7:01
  • $\begingroup$ @ЛюбомирБорисов: multiply both sides by $g^{-x}$ $\endgroup$
    – poncho
    Oct 22, 2022 at 12:55

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.