WP_2024HSCCTF_CRYPTO_SING_IN

题目

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) % n
print('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

题目

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
    # Chinese Remainder Theorem
    m = (xp*inverse(q, p)*q + xq*inverse(p, q)*p) % N
    return m

#c = encrypt(bytes_to_long(flag))

N = 18680643069610062851842282268594530254220611012409807422663284548187050713427682950720783343430650669361838067625768840896513125210105582070603021732086193955893838077699465426052925750736212977005683541174195320832791835197114668838654054444342903298662698415765898335350206380896849522280206304272801325820946987172164086644949521111058774180676742851681476123338557138770304164634321305204827406522957769478330124484710532963132900017800651579612646041955628867746525508376194147796920773364680264059390497210260540079810501777507814448518995581208169818764701641258963569599247156932381367802991222265241699715283
g1 = 9143176283300810019842153344177123108612540016879643936458724056602746667157014763960725115919119704406826965726023263657276550779443988565368344040505696950820899770544814163379169539926317676679421275092688200844094929042154854719312788471536324082041360841253720783220459009201882865091829118575721525038404689868986360373373122049951274015083845966946475469982961355934516388706446794517870569063777231434618411404965077775991870069073539415961610645268985004687402050059891500490949250730689691141954694508001895390336750734542724392709744200091587065816283592253967715080611459937165344139809223328071517060208
g2 = 14068322834597276347776814624877614869834816383564391664570268934537693322688875343215293618493363798985047779057952636529313879548457643220996398640913517182122425631198219387988691569709691279442005545716133131472147592456812502863851227108284027033557263611949365667779259585770738623603814004666845554284808166195201470503432803440754207350347128045893594280079379926676477680556845095378093693409219131090910168117334308781843178748431526974047817218228075136005979538773141427004682344298827618677773735288946271346252828348742296301538573408254015281232250841148556304927266143397565889649305095857756884049430
c1, c2 = (3976514029543484086411168675941075541422870678409709261442618832911574665848843566949154289825219682094719766762966082440586568781997199077781276145091509192208487682443007457513002005089654365915817414921574344557570444253187757317116858499013550050579856269915915792827620535138057468531410166908365364129001407147467636145589396570815405571923148902993581000542566387654639930651683044853608873583911638108204074537952317056718986683846742909366072461130053275195290631718363272923316002049685111871888148244026652658482359335651889139243735138819453744763293112267738369048641158946411500606588429007794613880534, 18524535479582837341745231233387403662294605513261199630593257391163433751052467785080620993007681605662927226603747560698627838567782891522546977611597418150309028806158429831471152782211111046118637630899456903846057977815397285171313888516791822545633820066408276065732715348834255021260666966934592884548856831383262013360819013814149529393178712576141627031723067564594282618223686778534522328204603249125537258294561872667849498796757523663858312311082034700705599706428944071848443463999351872482644584735305157234751806369172212650596041534643187402820399145288902719434158798638116870325144146218568810928344)

这题给了解密函数，简单了许多。根据解密函数，只要知道c1、c2、p、q就能求出m。因为c1、c2是已知的，所以求p和q即可

根据加密的过程，与p，q有关系的语句只有这两个：

g1 = pow(g, r1 * (p-1), N)
g2 = pow(g, r2 * (q-1), N)

接下来的推导我也没学过，就当懂了吧。。。

只看第一个式子： #### (g^r1)(p-1) mod pq = g1 两边同模p： #### (g^r1)(p-1) mod p = g1 mod p 根据费马小定理（这个可以有）： #### a^（p-1）≡1（mod p） 带入公式显然有： #### g1 mod 1 = p 简单转换一下就有： #### gcd(g1-1,pq)=p

结合上述推导过程，我们可以得出一下结论：

gcd(g1-1,p*q)=p
gcd(g2-1,p*q)=q

因此可以使用g1,g2和n来求得p和q，与加密过程中的随机质数无关

解

利用上述结论以及母题提供的解密函数，构建如下解密脚本：

from Crypto.Util.number import *
from gmpy2 import *

def decrypt(c1, c2):
    xp = c1 % p
    xq = c2 % q
    # Chinese Remainder Theorem
    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!