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
G = 0x7db10e27fffe43fc9582367a449f7be217130cdf89a5eff65fbebefc9478ba39ad03d1b0d0254c0f1b8246d914c0d1df25f55a5dabbb51caa1942403fdc22c832e4d7048ce0ad64cb76252fdcfaecd78722c2e10417495ee9d4e0d8376f891a3042b103de915355c0e60e168cf48c0fa232a13bf9b58a0f9b3ad7db7ad39c536
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)