Fword CTF 2020 | Schuuuuush - crypto-writeup-public

from Crypto.Util.number import getPrime, bytes_to_long
from gmpy2 import gcd
from sympy import nextprime
from secret import flag,BITS

def func(x, bits):
    return x**12 + (x & (2 ** (bits/2) - 1))

def PrimeGen(bits):
    pr = getPrime(bits)
    p = nextprime(func(pr,bits))
    qr = getPrime(bits)
    q = nextprime(func(qr,bits))
    return p, q    

p,q = PrimeGen(BITS)
n = pow(p,2)*q
c = pow(bytes_to_long(flag),n,n)

Suspicious PrimeなRSAに見えるが、この暗号方式はSchmidt-samoa cryptosystemというらしい。まあRSAです

解けなかったんだけど解法がひどいねこれ。

$n = pq$ で $p = pr^{12} + (pr & (2^x - 1)), q = qr^{12} + (qr&(2^x-1))$

なんで $n^{\frac{1}{12}} \simeq pr * qr$ で、 $x$ を全探索するらしい

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
from sympy import invert, nextprime,lcm

n = 12838608941410176012340339820403664970195097778934681712442256463398083779434726523727337362548077816498494779634767166505330187300918251880884095061402948317273750734359805972172291702330170769941722135721254301797373910929209389934028023681108705224982459292501258476944977718620453591356928959990356039307404842140809349783009344965382885388230201854950013659777184155467116001057622057495928115145173039957373456282486463372004327112269636005406697476348929483659820840611834738925620510057932617464105487439853704904186236400811201279769590508776546485548532642090814468965154747150494170880560045656388451020601
c = 7050573356706442469683539123500770567737718645915519903139491762612445024317075069313476689401710155602518263519640817376340655413504872884207299668765616582487443371872620836280094522785104280556591702549809637571584448052503290838137680131373345867011613789868193526268278698789425705452031352784824472345055152400817574925351780178219492978046243297746285248144022980576645706737451329739930693946984047194996318634833190911615115111633867444659880674198115147887713534332191601313998075654936972222500960455343228277446386199666597757275851736103707318615905859809209855195657904316567873616670459334137634275173


appn = iroot(n,12)
print (appn)
#prime factor it to get pr and qr
pr = 124753565845126613

qr = 132788897400365081

for bits in range(2048):
    print bits
    p = nextprime(pr**12 + (pr & (2**(bits/2)-1)))
    q = nextprime(qr**12 + (qr & (2**(bits/2)-1)))
    l = lcm(p-1,q-1)
    try:
        d = invert(n,l)
        flag = long_to_bytes(pow(c,int(d),p*q))
        if "FwordCTF{" in flag:
            print flag
            break
    except Exception:
        continue