[SWPUCTF 2022 新生赛]yafu分解题目from gmpy2 import invert from Crypto.Util.number import getPrime, bytes_to_long from flag import getflag e 65537 p getPrime(140) q getPrime(140) n p * q phiN (p - 1) * (q - 1) d invert(e, phiN) m bytes_to_long(getflag().encode()) c pow(m, e, n) print(n str(n)) print(c str(c)) #n1851012829537540993346897265450988006921329733937556249710137670254755668838970157221 #c1165608868963663237838494928147497339359377331987999335624507621030816298293537918937根据题目用yafufactor也彳亍分解 N成功分解出怕pq接下来解RSAfrom Crypto.Util.number import* import gmpy2 p1358730637766188714476624560503309609820513 q1362310363870711901033415700690289289304517 n1851012829537540993346897265450988006921329733937556249710137670254755668838970157221 c1165608868963663237838494928147497339359377331987999335624507621030816298293537918937 e65537 np*q phi(p-1)*(q-1) d gmpy2.invert(e, phi) m pow(c, d, n) print(long_to_bytes(m))得到AFFPGS{snzv1l_ov9_gur_g0_Jr1p0zr}很明显应该还有一步从密文格式花括号 字母数字混合看这是ROT13凯撒密码的特例位移 13 位加密ROT13 是经典的替换加密每个字母替换为字母表中后 13 位的字母A↔N、B↔O…M↔Z小写同理数字无变化。最后解出flag为NSSCTF{fami1y_bi9_the_t0_We1c0me}[LitCTF 2025]basic.py题目from Crypto.Util.number import * from enc import flag m bytes_to_long(flag) n getPrime(1024) e 65537 c pow(m,e,n) print(fn {n}) print(fe {e}) print(fc {c}) n 150624321883406825203208223877379141248303098639178939246561016555984711088281599451642401036059677788491845392145185508483430243280649179231349888108649766320961095732400297052274003269230704890949682836396267905946735114062399402918261536249386889450952744142006299684134049634061774475077472062182860181893 e 65537 c 22100249806368901850308057097325161014161983862106732664802709096245890583327581696071722502983688651296445646479399181285406901089342035005663657920475988887735917901540796773387868189853248394801754486142362158369380296905537947192318600838652772655597241004568815762683630267295160272813021037399506007505 ok这题我最开始没细看直接尝试分解了一下没分解出来然后我仔细观察了一下发现 n getPrime(1024)也就是说n是一个素数.根据素数的定义只能被 1 和自身整除的大于 1 的整数也就是说φ(n)n−1所以我们可以直接求出φ(n)然后就可以求私钥d解出m了.from Crypto.Util.number import * import gmpy2 n 150624321883406825203208223877379141248303098639178939246561016555984711088281599451642401036059677788491845392145185508483430243280649179231349888108649766320961095732400297052274003269230704890949682836396267905946735114062399402918261536249386889450952744142006299684134049634061774475077472062182860181893 #n是素数所以欧拉函数phi(n) n-1 e 65537 c 22100249806368901850308057097325161014161983862106732664802709096245890583327581696071722502983688651296445646479399181285406901089342035005663657920475988887735917901540796773387868189853248394801754486142362158369380296905537947192318600838652772655597241004568815762683630267295160272813021037399506007505 phi n-1 d inverse(e, phi) m pow(c, d, n) print(long_to_bytes(m))解出flagLitCTF{ee2c30dfe684f13a6e6c07b9ec90cc2c}[FSCTF 2023]Do you know gcd题目from Crypto.Util.number import * from secret import flag m1bytes_to_long(flag[:16]) m2bytes_to_long(flag[16:]) pgetPrime(1024) q1getPrime(1024) q2getPrime(1024) n1p*q1 n2p*q2 e65537 c1pow(m1,e,n1) c2pow(m2,e,n2) print(n1,n1) print(n2,n2) print(c1,c1) print(c2,c2) n1 18680935400842120133090782991548100098299141114788036098274292600814484762178879421175852824971602717084073867867453382415307589970440719890918576225495401632854107018246844209327118177917122236073227158593514362850629722223228335334773008682775987859295083444638923726449899310854161394586430943134469559429878238769266114132469166535509030877235272476877484918308883799496627699789051809542538091061550107526246728583019140703765888157806778516567048103700384849598143249322109207879381251223776896702362630437178664824125387477797876186939235800859102380783259361745143574493440078787931593394188675093506492640857 n2 16308523133405725830120564525574438512803584148781960516042054284309437381876822602134185065101371986717984978566359252072738078020261823966208153922611063201149105749778596739692554295573408850719208215646167050188830459343054219856901871953140988948482577813730729085764541988120049026971705499798003225755018687242522370406495429425494022876627543617474873929054728724093702291448754458748923218635900061398716191201846139296921753782690468189409101899415028480878296408735247604084627019116374444335509072590669239349212479592499426230525792270750612371117196200786891891430446212938482959351978202358044864822577 c1 534518909595318304521410713148076850830155521838755402438490325620155197496935820831936109252194297244161393310730073882257949954815312409974998733265641354273665213856408848764503848122264972023143474923678585167025591255034150826271791019266426616987355463111138963331008761826310757292765842789380409826387579098421126952331558360737102888876551724241978020305977032047901621477384392409864427091911872691182528938458750707982564581322551517287491916691010743390992018974168703956622998928457142606354825714033609199676987795174032254878017883605565760275857658822315970522114838062469258676628619381342357632179 c2 10248394002302905069278122013496854496130190499518622376819239887579692634750808499513497018453473232140518824608976734237637842228035017757831938865937098325684711995382081489403971465596662585196007547659143066184546400992333479193424580690897692586491475768279754939199148642035267049092880715299621206567123356521609120801306358100326600900326310677054810032471472266402660807205675696110133573150125117412696328434523507708110949743705536889950671778501402435457354251761692098671783596194430798692942013503015764266392551048702428063161786512924608239609802040937400619384828550050291094616346317726139970219621 观察题目我们可以发现两个模数n1和n2共享同一个素数p我们可以通过欧几里得算法快速算出pp gcdn1n2 16179285226258578424021061494367385836443584807845889279383573430184747626235724511518535827053872636321947687728779928622076152770221353045874914490577545364588996855878195294935676463370870311709408195570605563650563823838386154613300367999203391214807118993667323902709695921455465492295974708948478929823然后求出n1和n2解密from Crypto.Util.number import inverse, long_to_bytes, GCD n1 18680935400842120133090782991548100098299141114788036098274292600814484762178879421175852824971602717084073867867453382415307589970440719890918576225495401632854107018246844209327118177917122236073227158593514362850629722223228335334773008682775987859295083444638923726449899310854161394586430943134469559429878238769266114132469166535509030877235272476877484918308883799496627699789051809542538091061550107526246728583019140703765888157806778516567048103700384849598143249322109207879381251223776896702362630437178664824125387477797876186939235800859102380783259361745143574493440078787931593394188675093506492640857 n2 16308523133405725830120564525574438512803584148781960516042054284309437381876822602134185065101371986717984978566359252072738078020261823966208153922611063201149105749778596739692554295573408850719208215646167050188830459343054219856901871953140988948482577813730729085764541988120049026971705499798003225755018687242522370406495429425494022876627543617474873929054728724093702291448754458748923218635900061398716191201846139296921753782690468189409101899415028480878296408735247604084627019116374444335509072590669239349212479592499426230525792270750612371117196200786891891430446212938482959351978202358044864822577 c1 534518909595318304521410713148076850830155521838755402438490325620155197496935820831936109252194297244161393310730073882257949954815312409974998733265641354273665213856408848764503848122264972023143474923678585167025591255034150826271791019266426616987355463111138963331008761826310757292765842789380409826387579098421126952331558360737102888876551724241978020305977032047901621477384392409864427091911872691182528938458750707982564581322551517287491916691010743390992018974168703956622998928457142606354825714033609199676987795174032254878017883605565760275857658822315970522114838062469258676628619381342357632179 c2 10248394002302905069278122013496854496130190499518622376819239887579692634750808499513497018453473232140518824608976734237637842228035017757831938865937098325684711995382081489403971465596662585196007547659143066184546400992333479193424580690897692586491475768279754939199148642035267049092880715299621206567123356521609120801306358100326600900326310677054810032471472266402660807205675696110133573150125117412696328434523507708110949743705536889950671778501402435457354251761692098671783596194430798692942013503015764266392551048702428063161786512924608239609802040937400619384828550050291094616346317726139970219621 e 65537 # 步骤1求共享素数pgcd(n1, n2) p GCD(n1, n2) print(f共享素数p {p}) # 步骤2分解n1和n2 q1 n1 // p q2 n2 // p print(fq1 {q1}) print(fq2 {q2}) # 步骤3计算欧拉函数 phi_n1 (p - 1) * (q1 - 1) phi_n2 (p - 1) * (q2 - 1) # 步骤4求私钥d1和d2 d1 inverse(e, phi_n1) d2 inverse(e, phi_n2) # 步骤5解密m1和m2 m1 pow(c1, d1, n1) m2 pow(c2, d2, n2) # 步骤6转换为字节并拼接flag flag_part1 long_to_bytes(m1) flag_part2 long_to_bytes(m2) flag flag_part1 flag_part2 # 输出结果 print(f{flag_part1.hex()} - {flag_part1.decode(utf-8)}) print(f{flag_part2.hex()} - {flag_part2.decode(utf-8)}) print(f{flag.decode(utf-8)})flag为FSCTF{0hN0_Y0u_f1nd_th3_gcd!}欧几里得算法欧几里得算法Euclidean Algorithm又称辗转相除法是用于计算两个非负整数最大公约数GCD的经典且高效的算法。算法核心原理该算法基于一个核心原理两个整数的最大公约数等于其中较小的数和两数相除所得余数的最大公约数。用数学公式可以表示为gcd(a, b) gcd(b, a mod b)这里a和b是两个整数假设a ba mod b表示a除以b的余数。这个过程可以不断重复因为每次的余数都在变小最终余数会变为0。当余数为0时此时的除数就是最初两个数的最大公约数。算法执行步骤假设要求正整数a和b的最大公约数步骤如下取模计算a除以b的余数记为r。判断如果r等于 0则b就是a和b的最大公约数算法结束。迭代如果r不等于 0则将b的值赋给a将r的值赋给b然后回到第1步继续运算。