# Python code for 'Verifiable Canonical Generation of the Generator g', FIPS 186-4, returns False [closed]

Edit: if anyone, inexperienced like me, lands on this question, it has been answered at the stackoverflow.

Why the Python code, see below, returns false?

More context: I am going through the FIPS 186-4 and on the page 43, there is a algorithm, A.2.3 Verifiable Canonical Generation of the Generator g, to generate generators. I wrote a Python code, see below, that encodes this algorithm. However, it always returns false against the test data which I took from NIST Test Vectors (Test Vectors, FIPS-186-4, DSA. I have also posted the whole file at [gist][3). from Crypto.Hash import SHA256

P = 0xfbdf34147bf5d8a45671c906923c1dbe86e9123fae5750d6c1986e00a9946f7f833372a436f98f75dc798bb454825eb625d49011d1e4401baacb653bb9dac6cc8ac91e61ba4310458ff6d6ddabcba29db025eedba6e2f837344dee4814e2a7e2e92ceb1e6e665ee08ce187ffd420fee7a99e046a4af719fa8c689630e88f8729
Q = 0x93db61194cb0b9236eea63617d149cd6dd8e2bf1
domain_parameter_seed = 0x75709e9ca555a80cb7ab154e9d29d2775fe215d8
index = 0xae

def Hash(number):
string = number.to_bytes((number.bit_length()+7)//8, 'big')
return int(SHA256.new(string).hexdigest(), 16)

def compute_gen():
k = (P - 1) // Q
for count in range(1, 0xffff):

U = count + 2^16 * (index + 2^16 * (0x6767656e + 2^32 * domain_parameter_seed))
W = Hash(U)
g = pow(W, k, P)
print(hex(g))
if g != 1:
break

return g

print (compute_gen() == G)


The closest to a cryptographic reason the code does not work is that it does not implement the prescription

index is a bit string of length 8

when it does

U = count + 2^16 * (index + 2^16 * (0x6767656e + 2^32 * domain_parameter_seed))


where the second 2^16 is intended to be $$2^8$$.

A programming error in that same line is that ^ means XOR, not power; and has lower priority than addition and multiplication on top of that.

More generally, the code uses integers where there should be bytetrings. Bytetrings ease concatenation, and prevent errors such as the one currently occuring when the first byte of domain_parameter_seed changes from 0x75 to 0x00, which is perfectly legit.

Using hexdigest and converting it back to integer works in the context, but is terrible programming practice. Use digest.

• Thanks for the answer. Apologies, I am not very much familiar with etiquette here. Dec 7, 2021 at 7:56