可擴展的雜湊函式

我一直在研究使用梅森素數的密碼系統。更具體地說，這篇論文。

我已經在 Python 中實現了這個密碼系統，但是我缺少密鑰封裝系統。

在第 12 頁，他們提到了一種稱為“可擴展散列函式”的東西。它應該作為輸入 $ \lambda $ -bit 字元串並輸出一個均勻隨機的 $ n $ -位字元串（ $ \lambda<<n $ ) 的漢明權重 $ h $ . 這個重量 $ h $ 已經確定（實際上 $ h=\lambda $ ).

我對這些東西有點陌生。有沒有辦法在 Python 中實現這個雜湊函式？

請記住：隨機排列（或者，當按位計算時，“保持漢明權重的單向函式”）在外行術語中稱為shuffle。

有眾所周知的正確算法可以做到這一點——例如，Python 本身通過使用您選擇的DRBG進行子類化來利用其shuffle實現非常方便：Random

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)
   random.shuffle(seq)


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；它應該可以輕鬆地重新用於任何位生成器。有關其他一些想法，請參見此答案，並在此答案的附錄中了解如何完成此操作的具體範例。）

在您的程式碼中使用它是這樣的：

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())

---

附錄：另一個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)
   random.shuffle(seq)

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())

引用自：https://crypto.stackexchange.com/questions/90156