Coppersmith

tl;dr Coppersmith’s Attack to recover RSA primes Challenge Points: 99 Challenge Description: You can’t break my public key if you don’t know it, amirite? The challenge is based on RSA and we are given the following script: def bytes_to_long(data): return int(data.encode("hex"),16) def rsa(msg,e,n): return pow(bytes_to_long(msg),e,n) flag = open('flag.txt','r').read() tmp = randint(2**1023, 2**1024) e = 65537 p = next_prime(0xDEAD*tmp+randint(2, 2**500)) q = next_prime(0xBEEF*tmp+randint(2, 2**500)) N = p*q print('msg1 = '+str(rsa("You can't factor the modulus",e,N))) print('msg2 = '+str(rsa("If you don't know the modulus!",e,N))) print('flag = '+str(rsa(flag,e,N))) We are given ciphertext of two plaintext messages \(m_1\) “You can’t factor the modulus” and \(m_2\) “If you don’t know the modulus!”, and encrypted text of the flag in output.txt: ...

InCTF is over and I must say that we enjoyed a lot! We stayed for two days straight in front of our laptop screens, sleep deprived, fixing services, solving queries on IRC, eating and what not! My experience organising InCTF-2018, creating crypto challenges, how I came across the idea of creating all the crypto challenges etc. is another blog post I have to write soon, let us jump to what is in scope of this blog post. ...