Skip to content

Instantly share code, notes, and snippets.

@tylerkerr
Created April 30, 2017 19:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tylerkerr/e2b7ceab62139cf1c277c54331ea5383 to your computer and use it in GitHub Desktop.
Save tylerkerr/e2b7ceab62139cf1c277c54331ea5383 to your computer and use it in GitHub Desktop.
import hashlib
import rsa
import binascii
import os
from gmpy2 import mpz, iroot, powmod, mul, t_mod
def to_bytes(n):
""" Return a bytes representation of a int """
return n.to_bytes((n.bit_length() // 8) + 1, byteorder='big')
def from_bytes(b):
""" Makes a int from a bytestring """
return int.from_bytes(b, byteorder='big')
def get_bit(n, b):
""" Returns the b-th rightmost bit of n """
return ((1 << b) & n) >> b
def set_bit(n, b, x):
""" Returns n with the b-th rightmost bit set to x """
if x == 0: return ~(1 << b) & n
if x == 1: return (1 << b) | n
def cube_root(n):
return int(iroot(mpz(n), 3)[0])
message = "right below".encode("ASCII")
message_hash = hashlib.sha256(message).digest()
ASN1_blob = rsa.pkcs1.HASH_ASN1['SHA-256']
suffix = b'\x00' + ASN1_blob + message_hash
sig_suffix = 1
for b in range(len(suffix)*8):
if get_bit(sig_suffix ** 3, b) != get_bit(from_bytes(suffix), b):
sig_suffix = set_bit(sig_suffix, b, 1)
while True:
prefix = b'\x00\x01' + os.urandom(2048//8 - 2)
sig_prefix = to_bytes(cube_root(from_bytes(prefix)))[:-len(suffix)] + b'\x00' * len(suffix)
sig = sig_prefix[:-len(suffix)] + to_bytes(sig_suffix)
if b'\x00' not in to_bytes(from_bytes(sig) ** 3)[:-len(suffix)]: break
hexsig = binascii.hexlify(sig)
print(hexsig.decode())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment