# WMCTF 2023 Writeups
# Crypto
# Signin
## challenge
Challenge cho file task.py

from Crypto.Util.number import *
from random import randrange
from secret import flag

def pr(msg):
    print(msg)

pr(br"""
                        ....''''''....                        
                     .`",:;;II;II;;;;:,"^'.                    
                  '"IlllI;;;;;;;;;;;;;Il!!l;^.                 
                `l><>!!!!!!!!iiiii!!!!!!!!i><!".               
             ':>?]__++~~~~~<<<<<<<<<<<<<<<<~~+__i".            
           .:i+}{]?-__+++~~~~~~<<<<<~~~~~~+_-?[\1_!^           
          .;<_}\{]-_++~<<<<<<<<<<<<<<<<<<<~+-?]\|]+<^          
          .!-{t|[?-}(|((){_<<<<<<<<<_}1)))1}??]{t|]_"          
           !)nf}]-?/\){]]]_<<<<<<<<<_]]}}{\/?-][)vf?`          
          '!tX/}]--<]{\Un[~~<<<<<~~<~-11Yz)<--?[{vv[".         
         .<{xJt}]?!ibm0%&Ci><<<<<<<<!0kJW%w+:-?[{uu)},         
          !1fLf}]_::xmqQj["I~<<<<<<>"(ZqOu{I^<?[{cc)[`         
          `}|x\}]_+<!<+~<<__~<<<<<<+_<<_+<><++-[1j/(>          
           !\j/{]-++___--_+~~<i;I>~~~__-______?}(jf}`          
            ;~(|}?_++++~~++~+]-++]?+++~~~~+++-[1/]>^           
              ;\([?__+_-?]?-_-----__-]?-_+++-]{/].             
               l||}?__/rjffcCQQQQQLUxffjf}+-]1\?'              
                ,[\)[?}}-__[/nzXXvj)?__]{??}((>.               
                 .I[|(1{]_+~~~<~~<<<~+_[}1(1+^                 
                    ,~{|\)}]_++++++-?}1)1?!`                   
                      ."!_]{11))1{}]-+i:'                      
                          .`^","^`'.                           
""".decode())

def gen_prime(bit):
    while 1:
        P = getPrime(bit)
        if len(bin(P)) - 2 == bit:
            return P

pq_bit = 512
offset = 16

P,Q = [gen_prime(pq_bit) for i in range(2)]
N = P * Q
gift = int(bin(P ^ (Q >> offset))[2+offset:],2)
pr(N)
pr(gift)

inpP = int(input())
if inpP != P:
    pr(b"you lose!")
    exit()

secret = randrange(0,P)
bs = [randrange(0,P) for _ in range(38)]

results = [(bi * secret) % P for bi in bs]
rs = [ri & (2 ** offset - 1)  for ri in results]

pr(bs)
pr(rs)
inpsecret = int(input())
if inpsecret == secret:
    pr(flag)

Server trả về 2 giá trị N và gift trong đó
==gift = int(bin(P ^ (Q >> 16))[2+16:],2)==
vì P và Q dài đúng 512 bits nên gift = 496 bits cuối của P xor với 496 bits đầu của Q
Đầu tiên ta cần tìm giá trị P từ N và gift khi gửi cho server thì server sẽ trả về 2 mảng bs và rs , để sử sụng tìm ==secret==

Tìm p
## script

N = 57252869175637212568236748640925893827160364084453077592917520099746923875450673203603122133211413258193637689074143351818835395604472446180951873843259943128920430046860737145456699076020104424455592112300084656390276993199353749868155331424480732785402069537620405984757756117761662821257241121160688236059
gift = 9490317877722370366220947396358892780057993488031240787042699498466930877039204847729338907643916122079293748219234616642879370438435175064743981096

def get_P_Q(N, tmp_P, tmp_Q, gift, base_w):
    if N % base_w != (tmp_P * tmp_Q) % base_w: return False, (-1, -1)
    if base_w == (1 << 512):
        if tmp_P * tmp_Q == N: return True, (tmp_P, tmp_Q)
    else:
        if base_w > 65536:
            new_Q1 = (gift ^ tmp_P) % (base_w >> 16)
            new_Q2 = tmp_Q >> 16
            if new_Q1 != new_Q2: return False, (-1, -1)
        res = get_P_Q(N, tmp_P, tmp_Q, gift, base_w << 1)
        if res[0]: return res
        res = get_P_Q(N, tmp_P + base_w, tmp_Q, gift, base_w << 1)
        if res[0]: return res
        res = get_P_Q(N, tmp_P, tmp_Q + base_w, gift, base_w << 1)
        if res[0]: return res
        res = get_P_Q(N, tmp_P + base_w, tmp_Q + base_w, gift, base_w << 1)
        if res[0]: return res
    return False, (-1, -1)

_ ,(p,q) = get_P_Q(N, 0, 0, gift, 1)
print(p,q)

Tìm secret

p = 13069431200886265537001586157218694353609198430802370736318329550702794255703546553999035892073565012935857045988471420505276499177341376677245399268015729
bs = [7985928586953925271375739101982050171597371464562675324677194505571236401610965801142635320335801840127281833818339610435024434508048848908329150054391442, 2779179752638185211731196681582087404490375040089261984390247706727766526772220984957732932258580726359236606912050516088399703014879191223513324325249744, 5957090134892682915148728697296766471113217538918437557018386189034050524442167613231653823908697532882200879059466265926689296668594416339062080940658841, 8778964766022300712018244566167487763950450319658215251205731632050696126719490762768511119667552948384164976006688614182419442527555348340875538150129022, 5654494785299467114600749446547641046685646240137177143283124953362883613949651864800086867522297344350484160328162923330838787370140337409084955422225642, 9808029790124631699764409791564006267357077352469032519288610055432116892781673597807490563247474528913508397992109882333794414022501544528031043559125230, 12831778633568734298468989146207272262614946691936131647933388178695946547500217713662792218832910068568276583581366256902820912032428835215716193809524114, 5499904468390112394521533617202301108817542726737855397740298486883977209095021112928111141412927311417109886223067933071490084759541851985251515909152361, 10618752175910043302272740484632168893461333628195438429319983095228691046187036526956248787441460253357429588505627148999550042146207685836839694370081499, 10229590851158471914357648539655273679260875817170070383253924572940804345312224685779553890242235322332276896026044243625365145681194847291421967653117158, 1847627739106586513447516091484207688395611814381351546351212746830815773104496964320117696685360350841257305747634519263848045393823266539266803480683522, 12766274647057655920640115604350937653164504135335952036705559616096985009823829195009514876011108124649971337270499966673914642871378246307598504869402498, 10193780281641675654937343491340118627588830156095459803628844472031533339211875519073105928478885430873486509945570825634769276164447711669904842458975320, 10767877973825154873545279201729695689997135914287949586480656622093565017247336052994836411855179958920169916981928744022409315406368213044187274090984912, 647380302198273132258496946176534331189448062852361470221687188323363124727492704568097999264057808875198993895249863944830072153951430746316749769522659, 11555506770310033865072509178444235629855877955171028871759157273465523002505459234265747884772147672409403311694280305791141170116503248441824114420095302, 9982532266813217416059256481097203392145386503900715248652147666993972529628918990307151042855725763050130676573085771558301864644997136540993785073727965, 744013214576846946054115141916693068491275615493161145799432662164325135612197067821579491197806617320856121370273809555837748180273326079516021918531364, 4201303883017182505101349654607969532119767397627025702212583394891631498414690878233517370124226868558367176788063392049016290825878576803083485111506945, 5269978486091127016511021436837988246533903981670486152321093027577685815325339833747555734981918186859940996294493819516411706523250464154046338872747072, 9776684308698030867923944122729554264401160134478546041977724596725780449976088254505898271699522683864842076278944633751830271008943215946473565713040967, 6867753629073425880243274392752300484441480687153413348666203662094668629336610234842295784233797133890984453249394650657993314960447903373898541170762637, 10720837492294645391527412053160592727741130164979412521209259411490760346146169463945024685873001228789255012616072026603737355116890054486357983963724388, 6907681559227686172390185885058616481610833859407267428004251170302603182756592846977027135313157157495761135037356825046805466405487317829186761883658807, 9214234856436932409607408126018692071536525459051365986952670191523720762587140877324085587523293412945968495344711900575984829884559982681391438952262868, 1594539209345311877418816711892172349482633286793419468631258969094687990561704843995879011994634386125607563665840318642507527044690392504642521811920091, 12890771377755087121816924077795423982734018812502581456185239245977388667765151586967105199593312255311191814212721286722392637799077313871589008599669153, 5400376736704401556853440466900145212226392736429008989461596878790583788284068940118632479530605910065003815707529981583704996138980390558053468577816046, 8297690692540995345082291397643667664548989828067499440236727151989832813376036322343020949906023879040557619677630212848738313756100234770789469783066829, 3616082006340056100284955939141717638707846781692178586502802327515658355591504403967223048949879753993704233898544745317039706673035105268655946658052683, 5526388088947885136195286206202787384211302747288906280257201768930517124785199159927048153723009471472368199414413811726197201060685551326721258832789720, 6166034178163913712791337959372785398008982012614085917316076194038445222966012583577882734630736754953894544604121671982089960180261708084262221046128611, 12466794441663468626859040895771923161098353239484458837310994478644580580584306816583217346285577830357602002123233740158860010288430555235167304322907460, 436545699769996811042518154671435312178205091904510173794190527221794651981549010400102971731593327932551850027933355534083212564520278777872847446946578, 11054091445750149286735077811314085677971105967108879826282766731327263205419056229761960680821444659788557843870628534413580052188442940154256562399418508, 7904183631730350109273382468837990449460592304984581877780525960067635805198797072569827591135676479603053124964362014578405189505731442993339371111704958, 5395106401210302349187902248637866718011091440528292648024820922509625247612667041987143158939218495456012266440665367597128392142950157806747663130801795, 12753427159920461501526496307538683697909326626081372560633563224438441610638661969416920091519308441313584224063138519681786528289869947974179598023433826]
rs = [32575, 8331, 38341, 880, 57255, 23322, 32743, 20829, 23232, 7676, 34860, 45086, 24766, 38647, 53349, 39023, 63714, 7197, 24557, 26351, 35471, 20540, 7168, 26313, 427, 32022, 11690, 1000, 52712, 37751, 57511, 46071, 55740, 60443, 64107, 8106, 21202, 1485]
xx = 2567269449395731757406127144140018015566291770960585103898960024009577900389618351899793385860477640769561715741426011216820879021723148773127995195110584

cols = len(rs)
M = Matrix(ZZ,cols+2,cols+2)

tmpb = [int(bi * inverse_mod(2**16,p)) << 16  for bi in bs]
tmpc = [int(ri * inverse_mod(2**16,p)) << 16 for ri in rs]
for i in range(cols):
    M[i,i] = p << 16
M[-2] = tmpb + [1,0]
M[-1] = tmpc + [0,2^512]


ML = M.LLL()
for mi in ML:
    if abs(mi[-1]) == 2^512:
        if mi[-2] % p == xx:
            print(mi[-2])
        if abs(mi[-2]) % p == xx:
            print(mi[-2])
        if abs(- mi[-2]) % p == xx:
            print(mi[-2])
        if - mi[-2] % p == xx:
            print(mi[-2])

Flag:`wmctf{b4d_primE_f4ctor_1s_the_w3akness_for_RSA}`
# badprime
## challenge
Challenge cho file task.py

from Crypto.Util.number import *
from gmpy2 import gcd
#from secret import flag
flag = b"flag"
M = 0x7cda79f57f60a9b65478052f383ad7dadb714b4f4ac069997c7ff23d34d075fca08fdf20f95fbc5f0a981d65c3a3ee7ff74d769da52e948d6b0270dd736ef61fa99a54f80fb22091b055885dc22b9f17562778dfb2aeac87f51de339f71731d207c0af3244d35129feba028a48402247f4ba1d2b6d0755baff6
print(int(M.bit_length()))
def getMyprime(BIT):
    while True:
        p = int(pow(65537, getRandomRange(M>>1, M), M)) + getRandomInteger(BIT-int(M).bit_length()) * M
        if isPrime(p):
            return p
print(gcd(int(M),65537))
p = getMyprime(1024)
q = getPrime(1024)
n = p * q
m = bytes_to_long(flag)

print("Try to crack the bad RSA")
print("Public key:", n)
print("The flag(encrypted):", pow(m, 65537, n))
print("Well well, I will give you the hint if you please me ^_^")
leak = int(input("Gift window:"))
if M % leak == 0:
    print("This is the gift for you: ", p % leak)
else:
    print("I don't like this gift!")

Server cho ==n==,==c== và ==p_leak==
==p== được sinh ra theo M <=> `p = k*M * p_leak`
p 1024 bits và M 971 bits
=> k < $2^{53}$

solve bằng sagemath
## script

M=0x7cda79f57f60a9b65478052f383ad7dadb714b4f4ac069997c7ff23d34d075fca08fdf20f95fbc5f0a981d65c3a3ee7ff74d769da52e948d6b0270dd736ef61fa99a54f80fb22091b055885dc22b9f17562778dfb2aeac87f51de339f71731d207c0af3244d35129feba028a48402247f4ba1d2b6d0755baff6
p_leak=15229228386374645813197582482430632393953233509151485400791979799583245377765022591038937869943385183055055367938419486529208097888386536560724758542005382157391406322399905293334276730300209069645287555236325177873445344825505354610184811434336950395897257467767497279723244031611080289764599
c=1486234359230455886531946415331133048629770614657188685781862452654146110337656260637369591693476400046586465398643950385536511696712872388080081645977371084518637989245195606595398883619314728288695753666375717965760333705080779539063671062081483586963339130771066463091039031012873935695717090205311482558606293610603288150538204843845836289668866617408703032998462472835252162698797755810219765125695497632595892950122124897657818592561548603915202049620416218894636317458387035568822802927567579532823442907931706305368293575758876044711528168229274944527876912994911019792540229628043081574236573685786793539826
n=1861858815805774290018892209954681528798763333107583784171306798501020754736245248934918287234500940403212914291731800923479570089678395480534165091021125751477190762921780524738016428663965534423300012300269779539670025897732250953000343108502744679672046779378861088259278389388567856115881808007217663017412350448194504117681798552969721552682293804947750153578394214464850313060969613429466416685902116881901796350654887406788040909248937052665216550481750301238502245354518914608097646690563197192175330962500810370437811979063456694158378580205988900931991035646090867098902901734968983336408959865172070990669
P.<k>=PolynomialRing(Zmod(n))
f=k*M + p_leak
k=f.monic().small_roots(X=2**54,beta=0.4)[0]
p=k*M+p_leak
q=n//ZZ(p)
e=65537
d=inverse_mod(e,(p-1)*(q-1))
m=hex(pow(c,d,n))[2:]
print(bytes.fromhex(m))

Flag: `wmctf{b4d_primE_f4ctor_1s_the_w3akness_for_RSA}`