from Crypto.Util.number import * import gmpy2 from secret import flag
p = getPrime(1024) q = gmpy2.next_prime(p ^ ((1<<512) - 1)) n = p * q
m = bytes_to_long(flag) c = pow(m, 0x10001, n)
print(f'n = {n}') print(f'c = {c}')
# n = 8453885765996913712618062109378707336659130808787301279941263026230651123070106797459062171000365889994637175402858207703151564500044390548869930188515842218557849229740014562965962263746070780549831396891941705994713622110082033242683660650189932659146881550116146449462428053806160356286227504339325337551581898256519567742962705944357524118970267940699968649549638664106325348777220329180207763585954844657368022890561945863245866119393292338388874234105489358762483907848160656454959089695615978146121577179680980714139225315343600794084432162921599675629785310474796715614965665548579610931418351539799337817619 # c = 4726796252980174161046218845942217649424568401323709384597987506914998319313028475356589060134652759506342796030407465347005448331069693045017091974740952306073381267159127993316990722810446654483498674864178248933608184916573435206509642940143728451269969858398426505931978537235555412868665335820446174504598837828390480570204676276734825131481678802430374111871526775180382682425326162372961045184794546853714707142847989253670252568609776762123439804531096509110613753591697237646272201574711041532981320571426156783791774414173297059578746114766276851312499691484037841701642575636452384758406187350074232695865
from Crypto.Util.number import * from gmpy2 import *
deffermat_attack(n): a = isqrt(n) b2 = a*a - n b = isqrt(n) count = 0 while b*b != b2: a = a + 1 b2 = a*a - n b = isqrt(b2) count += 1 p = a+b q = a-b assert n == p * q return p, q
n = 8453885765996913712618062109378707336659130808787301279941263026230651123070106797459062171000365889994637175402858207703151564500044390548869930188515842218557849229740014562965962263746070780549831396891941705994713622110082033242683660650189932659146881550116146449462428053806160356286227504339325337551581898256519567742962705944357524118970267940699968649549638664106325348777220329180207763585954844657368022890561945863245866119393292338388874234105489358762483907848160656454959089695615978146121577179680980714139225315343600794084432162921599675629785310474796715614965665548579610931418351539799337817619 c = 4726796252980174161046218845942217649424568401323709384597987506914998319313028475356589060134652759506342796030407465347005448331069693045017091974740952306073381267159127993316990722810446654483498674864178248933608184916573435206509642940143728451269969858398426505931978537235555412868665335820446174504598837828390480570204676276734825131481678802430374111871526775180382682425326162372961045184794546853714707142847989253670252568609776762123439804531096509110613753591697237646272201574711041532981320571426156783791774414173297059578746114766276851312499691484037841701642575636452384758406187350074232695865 e = 65537
N = 624#: 624 values (of 32bit) is just enough to reconstruct the internal state M = 397#: MATRIX_A = 0x9908b0df#: UPPER_MASK = 0x80000000#: LOWER_MASK = 0x7fffffff#:
deftempering(y): y ^= (y >> 11) y ^= (y << 7) & 0x9d2c5680 y ^= (y << 15) & 0xefc60000 y ^= (y >> 18) return y
defuntempering(y): y ^= (y >> 18) y ^= (y << 15) & 0xefc60000 y ^= ((y << 7) & 0x9d2c5680) ^ ((y << 14) & 0x94284000) ^ ((y << 21) & 0x14200000) ^ ((y << 28) & 0x10000000) y ^= (y >> 11) ^ (y >> 22) return y
defgenrand_int32(mt, mti): generate(mt, mti) y = mt[mti] mti = (mti + 1) % N return tempering(y), mti
classMT19937Predictor(random.Random): ''' Usage: .. doctest:: >>> import random >>> from mt19937predictor import MT19937Predictor >>> predictor = MT19937Predictor() >>> for _ in range(624): ... x = random.getrandbits(32) ... predictor.setrandbits(x, 32) >>> random.getrandbits(32) == predictor.getrandbits(32) True >>> random.random() == predictor.random() True >>> a = list(range(100)) >>> b = list(range(100)) >>> random.shuffle(a) >>> predictor.shuffle(b) >>> a == b True '''
def__init__(self): self._mt = [0] * N self._mti = 0
defsetrand_int32(self, y): '''Feceive the target PRNG's outputs and reconstruct the inner state. when 624 consecutive DOWRDs is given, the inner state is uniquely determined. ''' assert0 <= y < 2 ** 32 self._mt[self._mti] = untempering(y) self._mti = (self._mti + 1) % N
defgenrand_int32(self): y, self._mti = genrand_int32(self._mt, self._mti) return y
defsetrandbits(self, y, bits): '''The interface for :py:meth:`random.Random.getrandbits` in Python's Standard Library ''' ifnot (bits % 32 == 0): raise ValueError('number of bits must be a multiple of 32') ifnot (0 <= y < 2 ** bits): raise ValueError('invalid state') if bits == 32: self.setrand_int32(y) else: while bits > 0: self.setrand_int32(y & 0xffffffff) y >>= 32 bits -= 32
defgetrandbits(self, bits): '''The interface for :py:meth:`random.Random.getrandbits` in Python's Standard Library ''' ifnot (bits > 0): raise ValueError('number of bits must be greater than zero') if bits <= 32: returnself.genrand_int32() >> (32 - bits) else: acc = bytearray() while bits > 0: r = self.genrand_int32() if bits < 32: r >>= 32 - bits acc += _to_bytes(r, 4, byteorder='little') bits -= 32 return _from_bytes(acc, byteorder='little')
defrandom(self): '''The interface for :py:meth:`random.Random.random` in Python's Standard Library ''' a = self.genrand_int32() >> 5 b = self.genrand_int32() >> 6 return ((a * 67108864.0 + b) * (1.0 / 9007199254740992.0))
defget_wiki(): r = rq.get('https://en.wikipedia.org/wiki/Special:Random') soup = BeautifulSoup(r.text, 'html.parser') text = ''.join(x.getText() for x in soup.select('#mw-content-text p')) return text
for x inrange(100): withopen(f'wiki/{x}.bin', 'wb') as f: f.write(encrypt(get_wiki()))
import requests as rq from bs4 import BeautifulSoup from Crypto.Cipher import AES from pwn import * import warnings
warnings.filterwarnings('ignore')
starttext=[] enc=b'\x92\xc2\xbe\xf0ia\xb8\xe6$\xf3\x85\x9e\xc9\x1bq\xfe\xdc\xc0\xfb@AB/\x15\xee\x15\xf5\x0b\t\xf3_\x8b\xe5Vi\n\xad' f=b'HITCTF2023{' for x inrange(100): wiki=open(f'./wiki/{x}.bin','rb').read()[:len(f)] key=b'' for i inrange(len(f)): key+=p8(enc[i]^f[i]^wiki[i]) starttext.append(key.decode()) print(starttext) for _ inrange(10000): whileTrue: try: r = rq.get('https://en.wikipedia.org/wiki/Special:Random',verify=False,proxies={'https':'https://127.0.0.1:7890'}) break except rq.exceptions.ProxyError: continue soup = BeautifulSoup(r.text, 'html.parser') text = ''.join(x.getText() for x in soup.select('#mw-content-text p')) # print(text[:30]) flag=False for x inrange(100): if starttext[x]==text[:len(f)]: # print(x,text) enc=b'\x92\xc2\xbe\xf0ia\xb8\xe6$\xf3\x85\x9e\xc9\x1bq\xfe\xdc\xc0\xfb@AB/\x15\xee\x15\xf5\x0b\t\xf3_\x8b\xe5Vi\n\xad' wiki=open(f'./wiki/{x}.bin','rb').read() key=b'' for i inrange(len(enc)): key+=p8(enc[i]^text.encode()[i]^wiki[i]) print(key) flag=True # quit() ifnot flag: pass # print('fail')
# n = 17902353567622320185777049331592309927239379192917117124516253608017557550627376763554958867462642282718543076324834231080699086623868710566553973952161749036816316657408459820693134434685569943197364189133739682856780965058668333517601571118616370506564023806471382114482858088357033228430391110623954763871538990093806938234597382942012180059752099567844832912659963475196683651028851849981302053674312805891392388680444798065987917999016172592304263204248351584891058415818980019666086607175018795314608058824544702338113785073002606314177156566848980858910264144070733544539393470508272882039794755616359771719627 # e = 1034634982085939971822877252130515398229137701838084160804904278572779087263905524982867039382456627125720139442953049736278013459888513875454873912330970537830167429166547199300006618374698744011162743883768671546268984017745518427535961172408779556805945092711610212366863443025792023943002203100033357943550282607567215748076225755327456577797855829220040938158155034393838096697294851045502459515772190581191229891599270946348904293098125604418374903031570427182844970175294846199499086061932599929584168332019942366307492063085292032814310184327147039893062100775021251207692053416274742557240198045244353223877 # c = 14723945115918742456302931509235728534342691729551439971707959468746129976005121366466446595331259969536700193723388531609707306206111950891345249124123562757153406090874765289421941892028561640046821593863529710424324442809340720142304670377208025287443825716451893752244746535555688176067485135385849773481551193758429961182249805259097126618316927644797327132081971724413313476253673746378090768833873175854784850174609314401513707777282509452100625937487822417524568570482342892125363854710176244691334681860188285245854701213388715116327223347862337585079816713103737507482603397381805059087115251736140321565166
n = 17902353567622320185777049331592309927239379192917117124516253608017557550627376763554958867462642282718543076324834231080699086623868710566553973952161749036816316657408459820693134434685569943197364189133739682856780965058668333517601571118616370506564023806471382114482858088357033228430391110623954763871538990093806938234597382942012180059752099567844832912659963475196683651028851849981302053674312805891392388680444798065987917999016172592304263204248351584891058415818980019666086607175018795314608058824544702338113785073002606314177156566848980858910264144070733544539393470508272882039794755616359771719627 e = 1034634982085939971822877252130515398229137701838084160804904278572779087263905524982867039382456627125720139442953049736278013459888513875454873912330970537830167429166547199300006618374698744011162743883768671546268984017745518427535961172408779556805945092711610212366863443025792023943002203100033357943550282607567215748076225755327456577797855829220040938158155034393838096697294851045502459515772190581191229891599270946348904293098125604418374903031570427182844970175294846199499086061932599929584168332019942366307492063085292032814310184327147039893062100775021251207692053416274742557240198045244353223877 c = 14723945115918742456302931509235728534342691729551439971707959468746129976005121366466446595331259969536700193723388531609707306206111950891345249124123562757153406090874765289421941892028561640046821593863529710424324442809340720142304670377208025287443825716451893752244746535555688176067485135385849773481551193758429961182249805259097126618316927644797327132081971724413313476253673746378090768833873175854784850174609314401513707777282509452100625937487822417524568570482342892125363854710176244691334681860188285245854701213388715116327223347862337585079816713103737507482603397381805059087115251736140321565166
pq = [] c = continued_fraction(Integer(e) / Integer(n)) for i inrange(500): d = c.denominator(i) k = c.numerator(i) if k != 0: p_q = ((n+63**2)-(e*d-1)//k) // 63# p+q if2**399 < d < 2**400and p_q > 0: print('p_q=',p_q) break
var("p q") solve([p+q==p_q,p*q==n],p,q)
RSA 解密:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
# pycharm from Crypto.Util.number import * import gmpy2
n = 17902353567622320185777049331592309927239379192917117124516253608017557550627376763554958867462642282718543076324834231080699086623868710566553973952161749036816316657408459820693134434685569943197364189133739682856780965058668333517601571118616370506564023806471382114482858088357033228430391110623954763871538990093806938234597382942012180059752099567844832912659963475196683651028851849981302053674312805891392388680444798065987917999016172592304263204248351584891058415818980019666086607175018795314608058824544702338113785073002606314177156566848980858910264144070733544539393470508272882039794755616359771719627 e = 1034634982085939971822877252130515398229137701838084160804904278572779087263905524982867039382456627125720139442953049736278013459888513875454873912330970537830167429166547199300006618374698744011162743883768671546268984017745518427535961172408779556805945092711610212366863443025792023943002203100033357943550282607567215748076225755327456577797855829220040938158155034393838096697294851045502459515772190581191229891599270946348904293098125604418374903031570427182844970175294846199499086061932599929584168332019942366307492063085292032814310184327147039893062100775021251207692053416274742557240198045244353223877 c = 14723945115918742456302931509235728534342691729551439971707959468746129976005121366466446595331259969536700193723388531609707306206111950891345249124123562757153406090874765289421941892028561640046821593863529710424324442809340720142304670377208025287443825716451893752244746535555688176067485135385849773481551193758429961182249805259097126618316927644797327132081971724413313476253673746378090768833873175854784850174609314401513707777282509452100625937487822417524568570482342892125363854710176244691334681860188285245854701213388715116327223347862337585079816713103737507482603397381805059087115251736140321565166
p = 133692662205255845070134110211670069667562916611371168507338192638194811505238452911914167515227517561862383086864760853808343895528706459499417435431475609839307792155077671384159375749461187350011029990926277137666886607094014846229250724641865027117205014766152841534334624932589472229751110506457363204899 q = 133906777472477669829367660266874760999031712017146297400180540508325757132358918905621761484071456765643249548179748826272000598844722639479610013946944328244706853438688760358571667788680154767060315954219244186381237004913488011028446790450515241197741963630738164793387760358398092746357413686882688438073 phi = (p-1)*(q-1) d = inverse(e, phi) m = pow(c, d, n) print(long_to_bytes(m))