サマリ
VTuberのkurenaifさんのYouTubeチャンネル登録者数が2000人を超えたことを記念して出題された「kurenaif 2000 subscribers challenge」のWriteupです。
設問
kurenaif_2000_subscribers_challenge
twitter hash tag: #kurenaif2000
decrypt and please submit questionnaire :)
problem.py
from Crypto.Util.number import *
flag = bytes_to_long(b"kurenaifCTF{DUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMY}")
print("# bit_length = ", flag.bit_length())
e = 20000
ns = []
cs = []
for i in range(2*200):
p = getPrime(20)
q = getPrime(20)
n = p * q
ns.append(n)
cs.append(pow(flag, e, n))
print("e=", e)
print("ns=", ns)
print("cs=", cs)
output.txt
# bit_length = 383
e= 20000
ns= [416139590521, 427116314293, 629446878757, 540561700729, 341464769021, 386598158627, 739869891443, 719424263057, 750864958793, 738525027901, 594886607879, 391411790867, 379532548217, 1000489909687, 489710264233, 733592270407, 762436223729, 981666183907, 870493155041, 672471556039, 573863431201, 634270377707, 480202644293, 413441927111, 388403742799, 697686561941, 477146152627, 291705838579, 515434665169, 516663746737, 565539264211, 510536182031, 810228175007, 888883623757, 635004975359, 366174404357, 508619347967, 563924857843, 510231802337, 444634627961, 762748212463, 286974910129, 549977277893, 552888197051, 545326431431, 787270434047, 387195259261, 529735865839, 967379124871, 677879791187, 477853738357, 400447108489, 876781578313, 442343525369, 499455406423, 783815513567, 662458169327, 553516828261, 685733996483, 469135113913, 876795401837, 715872074279, 625102944731, 775671604613, 1033889834191, 396293887559, 753666133511, 514990433807, 525063567407, 517324443059, 546915612521, 454398156013, 830198745643, 607615609819, 639092323171, 692985151843, 1039674830279, 523915260797, 677706059077, 700530120799, 361362314441, 857594812021, 704163578663, 702485564761, 383210628173, 843126913789, 492950143877, 425706272291, 777494997907, 354454958597, 567234257329, 1081228374899, 552164740691, 737931039889, 555017957521, 683696382881, 418116816287, 407135404777, 718677396611, 745399890997, 728286164789, 548062081187, 686430534239, 564016254001, 688299086609, 630060540541, 893111515529, 463186857613, 737916919093, 897028486561, 460596463783, 541655749493, 427535601601, 807354417137, 534097248953, 470345770163, 466283286851, 853809038699, 668601049933, 691427647439, 1015599871343, 462005230153, 624232013399, 766292538251, 406372472221, 456911615243, 497075714537, 516680278241, 529948178779, 436309222087, 690457186021, 714014130433, 543046976933, 711747660161, 692841105157, 637555673101, 676106043797, 560349974053, 663068046101, 353925023671, 651286181209, 535321424641, 599371459823, 496915696099, 441436821659, 584045514907, 600052399361, 488805482507, 577337452793, 705243714433, 521017231183, 731731760927, 996583300127, 748736349103, 347993285593, 731999442469, 564073158823, 553102093997, 677905511513, 618243196633, 484197990959, 562677385489, 960948109061, 397355632321, 425691483617, 579319534967, 833920096417, 517413464509, 432105296509, 844567320137, 510325037077, 515987853929, 663370311449, 351125309849, 630564884699, 626197816997, 463587226259, 607848745633, 822473368217, 904140570623, 384357666323, 531750698851, 913874855219, 857492552843, 734682781501, 661572346753, 420180189311, 487991755621, 475801574153, 290777853589, 573460297979, 627696570307, 652691335217, 751225817281, 469608583207, 620274475367, 800899573483, 310509589001, 534688398031, 813037682749, 454574819341, 348710508823, 695813104549, 672633409051, 386601103081, 618651189209, 459225065099, 465478069501, 612183886273, 978479359751, 668936991559, 512719298909, 889511440969, 542870384057, 700237277867, 968798942099, 509258018123, 732328488011, 371479583947, 493587086081, 885492636449, 747085328207, 730790027417, 530769760667, 494021025439, 880219721651, 624088199153, 685680734111, 805904257567, 766472007559, 831608409143, 723933961477, 520631889667, 808950064837, 911979545293, 1050385315409, 380003579203, 743221631099, 710585108509, 675570591743, 758871261787, 708838350973, 557473274681, 318559858703, 865957190081, 594272778133, 478286591621, 624427846759, 860625309197, 610673601341, 645300326621, 426530629417, 411679725673, 732453707743, 447932283173, 559326497011, 507117602671, 622203478669, 918890891777, 647370038893, 766896620603, 591799538387, 817941151759, 527393256521, 453502243531, 541520786581, 420392388929, 314558272997, 502875977147, 491160518923, 569001014359, 389597477587, 694518730637, 533694182689, 902134612157, 684038159813, 458478127441, 659574779641, 960324905417, 555168703897, 744659885743, 780723448091, 765797579467, 582731974523, 626663804147, 542461719271, 329050229341, 703326148397, 610565838011, 504420516737, 538931680153, 463716187229, 587703367379, 707700137503, 914766412163, 375525904987, 841140267673, 894601281859, 1019278272317, 876478349491, 542823469193, 573791326117, 761313652433, 471505757669, 510682185581, 576313697941, 792734276359, 841234476431, 770918737297, 598258614839, 673950249677, 481180785133, 429030376097, 661505239609, 499221219533, 678278775641, 669893738513, 388005312917, 503732691659, 610737798691, 517250807929, 636472208279, 923839654237, 732898527913, 600853539131, 622838563717, 378619611437, 557402457431, 392093513153, 540546421489, 688966126603, 795668968999, 529138538153, 601849166459, 492393921347, 412429610129, 565896273749, 492116626823, 396016005127, 810390442307, 505104268783, 523820659447, 760691559197, 680655757867, 664052944117, 438117880601, 432049051927, 540791992633, 1018393700881, 505358782703, 307616663777, 811584946649, 706663841057, 668714698891, 1050588090523, 591094482533, 1012806857533, 669088161067, 656670945317, 494627391091, 825177792799, 444517215529, 505319069903, 640384880071, 546331206613, 601895730871, 625426847491, 441948657053, 384220541209, 407947031369, 683880669137, 547565312257, 372530810837, 896528913479, 931675919491, 448268845333, 697729156661, 450050121281, 443335626827, 777815695159, 466929512183, 597608951501, 818240787107, 590361196973, 720770420609, 751229775929, 605231463071, 1000508797949, 541809354451, 739232732753, 542512889629, 699558645209, 836469356231, 399834379181, 509801237291, 677270952053, 748228317527, 586434407731, 450108113423, 587973453173]
cs= [69902148630, 222211746557, 205569643709, 115729867285, 198734094886, 382713736060, 213825513190, 427383686496, 390192712132, 478725693806, 239281085636, 39774628741, 75293500879, 22385603096, 358641807080, 476392503284, 255809163845, 665492411525, 319922581207, 557421312828, 422420765556, 455039439732, 233165122018, 85369982969, 71181503330, 651969712789, 306333538946, 49940605188, 435821196394, 128381942241, 2951394731, 486295015535, 60038886170, 825563310732, 134574523650, 37354800411, 136065411247, 35197630181, 244737346455, 113138663671, 759930694913, 3573374691, 390851161461, 412130949409, 536129731729, 737398917631, 239756338992, 227622762676, 858544625132, 126166118758, 383658864412, 274519151211, 480935434755, 230116893790, 64006706397, 467803341439, 622291695210, 64355817213, 424241211920, 287307676501, 284273827878, 111241077945, 241519360034, 229261839493, 165452390773, 366255651274, 500093866866, 448665148219, 411612313147, 214995028415, 14215300935, 283051823444, 498567224659, 27786013980, 106119664519, 393453941912, 500536811905, 216794968072, 610882961787, 5959300710, 227750048195, 450180020469, 270878288284, 427054761306, 40339473989, 190327698363, 306765822280, 20315211458, 774643953062, 231522537471, 512990217663, 375940013221, 36367486388, 491558040448, 101237062326, 245702345765, 291796692128, 322179308195, 70696339725, 368117157480, 309753566692, 75722935044, 126627376054, 441821108159, 93678271694, 167306392326, 141314241199, 262298867259, 77147464838, 556548299344, 36128335663, 104483805772, 103164205095, 643030397559, 171197435564, 324338180490, 355946449053, 503016179102, 517738991424, 597688779623, 974574218665, 115677939120, 243978775914, 165720748602, 181552745024, 346195537222, 397619551292, 490930224599, 94945016983, 32386291499, 677949157879, 494061938163, 333415863256, 256958297088, 66577685018, 446447848852, 375316242136, 15008747981, 368491200047, 132493180534, 302535426550, 292194515209, 311094242207, 290169238726, 265620857299, 297691688740, 346959320484, 398336117422, 288701151544, 177735392850, 344060446415, 329498790336, 512465308251, 630087468071, 322989684874, 337555320317, 203193272363, 189011573619, 639045232923, 608049339889, 189413240475, 553654464453, 65716069421, 9507219535, 67641304725, 576180999446, 503316780487, 259428818269, 92849168620, 14796402226, 118927058601, 329267111488, 517339247708, 89125204038, 492252854498, 352910784219, 278430445373, 146483337789, 537796524544, 776349829797, 251252074487, 187803062407, 699487407518, 4529671666, 174176759779, 261994270302, 183251596110, 465537066594, 215277940184, 141645237738, 11282265390, 575260644839, 606560607117, 213509864926, 79510206738, 351143099814, 740822916586, 17000305560, 170633086711, 437315252678, 412985103287, 156492582667, 85464843113, 385331599995, 126261274727, 436782885745, 283531697140, 217021364923, 145335099443, 613309295461, 488191349182, 158174438354, 156082610552, 283597949478, 8885199765, 307506065230, 115213221850, 537905914167, 178246704975, 260335189214, 402450039111, 48825578108, 315492800508, 519379883130, 64804887282, 219888883040, 155915789548, 57515472088, 54227894322, 290514328884, 488025042326, 411519325212, 206828858790, 804187196520, 49981221366, 216130860505, 295722263026, 247799462956, 360455655205, 295430987753, 104604506214, 654879656631, 227128964026, 294087729473, 499861539798, 319404847535, 211818753389, 14466510625, 519711048469, 47801518418, 299890064280, 349792811215, 369230306663, 79462088242, 237550811567, 260861362485, 160597010683, 480088939659, 333336133384, 455313093675, 221724361630, 108862110992, 417380750726, 386156949564, 42095749166, 469609207543, 119184511189, 273012875383, 90692647741, 357157685992, 523483568081, 341161145567, 164857778640, 51762991449, 789570444615, 289807890146, 159551791215, 651423263978, 907653680681, 411963495246, 38743675187, 434993860704, 713855384182, 359698247058, 486110395210, 27550484002, 261458421192, 159549135722, 148869292375, 226423909413, 372796309085, 375446797797, 153252229892, 404664892530, 197861612744, 267346605502, 310723307851, 633073058456, 375880992428, 1561804161, 378633690087, 167363938303, 578362320029, 348377843815, 471815616632, 271896858604, 195344059906, 672706069333, 766113530136, 437892144106, 626160130032, 442514533589, 126449506027, 165067423902, 463870899101, 570250437613, 583125967774, 70244914318, 135880149949, 182879147351, 369385389529, 530311354050, 892544976278, 431141268603, 129205234791, 329873507375, 14918301653, 429738972776, 7489312318, 76229811792, 666580960166, 532139429845, 313888296685, 117943787740, 99242595045, 382236208819, 370816939304, 426613613752, 315246412026, 532207880063, 283523236920, 118693220994, 136910323048, 493147606643, 79704607880, 217642729534, 312277747339, 97780769772, 81105707912, 10290185356, 145961083373, 422371538160, 49646252887, 133661201126, 457181972971, 370092318083, 39591637691, 631128644793, 472786198181, 301984955937, 75512628802, 128479990357, 42841804071, 52144380380, 6749255578, 92207251150, 109785014911, 106093369432, 109169573805, 200354890983, 21591294075, 17405816358, 324156962220, 703629876301, 679113504783, 12804958347, 665563664164, 6626244349, 249400225378, 248624150411, 195002538074, 1450745751, 162657180153, 194970260802, 417074688105, 571620032133, 478478169557, 747439259706, 464458686748, 585020993816, 448381575839, 92687317926, 107939652889, 28879410930, 180518608737, 61036995406, 665028714238, 534947113858, 258671499110, 569600317768]
解法
RSA 問です。n（modulus） と c（暗号文）の組が多数与えられます。各 n は小さいので素因数分解は容易ですが e が 偶数（つまり totientとは互いに素ではない）なので面倒です。
そこで試しに計算してみると、totient と e との GCD が 4 になるような n が結構たくさん出てきます。これらにおいては m ** 4 がすぐ計算できるので、m ** 4 の 4 乗根の可能性つまり m の可能性（このケースではおそらく 4 個ずつ出てくることが理論上証明できると思われるが、サボった）を洗い出してストックして、最後総当たりでCRTしてみてフラグになるやつを出しました。
ぶっちゃけ相当無駄な計算をしていますが、与えられた（使える）n の情報が足りなかった場合はこの方法が有効かと思います。
ソルバ
solve.sage
from Crypto.Util.number import *
import itertools
# bit_length = 383
e= 20000
ns= [416139590521, 427116314293, 629446878757, 540561700729, 341464769021, 386598158627, 739869891443, 719424263057, 750864958793, 738525027901, 594886607879, 391411790867, 379532548217, 1000489909687, 489710264233, 733592270407, 762436223729, 981666183907, 870493155041, 672471556039, 573863431201, 634270377707, 480202644293, 413441927111, 388403742799, 697686561941, 477146152627, 291705838579, 515434665169, 516663746737, 565539264211, 510536182031, 810228175007, 888883623757, 635004975359, 366174404357, 508619347967, 563924857843, 510231802337, 444634627961, 762748212463, 286974910129, 549977277893, 552888197051, 545326431431, 787270434047, 387195259261, 529735865839, 967379124871, 677879791187, 477853738357, 400447108489, 876781578313, 442343525369, 499455406423, 783815513567, 662458169327, 553516828261, 685733996483, 469135113913, 876795401837, 715872074279, 625102944731, 775671604613, 1033889834191, 396293887559, 753666133511, 514990433807, 525063567407, 517324443059, 546915612521, 454398156013, 830198745643, 607615609819, 639092323171, 692985151843, 1039674830279, 523915260797, 677706059077, 700530120799, 361362314441, 857594812021, 704163578663, 702485564761, 383210628173, 843126913789, 492950143877, 425706272291, 777494997907, 354454958597, 567234257329, 1081228374899, 552164740691, 737931039889, 555017957521, 683696382881, 418116816287, 407135404777, 718677396611, 745399890997, 728286164789, 548062081187, 686430534239, 564016254001, 688299086609, 630060540541, 893111515529, 463186857613, 737916919093, 897028486561, 460596463783, 541655749493, 427535601601, 807354417137, 534097248953, 470345770163, 466283286851, 853809038699, 668601049933, 691427647439, 1015599871343, 462005230153, 624232013399, 766292538251, 406372472221, 456911615243, 497075714537, 516680278241, 529948178779, 436309222087, 690457186021, 714014130433, 543046976933, 711747660161, 692841105157, 637555673101, 676106043797, 560349974053, 663068046101, 353925023671, 651286181209, 535321424641, 599371459823, 496915696099, 441436821659, 584045514907, 600052399361, 488805482507, 577337452793, 705243714433, 521017231183, 731731760927, 996583300127, 748736349103, 347993285593, 731999442469, 564073158823, 553102093997, 677905511513, 618243196633, 484197990959, 562677385489, 960948109061, 397355632321, 425691483617, 579319534967, 833920096417, 517413464509, 432105296509, 844567320137, 510325037077, 515987853929, 663370311449, 351125309849, 630564884699, 626197816997, 463587226259, 607848745633, 822473368217, 904140570623, 384357666323, 531750698851, 913874855219, 857492552843, 734682781501, 661572346753, 420180189311, 487991755621, 475801574153, 290777853589, 573460297979, 627696570307, 652691335217, 751225817281, 469608583207, 620274475367, 800899573483, 310509589001, 534688398031, 813037682749, 454574819341, 348710508823, 695813104549, 672633409051, 386601103081, 618651189209, 459225065099, 465478069501, 612183886273, 978479359751, 668936991559, 512719298909, 889511440969, 542870384057, 700237277867, 968798942099, 509258018123, 732328488011, 371479583947, 493587086081, 885492636449, 747085328207, 730790027417, 530769760667, 494021025439, 880219721651, 624088199153, 685680734111, 805904257567, 766472007559, 831608409143, 723933961477, 520631889667, 808950064837, 911979545293, 1050385315409, 380003579203, 743221631099, 710585108509, 675570591743, 758871261787, 708838350973, 557473274681, 318559858703, 865957190081, 594272778133, 478286591621, 624427846759, 860625309197, 610673601341, 645300326621, 426530629417, 411679725673, 732453707743, 447932283173, 559326497011, 507117602671, 622203478669, 918890891777, 647370038893, 766896620603, 591799538387, 817941151759, 527393256521, 453502243531, 541520786581, 420392388929, 314558272997, 502875977147, 491160518923, 569001014359, 389597477587, 694518730637, 533694182689, 902134612157, 684038159813, 458478127441, 659574779641, 960324905417, 555168703897, 744659885743, 780723448091, 765797579467, 582731974523, 626663804147, 542461719271, 329050229341, 703326148397, 610565838011, 504420516737, 538931680153, 463716187229, 587703367379, 707700137503, 914766412163, 375525904987, 841140267673, 894601281859, 1019278272317, 876478349491, 542823469193, 573791326117, 761313652433, 471505757669, 510682185581, 576313697941, 792734276359, 841234476431, 770918737297, 598258614839, 673950249677, 481180785133, 429030376097, 661505239609, 499221219533, 678278775641, 669893738513, 388005312917, 503732691659, 610737798691, 517250807929, 636472208279, 923839654237, 732898527913, 600853539131, 622838563717, 378619611437, 557402457431, 392093513153, 540546421489, 688966126603, 795668968999, 529138538153, 601849166459, 492393921347, 412429610129, 565896273749, 492116626823, 396016005127, 810390442307, 505104268783, 523820659447, 760691559197, 680655757867, 664052944117, 438117880601, 432049051927, 540791992633, 1018393700881, 505358782703, 307616663777, 811584946649, 706663841057, 668714698891, 1050588090523, 591094482533, 1012806857533, 669088161067, 656670945317, 494627391091, 825177792799, 444517215529, 505319069903, 640384880071, 546331206613, 601895730871, 625426847491, 441948657053, 384220541209, 407947031369, 683880669137, 547565312257, 372530810837, 896528913479, 931675919491, 448268845333, 697729156661, 450050121281, 443335626827, 777815695159, 466929512183, 597608951501, 818240787107, 590361196973, 720770420609, 751229775929, 605231463071, 1000508797949, 541809354451, 739232732753, 542512889629, 699558645209, 836469356231, 399834379181, 509801237291, 677270952053, 748228317527, 586434407731, 450108113423, 587973453173]
cs= [69902148630, 222211746557, 205569643709, 115729867285, 198734094886, 382713736060, 213825513190, 427383686496, 390192712132, 478725693806, 239281085636, 39774628741, 75293500879, 22385603096, 358641807080, 476392503284, 255809163845, 665492411525, 319922581207, 557421312828, 422420765556, 455039439732, 233165122018, 85369982969, 71181503330, 651969712789, 306333538946, 49940605188, 435821196394, 128381942241, 2951394731, 486295015535, 60038886170, 825563310732, 134574523650, 37354800411, 136065411247, 35197630181, 244737346455, 113138663671, 759930694913, 3573374691, 390851161461, 412130949409, 536129731729, 737398917631, 239756338992, 227622762676, 858544625132, 126166118758, 383658864412, 274519151211, 480935434755, 230116893790, 64006706397, 467803341439, 622291695210, 64355817213, 424241211920, 287307676501, 284273827878, 111241077945, 241519360034, 229261839493, 165452390773, 366255651274, 500093866866, 448665148219, 411612313147, 214995028415, 14215300935, 283051823444, 498567224659, 27786013980, 106119664519, 393453941912, 500536811905, 216794968072, 610882961787, 5959300710, 227750048195, 450180020469, 270878288284, 427054761306, 40339473989, 190327698363, 306765822280, 20315211458, 774643953062, 231522537471, 512990217663, 375940013221, 36367486388, 491558040448, 101237062326, 245702345765, 291796692128, 322179308195, 70696339725, 368117157480, 309753566692, 75722935044, 126627376054, 441821108159, 93678271694, 167306392326, 141314241199, 262298867259, 77147464838, 556548299344, 36128335663, 104483805772, 103164205095, 643030397559, 171197435564, 324338180490, 355946449053, 503016179102, 517738991424, 597688779623, 974574218665, 115677939120, 243978775914, 165720748602, 181552745024, 346195537222, 397619551292, 490930224599, 94945016983, 32386291499, 677949157879, 494061938163, 333415863256, 256958297088, 66577685018, 446447848852, 375316242136, 15008747981, 368491200047, 132493180534, 302535426550, 292194515209, 311094242207, 290169238726, 265620857299, 297691688740, 346959320484, 398336117422, 288701151544, 177735392850, 344060446415, 329498790336, 512465308251, 630087468071, 322989684874, 337555320317, 203193272363, 189011573619, 639045232923, 608049339889, 189413240475, 553654464453, 65716069421, 9507219535, 67641304725, 576180999446, 503316780487, 259428818269, 92849168620, 14796402226, 118927058601, 329267111488, 517339247708, 89125204038, 492252854498, 352910784219, 278430445373, 146483337789, 537796524544, 776349829797, 251252074487, 187803062407, 699487407518, 4529671666, 174176759779, 261994270302, 183251596110, 465537066594, 215277940184, 141645237738, 11282265390, 575260644839, 606560607117, 213509864926, 79510206738, 351143099814, 740822916586, 17000305560, 170633086711, 437315252678, 412985103287, 156492582667, 85464843113, 385331599995, 126261274727, 436782885745, 283531697140, 217021364923, 145335099443, 613309295461, 488191349182, 158174438354, 156082610552, 283597949478, 8885199765, 307506065230, 115213221850, 537905914167, 178246704975, 260335189214, 402450039111, 48825578108, 315492800508, 519379883130, 64804887282, 219888883040, 155915789548, 57515472088, 54227894322, 290514328884, 488025042326, 411519325212, 206828858790, 804187196520, 49981221366, 216130860505, 295722263026, 247799462956, 360455655205, 295430987753, 104604506214, 654879656631, 227128964026, 294087729473, 499861539798, 319404847535, 211818753389, 14466510625, 519711048469, 47801518418, 299890064280, 349792811215, 369230306663, 79462088242, 237550811567, 260861362485, 160597010683, 480088939659, 333336133384, 455313093675, 221724361630, 108862110992, 417380750726, 386156949564, 42095749166, 469609207543, 119184511189, 273012875383, 90692647741, 357157685992, 523483568081, 341161145567, 164857778640, 51762991449, 789570444615, 289807890146, 159551791215, 651423263978, 907653680681, 411963495246, 38743675187, 434993860704, 713855384182, 359698247058, 486110395210, 27550484002, 261458421192, 159549135722, 148869292375, 226423909413, 372796309085, 375446797797, 153252229892, 404664892530, 197861612744, 267346605502, 310723307851, 633073058456, 375880992428, 1561804161, 378633690087, 167363938303, 578362320029, 348377843815, 471815616632, 271896858604, 195344059906, 672706069333, 766113530136, 437892144106, 626160130032, 442514533589, 126449506027, 165067423902, 463870899101, 570250437613, 583125967774, 70244914318, 135880149949, 182879147351, 369385389529, 530311354050, 892544976278, 431141268603, 129205234791, 329873507375, 14918301653, 429738972776, 7489312318, 76229811792, 666580960166, 532139429845, 313888296685, 117943787740, 99242595045, 382236208819, 370816939304, 426613613752, 315246412026, 532207880063, 283523236920, 118693220994, 136910323048, 493147606643, 79704607880, 217642729534, 312277747339, 97780769772, 81105707912, 10290185356, 145961083373, 422371538160, 49646252887, 133661201126, 457181972971, 370092318083, 39591637691, 631128644793, 472786198181, 301984955937, 75512628802, 128479990357, 42841804071, 52144380380, 6749255578, 92207251150, 109785014911, 106093369432, 109169573805, 200354890983, 21591294075, 17405816358, 324156962220, 703629876301, 679113504783, 12804958347, 665563664164, 6626244349, 249400225378, 248624150411, 195002538074, 1450745751, 162657180153, 194970260802, 417074688105, 571620032133, 478478169557, 747439259706, 464458686748, 585020993816, 448381575839, 92687317926, 107939652889, 28879410930, 180518608737, 61036995406, 665028714238, 534947113858, 258671499110, 569600317768]
_pts = []
_ns = []
for i, n in enumerate(ns):
fs = factor(n)
p = fs[0][0]
q = fs[1][0]
phi = (p-1)*(q-1)
g = GCD(e,phi)
c = cs[i]
if g == 4 :
d = inverse(e//g, phi//g)
pt4 = pow(c,d,n)
R1.<x> = PolynomialRing(GF(p))
f1 = R1(x^4 - pt4)
sol_p = []
for i in range(len(f1.factor())):
ft = f1.factor()[i][0]
if ft.degree() == 1:
sol_p.append(int(-ft.coefficients()[0]))
R2.<y> = PolynomialRing(GF(q))
f2 = R2(y^4 - pt4)
sol_q = []
for i in range(len(f1.factor())):
ft = f2.factor()[i][0]
if ft.degree() == 1:
sol_q.append(int(-ft.coefficients()[0]))
lpts = []
for i in range(len(sol_p)):
for j in range(len(sol_q)):
lpt = crt([sol_p[i], sol_q[j]], [p,q])
if not lpt in lpts:
lpts.append(lpt)
_pts.append(lpts)
_ns.append(ZZ(n))
i = 0
n = ns[0]
while(True):
i += 1
n = n * _ns[i] // (GCD(n, _ns[i]))
if n > 2**384:
break
L = i + 1
ns = []
for i in range(L):
ns.append(_ns[i])
for x in itertools.product(range(4),repeat=L):
pts = []
for i in range(L):
pts.append(_pts[i][x[i]])
pt = crt(pts, ns)
pt = long_to_bytes(pt)
if b"kurenaifCTF{" in pt:
print(pt.decode())
break