Python – How to break word into 64bit chunks

I am doing an assignment where I have to institute the Diffie-Hellman key exchange. In order to speed things up I am using bit-operators in Python, and everything is working fine programming wise, but I have to perform a Parity Checksum, and I don’t think I have the proper understanding of what this is or how it works.

Basically I need to be able to take a key of variable length (up to 2048 bits), break it into 64 bit words, and perform Checksum. I am unsure what this means exactly. To break a word into 64 bit words using Python, how would one go about that? I think once I do that I should be able to just perform an XOR operation on the words to get a 64bit output. At the moment though I am stuck on exactly how one break up a word in 64 bit chunks in Python appropriately?

Answer

A parity checksum is just the xor of all the bits in the word. The most efficient way to do this will have log(nbits) operations, because you can halve the number of bits you are dealing with on each iteration. For example:

def parity(word, nbits):
    if nbits & (nbits - 1):
        raise ValueError("nbits must be power of two")

    while nbits > 1:
        nbits >>= 1
        word ^= (word >> nbits)
    return word & 1

A longitudinal parity check is a bit different, because you stop when you get to a given word-size, at which point, your parity should be all zeros or all ones, rather than a single one or zero. I don’t know whether you want odd or even parity, so this is a bit more general:

def longitudinal_parity(data, total_bits, word_bits, expected_parity=1):
    """
    Performs longitudinal parity check
    """
    for nbits in (total_bits, word_bits):
        if nbits & (nbits - 1):
            raise ValueError("bit size must be power of two")

    mask = (1 << total_bits) - 1

    while total_bits > word_bits:
        total_bits >>= 1
        data ^= (data >> total_bits)
        mask >>= total_bits
        data &= mask
    return data == (mask if expected_parity else 0)

So for your example, the first parameter would be a 2048 bit integer, the total_bits would be 2048, the word_bits would be 64, and the desired parity would be 0 or 1.

I don’t know anything about Diffie-Hellman’s parity check, but if your parity is provided separately (seems likely), then you are comparing against a separate parity word rather than all ones or all zeroes. This is a minor tweak:

def longitudinal_parity(data, total_bits, word_bits, expected_parity):
    """
    Performs longitudinal parity check
    """
    for nbits in (total_bits, word_bits):
        if nbits & (nbits - 1):
            raise ValueError("bit size must be power of two")

    mask = (1 << total_bits) - 1

    while total_bits > word_bits:
        total_bits >>= 1
        data ^= (data >> total_bits)
        mask >>= total_bits
        data &= mask
    return data == expected_parity

There are plenty of possible optimizations here, such as precalculating masks, starting the mask off at a smaller number, etc. Hopefully the code is readable.