[Python] How to correctly implement the multiplication function used by GHASH function in...

I am trying to implement AES-256-GCM in Python without using any external libraries, and I have implemented encryption and decryption in AES-256-ECB, AES-256-CBC, AES-256-CTR, and AES-256-OFB modes, and I also implemented Base64 encoding and decoding plus JSON serialization and deserialization, all are working properly and I have verified the results rigorously against various sources.

You can see an earlier version of my work here, I have implemented the code all by myself according to various sources.

I plan to add AES-256-CFB and AES-256-PCBC modes, it is extremely trivial for me to implement them at this point, plus I have found this, but I am not adding those modes because I am currently trying to implement AES-256-GCM which is my original goal, but I can't implement it. Currently there is no way for me to verify if my results were right.

I have found this specification and this and this.

A direct implementation of the algorithm for multiplication used in GHASH function is:

GHASH_POLY = 0xE1000000000000000000000000000000


def ghash_mul(a: int, b: int) -> int:
c = 0
for i in range(127, -1, -1):
if a >> i:
c ^= b

if b & 1:
b = (b >> 1) ^ GHASH_POLY
else:
b >>= 1

return c


I have found this, it is easy for me to adapt the code to my needs, but I can't verify its correctness.

Specifically, the multiplication function it uses is the following:

def ghash_mult(x, y):
res = 0
for i in range(127, -1, -1):
res ^= x * ((y >> i) & 1)
x = (x >> 1) ^ ((x & 1) * GHASH_POLY)

return res


I got rid of the comment and assert blocks as they weren't necessary.

For some inputs, my function agrees with the function from the linked repository, but the outputs aren't the same for all inputs:

In [354]: ghash_mul(255, 255)
Out[354]: 184305769290552241502318497701996581888

In [355]: ghash_mult(255, 255)
Out[355]: 184305769290552241502318497701996581888

In [356]: ghash_mult(12345, 255)
Out[356]: 176413478065579303506952143281585670830

In [357]: ghash_mul(12345, 255)
Out[357]: 184305769290552241502318497702000014804

In [358]: ghash_mul(MAX128, MAX128)
Out[358]: 324345477096475565862205004031948663466

In [359]: ghash_mult(MAX128, MAX128)
Out[359]: 324345477096475565862205004031948663466

In [360]: ghash_mult(999, 999)
Out[360]: 184305769290552241502318497701997396837

In [361]: ghash_mul(999, 999)
Out[361]: 237807196120895105386696731878281261212


Which one is correct? Or are they both wrong? How can I correctly implement the multiplication function used in GHASH?

Continue reading...