Tags: crypto rsa
e = 65537
N = 25693197123978473
encflag = ['0x2135d36aa0c278', '0x3e8f43212dafd7', '0x7a240c1672358', '0x37677cfb281b26', '0x26f90fe5a4bed0', '0xb0e1c482daf4', '0x59c069723a4e4b', '0x8cec977d4159']
Help me find out the secret to decrypt the flag
As we can se, the modulus N is quite small. This leads us to an easy bruteforce attack over the private key, so it is an easy crypto problem.
But I discovered a faster way: there are online tools capable of get the prime factors for the modulus N and the Euler´s totient, which was
PHI = 25693 196802 793728.
So now, it is easier to calculate the modular inverse of e. So the private key will be:
d = modular_inverse(e, PHI).
Once we have the private key, we can decrypt every hexadecimal string inside the encflag array. First of all we need to get the bytes string (binary) and take it as an integer. So let c be the encrypted integer for every encrypted hex string: m = c^d mod N.
After that, we take the integer m as a binary string and take the binary string as an hex string. We can now get the ASCII interpretation and get the flag:
Here is my solution in Python:
from sage.crypto.util import *
b = bin(int(h, 16))[2:]
#c = int(str(ascii_to_bin(enc)),2)
c = int(hex_to_bin(enc), 2)
#c = int('100001001101011101001101101010101000001100001001111000',2)
m = pow(c,d,n)
b = bin(m)[2:]
while len(b)%8 != 0:
b = '0'+b
res = ''
enc_flag = ['2135d36aa0c278', '3e8f43212dafd7', '7a240c1672358', '37677cfb281b26', '26f90fe5a4bed0', 'b0e1c482daf4', '59c069723a4e4b', '8cec977d4159']
for chunk in enc_flag:
res += decrypt(chunk)