Padding

00 01 [some non-zero bytes] 00 ASN.1 HASH

00 01 [some non-zero bytes] 00 ASN.1 HASH GARBAGE

message_with_padding = RSAdecrypt(ciphertext)

zero_byte = message_with_padding[0]
seed_xored = message_with_padding[1:hash_length+1]
random_xored_with_message = message_with_padding[hash_length+1:]

N = public_mod
key_size = 2048

# 256 bytes for 2048 key_size
bytes_size = math.floor(math.log(256, public_mod))

# 255 bytes for 2048 key_size
B = 2 ** (8 * (bytes_size - 1))


def binary_search(start, end):
	while start != end:
	middle = (end - start) /2
	#...


def message_oracle(ciphertext):
	#Decrypt ciphertext
	plaintext = RSAdecrypt(ciphertext)
	#Check Inital Padding
	return plaintext[0] == '\x00'

def find_power_mult(ciphertext, oracle):
	#Find a test power that is greater then B and less than 2B
	for power in range(key_size):
		modified_ciphertext = (ciphertext * 2**power) % N

		#Send to Oracle and get info if it is greater than B.
		if oracle(modified_ciphertext):
			# This means that we now know this property B <= plaintext < 2B
			
			return power

#Make better by using binary search
def find_wrap_around(power_mult, ciphertext, oracle):
	#Now we want to find the wrap around number
	start = (B + N) // B
	offset_max = math.ceiling(N / B) 
	offset_start = 0
	offset_end = offset_max

	first_part = 2**power_mult

	# Do Binary search to narrow down the number of guesses
	while offset_start + 1 != offset_end:
		#Set the offset for the binary search
		offset = ((offset_end - offset_start)//2) + offset_start
		
		mult_test = (start + offset) * first_part
		modified_ciphertext = (mult_test * ciphertext) % N

		#Send to Oracle and get info if it is larger than B.
		if oracle(modified_ciphertext):
			# modified plaintext is greater than B
			# Set the end to the current offset
			offset_end = offset

		else:
			# modified plaintext is less than B
			# Set the start to the current offset
			offset_start = offset

	#If it is smaller than B we know the message has wrapped around.
	#We know that (start + x) * ciphertext >= B
	return offset_start

def binary_serach_message(wrap_offset, ciphertext, oracle):
	message_minimum = N // wrap_offset
	message_maximum = (N + B) // wrap_offset
	BB = 2 * B

	#Do another Binary search for the message
	while message_minimum > message_maximum:
		#Mostly Zero until close to the end of the message space
		i = ((2 * B // (message_maximum - message_minimum)) * message_minimum) // N

		# Number to multiply to test message 
		test_mult = i * N // message_minimum
		modified_ciphertext = (mult_test * ciphertext) % N

		#Send to Oracle and get info if it is larger than B.
		if oracle(modified_ciphertext):
			# modified plaintext is greater than B
			# Set the end to the current offset
			message_maximum = (i * N + B) // test_mult

		else:
			# modified plaintext is less than B
			# Set the start to the current offset
			message_minimum = (i * N + B) // test_mult
	return message_minimum

if __name__ == '__main__':
	ciphertext = b""

	# Leak information about the decrypted message through the oracle where the following is true
	# B <= (plaintext * 2**power) % N < 2B
	power_mult = find_power_mult(ciphertext, message_oracle)

	# Using the power number gained from the last function lets divide everything by 2.
	# This means that B/2 <= (plaintext * 2**power)/2 < B
	# Using these properties lets try to find a number that can be multiplied to make the plaintext greater than N. This is before the mod N and the resulting output will be less than B which we can detect with the oracle.
	wrap_offset = find_wrap_around(power_mult - 1, ciphertext, message_oracle)

	# We now know that B <= plaintext * (((B + N) // B) + offset)     * 2**power
	#         and that B >  plaintext * (((B + N) // B) + offset + 1) * 2**power
	# Lets rearrange the terms
	# plaintext <= (N) // (((B + N) // B) + offset)
	# plaintext >  (N + B) // (((B + N) // B) + offset)
	# Now we have a low bound and a high bound. Lets narrow this down more to a single message
	plaintext = binary_serach_message(wrap_offset, ciphertext, message_oracle)

>>> echo "QP==" | base64 -d | xxd
00000000: 40                                       @
>>> echo "QR==" | base64 -d | xxd
00000000: 41                                       A
>>> echo "QQ==" | base64 -d | xxd
00000000: 41                                       A
>>> echo "QS==" | base64 -d | xxd
00000000: 41                                       A
>>> echo "Qf==" | base64 -d | xxd
00000000: 41                                       A
>>> echo "Qg==" | base64 -d | xxd
00000000: 42                                       B