Description: “can u break my RSA Signature system …”

السلام عليكم ورحمة الله وبركاته

Today, I am going to show how I solved the RSA Signature challenge with a creative approach which I think no one thought of.

PYTHON


from Crypto.Util.number import getPrime,long_to_bytes

FLAG=b'redacted'
m=b'give_me_the_flag'


p=getPrime(512)
q=getPrime(512)
n=p*q
phi=(p-1)*(q-1)
e=0x10001
d=pow(e,-1,phi)
def sign(msg):
	signed=pow(msg,d,n)
	return signed
def verify(s,m):
	msg=pow(s,e,n)
	return long_to_bytes(msg)==m
banner='''1.sign
2.verify
3.exit'''


while True:
	print(banner)
	option=int(input('> '))
	if option==1:
		msg=int(input('enter your msg as hex > '),16)
		if msg==m:
			print('that will not work here ')
			exit()
		s=sign(msg)
		print(f'here is your signed msg : {hex(s)}')

	elif option==2:
		s=int(input('enter your signed msg as hex > '),16)
		if verify(s,m):
			print(f'you got me this time here is the flag : {FLAG}')
			exit()
		else:
			print('wrong msg try harder ')
	else:
		exit()

This is code for the challenge we see here that we need to sign ‘give_me_the_flag’ and then verify it to get the flag but the code will not accept submitting ‘give_me_the_flag’ directly so how will we do it ??

The approach that I took is to transform the ‘give_me_the_flag’ into integer then factor it by factor db then sign the two factors then sign each one then multiply the two signed factors then verify them to get the flag let’s try this.

PYTHON

messege = b'give_me_the_flag'                                
print(int.from_bytes(messege))

then I got an int 137458076091903464215105250758897721703 let’s find it’s factors by factor db

First factor is 383307765419
Second factor is 27
Third factor is 13281859420955337970882031

Let’s write the code that will communicate with the server to get the flag

PYTHON

from pwn import *
from Crypto.Util.number import bytes_to_long

messege = b'give_me_the_flag'

messege_long = bytes_to_long(messege)

first_factor = 27

second_factor = messege_long // first_factor

conn = remote('127.0.0.1',1333)

def get_sig(m):
    conn.sendlineafter(b'> ',b'1')
    conn.sendlineafter(b'enter your msg as hex > ',hex(m).encode())
    conn.recvuntil(b'here is your signed msg : ')
    return int(conn.recvline().decode(),16)

sig_first_factor = get_sig(first_factor)
sig_second_factor = get_sig(second_factor)

fake_sig = sig_first_factor * sig_second_factor

conn.sendlineafter(b'> ',b'2')
conn.sendlineafter(b'enter your signed msg as hex > ',hex(fake_sig).encode())

print(conn.recvall().decode())

conn.close()

Here I used a shortcut instead of using gcd and multiple signatures to get N I tried factor db and found that it can factorized to three factors so I used this to get the flag.

:!PYTHON

[x] Opening connection to 127.0.0.1 on port 1333                                                                                    
[x] Opening connection to 127.0.0.1 on port 1333: Trying 127.0.0.1                                                                  
[+] Opening connection to 127.0.0.1 on port 1333: Done                                                                              
[x] Receiving all data                                                                                                              
[x] Receiving all data: 0B                                                                                                          
[x] Receiving all data: 72B                                                                                                         
[+] Receiving all data: Done (72B)                                                                                                  
[*] Closed connection to 127.0.0.1 port 1333                                                                                        
you got me this time here is the flag : b'YAO{i_didnot_guard_it_right}'

Important Note:

This solution will not work if the messeage can't be factorized