SYC三面

jrl Lv3
  2022-12-16 15:36:21 2022-12-16 15:36:21 Created   2023-07-26 18:40:35 2023-07-26 18:40:35 Updated    1.9k Words  9 Mins  

1.对于Task代码注释的补齐

1.1 Task：

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
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
import gmpy2 as gp
import random
from flag import flag
flag = bytes_to_long(flag)
p = getPrime(100)    #说明含义
q = getPrime(100)    #说明含义
n = p * q
clist = []
for i in bin(flag)[2:]:    #说明含义
    while True:
        x = random.randint(1, n)   #说明含义
        if gp.gcd(x, n) == 1:   #说明含义
            c = (pow(3, int(i) + x * 2, n) * x**2) % n     
            clist.append(c)
            break
print(n)

print(clist)
'''
1254676922968308054473282588201432441748387886551758353389559
[112490766735794793494258589897687977797993914062877995369853, 423825989606899409733986824741778284626898537704684650054048, 1239912440099782777043012567198356769914426423982980091061342, 1078272043845620437375344423460688188703277391763226546180151, 159286594418951337823608883690981934876156746053051292254402, 189434397083734065502133592439774066008070864031834709620441, 264105932521685455831442874483122006851812174082486446496525, 252479590298382195780257510632414277760400686563367629394825, 34602153293813328946647556336715300088648653636913843351330, 808692976248223555967993480457680585654329233137701900525232, 836623390705731389723338030121423143060093415003999783847569, 1218829648463542488706300570862499177531816513847669694517865, 571795296699927140597629733281737316938588378300113684751321, 324408602401500017634991400429058861929441907523133040616718, 652309276856121062936275131393396513436481452168222192943617, 135368324264829776566203256490111602190045577103623626459391, 677807894471260530035795635544578014296111908610448488780236, 1135708831589387209825610411788217272141435421502826225558333, 196882176169680492388044653063809988445336200851553236565493, 1130705847039352086713022625138307016610235729598245321418537, 974627899979016730650505688458957247745733629797568884460037, 948987355716018600108888773982169186615279073844787201014331, 364200727831752453880724784142441918092136276002472196567297, 811786724825671349602848333002825903390189436235744947667153, 248544601758659627780643527412918707686666534454807514221527, 1078860601713092925823762998344218082511712606733279204236487, 634851505432770176888905188832078431577879067601938324607512, 232972021265122845242665536151391828176473610240017058444456, 1080796896535347345799923528377657622102130648424673730618155, 622059452832122796944248249707923610120342427983134655552340, 837257289852652447556360719449396492271622453092839975184158, 626327369687614106133688347844033161113612134573404258486630, 1233019194503373412608053469954621323121044455057773900406773, 912564467902216938034173803480737819092198560216579817988291, 408076399689155479697691914877522087726703540593136498587215, 1118745562641959211267518507476218888452509349041078337285098, 1103228775032586830415033772993541541820163005491285279882940, 680899077364553221002722115625274809744677788062477442312086, 355349436487753936000721704075588637048102593449252106813298, 5254361838244723184679801326407268664182654715017847086461, 480145671282471097574354032682584083826945502763658946101104, 249136810947175342894562520096603076879372702701088690594445, 175216547555975039599856545426098941943382367602172941744494, 436310864447848960706296122266108102033486860525693191197797, 342620466614509535208918527767209905005823047382938223113086, 369848992268737575958936185907214270590887322936419642815242, 278575045025661827978388874494219837629182438978526195181637, 1189171180780533071473125545247289861677955100195126109964590, 256190182678715266654387215899616014762531664768736561586327, 719160215933023695898776016718481385742508618676368640641809, 147033122794177086112261858085593706727904275426698884436011, 247466503394960387825735598976068779045757078494832316444804, 787155643450160361724955357286670519256662665704845721250609, 112101120505278148126370035869523081506090979629681063614381, 890009544685851814191758439205974159586245412054287515881584, 1168625756997945588141764967298286550498540363325170551587334, 946031342434770434479581499217378781992921204179509449159996, 759124753621557368233069144948668001126536400499520990700641, 930584421635842804698880452391670787414151645249729141739148, 140981825203074314092967178062754008486703246602401550271041, 880126454149733441805446179826584472107299085899567279467558, 510129631452465708304688340114214360026947205003705062663759, 857274757020001316639221394675820731579775247610619594760511, 444486969413575687285961819261097401974268741167841964919716, 645830958128126799221416466698967430939726760487764050203821, 128864469762235652994228226148325614187747349331618451490354, 732913002124581119538173953534485652651112140400076340646452, 1245672039639609341331477592944058028011275464117654972595670, 1160765030758624190775369713232721901616189349905945190302338, 745734132091942990384796294800038299023052878196943617322617, 34973161572808799782240527358912894045293050940490682156733, 507586651070816931641904112686082840821460472219390068396982, 359195216122538975934588740641220005777478961423841727365432, 60506687352654743312206686911057762445232526009857863834444, 402036521271253699065227780662896890228371046068283711170220, 465427226677337673103293964961886503610313835775181975449721, 925246962888172144515172444374190859841851825972285013006527, 542176614893876361668218387162168517498644799220587472896002, 852215132196560596695876248813488364201491362280912035912061, 945548964927065532651141821562204387565145712002346337639711, 736943822066388892909878515650831955490636214039062998720510, 766357526983761241394182000478355475617711906398422036954152, 77156525593382594092608158744099524034892127423492520631820, 562562817542804973601572838378263130638457829485887327130286, 768093992370198202822524520006977816845162154854939167515517, 1099957424762490943973557935337350760135180754563993547358098, 698816668614997174913438496891169625976027534942525487303513, 417641699919584202170293946436276552973997395211792288687960, 1006229610175567855209117721408416419896921240126676949824724, 4206431689326446028142220658552064336105749936096602165359, 893846509909828693967573302731018066461118006150050253703744, 878425189026235350891203121924637130803808920422558040493294, 730047416245095988472212050949689633327186823542036387345181, 648095719945750715387983948406690533087473721929975873848169, 213513454359755001454814601053555627585345770061082141021326, 350001050012957205656929492039628823072469208940960439158263, 1016858635000037892730835311903706149371704230428070443107320, 1040987439471207869975679257301693610464700899302787643642354, 1194690615352550474729309715449838057220521596135246725909553, 508165053077110820797186371383859674371399129952105597675096, 266494438294281492504556232035584920066331725618646155019547, 28469482072427012244441092412738741355431846649166066368980, 790175775999108776289865518368056397969387298334297622465909, 590581138260907253939363764832940322585129285968275409510634, 221909012579985462013325803334419731308959816500415305934495, 1063780559219791515938747204569742799329237935871594345400252, 977747525495509380693721486866821791065499754056415279744653, 346306061371595730004513789139807509540063462412619321003626, 456103179467597859705969406860196938169100856240100927540401, 969300078509189631808517876996065933181606409375207150288464, 1029806631220370012120597683927351131622576733031694535189521, 344896431603140401163996810922500893279239069499717183710501, 430000423804197030568046280589772094106128395099434235915031, 700179843567016021775399107572964843751703290591400960796112, 961227906080189143689698720420426659986080298413605666115640, 607209606799750473714271393200060455739097869884727178692312, 106958847163040842225140399905505511449479709017540851084532, 953369942103273809257762268859167463617831445026988544378658, 428269440686506672744282327102546440435442014650795927162711, 56621803434665963032193024056111306570802155743250152849716, 800707635631355839166448276143596444307614901816577459076131, 1032256515703247765067950588859299047987257001987777631061065, 813725055801254665600156259482200403981770576173968929131487, 940024839745068011043019236327963504645352520797347949823455, 1065005324140908547287467504568283884363143527586278243210801, 1087828777506290663525994551834233065465427418753806182842291, 668387132001968449612224853010931354244797738682007519611989, 563185246196177998134932666270526715161378776103340983046580, 148292872313931508344196679476720973752571125303712466045656, 413889563851226543249984374872220761253120628252088546262699, 853542105910386365929770611480736086723126396438880650918917, 59730458840715910492468261806200793684923819793480597554146, 792260492800286127199649276659137441324248689470594987965190, 753608630500639136668081531883097047491651258191552267413126, 33514911499472634865669915075769163328171019557849259474018, 634963859228206842307837566519244534650818456901841184879977, 219354096455968590219445072777282329948785844491217770978344, 1123377226439583158729762969668999276741275445803396272436031, 357765295513680388973981712560200525235334734759663454993805, 385868499980630535766019957877752149506518574529845752144666, 138578212294299392480319417966870656714476525885983752756188, 1110526796192425688386237355263892073046060477008920073455044, 244699783645221387947312903861559688207612147588246639081699, 583209905862562678600202085212425597809036630416117298854978, 1207854793808762194414317661151529169444903662139065050090746, 1127506983223466275821900811940356395242309493951089427884032, 526185119576631048584313761548704536031634598332129570964689, 266882032196696984660521486449809902101615921156569537960109, 1188118705564450461919200724390473040524626320052324478509883, 682831747455078454647149830819696088960233603851250102828667, 669419928942561433130809268138650695825596612075801278942980, 1077750630919867687880983437504767304166615787212813240073843, 486023540111308483450127320955599047045479654684477043315645, 409429366346146233850088863324915025465847596238000661872172, 779883595226131237594759409249289551033410304517183865388408, 1155872225708857920911178110668279174877878422508206228579940, 411063490066038942009369947241345843238439795078686488373864, 1243453053541946030699872676712518536022061850799945414120045, 871711034820169700581685353768658469631429266493677466057997, 601920686459160120670719526703980120744719013393032353678765, 329932100141177850249406090412821976994089707958551194468769, 558327299751202100333335353826111016492585371503632197870640, 113444032302978611299580451314055133491399096282744687816086, 152525914892717139057165748051966776217223953242540511499945, 965404850400527912039904270871065001313018148780552532312669, 313557099445185696402013375071955475516203519824979749629786, 952254159335810337756614972813240144837526566801182319987154]
'''


1.2 注释与补齐：

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
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
import gmpy2 as gp
import random
from flag import flag  #flag未知
flag = bytes_to_long(flag)
#getPrime来自Crypto库中的Util.number模块，其作用是随机获得一个N比特位的素数，同时进行检验，确保正确性  
p = getPrime(100)   #随机获得一个100比特位的素数，并将它的值赋值给p
q = getPrime(100)   #随机获得一个100比特位的素数，并将它的值赋值给q
n = p * q
clist = []
for i in bin(flag)[2:]:    #将flag转为二进制数，获取从偏移为2到末尾的数，再历遍所有可能
    while True:
        x = random.randint(1, n)   #生成在1与n之间的整数x(1<=x<=n)
        if gp.gcd(x, n) == 1:   #引用gp.gcd函数，判断x与n是否互质
            c = (pow(3, int(i) + x * 2, n) * x**2) % n     
            clist.append(c)  #将c添加到clist列表末尾
            break
print(n)

print(clist)

#给出n与若干组c的值
'''
1254676922968308054473282588201432441748387886551758353389559
[112490766735794793494258589897687977797993914062877995369853, 423825989606899409733986824741778284626898537704684650054048, 1239912440099782777043012567198356769914426423982980091061342, 1078272043845620437375344423460688188703277391763226546180151, 159286594418951337823608883690981934876156746053051292254402, 189434397083734065502133592439774066008070864031834709620441, 264105932521685455831442874483122006851812174082486446496525, 252479590298382195780257510632414277760400686563367629394825, 34602153293813328946647556336715300088648653636913843351330, 808692976248223555967993480457680585654329233137701900525232, 836623390705731389723338030121423143060093415003999783847569, 1218829648463542488706300570862499177531816513847669694517865, 571795296699927140597629733281737316938588378300113684751321, 324408602401500017634991400429058861929441907523133040616718, 652309276856121062936275131393396513436481452168222192943617, 135368324264829776566203256490111602190045577103623626459391, 677807894471260530035795635544578014296111908610448488780236, 1135708831589387209825610411788217272141435421502826225558333, 196882176169680492388044653063809988445336200851553236565493, 1130705847039352086713022625138307016610235729598245321418537, 974627899979016730650505688458957247745733629797568884460037, 948987355716018600108888773982169186615279073844787201014331, 364200727831752453880724784142441918092136276002472196567297, 811786724825671349602848333002825903390189436235744947667153, 248544601758659627780643527412918707686666534454807514221527, 1078860601713092925823762998344218082511712606733279204236487, 634851505432770176888905188832078431577879067601938324607512, 232972021265122845242665536151391828176473610240017058444456, 1080796896535347345799923528377657622102130648424673730618155, 622059452832122796944248249707923610120342427983134655552340, 837257289852652447556360719449396492271622453092839975184158, 626327369687614106133688347844033161113612134573404258486630, 1233019194503373412608053469954621323121044455057773900406773, 912564467902216938034173803480737819092198560216579817988291, 408076399689155479697691914877522087726703540593136498587215, 1118745562641959211267518507476218888452509349041078337285098, 1103228775032586830415033772993541541820163005491285279882940, 680899077364553221002722115625274809744677788062477442312086, 355349436487753936000721704075588637048102593449252106813298, 5254361838244723184679801326407268664182654715017847086461, 480145671282471097574354032682584083826945502763658946101104, 249136810947175342894562520096603076879372702701088690594445, 175216547555975039599856545426098941943382367602172941744494, 436310864447848960706296122266108102033486860525693191197797, 342620466614509535208918527767209905005823047382938223113086, 369848992268737575958936185907214270590887322936419642815242, 278575045025661827978388874494219837629182438978526195181637, 1189171180780533071473125545247289861677955100195126109964590, 256190182678715266654387215899616014762531664768736561586327, 719160215933023695898776016718481385742508618676368640641809, 147033122794177086112261858085593706727904275426698884436011, 247466503394960387825735598976068779045757078494832316444804, 787155643450160361724955357286670519256662665704845721250609, 112101120505278148126370035869523081506090979629681063614381, 890009544685851814191758439205974159586245412054287515881584, 1168625756997945588141764967298286550498540363325170551587334, 946031342434770434479581499217378781992921204179509449159996, 759124753621557368233069144948668001126536400499520990700641, 930584421635842804698880452391670787414151645249729141739148, 140981825203074314092967178062754008486703246602401550271041, 880126454149733441805446179826584472107299085899567279467558, 510129631452465708304688340114214360026947205003705062663759, 857274757020001316639221394675820731579775247610619594760511, 444486969413575687285961819261097401974268741167841964919716, 645830958128126799221416466698967430939726760487764050203821, 128864469762235652994228226148325614187747349331618451490354, 732913002124581119538173953534485652651112140400076340646452, 1245672039639609341331477592944058028011275464117654972595670, 1160765030758624190775369713232721901616189349905945190302338, 745734132091942990384796294800038299023052878196943617322617, 34973161572808799782240527358912894045293050940490682156733, 507586651070816931641904112686082840821460472219390068396982, 359195216122538975934588740641220005777478961423841727365432, 60506687352654743312206686911057762445232526009857863834444, 402036521271253699065227780662896890228371046068283711170220, 465427226677337673103293964961886503610313835775181975449721, 925246962888172144515172444374190859841851825972285013006527, 542176614893876361668218387162168517498644799220587472896002, 852215132196560596695876248813488364201491362280912035912061, 945548964927065532651141821562204387565145712002346337639711, 736943822066388892909878515650831955490636214039062998720510, 766357526983761241394182000478355475617711906398422036954152, 77156525593382594092608158744099524034892127423492520631820, 562562817542804973601572838378263130638457829485887327130286, 768093992370198202822524520006977816845162154854939167515517, 1099957424762490943973557935337350760135180754563993547358098, 698816668614997174913438496891169625976027534942525487303513, 417641699919584202170293946436276552973997395211792288687960, 1006229610175567855209117721408416419896921240126676949824724, 4206431689326446028142220658552064336105749936096602165359, 893846509909828693967573302731018066461118006150050253703744, 878425189026235350891203121924637130803808920422558040493294, 730047416245095988472212050949689633327186823542036387345181, 648095719945750715387983948406690533087473721929975873848169, 213513454359755001454814601053555627585345770061082141021326, 350001050012957205656929492039628823072469208940960439158263, 1016858635000037892730835311903706149371704230428070443107320, 1040987439471207869975679257301693610464700899302787643642354, 1194690615352550474729309715449838057220521596135246725909553, 508165053077110820797186371383859674371399129952105597675096, 266494438294281492504556232035584920066331725618646155019547, 28469482072427012244441092412738741355431846649166066368980, 790175775999108776289865518368056397969387298334297622465909, 590581138260907253939363764832940322585129285968275409510634, 221909012579985462013325803334419731308959816500415305934495, 1063780559219791515938747204569742799329237935871594345400252, 977747525495509380693721486866821791065499754056415279744653, 346306061371595730004513789139807509540063462412619321003626, 456103179467597859705969406860196938169100856240100927540401, 969300078509189631808517876996065933181606409375207150288464, 1029806631220370012120597683927351131622576733031694535189521, 344896431603140401163996810922500893279239069499717183710501, 430000423804197030568046280589772094106128395099434235915031, 700179843567016021775399107572964843751703290591400960796112, 961227906080189143689698720420426659986080298413605666115640, 607209606799750473714271393200060455739097869884727178692312, 106958847163040842225140399905505511449479709017540851084532, 953369942103273809257762268859167463617831445026988544378658, 428269440686506672744282327102546440435442014650795927162711, 56621803434665963032193024056111306570802155743250152849716, 800707635631355839166448276143596444307614901816577459076131, 1032256515703247765067950588859299047987257001987777631061065, 813725055801254665600156259482200403981770576173968929131487, 940024839745068011043019236327963504645352520797347949823455, 1065005324140908547287467504568283884363143527586278243210801, 1087828777506290663525994551834233065465427418753806182842291, 668387132001968449612224853010931354244797738682007519611989, 563185246196177998134932666270526715161378776103340983046580, 148292872313931508344196679476720973752571125303712466045656, 413889563851226543249984374872220761253120628252088546262699, 853542105910386365929770611480736086723126396438880650918917, 59730458840715910492468261806200793684923819793480597554146, 792260492800286127199649276659137441324248689470594987965190, 753608630500639136668081531883097047491651258191552267413126, 33514911499472634865669915075769163328171019557849259474018, 634963859228206842307837566519244534650818456901841184879977, 219354096455968590219445072777282329948785844491217770978344, 1123377226439583158729762969668999276741275445803396272436031, 357765295513680388973981712560200525235334734759663454993805, 385868499980630535766019957877752149506518574529845752144666, 138578212294299392480319417966870656714476525885983752756188, 1110526796192425688386237355263892073046060477008920073455044, 244699783645221387947312903861559688207612147588246639081699, 583209905862562678600202085212425597809036630416117298854978, 1207854793808762194414317661151529169444903662139065050090746, 1127506983223466275821900811940356395242309493951089427884032, 526185119576631048584313761548704536031634598332129570964689, 266882032196696984660521486449809902101615921156569537960109, 1188118705564450461919200724390473040524626320052324478509883, 682831747455078454647149830819696088960233603851250102828667, 669419928942561433130809268138650695825596612075801278942980, 1077750630919867687880983437504767304166615787212813240073843, 486023540111308483450127320955599047045479654684477043315645, 409429366346146233850088863324915025465847596238000661872172, 779883595226131237594759409249289551033410304517183865388408, 1155872225708857920911178110668279174877878422508206228579940, 411063490066038942009369947241345843238439795078686488373864, 1243453053541946030699872676712518536022061850799945414120045, 871711034820169700581685353768658469631429266493677466057997, 601920686459160120670719526703980120744719013393032353678765, 329932100141177850249406090412821976994089707958551194468769, 558327299751202100333335353826111016492585371503632197870640, 113444032302978611299580451314055133491399096282744687816086, 152525914892717139057165748051966776217223953242540511499945, 965404850400527912039904270871065001313018148780552532312669, 313557099445185696402013375071955475516203519824979749629786, 952254159335810337756614972813240144837526566801182319987154]
'''


2.Paper‘s notes

2.1 关于数论：

image-20221128155523295

论文中会自主定义一些乘法群、域

image-20221128160020999

2.2 中国剩余定理与二次剩余：

2.2.1 中国剩余定理：

image-20221128161638439

中国剩余定理公式：

设正整数img两两互素，则同余方程组

​ img

有整数解。并且在模img下的解是唯一的，解为

​ img

其中img，而img为img模img的逆元。

中国剩余定理学习笔记 - MashiroSky - 博客园 (cnblogs.com)

2.2.2 二次剩余：

1. 二次剩余定理：

对于n和素数p来说，存在x使

方程 x^2≡n(mod p)

成立

2. 引入符号：

勒让德符号，这个符号里有两个值，一个是n,一个是p。假设p为奇素数，且n无法整除p时，有以下定义

image-20221128164649412

image-20221128164748783

类似于paper中的雅可比符号

image-20221128171832142

3. 证明：

image-20221128165544913

(5条消息) 二次剩余定理详解_gerayking的博客-CSDN博客_二次剩余定理

2.3 笔记整理：

2.3.1 算法：

1. 判断x是否为二次剩余
image-20221128222232986
2. 用N已知的因子p、q判断模N下数x是否为二次剩余
image-20221128222558921
3. 已知条件
image-20221128232726545
4. 加密算法
image-20221128233704272
5. 解密算法

由于接收者已知私钥：p、q，他就不需要另外单独的解密算法，通过判断c是否为二次剩余，他就可以知道密文为0还是1。

image-20221128234457449

2.3.2 命题：

1. 二次剩余

image-20221128234820942

2. 雅可比符号

image-20221128234849165

3. 雅可比乘法性质

image-20221128234920652

4. 二次剩余的复合运算

image-20221128235001930

5. 二次剩余与雅可比的分布

image-20221128235046610

image-20221128235104749

6. 雅可比的复合运算

image-20221128235142046

3. Task解题

3.1 题目模型：

本task的模型是 Goldwasser-Micali Cryprosystem，即GM公钥加密系统

image-20221129005320790

3.2解题思路：

3.2.1 题目分析：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
import gmpy2 as gp
import random
from flag import flag
flag = bytes_to_long(flag)
p = getPrime(100)   
q = getPrime(100)    
n = p * q
clist = []
for i in bin(flag)[2:]:    
    while True:
        x = random.randint(1, n)  
        if gp.gcd(x, n) == 1:  
            c = (pow(3, int(i) + x * 2, n) * x**2) % n     
            clist.append(c)
            break
print(n)

print(clist)
'''
1254676922968308054473282588201432441748387886551758353389559
[112490766735794793494258589897687977797993914062877995369853, 423825989606899409733986824741778284626898537704684650054048, 1239912440099782777043012567198356769914426423982980091061342, 1078272043845620437375344423460688188703277391763226546180151, 159286594418951337823608883690981934876156746053051292254402, 189434397083734065502133592439774066008070864031834709620441, 264105932521685455831442874483122006851812174082486446496525, 252479590298382195780257510632414277760400686563367629394825, 34602153293813328946647556336715300088648653636913843351330, 808692976248223555967993480457680585654329233137701900525232, 836623390705731389723338030121423143060093415003999783847569, 1218829648463542488706300570862499177531816513847669694517865, 571795296699927140597629733281737316938588378300113684751321, 324408602401500017634991400429058861929441907523133040616718, 652309276856121062936275131393396513436481452168222192943617, 135368324264829776566203256490111602190045577103623626459391, 677807894471260530035795635544578014296111908610448488780236, 1135708831589387209825610411788217272141435421502826225558333, 196882176169680492388044653063809988445336200851553236565493, 1130705847039352086713022625138307016610235729598245321418537, 974627899979016730650505688458957247745733629797568884460037, 948987355716018600108888773982169186615279073844787201014331, 364200727831752453880724784142441918092136276002472196567297, 811786724825671349602848333002825903390189436235744947667153, 248544601758659627780643527412918707686666534454807514221527, 1078860601713092925823762998344218082511712606733279204236487, 634851505432770176888905188832078431577879067601938324607512, 232972021265122845242665536151391828176473610240017058444456, 1080796896535347345799923528377657622102130648424673730618155, 622059452832122796944248249707923610120342427983134655552340, 837257289852652447556360719449396492271622453092839975184158, 626327369687614106133688347844033161113612134573404258486630, 1233019194503373412608053469954621323121044455057773900406773, 912564467902216938034173803480737819092198560216579817988291, 408076399689155479697691914877522087726703540593136498587215, 1118745562641959211267518507476218888452509349041078337285098, 1103228775032586830415033772993541541820163005491285279882940, 680899077364553221002722115625274809744677788062477442312086, 355349436487753936000721704075588637048102593449252106813298, 5254361838244723184679801326407268664182654715017847086461, 480145671282471097574354032682584083826945502763658946101104, 249136810947175342894562520096603076879372702701088690594445, 175216547555975039599856545426098941943382367602172941744494, 436310864447848960706296122266108102033486860525693191197797, 342620466614509535208918527767209905005823047382938223113086, 369848992268737575958936185907214270590887322936419642815242, 278575045025661827978388874494219837629182438978526195181637, 1189171180780533071473125545247289861677955100195126109964590, 256190182678715266654387215899616014762531664768736561586327, 719160215933023695898776016718481385742508618676368640641809, 147033122794177086112261858085593706727904275426698884436011, 247466503394960387825735598976068779045757078494832316444804, 787155643450160361724955357286670519256662665704845721250609, 112101120505278148126370035869523081506090979629681063614381, 890009544685851814191758439205974159586245412054287515881584, 1168625756997945588141764967298286550498540363325170551587334, 946031342434770434479581499217378781992921204179509449159996, 759124753621557368233069144948668001126536400499520990700641, 930584421635842804698880452391670787414151645249729141739148, 140981825203074314092967178062754008486703246602401550271041, 880126454149733441805446179826584472107299085899567279467558, 510129631452465708304688340114214360026947205003705062663759, 857274757020001316639221394675820731579775247610619594760511, 444486969413575687285961819261097401974268741167841964919716, 645830958128126799221416466698967430939726760487764050203821, 128864469762235652994228226148325614187747349331618451490354, 732913002124581119538173953534485652651112140400076340646452, 1245672039639609341331477592944058028011275464117654972595670, 1160765030758624190775369713232721901616189349905945190302338, 745734132091942990384796294800038299023052878196943617322617, 34973161572808799782240527358912894045293050940490682156733, 507586651070816931641904112686082840821460472219390068396982, 359195216122538975934588740641220005777478961423841727365432, 60506687352654743312206686911057762445232526009857863834444, 402036521271253699065227780662896890228371046068283711170220, 465427226677337673103293964961886503610313835775181975449721, 925246962888172144515172444374190859841851825972285013006527, 542176614893876361668218387162168517498644799220587472896002, 852215132196560596695876248813488364201491362280912035912061, 945548964927065532651141821562204387565145712002346337639711, 736943822066388892909878515650831955490636214039062998720510, 766357526983761241394182000478355475617711906398422036954152, 77156525593382594092608158744099524034892127423492520631820, 562562817542804973601572838378263130638457829485887327130286, 768093992370198202822524520006977816845162154854939167515517, 1099957424762490943973557935337350760135180754563993547358098, 698816668614997174913438496891169625976027534942525487303513, 417641699919584202170293946436276552973997395211792288687960, 1006229610175567855209117721408416419896921240126676949824724, 4206431689326446028142220658552064336105749936096602165359, 893846509909828693967573302731018066461118006150050253703744, 878425189026235350891203121924637130803808920422558040493294, 730047416245095988472212050949689633327186823542036387345181, 648095719945750715387983948406690533087473721929975873848169, 213513454359755001454814601053555627585345770061082141021326, 350001050012957205656929492039628823072469208940960439158263, 1016858635000037892730835311903706149371704230428070443107320, 1040987439471207869975679257301693610464700899302787643642354, 1194690615352550474729309715449838057220521596135246725909553, 508165053077110820797186371383859674371399129952105597675096, 266494438294281492504556232035584920066331725618646155019547, 28469482072427012244441092412738741355431846649166066368980, 790175775999108776289865518368056397969387298334297622465909, 590581138260907253939363764832940322585129285968275409510634, 221909012579985462013325803334419731308959816500415305934495, 1063780559219791515938747204569742799329237935871594345400252, 977747525495509380693721486866821791065499754056415279744653, 346306061371595730004513789139807509540063462412619321003626, 456103179467597859705969406860196938169100856240100927540401, 969300078509189631808517876996065933181606409375207150288464, 1029806631220370012120597683927351131622576733031694535189521, 344896431603140401163996810922500893279239069499717183710501, 430000423804197030568046280589772094106128395099434235915031, 700179843567016021775399107572964843751703290591400960796112, 961227906080189143689698720420426659986080298413605666115640, 607209606799750473714271393200060455739097869884727178692312, 106958847163040842225140399905505511449479709017540851084532, 953369942103273809257762268859167463617831445026988544378658, 428269440686506672744282327102546440435442014650795927162711, 56621803434665963032193024056111306570802155743250152849716, 800707635631355839166448276143596444307614901816577459076131, 1032256515703247765067950588859299047987257001987777631061065, 813725055801254665600156259482200403981770576173968929131487, 940024839745068011043019236327963504645352520797347949823455, 1065005324140908547287467504568283884363143527586278243210801, 1087828777506290663525994551834233065465427418753806182842291, 668387132001968449612224853010931354244797738682007519611989, 563185246196177998134932666270526715161378776103340983046580, 148292872313931508344196679476720973752571125303712466045656, 413889563851226543249984374872220761253120628252088546262699, 853542105910386365929770611480736086723126396438880650918917, 59730458840715910492468261806200793684923819793480597554146, 792260492800286127199649276659137441324248689470594987965190, 753608630500639136668081531883097047491651258191552267413126, 33514911499472634865669915075769163328171019557849259474018, 634963859228206842307837566519244534650818456901841184879977, 219354096455968590219445072777282329948785844491217770978344, 1123377226439583158729762969668999276741275445803396272436031, 357765295513680388973981712560200525235334734759663454993805, 385868499980630535766019957877752149506518574529845752144666, 138578212294299392480319417966870656714476525885983752756188, 1110526796192425688386237355263892073046060477008920073455044, 244699783645221387947312903861559688207612147588246639081699, 583209905862562678600202085212425597809036630416117298854978, 1207854793808762194414317661151529169444903662139065050090746, 1127506983223466275821900811940356395242309493951089427884032, 526185119576631048584313761548704536031634598332129570964689, 266882032196696984660521486449809902101615921156569537960109, 1188118705564450461919200724390473040524626320052324478509883, 682831747455078454647149830819696088960233603851250102828667, 669419928942561433130809268138650695825596612075801278942980, 1077750630919867687880983437504767304166615787212813240073843, 486023540111308483450127320955599047045479654684477043315645, 409429366346146233850088863324915025465847596238000661872172, 779883595226131237594759409249289551033410304517183865388408, 1155872225708857920911178110668279174877878422508206228579940, 411063490066038942009369947241345843238439795078686488373864, 1243453053541946030699872676712518536022061850799945414120045, 871711034820169700581685353768658469631429266493677466057997, 601920686459160120670719526703980120744719013393032353678765, 329932100141177850249406090412821976994089707958551194468769, 558327299751202100333335353826111016492585371503632197870640, 113444032302978611299580451314055133491399096282744687816086, 152525914892717139057165748051966776217223953242540511499945, 965404850400527912039904270871065001313018148780552532312669, 313557099445185696402013375071955475516203519824979749629786, 952254159335810337756614972813240144837526566801182319987154]
'''
1
2
3
4
5
6
7
8
9
for i in bin(flag)[2:]:    
    #历遍转化为二进制数的flag，即逐位获得flag的二进制位
    while True:
        x = random.randint(1, n)  
        #在（1，n）的范围内随机选择用于加密信息的x
        if gp.gcd(x, n) == 1:  
            c = (pow(3, int(i) + x * 2, n) * x**2) % n     
            clist.append(c)
            break

我们观察到本task的模型是 Goldwasser-Micali Cryprosystem，c的加密方式也已经给出，并且在clist数组内列出了每个c的值。

c是这样加密的：c=(3^(int(i)+2x)*x^2)%n

仔细观察上式，发现当i=0时情况特殊。若i=0,则c=(3^x*x)^2%n

而此时c是模n的二次剩余。

$$
总结一下，当c是模n的二次剩余，即J_n(c)=1时，i=0
$$

$$
那么相反，当c是模n的非二次剩余，即J_n(c)=-1时，i=1
$$

3.2.2 破解流程：

我们先列出已知条件，即n与clist中若干组加密的c的值

1
2
3
4
n=1254676922968308054473282588201432441748387886551758353389559
clist=['''
''' ]

通过分析，我们发现能够在仅知道公钥n的条件下，通过jacobi判断c是否为二次剩余对flag进行还原。

攻击设计如下

1
2
3
4
5
6
7
8
flag=''
#历遍给出的若干组c
for c in clist:   
#判断“二次剩余”，逐个还原flag的二进制数
	if gp.jacobi(c,n)==1:
		flag+='0'
	if  gp.jacobi(c,n)==-1:	
		flag+='1'
3.2.3 攻击脚本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#GM脚本
import gmpy2 as gp
from libnum import*

n=1254676922968308054473282588201432441748387886551758353389559
clist=[112490766735794793494258589897687977797993914062877995369853, 423825989606899409733986824741778284626898537704684650054048, 1239912440099782777043012567198356769914426423982980091061342, 1078272043845620437375344423460688188703277391763226546180151, 159286594418951337823608883690981934876156746053051292254402, 189434397083734065502133592439774066008070864031834709620441, 264105932521685455831442874483122006851812174082486446496525, 252479590298382195780257510632414277760400686563367629394825, 34602153293813328946647556336715300088648653636913843351330, 808692976248223555967993480457680585654329233137701900525232, 836623390705731389723338030121423143060093415003999783847569, 1218829648463542488706300570862499177531816513847669694517865, 571795296699927140597629733281737316938588378300113684751321, 324408602401500017634991400429058861929441907523133040616718, 652309276856121062936275131393396513436481452168222192943617, 135368324264829776566203256490111602190045577103623626459391, 677807894471260530035795635544578014296111908610448488780236, 1135708831589387209825610411788217272141435421502826225558333, 196882176169680492388044653063809988445336200851553236565493, 1130705847039352086713022625138307016610235729598245321418537, 974627899979016730650505688458957247745733629797568884460037, 948987355716018600108888773982169186615279073844787201014331, 364200727831752453880724784142441918092136276002472196567297, 811786724825671349602848333002825903390189436235744947667153, 248544601758659627780643527412918707686666534454807514221527, 1078860601713092925823762998344218082511712606733279204236487, 634851505432770176888905188832078431577879067601938324607512, 232972021265122845242665536151391828176473610240017058444456, 1080796896535347345799923528377657622102130648424673730618155, 622059452832122796944248249707923610120342427983134655552340, 837257289852652447556360719449396492271622453092839975184158, 626327369687614106133688347844033161113612134573404258486630, 1233019194503373412608053469954621323121044455057773900406773, 912564467902216938034173803480737819092198560216579817988291, 408076399689155479697691914877522087726703540593136498587215, 1118745562641959211267518507476218888452509349041078337285098, 1103228775032586830415033772993541541820163005491285279882940, 680899077364553221002722115625274809744677788062477442312086, 355349436487753936000721704075588637048102593449252106813298, 5254361838244723184679801326407268664182654715017847086461, 480145671282471097574354032682584083826945502763658946101104, 249136810947175342894562520096603076879372702701088690594445, 175216547555975039599856545426098941943382367602172941744494, 436310864447848960706296122266108102033486860525693191197797, 342620466614509535208918527767209905005823047382938223113086, 369848992268737575958936185907214270590887322936419642815242, 278575045025661827978388874494219837629182438978526195181637, 1189171180780533071473125545247289861677955100195126109964590, 256190182678715266654387215899616014762531664768736561586327, 719160215933023695898776016718481385742508618676368640641809, 147033122794177086112261858085593706727904275426698884436011, 247466503394960387825735598976068779045757078494832316444804, 787155643450160361724955357286670519256662665704845721250609, 112101120505278148126370035869523081506090979629681063614381, 890009544685851814191758439205974159586245412054287515881584, 1168625756997945588141764967298286550498540363325170551587334, 946031342434770434479581499217378781992921204179509449159996, 759124753621557368233069144948668001126536400499520990700641, 930584421635842804698880452391670787414151645249729141739148, 140981825203074314092967178062754008486703246602401550271041, 880126454149733441805446179826584472107299085899567279467558, 510129631452465708304688340114214360026947205003705062663759, 857274757020001316639221394675820731579775247610619594760511, 444486969413575687285961819261097401974268741167841964919716, 645830958128126799221416466698967430939726760487764050203821, 128864469762235652994228226148325614187747349331618451490354, 732913002124581119538173953534485652651112140400076340646452, 1245672039639609341331477592944058028011275464117654972595670, 1160765030758624190775369713232721901616189349905945190302338, 745734132091942990384796294800038299023052878196943617322617, 34973161572808799782240527358912894045293050940490682156733, 507586651070816931641904112686082840821460472219390068396982, 359195216122538975934588740641220005777478961423841727365432, 60506687352654743312206686911057762445232526009857863834444, 402036521271253699065227780662896890228371046068283711170220, 465427226677337673103293964961886503610313835775181975449721, 925246962888172144515172444374190859841851825972285013006527, 542176614893876361668218387162168517498644799220587472896002, 852215132196560596695876248813488364201491362280912035912061, 945548964927065532651141821562204387565145712002346337639711, 736943822066388892909878515650831955490636214039062998720510, 766357526983761241394182000478355475617711906398422036954152, 77156525593382594092608158744099524034892127423492520631820, 562562817542804973601572838378263130638457829485887327130286, 768093992370198202822524520006977816845162154854939167515517, 1099957424762490943973557935337350760135180754563993547358098, 698816668614997174913438496891169625976027534942525487303513, 417641699919584202170293946436276552973997395211792288687960, 1006229610175567855209117721408416419896921240126676949824724, 4206431689326446028142220658552064336105749936096602165359, 893846509909828693967573302731018066461118006150050253703744, 878425189026235350891203121924637130803808920422558040493294, 730047416245095988472212050949689633327186823542036387345181, 648095719945750715387983948406690533087473721929975873848169, 213513454359755001454814601053555627585345770061082141021326, 350001050012957205656929492039628823072469208940960439158263, 1016858635000037892730835311903706149371704230428070443107320, 1040987439471207869975679257301693610464700899302787643642354, 1194690615352550474729309715449838057220521596135246725909553, 508165053077110820797186371383859674371399129952105597675096, 266494438294281492504556232035584920066331725618646155019547, 28469482072427012244441092412738741355431846649166066368980, 790175775999108776289865518368056397969387298334297622465909, 590581138260907253939363764832940322585129285968275409510634, 221909012579985462013325803334419731308959816500415305934495, 1063780559219791515938747204569742799329237935871594345400252, 977747525495509380693721486866821791065499754056415279744653, 346306061371595730004513789139807509540063462412619321003626, 456103179467597859705969406860196938169100856240100927540401, 969300078509189631808517876996065933181606409375207150288464, 1029806631220370012120597683927351131622576733031694535189521, 344896431603140401163996810922500893279239069499717183710501, 430000423804197030568046280589772094106128395099434235915031, 700179843567016021775399107572964843751703290591400960796112, 961227906080189143689698720420426659986080298413605666115640, 607209606799750473714271393200060455739097869884727178692312, 106958847163040842225140399905505511449479709017540851084532, 953369942103273809257762268859167463617831445026988544378658, 428269440686506672744282327102546440435442014650795927162711, 56621803434665963032193024056111306570802155743250152849716, 800707635631355839166448276143596444307614901816577459076131, 1032256515703247765067950588859299047987257001987777631061065, 813725055801254665600156259482200403981770576173968929131487, 940024839745068011043019236327963504645352520797347949823455, 1065005324140908547287467504568283884363143527586278243210801, 1087828777506290663525994551834233065465427418753806182842291, 668387132001968449612224853010931354244797738682007519611989, 563185246196177998134932666270526715161378776103340983046580, 148292872313931508344196679476720973752571125303712466045656, 413889563851226543249984374872220761253120628252088546262699, 853542105910386365929770611480736086723126396438880650918917, 59730458840715910492468261806200793684923819793480597554146, 792260492800286127199649276659137441324248689470594987965190, 753608630500639136668081531883097047491651258191552267413126, 33514911499472634865669915075769163328171019557849259474018, 634963859228206842307837566519244534650818456901841184879977, 219354096455968590219445072777282329948785844491217770978344, 1123377226439583158729762969668999276741275445803396272436031, 357765295513680388973981712560200525235334734759663454993805, 385868499980630535766019957877752149506518574529845752144666, 138578212294299392480319417966870656714476525885983752756188, 1110526796192425688386237355263892073046060477008920073455044, 244699783645221387947312903861559688207612147588246639081699, 583209905862562678600202085212425597809036630416117298854978, 1207854793808762194414317661151529169444903662139065050090746, 1127506983223466275821900811940356395242309493951089427884032, 526185119576631048584313761548704536031634598332129570964689, 266882032196696984660521486449809902101615921156569537960109, 1188118705564450461919200724390473040524626320052324478509883, 682831747455078454647149830819696088960233603851250102828667, 669419928942561433130809268138650695825596612075801278942980, 1077750630919867687880983437504767304166615787212813240073843, 486023540111308483450127320955599047045479654684477043315645, 409429366346146233850088863324915025465847596238000661872172, 779883595226131237594759409249289551033410304517183865388408, 1155872225708857920911178110668279174877878422508206228579940, 411063490066038942009369947241345843238439795078686488373864, 1243453053541946030699872676712518536022061850799945414120045, 871711034820169700581685353768658469631429266493677466057997, 601920686459160120670719526703980120744719013393032353678765, 329932100141177850249406090412821976994089707958551194468769, 558327299751202100333335353826111016492585371503632197870640, 113444032302978611299580451314055133491399096282744687816086, 152525914892717139057165748051966776217223953242540511499945, 965404850400527912039904270871065001313018148780552532312669, 313557099445185696402013375071955475516203519824979749629786, 952254159335810337756614972813240144837526566801182319987154]


flag=''
for c in clist:
	if gp.jacobi(c,n)==1:
		flag+='0'
	if  gp.jacobi(c,n)==-1:	
		flag+='1'
		
print('flag二进制:',flag)
#二进制转化成十进制
f=int(flag,2)
print('flag十进制:',f)
print(n2s(f))

运行结果：

image-20221130000543407

顺利得到flag：

SYC{run_to_the_light}

  • Title: SYC三面
  • Author: jrl
  • Created at: 2022-12-16 15:36:21
  • Updated at: 2023-07-26 18:40:35
  • Link: https://jrl777.github.io/2022/12/16/SYC/
  • License: This work is licensed under CC BY-NC-SA 4.0.
 Comments
On this page
SYC三面
  1. 1.对于Task代码注释的补齐
    1. 1.1 Task：
    2. 1.2 注释与补齐：
  2. 2.Paper‘s notes
    1. 2.1 关于数论：
    2. 2.2 中国剩余定理与二次剩余：
    3. 2.3 笔记整理：
  3. 3. Task解题