Python - How to break word into 64bit chunks

Question

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?

unrelated: this doesn't sound right: *"In order to speed things up I am using bit-operators in Python"* -- bit-operations are not the way to speed up Python code (you want [the opposite as a rule: less Python operations on more data at a time](http://stackoverflow.com/questions/16308989/fastest-method-to-generate-big-random-string-with-lower-latin-letters#comment23400875_16310739)). — jfs, Sep 21 '15 at 01:17
what is the type of your input `int`, `bytes`, something else? — jfs, Sep 21 '15 at 01:18
J.F, yes you are probably right about that, but we are not allowed to use the pow() function, and doing something like 2**256 in python takes a long time compared to using bit-wise operators. The type of input is int. — Geordie Wicks, Sep 21 '15 at 01:30
here's the opposite task: [How to combine two 32-bit integers into one 64-bit integer?](http://stackoverflow.com/q/2768890/4279). It should give you an idea how to chop a 32bit integer chunk from 64bit integer key and continue from there (chop 64bit chunk from 2048bit key). — jfs, Sep 21 '15 at 01:47
I take it the best way to break something up into bits is simply to convert integer to binary, then do i just literally split it into 64 length chunks? Is it that easy or am i missing something? — Geordie Wicks, Sep 21 '15 at 01:55
no, the answers to [the question that i've linked](http://stackoverflow.com/q/2768890/4279) demonstrate *bit-manipulation* solutions. — jfs, Sep 21 '15 at 01:59
I'm not sure whether you need even or odd parity, but I have re-worked my answer to provide a longitudinal example. — Patrick Maupin, Sep 21 '15 at 02:35

Patrick Maupin · Accepted Answer · 2015-09-21T02:52:56.453

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.

you could check for power of 2 explicitly and raise `ValueError`: `is_power_of_2 = lambda n: (n > 0) and (n & (n - 1)) == 0` (note: zero is excluded). — jfs, Sep 21 '15 at 02:46
I thought about that, and also thought about allowing non-power-of-two by finding next lower power of two and doing fewer bits to start with (e.g. using log function). Either one is a good thing to add to production code, depending on needs, but I think I'll add your suggestion so they know they need to do the other if the exception is raised :-) — Patrick Maupin, Sep 21 '15 at 02:48
Thanks mate, haven't implemented yet, but your explanation and detail were awesome. Going to do some more reading before I do anything else, but really appreciate what you have done! — Geordie Wicks, Sep 22 '15 at 01:14

Python - How to break word into 64bit chunks

1 Answers1