Let's Decrypt Again

cryptohack

Task: an RSA signature server publishes one fixed SIGNATURE = DIGEST^D mod N (DIGEST is a 768-bit EMSA-PKCS1-v1.5/SHA-1 encoding). The attacker chooses a single composite modulus n (set once) and a per-claim exponent e, and must make pow(SIGNATURE,e,n) equal bytes_to_long(emsa(msg)) for three different message regexes — including a self-minted valid Bitcoin address — to collect three XOR shares of the flag. Solution: Desmedt–Odlyzko chosen-modulus forgery: build n = product of 9 smooth primes p=2m+1 where SIGNATURE is a QR generating the odd order-m subgroup and the m_i are pairwise coprime; for each pattern brute a message so D=emsa(msg) is a QR mod every p, recover e_i by Pohlig–Hellman discrete logs in each order-m subgroup combined by CRT, then XOR the three recovered shares to get the flag.