0
$\begingroup$

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).

enter image description here

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)
$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer. Apologies, I am not very much familiar with etiquette here. $\endgroup$ Commented Dec 7, 2021 at 7:56

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