Score:0

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

in flag

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)
Score:2
ng flag

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.

in flag
Thanks for the answer. Apologies, I am not very much familiar with etiquette here.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.