抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

勒让德和雅可比

crypto日常学习

发布于：2024年12月22日

次浏览

分享两题关于勒让德和雅可比的题目，以前都是拿到直接配合Tonelli_Shanks求二次剩余的，确实没太注意这个函数本身的作用

题1：

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
from sympy import *
from Crypto.Util.number import *
a = 288260533169915
p = 1007621497415251

FLAG = b'moectf{xxxxxxxxxxxxxxxxxxxxx}'


def encrypt_flag(flag):
    ciphertext = []
    plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag])
    for b in plaintext:
        e = randprime(2, p)
        if b == '1':
            n = pow(a, -e, p)
            ciphertext.append(n)
        else:
            n = pow(-a, e ,p)
            ciphertext.append(n)
    return ciphertext


print(encrypt_flag(FLAG))

'''
[869209361008868, 469987155014055, 477607245771711, 956121763882082, 460028889963055, 533967339350806, 476643304115038, 398098864395899, 708866397520182, 894852371427053, 830040978017214, 982890039414452, 407281601145406, 984373673613758, 331248820899125, 413731871413066, 112233590512619, 844508013531773, 660541015358267, 203847276465014, 196764266760616, 724197319842530, 812956074918088, 543222621016303, 696010102017333, 981894930207802, 267226118917619, 790129874087132, 347190586174502, 558560481026105, 950966879997572, 194292449369649, 939650649212499, 849325569453260, 954903252340838, 666432519482028, 633589915590432, 674835636376805, 411981317282694, 255883519424948, 20332021415046, 41211809179475, 615228291023827, 3174369207878, 692370202966600, 171277599642048, 550867407707890, 928211081192953, 619531888759759, 941561507423215, 227188515309784, 44358479590760, 191301655212015, 872434831540071, 139926467694171, 257184569797282, 424025125913335, 604314815606040, 688629170195562, 934061980780966, 117123867152708, 118775453146424, 650238997700650, 464296860203680, 846900558108148, 136810490139411, 734401553273199, 1003815301659353, 177890098513981, 989132152091058, 925193504078956, 16120118469157, 417698353358040, 321572997822303, 490470448511519, 143301632751724, 201665758214964, 55674980300458, 672801140720347, 538389842964759, 688041819793393, 205641306968894, 85514071959036, 765861630472651, 1002881651048918, 468366360167056, 617444592689374, 489960009824958, 277775292746563, 839649570289759, 44545172581275, 688402966446644, 63769456068611, 213999882436593, 216065701874753, 550918086303447, 537406584676363, 360111428305020, 49045746183886, 406387916012829, 616035592607376, 910420067160309, 793994862952614, 559040919034722, 563431245991661, 540696592133, 692916878493026, 196862724250440, 915740996075121, 93262251719033, 138249806426133, 804205456884944, 980827994771964, 610265656156428, 675182808097113, 871977346966751, 432436067933537, 442408025475728, 68859983520112, 981142230621570, 44959838765869, 718285129646124, 479524397547695, 589544640946059, 723473211888089, 45649254718349, 809760578240640, 924079152216550, 819111458104359, 635798987884173, 493145154891103, 930007668559676, 951257062978841, 271213718852471, 322982213108644, 399650597731932, 599981686178645, 679031137073299, 871271038222937, 181211009276874, 492456903306033, 565461124642037, 368127868271848, 818142124952965, 531075679825305, 470971994131221, 266554775796898, 667178714173757, 601760855209461, 973801647168834, 932955611573179, 560279111769633, 517548136647154, 549911181170332, 60313689384526, 949491482563099, 452808097613187, 526891136085621, 274705731912851, 434344133676355, 115452488467955, 777777483737098, 814398658724455, 910884139326892, 721153094839833, 123149817617701, 733044865256370, 453868668750506, 66612079427577, 764872507837542, 782137313744881, 24535133913719, 360725525868320, 843972203447559, 891517126809644, 360885232459056, 368491982324658, 283707800915486, 326364439338006, 577378371719791, 722856146079435, 103533837658784, 254688935670505, 377583660405763, 437013223157800, 104708446011619, 988031331348961, 6886781492092, 31048660015037, 202508578415311, 819068100189702, 945419575503259, 73138283255017, 139586913643073, 579156429956448, 1003950470653630, 43710932909704, 922978652768702, 2942054726977, 343866518172971, 681650663259700, 614368933971283, 778713632307973, 398606253834970, 652338331771108, 641949670227333, 252161824790388, 598999939736302, 316749687994360, 952960614096341, 396671237810412, 805539289473096, 358920713125289, 935634624997029, 663385581032613, 35662861967181, 651607545611746, 758681810095871, 611397958560345, 196198933017746, 886932929348591, 660636395367246, 468455431788915, 924092573734008, 950690129324433, 999587127966195, 888011838963394, 602531651309337, 872691790865711, 968486908482852, 453553188990935, 695483211524155, 202869346556262, 970853032785416, 464221034091328, 500444626777630, 938300733064411, 739460171542679, 106243138680201, 220381406498074, 736061259497615, 287985336691769, 828566732433388, 25653881073282, 621320181554384, 978367718394475, 699801594755984, 69045944311920, 918153290921350, 742496154847514, 363237956586620, 855864928899402, 800408376661392, 591608071268736, 644600617307002, 400767167982482, 909728690834744, 619305066037810, 403154906624258, 61283916530956, 841154857119583, 271928739448620, 943602826453375, 181046110086998, 505489926854412, 265242434598252, 397601251563453, 582010431811786, 867744877195598, 157197910775288, 966686261925769, 18876998620377, 389690805402299, 537227398431908, 347700971404069, 441035382034345, 130724065565645, 436020443846434, 995901787186173, 218421083750934, 171270989504749, 837304614857272, 95058522671678, 684115651758448, 759170700243634, 963623830143399, 134020269447492, 810880730174490, 197514429664776, 933293941632760, 298355176150228, 291165975126682, 652837005225218, 594968433103211, 717988266663274, 681283193706870, 94720698554954, 534912230024800, 57002875791544, 466283757471303, 98170275960806, 39674133238710, 328905545254275, 600446924183400, 170250560797853, 96447538360913, 402756881318255, 653833791145054, 624186905259950, 381562263941849, 65202471674875, 813603811804515, 82412251682881, 430813934901833, 630104191517524, 564446338863457, 521850616317191, 301536973562373, 530267275218593, 998500657074054, 7212267782858, 259640351421902, 387324702112626, 888396292341115, 749024753723971, 85418162375112, 883404575520240, 728635284501806, 407998283472092, 917783827814342, 843382891125076, 933249524460091, 237368870850561, 461947500031560, 606265478139720, 762497205024250, 196108161980785, 464712920731734, 802735147473729, 663472255956649, 80955982171827, 891052715882349, 129688607671519, 903004933201140, 813929727900992, 100503758506631, 602082014286842, 437397404488802, 47519859806478, 395180151536529, 546373743492093, 647339114173723, 411317111927540, 101696276166348, 678151959559988, 51668751683754, 265849155643268, 868421028571661, 787999759724884, 95267994279095, 689256950522950, 550554665183774, 426522315621696, 139457110594782, 807574535966969, 181385017851905, 221826095950324, 222071619532288, 419028990094469, 976525300090124, 328201093236083, 286722736191619, 492796951075221, 651514298199139, 571796506342022, 206711677756906, 47331710606546, 702594972120132, 392046509167760, 478407918714814, 592730815648701, 138641638103370, 174303830676571, 529279947866956, 137415107280702, 216392715868670, 86947465794518, 818726716800394, 340254397869880, 371508780067424, 325307981047717, 567687140806415, 822565446854328, 660813456229288, 19186753583566, 644846006777331, 141327393629965, 235920480869413, 838745724950584, 276825516838237, 662761874040532, 418355702214096, 313711926685110, 88437689500328, 460176433574732, 2450228266396, 882266239157054, 673897905650082, 206208153755434, 548920099001980, 153266184111387, 13255788142270, 922484903048545, 440748803998307, 916906240947778, 400842493149205, 220485381482889, 487235065872011, 956191700672996, 995028709816052, 494918773812268, 786696522967722, 535635917789998, 659174735355314, 463254511578315, 933226451519003, 145072370503877, 625388715158253, 426295995778131, 115935587473835, 600764310873265, 1001986508035110, 209492238677627, 654076248845276, 255757144067046, 688372647240070, 337337203838464, 515859807535188, 875162734787756, 794777961098119, 609676420444937, 212529507506835, 795546633511290, 241207048060749, 776801875116315, 481556344267066, 816808129431759, 493895095538575, 51663065130083, 872561553334056, 142484860361584, 366178848478200, 582100262745320, 442278448664580, 658722265331043, 838584617412841, 618888833439999, 841459921663339, 442091548782434, 871146541604948, 361232391335863, 267110542973009, 98775266993905, 726739643823148, 208174460713647, 436363607002850, 109080678453891, 324963987304404, 747129957189381, 629090382627354, 326901225863526, 501411395019558, 605957277216355, 924462072245263, 681742264224629, 411620165150528, 978576627121525, 942031139574369, 93231172524187, 25708686373165, 706440278468996, 89296822699255, 609549323696105, 348801631103012, 301019857245003, 568429888021619, 696641838804966, 449524020606334, 717635512592258, 621428075417344, 165738165511311, 158410762741058, 161602488447872, 382183389407570, 328907274595208, 766746904253365, 107746916578801, 659628742394117, 39850489385122, 666051397127749, 474312422270748, 261139991035351, 482902564645709, 676254393545935, 110235980231748, 299458232064890, 656749827505033, 963908115927553, 722720798875107, 905063483734809, 990795739600264, 945238054995697, 176905467315680, 259111931319224, 422601938259904, 117159396440728, 409211931685475, 396232968955842, 114107681334804, 654283725172919, 351622702709255, 679987416555993, 641640026840576, 609806003053710, 482822259657548, 356518658585635, 61811805139089, 69776954369190, 207172995482414, 423131926063329, 943649643602454, 293676703457600, 563080562597489, 908147079943053, 310010658630352, 911778151386170, 817768239483378, 693612854841870, 214788531589375, 582512152031643, 757729953753937, 856571657360108, 680607952419663, 916077663157203, 731305462677020, 66803615445082, 419287139690140, 861593185826982, 616548630486552, 565256279891822, 282588409958136, 520541630210605, 767345971760815, 656739637241909, 379580509057753, 932925281918941, 251029261628871, 725236776074076, 670964848242950, 999244627445965, 916872955089430, 213213460785344, 211432261756385, 31972183664064, 951358022841870, 284145155237805, 785243558960859, 106902570235769, 766091290254305, 795338261445944, 309041437408721, 676408097676556, 502688492691042, 305931665252032, 139617780975991, 783387572420705, 318509103806236, 279274843786582, 960812728784, 765420810885287, 675301912122800, 220900827019425, 68258429521733, 500343726947640]
'''


这边每次的e都是素数，然后a本身就是p的二次剩余，所以一直是有

x2=a (mod p)x^2=a\ (mod\ p)

如果两边同时e次方，仍然是有等式成立，可以判断，但是换成-a就不行了，根据这个依据来判断就行了

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import long_to_bytes
a = 288260533169915
p = 1007621497415251


def Legendre(n, p):
    return pow(n, (p - 1) // 2, p)

flag = ''
cip = [869209361008868, 469987155014055, 477607245771711, 956121763882082, 460028889963055, 533967339350806, 476643304115038, 398098864395899, 708866397520182, 894852371427053, 830040978017214, 982890039414452, 407281601145406, 984373673613758, 331248820899125, 413731871413066, 112233590512619, 844508013531773, 660541015358267, 203847276465014, 196764266760616, 724197319842530, 812956074918088, 543222621016303, 696010102017333, 981894930207802, 267226118917619, 790129874087132, 347190586174502, 558560481026105, 950966879997572, 194292449369649, 939650649212499, 849325569453260, 954903252340838, 666432519482028, 633589915590432, 674835636376805, 411981317282694, 255883519424948, 20332021415046, 41211809179475, 615228291023827, 3174369207878, 692370202966600, 171277599642048, 550867407707890, 928211081192953, 619531888759759, 941561507423215, 227188515309784, 44358479590760, 191301655212015, 872434831540071, 139926467694171, 257184569797282, 424025125913335, 604314815606040, 688629170195562, 934061980780966, 117123867152708, 118775453146424, 650238997700650, 464296860203680, 846900558108148, 136810490139411, 734401553273199, 1003815301659353, 177890098513981, 989132152091058, 925193504078956, 16120118469157, 417698353358040, 321572997822303, 490470448511519, 143301632751724, 201665758214964, 55674980300458, 672801140720347, 538389842964759, 688041819793393, 205641306968894, 85514071959036, 765861630472651, 1002881651048918, 468366360167056, 617444592689374, 489960009824958, 277775292746563, 839649570289759, 44545172581275, 688402966446644, 63769456068611, 213999882436593, 216065701874753, 550918086303447, 537406584676363, 360111428305020, 49045746183886, 406387916012829, 616035592607376, 910420067160309, 793994862952614, 559040919034722, 563431245991661, 540696592133, 692916878493026, 196862724250440, 915740996075121, 93262251719033, 138249806426133, 804205456884944, 980827994771964, 610265656156428, 675182808097113, 871977346966751, 432436067933537, 442408025475728, 68859983520112, 981142230621570, 44959838765869, 718285129646124, 479524397547695, 589544640946059, 723473211888089, 45649254718349, 809760578240640, 924079152216550, 819111458104359, 635798987884173, 493145154891103, 930007668559676, 951257062978841, 271213718852471, 322982213108644, 399650597731932, 599981686178645, 679031137073299, 871271038222937, 181211009276874, 492456903306033, 565461124642037, 368127868271848, 818142124952965, 531075679825305, 470971994131221, 266554775796898, 667178714173757, 601760855209461, 973801647168834, 932955611573179, 560279111769633, 517548136647154, 549911181170332, 60313689384526, 949491482563099, 452808097613187, 526891136085621, 274705731912851, 434344133676355, 115452488467955, 777777483737098, 814398658724455, 910884139326892, 721153094839833, 123149817617701, 733044865256370, 453868668750506, 66612079427577, 764872507837542, 782137313744881, 24535133913719, 360725525868320, 843972203447559, 891517126809644, 360885232459056, 368491982324658, 283707800915486, 326364439338006, 577378371719791, 722856146079435, 103533837658784, 254688935670505, 377583660405763, 437013223157800, 104708446011619, 988031331348961, 6886781492092, 31048660015037, 202508578415311, 819068100189702, 945419575503259, 73138283255017, 139586913643073, 579156429956448, 1003950470653630, 43710932909704, 922978652768702, 2942054726977, 343866518172971, 681650663259700, 614368933971283, 778713632307973, 398606253834970, 652338331771108, 641949670227333, 252161824790388, 598999939736302, 316749687994360, 952960614096341, 396671237810412, 805539289473096, 358920713125289, 935634624997029, 663385581032613, 35662861967181, 651607545611746, 758681810095871, 611397958560345, 196198933017746, 886932929348591, 660636395367246, 468455431788915, 924092573734008, 950690129324433, 999587127966195, 888011838963394, 602531651309337, 872691790865711, 968486908482852, 453553188990935, 695483211524155, 202869346556262, 970853032785416, 464221034091328, 500444626777630, 938300733064411, 739460171542679, 106243138680201, 220381406498074, 736061259497615, 287985336691769, 828566732433388, 25653881073282, 621320181554384, 978367718394475, 699801594755984, 69045944311920, 918153290921350, 742496154847514, 363237956586620, 855864928899402, 800408376661392, 591608071268736, 644600617307002, 400767167982482, 909728690834744, 619305066037810, 403154906624258, 61283916530956, 841154857119583, 271928739448620, 943602826453375, 181046110086998, 505489926854412, 265242434598252, 397601251563453, 582010431811786, 867744877195598, 157197910775288, 966686261925769, 18876998620377, 389690805402299, 537227398431908, 347700971404069, 441035382034345, 130724065565645, 436020443846434, 995901787186173, 218421083750934, 171270989504749, 837304614857272, 95058522671678, 684115651758448, 759170700243634, 963623830143399, 134020269447492, 810880730174490, 197514429664776, 933293941632760, 298355176150228, 291165975126682, 652837005225218, 594968433103211, 717988266663274, 681283193706870, 94720698554954, 534912230024800, 57002875791544, 466283757471303, 98170275960806, 39674133238710, 328905545254275, 600446924183400, 170250560797853, 96447538360913, 402756881318255, 653833791145054, 624186905259950, 381562263941849, 65202471674875, 813603811804515, 82412251682881, 430813934901833, 630104191517524, 564446338863457, 521850616317191, 301536973562373, 530267275218593, 998500657074054, 7212267782858, 259640351421902, 387324702112626, 888396292341115, 749024753723971, 85418162375112, 883404575520240, 728635284501806, 407998283472092, 917783827814342, 843382891125076, 933249524460091, 237368870850561, 461947500031560, 606265478139720, 762497205024250, 196108161980785, 464712920731734, 802735147473729, 663472255956649, 80955982171827, 891052715882349, 129688607671519, 903004933201140, 813929727900992, 100503758506631, 602082014286842, 437397404488802, 47519859806478, 395180151536529, 546373743492093, 647339114173723, 411317111927540, 101696276166348, 678151959559988, 51668751683754, 265849155643268, 868421028571661, 787999759724884, 95267994279095, 689256950522950, 550554665183774, 426522315621696, 139457110594782, 807574535966969, 181385017851905, 221826095950324, 222071619532288, 419028990094469, 976525300090124, 328201093236083, 286722736191619, 492796951075221, 651514298199139, 571796506342022, 206711677756906, 47331710606546, 702594972120132, 392046509167760, 478407918714814, 592730815648701, 138641638103370, 174303830676571, 529279947866956, 137415107280702, 216392715868670, 86947465794518, 818726716800394, 340254397869880, 371508780067424, 325307981047717, 567687140806415, 822565446854328, 660813456229288, 19186753583566, 644846006777331, 141327393629965, 235920480869413, 838745724950584, 276825516838237, 662761874040532, 418355702214096, 313711926685110, 88437689500328, 460176433574732, 2450228266396, 882266239157054, 673897905650082, 206208153755434, 548920099001980, 153266184111387, 13255788142270, 922484903048545, 440748803998307, 916906240947778, 400842493149205, 220485381482889, 487235065872011, 956191700672996, 995028709816052, 494918773812268, 786696522967722, 535635917789998, 659174735355314, 463254511578315, 933226451519003, 145072370503877, 625388715158253, 426295995778131, 115935587473835, 600764310873265, 1001986508035110, 209492238677627, 654076248845276, 255757144067046, 688372647240070, 337337203838464, 515859807535188, 875162734787756, 794777961098119, 609676420444937, 212529507506835, 795546633511290, 241207048060749, 776801875116315, 481556344267066, 816808129431759, 493895095538575, 51663065130083, 872561553334056, 142484860361584, 366178848478200, 582100262745320, 442278448664580, 658722265331043, 838584617412841, 618888833439999, 841459921663339, 442091548782434, 871146541604948, 361232391335863, 267110542973009, 98775266993905, 726739643823148, 208174460713647, 436363607002850, 109080678453891, 324963987304404, 747129957189381, 629090382627354, 326901225863526, 501411395019558, 605957277216355, 924462072245263, 681742264224629, 411620165150528, 978576627121525, 942031139574369, 93231172524187, 25708686373165, 706440278468996, 89296822699255, 609549323696105, 348801631103012, 301019857245003, 568429888021619, 696641838804966, 449524020606334, 717635512592258, 621428075417344, 165738165511311, 158410762741058, 161602488447872, 382183389407570, 328907274595208, 766746904253365, 107746916578801, 659628742394117, 39850489385122, 666051397127749, 474312422270748, 261139991035351, 482902564645709, 676254393545935, 110235980231748, 299458232064890, 656749827505033, 963908115927553, 722720798875107, 905063483734809, 990795739600264, 945238054995697, 176905467315680, 259111931319224, 422601938259904, 117159396440728, 409211931685475, 396232968955842, 114107681334804, 654283725172919, 351622702709255, 679987416555993, 641640026840576, 609806003053710, 482822259657548, 356518658585635, 61811805139089, 69776954369190, 207172995482414, 423131926063329, 943649643602454, 293676703457600, 563080562597489, 908147079943053, 310010658630352, 911778151386170, 817768239483378, 693612854841870, 214788531589375, 582512152031643, 757729953753937, 856571657360108, 680607952419663, 916077663157203, 731305462677020, 66803615445082, 419287139690140, 861593185826982, 616548630486552, 565256279891822, 282588409958136, 520541630210605, 767345971760815, 656739637241909, 379580509057753, 932925281918941, 251029261628871, 725236776074076, 670964848242950, 999244627445965, 916872955089430, 213213460785344, 211432261756385, 31972183664064, 951358022841870, 284145155237805, 785243558960859, 106902570235769, 766091290254305, 795338261445944, 309041437408721, 676408097676556, 502688492691042, 305931665252032, 139617780975991, 783387572420705, 318509103806236, 279274843786582, 960812728784, 765420810885287, 675301912122800, 220900827019425, 68258429521733, 500343726947640]
for i in cip:
    if Legendre(i, p) == 1:
        flag += '1'
    else:
        flag += '0'
print(long_to_bytes(int(flag, 2)))

题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
29
30
31
32
from Crypto.Util.number import *
from secret import flag
import gmpy2
import random

p = getPrime(512)
q = getPrime(512)
N = p*q
e = 65537

# this is your hint
f = open('enc.txt','w+')
n = getPrime(512)*getPrime(512)
while gmpy2.jacobi(2,n) == 1:
    n = getPrime(512)*getPrime(512)
while p:
    pad = random.randint(0, 2**2023)**2 
    message = pad << 1 + p % 2
    cipher = pow(message, e, n)
    f.write(str(cipher)+'n')
    p //= 2

print(f"n = {n}")
m = bytes_to_long(flag)
c = pow(m,e,N)
print(f"c = {c}")
print(f"N = {N}")
"""
n = 82923926622559692797413399236810034376108584757782065159980339372753222716219921590160225492580275427915752568365221414556256818363760115994728221502369868369002752050846974475991745713189008605110299692339240298965171454485097086422483463462325085226035968868532041299192645499454997827014006970410602586899
c = 5268098693947601218678318823509471571641279409624943251746647090202567499752709232665697183505417421153691929827349942882009815935669724043141950887766485187370271734400923450597010490530223361843541245067817924748052146859671680883073052134640991595920714483571789648126922566108317490787317661128294600152
N = 109628115860704625986265200696596612897391500367605131119456557370327560909624343904428497200076500891833170758691164654954696453518335303906271404285089946230989420194893031114417670761660150790683339988822977604942830134644107915859363425376973310923755737797468892908831973816405901129172182483392347465597
"""

一个要注意的点，+的优先级是比<<高的，所以其实是message = pad << (1 + p % 2)

因为这边n不是奇素数，所以不能用Legendre函数来判断

这题首先要了解一些关于雅可比的性质

image-20241221234311628

这边的a实际上应该是叫被测数，m是叫做模数，他们并不是分子和分母的关系，是一种特殊的数学表示

这边不止模数可以分解变成连乘，被测数如果也可以分解的话，也可以变成连乘

注：雅可比符号是勒让德符号的推广，但是根据雅可比符号的值不能判断同余式是否有解。

也就是

image-20241221234806991

一般有如下的性质

image-20241221235740440

还有一个性质就是

(nem)=(nm)e\left( \frac{n^e}{m} \right) = \left( \frac{n}{m} \right)^e

不过主要用到的还是红框的性质，下面我们分情况讨论

当p的低位是1的时候，有

image-20241222002403118

当p的低位是0的时候，有

image-20241222002433487

由此构造exp即可

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 *
import sys 
from gmpy2 import jacobi

def Legendre(n, p):
    return pow(n, (p - 1) // 2, p)

e = 65537
n = 82923926622559692797413399236810034376108584757782065159980339372753222716219921590160225492580275427915752568365221414556256818363760115994728221502369868369002752050846974475991745713189008605110299692339240298965171454485097086422483463462325085226035968868532041299192645499454997827014006970410602586899
c = 5268098693947601218678318823509471571641279409624943251746647090202567499752709232665697183505417421153691929827349942882009815935669724043141950887766485187370271734400923450597010490530223361843541245067817924748052146859671680883073052134640991595920714483571789648126922566108317490787317661128294600152
N = 109628115860704625986265200696596612897391500367605131119456557370327560909624343904428497200076500891833170758691164654954696453518335303906271404285089946230989420194893031114417670761660150790683339988822977604942830134644107915859363425376973310923755737797468892908831973816405901129172182483392347465597
with open('enc.txt', 'r') as f:
    res = [i for i in f.read().split('n')]


p = ''
for i in res[:-1:]:
    if jacobi(int(i) % n, n) == 1:
        p = '1' + p
    elif jacobi(int(i) % n, n) == -1:
        p = '0' + p

p = int(p, 2)
assert N % p == 0
q = N // p
d = inverse(e, (p - 1) * (q - 1))
print(long_to_bytes(pow(c, d, N)))   #b'flag{Welcome_to_XMCVE!#$%$#%%^@%#&!$%#!}'

更新于：2024年12月23日

评论

评论区