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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ How can we prove that if g^z = g^x then g^(z-x) = 1? $\endgroup$
    – Любомир Борисов
    Commented Oct 22, 2022 at 7:01
  • $\begingroup$ @ЛюбомирБорисов: multiply both sides by $g^{-x}$ $\endgroup$
    – poncho
    Commented 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.