from Crypto.Util.number import getPrime, bytes_to_long from random import randint FLAG = b'CHTB{??????????????????????????????????}' flag = bytes_to_long(FLAG) def keygen(): p, q = getPrime(1024), getPrime(1024) N = p*q g, r1, r2 = [randint(1,N) for _ in range(3)] g1, g2 = pow(g, r1*(p-1), N), pow(g, r2*(q-1), N) return [N, g1, g2], [p, q] def encrypt(m, public): N, g1, g2 = public assert m < N, "Message is too long" s1, s2 = randint(1,N), randint(1,N) c1 = m*pow(g1,s1,N) % N c2 = m*pow(g2,s2,N) % N return [c1, c2] def decrypt(enc, private): c1, c2 = enc p, q = private m1 = c1 * pow(q, -1, p) * q m2 = c2 * pow(p, -1, q) * p return (m1 + m2) % (p*q) public, private = keygen() enc = encrypt(flag, public) assert flag == decrypt(enc, private) print(f'Public key: {public}') print(f'Encrypted Flag: {enc}')
overview
solution
は と書けるので
あるいは から の univariate coppersmith method を求めてもよい
これは が適切にパディングされていれば生じなかった解法。 ref:
作問するときに気をつけること
from math import gcd public = [15046368688522729878837364795846944447584249939940259042809310309990644722874686184397211078874301515249887625469482926118729767921165680434919436001251916009731653621249173925306213496143518405636216886510423114656445458948673083827223571060637952939874530020017901480576002182201895448100262702822444377134178804257755785230586532510071013644046338971791975792507111644403115625869332161597091770842097004583717690548871004494047953982837491656373096470967389016252220593050830165369469758747361848151735684518721718721910577759955840675047364431973099362772693817698643582567162750607561757926413317531802354973847, 9283319553892803764690461243901070663222428323113425322850741756254277368036028273335428365663191030757323877453365465554132886645468588395631445445583253155195968694862787593653053769030730815589172570039269584478526982112345274390480983685543611640614764128042195018064671336591349166188571572536295612195292864841173479903528383123563226015278849646883506520514470333897880659139687610612049230856991239192330160727258048546502899802982277188877310126410571180236389500463464659397850999622904270520629126455639717497594792781963273264274684421455422023088932590387852813426966580288533263121276557350436900246463, 8170671201621857973407215819397012803619280999847588732628253232283307833188933536560440103969432332185848983745037071025860497584949115721267685519443159539783527315198992420655868110884873218133385835580345201078361745220227561551654718787264374257293351098299807821798471006283753277157555438331734456302990269860368479905882644912688806233577606978042582643369428542665819950283055672363935065844777322370865181261974289403517780920801228770368401030437376412993457855872519154731210534206120823952983817295670102327952847504357905927290367724038039202573992755780477507837498958878434898475866081720566629437645] enc = [7276931928429452854246342065839521806420418866856294154132077445353136752229297971239711445722522895365037966326373464771601590080627182837712349184127450287007143044916049997542062388957038193775059765336324946772584345217059576295657932746876343366393024413356918508539249571136028895868283293788299191933766033783323506852233709102246103073938749386863417754855718482717665887208176012160888333043927323096890710493237011980243014972091979988123240671317403963855512078171350546136813316974298786004332694857700545913951953794486310691251777765023941312078456072442404873687449493571576308437181236785086220324920, 323136689475858283788435297190415326629231841782013470380328322062914421821417044602586721782266492137206976604934554032410738337998164019339195282867579270570771188637636630571301963569622900241602213161396475522976801562853960864577088622021373828937295792222819561111043573007672396987476784672948287600574705736056566374617963948347878220280909003723932805632146024848076789866573232781595349191010186788284504514925388452232227920241883518851862145988532377145521056940790582807479213216240632647108768886842632170415653038740093542869598364804101879631033516030858720540787637217275393603575250765731822252109] N, g1, g2 = public c1, c2 = enc # solution 1 p = gcd(N, g1 - 1) assert p != 1 and p != N assert N % p == 0 q = N // p m = CRT([c1, c2], [p, q]) print(bytes.fromhex(hex(m)[2:])) # solution 2 PR.<x> = PolynomialRing(Zmod(N)) f = (c1 - x)*(c2 - x) f = f.monic() for root in f.small_roots(): r = int(root) print(r.to_bytes((r.bit_length() + 7) // 8, "big"))