We’re given a public key and a encrypted flag, with the task to get the private key. I’m not very good at crypto challenges so I wanted to see if I could break this one and learn something in the process.
Hmm. Since the modulus n is made from the product of two primes, we’d better find those primes. Luckily, I found another writeup and a website called factordb.com. Factordb does exactly what it says on the box and yields two factors, 3133337 and another large number. The first number made me think I was on the right way!
Now, we need to reconstruct the key. We have n, p and q which is all we need. I couldn’t decrypt the message in Python, as Python’s cryptolib requires the modulus to be a multiple of 256 bits. So I resorted to the voodoo magic that is openssl. I found this nice post on stackoverflow about creating specific rsa keys.
I followed that post, computing:
d mod(p-1)= e1
d mod(q-1)= e2
q^-1 mod p= coeff
for which I needed
defegcd(a,b):ifa==0:return(b,0,1)else:g,y,x=egcd(b%a,a)return(g,x-(b//a)*y,y)defmodinv(a,m):g,x,y=egcd(a,m)ifg!=1:raiseException('modular inverse does not exist')else:returnx%m
Then I put everything in a file called newkey.der:
importgmpydefegcd(a,b):ifa==0:return(b,0,1)else:g,y,x=egcd(b%a,a)return(g,x-(b//a)*y,y)defmodinv(a,m):g,x,y=egcd(a,m)ifg!=1:raiseException('modular inverse does not exist')else:returnx%mp=25478326064937419292200172136399497719081842914528228316455906211693118321971399936004729134841162974144246271486439695786036588117424611881955950996219646807378822278285638261582099108339438949573034101215141156156408742843820048066830863814362379885720395082318462850002901605689761876319151147352730090957556940842144299887394678743607766937828094478336401159449035878306853716216548374273462386508307367713112073004011383418967894930554067582453248981022011922883374442736848045920676341361871231787163441467533076890081721882179369168787287724769642665399992556052144845878600126283968890273067575342061776244939q=3133337totien=(p-1)*(q-1)e=65537d=modinv(e,totien)printd
I then ran $ openssl asn1parse -genconf newkey.der -out key.der. After mucking around with the flag, I verified I had the right private key by encrypting a test message with the public key. I noticed that the flag was base64 encoded whereas my encrypted message wasn’t…