System32.kr [RSA106] 풀이

System32.kr

RSA106 풀이

 

이번에는 작은 e값과 다른 n값이 주어질 때다.

 

문제를 보면 n, c값이 각각 7개가 주어진다.

 

n0 = 10022036265379037873283606776808482557866459308090111534883940865718177639983512662119342281119416241158033537298567286851709556229498058859877121683228774596682463530354223972067629198444968982788922250713559891865919261816911330848802614913631706032562776893224597357355324255263321117746371249374897281379618765006492730806494403308111072966637211560823960482878492897669436775113233218090173773953205373859777529204336743904524724605913439667291642450283502539056317167865950955271726411160185108661710605305209881749978968104668372320740311039079195405595564405545553067816984977942352952679613295335945453198237
e0 = 7
c0 = 7391172673494652807685679927464443742804469716124686497937352685631944739927403334100753118718810827819939551249092644730733640887813475157863909267732710966904033874563749607452101004880603517576015117231543666882714876053816889315304434716583902097326869862769223330226929267650196146699723546298777721549327230579524043853731525842228354074211952590809573512193002908675659981910521560218722078118583409532890190350278993572874200629804040761922640444870232404736174533503458666401049021690701120014711135662159756073554655169987524174160454336199103732766648969310872094773896573037726906071280884398964499625020
n1 = 5466545789924978392117734846441651025566944649290017587961487324101229594609777422305368037344954585418241587633957551279641772525768764611188988227720597556634650034264505822514430445671371902394845226110100975570935303274836520009041255673258743208173396958290432905543148641745168024380646078191379194650244323448918977124653886707963511968894925605598683697007725355334218510153808020236986866621440493131392397106674236875719949237921916816824901951782815445968997182425608119302657645645838081847911729329333764403590828687896595484627953582720022494684431177689169562431514156723717431880081981556861583018517
e1 = 7
c1 = 2843216698827041985234155126413219625102551967694195507616270458944256794024725727982775312996964360225107871298400288303715856835949437523897251998356574507142899492557143968158430397540293189973986706379386430519381858403628687144765951766733259166975201698201001559608435647196300391229794290104430338488390377935687114237067952186727947306540592887865659962691657932063711547531829312199823488118775597548579002212505954186919111624039557627729228692097539779090276034544147566301508294383730646789567286167983001460941761651651550106133788841812817514137482151210600991083197714286954280138543861307503606716687
n2 = 5216273350923762348996819172932047657740263255248423536832070896504436079290996116053910458202206066607495080005143242081376348478552546332314483414339219088245406077072653291793201707938210052137737032136008691204273974883871392886847900590411035963981133018158012140770585855836554605968542686051767074445169576528595295868833612083435959789899465479063315706805137423972403304919456897675923521668190245644201632092213606749130854730067502251227674778549657054487536558408785381601255488927062660442522496864532745842104460605804514922118066012819002689049981557892095296223518873642160006462186453091627377846719
e2 = 7
c2 = 2302840660982990706559514467752282608279989971179438892300937945447548784136021634663470424995563089657378083878340327507907273677046617011731588253183115962507981205380038591937454135692479378461272309601984068994340223460110011927750428790367899740123933101545519333275378177450046677349361228228756023343552737751276656981842493825940592644061106798477517795237715348144352954728534699021231559916391882314536204099649751257130666668855055343556693412599766542087842727824032038771853002304289245363376208213623603995010083510086051017014020583014841158059684157033215101586049552797894220844380611133865673630801
n3 = 23877677498268410284879275681599753946472064168982107017698987574875291853430610166705520818854679284024035965166084667071782959877626088875201104444061372210767667483286033873186027043018865270765379778972734594727020084433542927434622162385031073045949543728094450158066806302710336945902706311444702067892897382023369572561933840697091647190739941807440726157963736515169755622514090303488227644584510175870987096541366007967982302476854613123392400570876217436169696368690150208874814955767774660004903549034030453797617219708937501949676157124852802614561580437881345741238143591504284958256829966154954860310643
e3 = 7
c3 = 21542650580244090952784375188737468745448203348922868429406196302086271073676866277485976451720227641278427496915785578412784529024335740676758107987503859146577358215708248682437455044274509620470752764937668805057881069241160619380098319880566533327878406656365405208233812965208982731078254898819598904848966997244978017829737683687504578693319927257965587343277686790692897770069007188699761774062935389828173866322096724684461746266895396261083359145450376711339892131239899937109104845549497760224715797430549267596702844680269969086579967938513817206661072633561450576990683873838952925270459005180113251070249
n4 = 14095304106189288640829933284328100925981109805290171926596523882500992828050689610054551419208961617895244032677408948518722739184220513962788253695294440224817835843547289773514113860609727834208120554675150777100035341397359695754443831969620545126239117460426602273999534524462242741389375433175237422632997941648269022097426901783701566115072520388843879171454672942810241915423341751813855234874758865121037886735845464875242609743056346324057991215234482527871877337706502944703023808957350962273199545033462807203671480858363579332623386369851297631986187711675134368500976725781503614885257984375549898158689
e4 = 7
c4 = 5841298358718613696062311056221508337701416292725004974138314539876150378702426703549430117040191903647122061403407396288001626124108215908094632322171004807595060730467760110047822011747633210272450557602443585240325321882265082987790788937409746656818781811819115452970840966600299402274664167896074281874767663751931697405940475209595160606989446399735956632932740140774120362773964862067823210273048778380937955790417026758705126758582714675929109140032046187572583702405164513719448544031934183587141634161632757693697249167749952737814924049718225194470053426092226496663009906557955566430066736079650924094775
n5 = 2805822354201662117320594043711993782804865769293499426012360087817858551003001395302163740603703828195195932459444805174556152674013174027197071452536007720377642902614079800876454139985267840390802982000981391589121247087945323071621814892873054291187100453510563927190923456819020327967812411342557586095287060637718034456241630931342321644065932761169946330107762168341828247523519427454538373734712173180277190763105614286976239296025622448068573996830818370176355468420604889972971911137825122031079799394840034520000378583048365213663261323826755042085539056699658078298352991498848183741926741253336809983081
e5 = 7
c5 = 1840296233218477853481534562215626625414182376149520279565477106636326502423629202398872352247072974928247089059258779616805363438919346177179751144150840146502100528681001973857981344372271699254564085124019490542816704779558116713918712764905289545904746631301089653173086838314931849726257101196974182707388814949943497825270433233859953596462571591644141313685767121169211812959266024665387037379326240471760061808331954030889737904363024686917008151847474903564630772753685195974245871917099262116749552267414561620711561171348300446183668428521497810537883987976853838751652062973640912281502768323552961119727
n6 = 25454009749168470343695633209096091829115329722572151778843118833425745470034996921255287732666381145235781038972818879902175747917173596391714646458631517429967987558853821226063117620100131280109980358660151611745478185529770001530290709260636770225215186800776097876644514962324976911466656250316831758848397129882568596479711529118559633884457580705072157006277242414838614921959845416195868135339484150235079747708585021249992266719965641249640344662274664797188479304252760363884135230450876493335745378727727079727827645384850449255019980920544237025044248135670516643488962958548195014144666470074377908386063
e6 = 7
c6 = 789032093589329919433103064912734499692800138044594105985741187192587133548423627123979828515942204884228205644612915396782678903901468096055669312556620684388723470685365523376229767716532460150705694588934426363146781448912873886792079146178749619507171787017137430583992061952004088013585625578578697225347700205144867425958935656640766720643294601810945228322481781587820554087577038637902482084286507222529109418279162740318995563410236088568237694026601631788889001088963413678782229872782538151806577918829849586853938669782376616395525544507480942096894639889844916812413303666411186051339002485237155449662

 

http://blog.naver.com/PostView.nhn?blogId=yjw_sz&logNo=221441769257&parentCategoryNo=&categoryNo=46&viewDate=&isShowPopularPosts=true&from=search

RSA for CTF

'5. 하스타드 공격'에 나와있는 코드를 수정하여 문제를 풀었다.

 

import binascii
from Crypto.PublicKey import RSA
from base64 import b64decode
 
print "\n"
print "\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
print "\t        RSA Hastad Attack         "
print "\t         JulesDT -- 2016          "
print "\t         License GNU/GPL          "
print "\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
 
def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)
 
    for n_i, a_i in zip(n, a):
        p = prod / n_i
        sum += a_i * mul_inv(p, n_i) * p
    return sum % prod
 
def mul_inv(a, b):
    b0 = b
    x0, x1 = 0, 1
    if b == 1: return 1
    while a > 1:
        q = a / b
        a, b = b, a%b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0: x1 += b0
    return x1
 
def find_invpow(x,n):
    high = 1
    while high ** n < x:
        high *= 2
    low = high/2
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1
 
def parseC(argv, index, verbose):
    import string
    file = open(argv[index],'r')
    cmd = ' '.join(argv)
    fileInput = ''.join(file.readlines()).strip()
    if '--decimal' in cmd:
        if verbose:
            print "##"
            print "##",fileInput
            print "## Considered as decimal input"
            print "##"
        return long(fileInput)
    elif '--hex' in cmd:
        if verbose:
            print "##"
            print "##",fileInput
            print "## Considered as hexadecimal input"
            print "##"
        return long(fileInput,16)
    elif '--b64' in cmd:
        if verbose:
            print "##"
            print "##",fileInput
            print "## Considered as base64 input"
            print "##"
        return long(binascii.hexlify(binascii.a2b_base64(fileInput)),16)
    else:
        try:
            fileInput = long(fileInput)
            if verbose:
                print "##"
                print "##",fileInput
                print "## Guessed as decimal input"
                print "##"
            return long(fileInput)
        except ValueError:
            if all(c in string.hexdigits for c in fileInput):
                if verbose:
                    print "##"
                    print "##",fileInput
                    print "## Guessed as hexadecimal input"
                    print "##"
                return long(fileInput,16)
            else:
                if verbose:
                    print "##"
                    print "##",fileInput
                    print "## Guessed as base64 input"
                    print "##"
                return long(binascii.hexlify(binascii.a2b_base64(fileInput)),16)
            pass
 
def parseN(argv,index):
    file = open(argv[index],'r')
    fileInput = ''.join(file.readlines()).strip()
    try:
        fileInput = long(fileInput)
        return fileInput
    except ValueError:
        from Crypto.PublicKey import RSA
        return long(RSA.importKey(fileInput).__getattr__('n'))
        pass
 
 
if __name__ == '__main__':
    e = 7
 
    n1 = 10022036265379037873283606776808482557866459308090111534883940865718177639983512662119342281119416241158033537298567286851709556229498058859877121683228774596682463530354223972067629198444968982788922250713559891865919261816911330848802614913631706032562776893224597357355324255263321117746371249374897281379618765006492730806494403308111072966637211560823960482878492897669436775113233218090173773953205373859777529204336743904524724605913439667291642450283502539056317167865950955271726411160185108661710605305209881749978968104668372320740311039079195405595564405545553067816984977942352952679613295335945453198237
    n2 = 5466545789924978392117734846441651025566944649290017587961487324101229594609777422305368037344954585418241587633957551279641772525768764611188988227720597556634650034264505822514430445671371902394845226110100975570935303274836520009041255673258743208173396958290432905543148641745168024380646078191379194650244323448918977124653886707963511968894925605598683697007725355334218510153808020236986866621440493131392397106674236875719949237921916816824901951782815445968997182425608119302657645645838081847911729329333764403590828687896595484627953582720022494684431177689169562431514156723717431880081981556861583018517
    n3 = 5216273350923762348996819172932047657740263255248423536832070896504436079290996116053910458202206066607495080005143242081376348478552546332314483414339219088245406077072653291793201707938210052137737032136008691204273974883871392886847900590411035963981133018158012140770585855836554605968542686051767074445169576528595295868833612083435959789899465479063315706805137423972403304919456897675923521668190245644201632092213606749130854730067502251227674778549657054487536558408785381601255488927062660442522496864532745842104460605804514922118066012819002689049981557892095296223518873642160006462186453091627377846719
    n4 = 23877677498268410284879275681599753946472064168982107017698987574875291853430610166705520818854679284024035965166084667071782959877626088875201104444061372210767667483286033873186027043018865270765379778972734594727020084433542927434622162385031073045949543728094450158066806302710336945902706311444702067892897382023369572561933840697091647190739941807440726157963736515169755622514090303488227644584510175870987096541366007967982302476854613123392400570876217436169696368690150208874814955767774660004903549034030453797617219708937501949676157124852802614561580437881345741238143591504284958256829966154954860310643
    n5 = 14095304106189288640829933284328100925981109805290171926596523882500992828050689610054551419208961617895244032677408948518722739184220513962788253695294440224817835843547289773514113860609727834208120554675150777100035341397359695754443831969620545126239117460426602273999534524462242741389375433175237422632997941648269022097426901783701566115072520388843879171454672942810241915423341751813855234874758865121037886735845464875242609743056346324057991215234482527871877337706502944703023808957350962273199545033462807203671480858363579332623386369851297631986187711675134368500976725781503614885257984375549898158689
    n6 = 2805822354201662117320594043711993782804865769293499426012360087817858551003001395302163740603703828195195932459444805174556152674013174027197071452536007720377642902614079800876454139985267840390802982000981391589121247087945323071621814892873054291187100453510563927190923456819020327967812411342557586095287060637718034456241630931342321644065932761169946330107762168341828247523519427454538373734712173180277190763105614286976239296025622448068573996830818370176355468420604889972971911137825122031079799394840034520000378583048365213663261323826755042085539056699658078298352991498848183741926741253336809983081
    n7 = 25454009749168470343695633209096091829115329722572151778843118833425745470034996921255287732666381145235781038972818879902175747917173596391714646458631517429967987558853821226063117620100131280109980358660151611745478185529770001530290709260636770225215186800776097876644514962324976911466656250316831758848397129882568596479711529118559633884457580705072157006277242414838614921959845416195868135339484150235079747708585021249992266719965641249640344662274664797188479304252760363884135230450876493335745378727727079727827645384850449255019980920544237025044248135670516643488962958548195014144666470074377908386063
 
    c1 = 7391172673494652807685679927464443742804469716124686497937352685631944739927403334100753118718810827819939551249092644730733640887813475157863909267732710966904033874563749607452101004880603517576015117231543666882714876053816889315304434716583902097326869862769223330226929267650196146699723546298777721549327230579524043853731525842228354074211952590809573512193002908675659981910521560218722078118583409532890190350278993572874200629804040761922640444870232404736174533503458666401049021690701120014711135662159756073554655169987524174160454336199103732766648969310872094773896573037726906071280884398964499625020
    c2 = 2843216698827041985234155126413219625102551967694195507616270458944256794024725727982775312996964360225107871298400288303715856835949437523897251998356574507142899492557143968158430397540293189973986706379386430519381858403628687144765951766733259166975201698201001559608435647196300391229794290104430338488390377935687114237067952186727947306540592887865659962691657932063711547531829312199823488118775597548579002212505954186919111624039557627729228692097539779090276034544147566301508294383730646789567286167983001460941761651651550106133788841812817514137482151210600991083197714286954280138543861307503606716687
    c3 = 2302840660982990706559514467752282608279989971179438892300937945447548784136021634663470424995563089657378083878340327507907273677046617011731588253183115962507981205380038591937454135692479378461272309601984068994340223460110011927750428790367899740123933101545519333275378177450046677349361228228756023343552737751276656981842493825940592644061106798477517795237715348144352954728534699021231559916391882314536204099649751257130666668855055343556693412599766542087842727824032038771853002304289245363376208213623603995010083510086051017014020583014841158059684157033215101586049552797894220844380611133865673630801
    c4 = 21542650580244090952784375188737468745448203348922868429406196302086271073676866277485976451720227641278427496915785578412784529024335740676758107987503859146577358215708248682437455044274509620470752764937668805057881069241160619380098319880566533327878406656365405208233812965208982731078254898819598904848966997244978017829737683687504578693319927257965587343277686790692897770069007188699761774062935389828173866322096724684461746266895396261083359145450376711339892131239899937109104845549497760224715797430549267596702844680269969086579967938513817206661072633561450576990683873838952925270459005180113251070249
    c5 = 5841298358718613696062311056221508337701416292725004974138314539876150378702426703549430117040191903647122061403407396288001626124108215908094632322171004807595060730467760110047822011747633210272450557602443585240325321882265082987790788937409746656818781811819115452970840966600299402274664167896074281874767663751931697405940475209595160606989446399735956632932740140774120362773964862067823210273048778380937955790417026758705126758582714675929109140032046187572583702405164513719448544031934183587141634161632757693697249167749952737814924049718225194470053426092226496663009906557955566430066736079650924094775
    c6 = 1840296233218477853481534562215626625414182376149520279565477106636326502423629202398872352247072974928247089059258779616805363438919346177179751144150840146502100528681001973857981344372271699254564085124019490542816704779558116713918712764905289545904746631301089653173086838314931849726257101196974182707388814949943497825270433233859953596462571591644141313685767121169211812959266024665387037379326240471760061808331954030889737904363024686917008151847474903564630772753685195974245871917099262116749552267414561620711561171348300446183668428521497810537883987976853838751652062973640912281502768323552961119727
    c7 = 789032093589329919433103064912734499692800138044594105985741187192587133548423627123979828515942204884228205644612915396782678903901468096055669312556620684388723470685365523376229767716532460150705694588934426363146781448912873886792079146178749619507171787017137430583992061952004088013585625578578697225347700205144867425958935656640766720643294601810945228322481781587820554087577038637902482084286507222529109418279162740318995563410236088568237694026601631788889001088963413678782229872782538151806577918829849586853938669782376616395525544507480942096894639889844916812413303666411186051339002485237155449662
 
    n = [n1,n2,n3,n4,n5,n6,n7]
    a = [c1,c2,c3,c4,c5,c6,c7]
 
    result = (chinese_remainder(n, a))
    resultHex = str(hex(find_invpow(result,e)))[2:-1]
    print ""
    print "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
    print "Decoded Hex :\n",resultHex
    print "---------------------------"
    print "As Ascii :\n",resultHex.decode('hex')
    print "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
 

 

FLAG : FLAG{}