I have been studying a cryptosystem using Mersenne primes. More specifically, this paper.

I have implemented this cryptosystem in Python, but I am missing the key encapsulation system.

On page 12, they refer to something known as an "expandable hash function". It should take as input a $\lambda$-bit string and output a uniformly random $n$-bit string ($\lambda<<n$) of Hamming weight $h$. This weight $h$ is already determined (actually $h=\lambda$).

I am kind of new to this stuff. Is there a way to implement this hash function in Python?

  • 2
    $\begingroup$ @kelalaka but what about the Hamming weight? $\endgroup$
    – guipa
    Commented May 24, 2021 at 20:29
  • $\begingroup$ Hmm, would this just be $H'(m)\leftarrow_\$ S(\text{1}^h\parallel\text{0}^\left(n-h\right))$? All you gotta do is find a way to use $H$ to uniformly randomly select a permutation of '1' * h + '0' * (n-h). Have you got any candidates for expandable hash functions currently? (This question may prove informative or helpful) $\endgroup$ Commented May 25, 2021 at 17:31
  • $\begingroup$ @JamesTheAwesomeDude no, I have not. How would you implement it in python? $\endgroup$
    – guipa
    Commented May 25, 2021 at 18:32
  • $\begingroup$ I was too dumb to properly understand or implement it, but it appears that this paper provides a general method for doing so (or, at least, constructing a function that constructs functions that do so) $\endgroup$ Commented May 26, 2021 at 15:13
  • $\begingroup$ While I haven't yet figured out the permutation generator, It looks like pycryptodome includes a reputable expandable-output hash function: “Are there any variable length hash functions available for Python? $\endgroup$ Commented May 27, 2021 at 4:27

1 Answer 1


Remember: a random permutation (or, when taken bitwise, "a hamming-weight-preserving one-way function") is known in layman's terms as a shuffle.

There are well-known correct algorithms to do this — Python itself, for example, makes it quite convenient to just leverage its shuffle implementation by subclassing Random with your choice of DRBG:

from random import Random
from resource import getpagesize as _getpagesize
from functools import reduce as _reduce
from itertools import islice as _islice, repeat as _repeat

from Cryptodome.Hash import SHAKE256

def deterministic_shuffle(seq, seed, sponge=SHAKE256):
    """Applies a pseudorandom permutation from arbitrary bytestring `seed` to mutable sequence `seq`, using SHAKE256 as the DRBG."""
    stream = sponge.new(data=seed)
    random = StreamBasedRandom(stream=stream, blocksize=136)

class StreamBasedRandom(Random):
    def __init__(self, stream, blocksize=_getpagesize()):
        self._randbitgen = _ibytestobits(map(stream.read, _repeat(blocksize)))
    def getrandbits(self, k):
        return _concatbits(_islice(self._randbitgen, k))
    # Fix the following functions to prevent implementation-dependency
    def randbytes(self, n):
        return self.getrandbits(n * 8).to_bytes(n, 'big')
    def _randbelow(self, n):
        """Replacement for CPython's Random._randbelow that wastes very few bits"""
        if n <= 1:
            return 0
        getrandbits = self.getrandbits
        k = (n - 1).bit_length()
        a = getrandbits(k)
        b = 2 ** k
        if n == b:
            return a
        while (n * a // b) != (n * (a + 1) // b):
            a = a * 2 | getrandbits(1)
            b *= 2
        return n * a // b
    def shuffle(self, x):
        """Modern Fisher-Yates shuffle"""
        randbelow = self._randbelow
        for i in reversed(range(1, len(x))):
            j = randbelow(i + 1)
            x[i], x[j] = x[j], x[i]

def _ibytestobits(ibytes):
    """Turns an iterator of bytes into an iterator of its component bits, big-endian"""
    yield from ((i >> k) & 0b1 for b in ibytes for i in b for k in reversed(range(8)))

def _concatbits(bits):
    """Takes a finite iterator of bits and returns their big-endian concatenation as an integer"""
    return _reduce((lambda acc, cur: ((acc << 1) | cur)), bits, 0)

(SHAKE256 was used in this example code; it should be easily repurposeable to any bit generator. See this answer for some other ideas, and the appendix to this answer for a concrete example of how that might be done.)

To use this in your code would be something like this:

k = b'Hyper Secret Input Key'
h = len(k) * 8
n = 4096
assert n > (8 * h)

# An n-element bit sequence of hamming weight h
bitstream = ([1] * h) + ([0] * (n - h))
deterministic_shuffle(bitstream, k)

print("Shuffled bitstream:", _concatbits(bitstream).to_bytes(n // 8, 'big').hex())

Appendix: example usage of another DRBG

# this block of code depends on StreamBasedRandom, defined above
from types import SimpleNamespace as _SimpleNamespace

from Cryptodome.Cipher import AES
from Cryptodome.Hash import SHA256

def deterministic_shuffle(seq, seed, nonce=b''):
    """Applies a pseudorandom permutation from 256-bit (32-byte) `seed` to mutable sequence `seq`, using AES-256-CTR as the DRBG."""
    assert len(seed) == 32, "seed must be 256 bits (32 bytes) long for AES-256."
    cipher = AES.new(key=seed, mode=AES.MODE_CTR, nonce=nonce)
    def randbytes(n):
        return cipher.encrypt(b'\x00' * n)
    stream = _SimpleNamespace(read=randbytes)
    random = StreamBasedRandom(stream=stream, blocksize=cipher.block_size)

def _normalize(data):
    return SHA256.new(data).digest()

k = b'Hyper Secret Input Key'
h = len(k) * 8
n = 4096
assert n > (8 * h)

bitstream = ([1] * h) + ([0] * (n - h))
deterministic_shuffle(bitstream, _normalize(k))

print("AES-shuffled bitstream:", _concatbits(bitstream).to_bytes(n // 8, 'big').hex())
  • $\begingroup$ Interestingly, according to some dude on Quora, Fisher-Yates (which Python uses) is "optimal" -- his description of why seems underwhelming, but I don't doubt it per se... $\endgroup$ Commented Jun 16, 2021 at 15:12
  • $\begingroup$ (Admittedly, with the key functions fixed thus, I suppose it doesn't actually need to subclass Random…) $\endgroup$ Commented Jun 16, 2021 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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