shush

FwordCTF2020
Cryptography
ac01010
Aug. 30th, 2020
RSA


.

Shush

Crypto, First Blood

We can see in lambda x, bits : x**12 + (x & (2**28-1)) that each prime is approximately a twelth power. Since n = p^2 * q, we get that n is approximately equal to p^24 * q*12. Taking the 12th root of this, we are much more easily able to factor the smaller integer. After factoring, we can recover both p and q. Finally, we decrypt using the Schmidt-Samoa cryptosystem.

BITS = 57
n = 12838608941410176012340339820403664970195097778934681712442256463398083779434726523727337362548077816498494779634767166505330187300918251880884095061402948317273750734359805972172291702330170769941722135721254301797373910929209389934028023681108705224982459292501258476944977718620453591356928959990356039307404842140809349783009344965382885388230201854950013659777184155467116001057622057495928115145173039957373456282486463372004327112269636005406697476348929483659820840611834738925620510057932617464105487439853704904186236400811201279769590508776546485548532642090814468965154747150494170880560045656388451020601
a = (factor(round(n^(1/12))))
if a[0][1]==1:
    qr = a[0][0]
    pr = a[1][0]
else:
    qr = a[1][0]
    pr = a[0][0]
func = lambda x, bits : x**12 + (x & (2**28-1))
p = next_prime(func(pr,57))
q = next_prime(func(qr,57))
d = inverse_mod(p*p*q, (p-1)*(q-1))
c = 7050573356706442469683539123500770567737718645915519903139491762612445024317075069313476689401710155602518263519640817376340655413504872884207299668765616582487443371872620836280094522785104280556591702549809637571584448052503290838137680131373345867011613789868193526268278698789425705452031352784824472345055152400817574925351780178219492978046243297746285248144022980576645706737451329739930693946984047194996318634833190911615115111633867444659880674198115147887713534332191601313998075654936972222500960455343228277446386199666597757275851736103707318615905859809209855195657904316567873616670459334137634275173
m = pow(c,d,p*q)
print(bytes.fromhex(hex(m)[2:]).decode('utf-8'))

Flag: FwordCTF{Mehdi_knows_alot_about_Schmidt-samoa_but_is_it_better_than_RSA?}