I am trying to implement given DSA signature generation instructions in python, there are few instructions that I couldn't understand in step 3 and 4.

Let m be an arbitrary length message. The signature is computed as follows:

  1. generate k (i.e., k is a random integer in [0, q − 1])
  2. r = g^^k(mod p)
  3. h = SHA3 256(m||r)

    What does m||r mean? m is a message length r is also a number so what should be the input of hashlib.sha3_256(input) function? As I see in Python it says input must be a string (converted to byte).

  4. s = α · h + k (mod q)

    h is a string returned by sha3_256 so how do I multiply it with α?

  5. The signature for m is the tuple (s, h)

  • $\begingroup$ Although the questions are about one scheme, the questions themselves are rather distinct. Better ask two questions in that case, especially because the first question has actually already been answered and counts as a dupe. $\endgroup$ – Maarten Bodewes Dec 11 '18 at 15:15

The $\parallel$ notation means concatenation. In this case, take the message $m$ (it's a sequence of bits), encode the value $r$ as a sequence of bits, and hash the sequence of bits that consists in $m$ followed by the encoded $r$.

In the step 4, you have a sequence of bits (hash output) that you must somehow convert back to an integer. This is again a question of encoding, but in the decoding direction this time. The underlying theme here is that you must have some convention that lets you encode integers into bits, and decode bits into integers. From a security point of view, the choice of convention is more or less open, but of course it is part of the algorithm specification: signer and verifier must agree on these details, otherwise the verifier won't accept as valid the signatures produced by the signer.

By the way, this is not DSA. DSA is specified by FIPS 186-4. What you describe is known as Schnorr signatures (there are several variants, e.g. on the order of $m$ and $r$ in the concatenation, or whether $s = \alpha h + k$ or $s = \alpha h - k$; all these variants procure more-or-less equivalent security). Historically, the distinction was important: DSA was defined at a time when Schnorr had patented his scheme, and the definition of DSA was carefully made to avoid that patent. Cryptographically, the difference also matters: the "security picture" of Schnorr signatures is better (we can make security proofs on Schnorr signatures, but we don't know how to do that with DSA; and DSA signatures are malleable, a property which is usually harmless but has allowed replay attacks in Bitcoin in the past).

| improve this answer | |
  • $\begingroup$ Good info, but it doesn't explicitly answer the question in step 4 of the question (which I've answered in the comments). Upvoted none-the-less because of the very useful remarks about the scheme in the question. $\endgroup$ – Maarten Bodewes Dec 11 '18 at 15:14
  • $\begingroup$ @MaartenBodewes Ah yes, I missed that. I added a paragraph to answer that part too. $\endgroup$ – Thomas Pornin Dec 11 '18 at 16:13

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