Rabin Signature https://aaron67.cc/2021/07/10/rabin-signatures/

rabin.py

import hashlib


def hash_to_int(x: bytes) -> int:
    hx = hashlib.sha256(x).digest()
    for i in range(11):
        hx += hashlib.sha256(hx).digest()
    return int.from_bytes(hx, 'little')


def sign(p: int, q: int, digest: bytes) -> tuple:
    """
    :param p: part of private key
    :param q: part of private key
    :param digest: message digest to sign
    :return: rabin signature (S: int, U: bytes)
    """
    n = p * q
    i = 0
    while True:
        h = hash_to_int(digest + b'\x00' * i) % n
        if (h % p == 0 or pow(h, (p - 1) // 2, p) == 1) and (h % q == 0 or pow(h, (q - 1) // 2, q) == 1):
            break
        i += 1
    lp = q * pow(h, (p + 1) // 4, p) * pow(q, p - 2, p)
    rp = p * pow(h, (q + 1) // 4, q) * pow(p, q - 2, q)
    s = (lp + rp) % n
    return s, b'\x00' * i


def verify(n: int, digest: bytes, s: int, u: bytes) -> bool:
    """
    :param n: rabin public key
    :param digest: digest of signed message
    :param s: S of signature
    :param u: padding U of signature
    """
    return hash_to_int(digest + u) % n == (s * s) % n


if __name__ == '__main__':
    from binascii import hexlify

    priv_p = 7
    priv_q = 11
    pub_n = priv_p * priv_q
    msg = 'Hello World. Hello Rabin Signatures!'
    d = hashlib.sha256(msg.encode('utf-8')).digest()
    sig_s, sig_u = sign(priv_p, priv_q, d)
    print(sig_s)
    print(hexlify(sig_u))
    print(verify(pub_n, d, sig_s, sig_u))

71
b'00'
True