Skip to content

Instantly share code, notes, and snippets.

@gitzhou
Last active Jul 12, 2021
Embed
What would you like to do?
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
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
if (s * s) % n == h % n:
break
i += 1
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))
@gitzhou

This comment has been minimized.

Copy link
Owner Author

@gitzhou gitzhou commented Jul 9, 2021

71
b'00'
True
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment