728x90
반응형

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

1. d 값 계산복호화를 하기 위해 d 값이 필요한데, e 값이 주어지고 d 값을 모르는 경우가 대부분이다.e * ...

blog.naver.com

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

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
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 = 01
    if b == 1return 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**< x:
            low = mid
        elif high > mid and mid**> 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 "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
 
cs

 

FLAG : FLAG{}

728x90
반응형

'WAR GAME > System32.kr' 카테고리의 다른 글

System32.kr [RSA107] 풀이  (0) 2021.01.18
System32.kr [EZB64] 풀이  (0) 2019.12.28
System32.kr [RSA104] 풀이  (0) 2019.05.19
System32.kr [RSA105] 풀이  (0) 2019.05.19
System32.kr [RSA103] 풀이  (0) 2019.05.19

+ Recent posts