题目
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 from Crypto.Util.number import *from random import *from gmpy2 import * flag = 'HSCCTF{66666666666666666666666666666666666}' m = bytes_to_long(flag.encode()) p, q = getPrime(1024 ), getPrime(1024 ) n = p * q g, r1, r2, k1, k2 = [randint(1 , n) for _ in range (5 )] g1 = powmod(g, r1 * (p - 1 ), n) g2 = powmod(g, r2 * (q - 1 ), n) c1 = m * powmod(g1, k1, n) % n c2 = m * powmod(g2, k2, n) % nprint ('enc=' , [c1, c2])print ('n, g1, g1=' , [n, g1, g2])''' enc= [15258813801182767957948809411445530114743580005667897427534365589851124401953952700888032330082278736578651674105204553630115929829327520950316902504433079359916257355896937562916556083469602985115254272625361902512966905366505705193603115063442567259505806926885597909346860116511116593562896739734663097631870026814495999405532329662713707140991693625596972404484374296588505369466138353714461787853643947646268147993568111775200297788443085689323703846485412670213780175163562460311256388185948613714551169278328397181176821021494625532973065606678522088011055084956579073665474553688838705105692370860815836968744, 6812252973072040071827764212287068485224506664962923279994614164374840095630460681859406585838865259535150445414577263383839286602668872146630568583093203237350230531896113453730563536559780725054737930704052263836882704963528437893607940373145674848731274193348770450738356162141551719346994698149112827383011042635625991946491545698464513315705253441372356270248537025391519052228332747340090073726648071921053097612521949040588826684887577900030607964457543549015338544684381220552952995724701579427363382069065679545196826947900332605250858694574423497096207350532949517663416877954484913664168104807510052994343] n, g1, g1= [20807018344486474639307429177279931766730766338068107239915507489300098048895435781756514265069820029246382818970733268271541419058569567895618666922180270584064313671561310704041755422624879418184008100473568396190523033929320245716340019444764233261191278982354931492880877566550189410854395486995604287009460090861952156686772486228583819235930673806632618770875593810617784176409247510465542253043645164164225524491704753384493817563203956665022724674535516870726747405974392352500432805602085261375142216501656342533659731098891481615791354504343987459436489040377662127479793769523359343534307819013289699807101, 13669954919111873554762685722926885077118528999414402163291237939605095249827361266585404348819936899557500751307328088850133462100189908649705354225171362748567332828733792410877365393472368767642223613483944864421225366984013053159643284842823692865975521013400160643858123645513020647367033022539177063702511618272018019345686324322865461583030805528508961559861228807898458344763909703624723082316946660539208262816734999777236686904487167545596412866146192769859422435979617441355968077981338491466670291310491623996943880557071723073298267310617017933994938481600905833829730599911183096116409487608858717083764, 16004755272896973088305242134835363565950101667041191767091338528075710730690484241256646402124331734165332717221873300040844257120250717798419429003342474882969292183331631773486056363790119500409511338474885148624744719334829519138941747721940978742668429331169327121848561577357339194970483392418062307133642660625962426570987080348107999849220769541832138719358407833846252908305766546561532003650472770370573552424932908544299331489147220956574184822433945571318688467182365231955276573176433559755313822566687880866791301904461559170416753669109833335824210853322226762705537051009387847122221014380228383127427] '''
目测需要解决的问题是求出p和q,但是n无法分解,陷入沉思。。。后来不小心找到了这道题的原型
[V&N2020 公开赛] Fast
题目 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 from Crypto.Util.number import *from gmpy2 import * p = getPrime(1024 ) q = getPrime(1024 ) N = p * q g, r1, r2 = [getRandomRange(1 , N) for _ in range (3 )] g1 = pow (g, r1 * (p-1 ), N) g2 = pow (g, r2 * (q-1 ), N)def encrypt (m ): s1, s2 = [getRandomRange(1 , N) for _ in range (2 )] c1 = (m * pow (g1, s1, N)) % N c2 = (m * pow (g2, s2, N)) % N return (c1, c2)def decrypt (c1, c2 ): xp = c1 % p xq = c2 % q m = (xp*inverse(q, p)*q + xq*inverse(p, q)*p) % N return m N = 18680643069610062851842282268594530254220611012409807422663284548187050713427682950720783343430650669361838067625768840896513125210105582070603021732086193955893838077699465426052925750736212977005683541174195320832791835197114668838654054444342903298662698415765898335350206380896849522280206304272801325820946987172164086644949521111058774180676742851681476123338557138770304164634321305204827406522957769478330124484710532963132900017800651579612646041955628867746525508376194147796920773364680264059390497210260540079810501777507814448518995581208169818764701641258963569599247156932381367802991222265241699715283 g1 = 9143176283300810019842153344177123108612540016879643936458724056602746667157014763960725115919119704406826965726023263657276550779443988565368344040505696950820899770544814163379169539926317676679421275092688200844094929042154854719312788471536324082041360841253720783220459009201882865091829118575721525038404689868986360373373122049951274015083845966946475469982961355934516388706446794517870569063777231434618411404965077775991870069073539415961610645268985004687402050059891500490949250730689691141954694508001895390336750734542724392709744200091587065816283592253967715080611459937165344139809223328071517060208 g2 = 14068322834597276347776814624877614869834816383564391664570268934537693322688875343215293618493363798985047779057952636529313879548457643220996398640913517182122425631198219387988691569709691279442005545716133131472147592456812502863851227108284027033557263611949365667779259585770738623603814004666845554284808166195201470503432803440754207350347128045893594280079379926676477680556845095378093693409219131090910168117334308781843178748431526974047817218228075136005979538773141427004682344298827618677773735288946271346252828348742296301538573408254015281232250841148556304927266143397565889649305095857756884049430 c1, c2 = (3976514029543484086411168675941075541422870678409709261442618832911574665848843566949154289825219682094719766762966082440586568781997199077781276145091509192208487682443007457513002005089654365915817414921574344557570444253187757317116858499013550050579856269915915792827620535138057468531410166908365364129001407147467636145589396570815405571923148902993581000542566387654639930651683044853608873583911638108204074537952317056718986683846742909366072461130053275195290631718363272923316002049685111871888148244026652658482359335651889139243735138819453744763293112267738369048641158946411500606588429007794613880534 , 18524535479582837341745231233387403662294605513261199630593257391163433751052467785080620993007681605662927226603747560698627838567782891522546977611597418150309028806158429831471152782211111046118637630899456903846057977815397285171313888516791822545633820066408276065732715348834255021260666966934592884548856831383262013360819013814149529393178712576141627031723067564594282618223686778534522328204603249125537258294561872667849498796757523663858312311082034700705599706428944071848443463999351872482644584735305157234751806369172212650596041534643187402820399145288902719434158798638116870325144146218568810928344 )
这题给了解密函数,简单了许多。根据解密函数,只要知道c1、c2、p、q就能求出m。因为c1、c2是已知的,所以求p和q即可
根据加密的过程,与p,q有关系的语句只有这两个: 1 2 g1 = pow (g, r1 * (p-1 ), N) g2 = pow (g, r2 * (q-1 ), N)
接下来的推导我也没学过,就当懂了吧。。。
只看第一个式子: #### (gr1) (p-1) mod pq = g1
两边同模p: #### (gr1) (p-1) mod p = g1 mod p
根据费马小定理(这个可以有): #### a^(p-1)≡1(mod p)
带入公式显然有: #### g1 mod 1 = p 简单转换一下就有: ####
gcd(g1-1,p q)=p
结合上述推导过程,我们可以得出一下结论: 1 2 gcd(g1-1 ,p*q)=p gcd(g2-1 ,p*q)=q
因此可以使用g1,g2和n来求得p和q,与加密过程中的随机质数无关
解
利用上述结论以及母题提供的解密函数,构建如下解密脚本:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 from Crypto.Util.number import *from gmpy2 import *def decrypt (c1, c2 ): xp = c1 % p xq = c2 % q m = (xp*inverse(q, p)*q + xq*inverse(p, q)*p) % N return m N = 20807018344486474639307429177279931766730766338068107239915507489300098048895435781756514265069820029246382818970733268271541419058569567895618666922180270584064313671561310704041755422624879418184008100473568396190523033929320245716340019444764233261191278982354931492880877566550189410854395486995604287009460090861952156686772486228583819235930673806632618770875593810617784176409247510465542253043645164164225524491704753384493817563203956665022724674535516870726747405974392352500432805602085261375142216501656342533659731098891481615791354504343987459436489040377662127479793769523359343534307819013289699807101 g1 = 13669954919111873554762685722926885077118528999414402163291237939605095249827361266585404348819936899557500751307328088850133462100189908649705354225171362748567332828733792410877365393472368767642223613483944864421225366984013053159643284842823692865975521013400160643858123645513020647367033022539177063702511618272018019345686324322865461583030805528508961559861228807898458344763909703624723082316946660539208262816734999777236686904487167545596412866146192769859422435979617441355968077981338491466670291310491623996943880557071723073298267310617017933994938481600905833829730599911183096116409487608858717083764 g2 = 16004755272896973088305242134835363565950101667041191767091338528075710730690484241256646402124331734165332717221873300040844257120250717798419429003342474882969292183331631773486056363790119500409511338474885148624744719334829519138941747721940978742668429331169327121848561577357339194970483392418062307133642660625962426570987080348107999849220769541832138719358407833846252908305766546561532003650472770370573552424932908544299331489147220956574184822433945571318688467182365231955276573176433559755313822566687880866791301904461559170416753669109833335824210853322226762705537051009387847122221014380228383127427 c1, c2 = [15258813801182767957948809411445530114743580005667897427534365589851124401953952700888032330082278736578651674105204553630115929829327520950316902504433079359916257355896937562916556083469602985115254272625361902512966905366505705193603115063442567259505806926885597909346860116511116593562896739734663097631870026814495999405532329662713707140991693625596972404484374296588505369466138353714461787853643947646268147993568111775200297788443085689323703846485412670213780175163562460311256388185948613714551169278328397181176821021494625532973065606678522088011055084956579073665474553688838705105692370860815836968744 , 6812252973072040071827764212287068485224506664962923279994614164374840095630460681859406585838865259535150445414577263383839286602668872146630568583093203237350230531896113453730563536559780725054737930704052263836882704963528437893607940373145674848731274193348770450738356162141551719346994698149112827383011042635625991946491545698464513315705253441372356270248537025391519052228332747340090073726648071921053097612521949040588826684887577900030607964457543549015338544684381220552952995724701579427363382069065679545196826947900332605250858694574423497096207350532949517663416877954484913664168104807510052994343 ] p=gcd(N,g1-1 ) q=gcd(N,g2-1 ) m=decrypt(c1,c2)print (long_to_bytes(m))
over!