System32.kr [RSA103] 풀이

System32.kr 2019

RSA103 풀이입니다

 

p=randprim

e(bits=1024)
q=nextprime(p+rand(bits=64))

 

 

 

n = 523171545908439347079984829857166272490755110515501164347840985772081537607153032633627034283672952165088744702194194598263665644007012474218688874744119159433576941649802374269873297096542482864673663028420121028933290892148695399630471141652388858142837379625106663728466970543106475670944695178426345128622404188659395819609731517136209346499201958503231477376821955664260131840643055815735489615434847356385240589414518958821012582916986700315695213312797927
e = 75890823319493894649778238119866660628924668661939725653243821591293734119876987514543360050173914547032827753044199325926436760242819383884783456287774063959012970808345743726395349179476088924414519992417795625843440292670765531
c = 48724864779313923840771368863315403978774157546525429106022441664935683078731021092597773499396876686078062855830596180404569211641060040265424503580011984253306252131461826391739149934613684983289826611746524999894630859459114240689860752847497252922935755063842138052718553154569645504114125024099577779165840521064654503400340349866956420272930288416620386084299030911419380258260740993752837219665010025735212424683776284178649990068611783883405716180340421

 

n을 소인수분해 합니다.

https://www.alpertron.com.ar/ECM.HTM

Integer factorization calculator

 

• 523171 545908 439347 079984 829857 166272 490755 110515 501164 347840 985772 081537 607153 032633 627034 283672 952165 088744 702194 194598 263665 644007 012474 218688 874744 119159 433576 941649 802374 269873 297096 542482 864673 663028 420121 028933 290892 148695 399630 471141 652388 858142 837379 625106 663728 466970 543106 475670 944695 178426 345128 622404 188659 395819 609731 517136 209346 499201 958503 231477 376821 955664 260131 840643 055815 735489 615434 847356 385240 589414 518958 821012 582916 986700 315695 213312 797927 (462 digits) = 723 305983 597840 387090 073124 295695 063058 926103 842858 618139 332402 030402 176745 237557 965345 230728 740505 468522 590100 663617 877936 830954 821254 102084 213431 441982 251604 821311 082681 331648 040651 828570 490510 112186 434619 298867 817000 367372 585141 (231 digits) × 723 305983 597840 387090 073124 295695 063058 926103 842858 618139 332402 030402 176745 237557 965345 230728 740505 468522 590100 663617 877936 830954 821254 102084 213431 441982 251604 821311 082681 331648 040651 828570 490510 112186 434619 298867 817000 367372 594347 (231 digits)

p와 q를 구할 수 있습니다. 

 

c를 복호화하기 위해 주어진 e, c 와 위에서 구한 p, q를 아래 코드에 대입해준 뒤에 실행합니다.

 

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
    return gcd, x, y
def main():
    p = 723305983597840387090073124295695063058926103842858618139332402030402176745237557965345230728740505468522590100663617877936830954821254102084213431441982251604821311082681331648040651828570490510112186434619298867817000367372585141
    q = 723305983597840387090073124295695063058926103842858618139332402030402176745237557965345230728740505468522590100663617877936830954821254102084213431441982251604821311082681331648040651828570490510112186434619298867817000367372594347
    e = 75890823319493894649778238119866660628924668661939725653243821591293734119876987514543360050173914547032827753044199325926436760242819383884783456287774063959012970808345743726395349179476088924414519992417795625843440292670765531
    ct = 48724864779313923840771368863315403978774157546525429106022441664935683078731021092597773499396876686078062855830596180404569211641060040265424503580011984253306252131461826391739149934613684983289826611746524999894630859459114240689860752847497252922935755063842138052718553154569645504114125024099577779165840521064654503400340349866956420272930288416620386084299030911419380258260740993752837219665010025735212424683776284178649990068611783883405716180340421
    # compute n
    n = p * q
    # Compute phi(n)
    phi = (p - 1) * (q - 1)
    # Compute modular inverse of e
    gcd, a, b = egcd(e, phi)
    d = a
    print( "d:  " + str(d) );
    # Decrypt ciphertext
    pt = pow(ct, d, n)
    print( "pt: " + str(pt) )
if __name__ == "__main__":
    main()
 

 

그 다음 plaintext 값을 hex로 변환해준뒤에 ascii로 변환하면 flag가 나온다

 

46470827271975360721170849266738216410598415569944733823469870790619975080677955656802059050975833386869168748918671974627709

 

https://www.mobilefish.com/services/big_number/big_number.php

Mobilefish.com - Big number converter

 

464C41477B6E65696768626F725F69735F7468655F626967676573745F73656375726974795F76756C6E65726162696C6974797D

 

https://www.branah.com/ascii-converter

ASCII Converter - Hex, decimal, binary, base64, and ASCII converter

 

FLAG : FLAG{neighbor_is_the_biggest_security_vulnerability}