qaq
题目如下：
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from sage.all import *
from functools import reduce
def mul(numbers):
return reduce(lambda x, y: x * y, numbers)
res = [4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272555731, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272556223, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272556437, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272556749, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272557237, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272557459, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272557687, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272558239, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272558627, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559239, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559523, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272560169, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272560343, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272560433, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272560751, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272560969, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272561441, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272562103, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272562601, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272563261, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272563297, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272563391, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272563511, 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272563711]
p = res[11]
pp = mul(res)
K = GF(p)
E = EllipticCurve(K, (0, 4))
qwq = 0x320238b
qaq = E.order()//qwq**2
flag = pad(open("flag.txt", "rb").read().strip(),4)
flag_part = [bytes_to_long(flag[i:i+2]) for i in range(0, len(flag), 2)]
output = []
for c in flag_part:
P1 = qaq*E.random_element()
P2 = qaq*E.random_element()
out = P1.weil_pairing(P2, qwq)**3*c
output.append(pow(out,qaq, pp))
print(output)比较简单，知道 pow(P1.weil_pairing(P2, qwq), qwq, pp) 为 1 这个性质就好搞了，直接爆破。
from tqdm import trange
output = [2258729984869869545899085887518820011795880892632317458813070773270633871398785757696896679887453336507722151037267, 1843407310728065127389586068976768146728145160643439144895915852634291722663455873979176336542780552480617232750208, 1107061034832953338095294459542523703297843192927313275050958753437078121375795698115353665062727895555487155331316, 460337686287218470707660572908024613140030922587867288532588857547792028112129697850035268228038619747643899804437, 1659483062154723617504533638726171721668768657049197025961515070605996080663312140357834824850074607457421362000265, 3150528329201636320206556304125544975332446992414777732425647667048147102509308959254762895094589762017857965981432, 3338854035461286314545186888372727000962778038359519702308782495912356677650264814573463929190025956045491115654437, 3042574495339632074308497406446851120362994432361876743901608172567070991832258762751304397604780567703759317642849, 380771388315580393673388198522357440257018642337119013880143084485482127962577943753495690258532782147018511750175, 507222017133457507399048159541059729302482262298099528096040456818913085187752925782279385808732260473494863290057, 533663958640518878580794848474449572155795564171089765377581587253792204491009275840408579120376539757958097910250, 2681145160205204287930367627648683111546318004811732016137828270063753300095675791698398080219566725174890793619305, 3259478178021541801713314504097142165241891541242669456591074651894459393333167453811425864198267757724232689747676, 3553147298452254907907643059383506744982654808021508866104139240155822133286673657139615950259800036058045049186173, 1778776925369812510137824472396145391840300438509021838870105004154301861222612045533034046889878767915343446874895, 3409071358092535255033136229525415652816479844958949032220987821989305575696869929136493897719813036034016228268240, 571819148781137687997336847709735468532344087614483867682513640750800758034003212746545051127998686475933050072942, 2676666310158795770609746651024766841212271213339384335651155407291004834251914242990757216402110096603729617413168, 2557670339976470006330058052583841683167706755578266425502679937976714609864257535859316483527764340425703004883241, 973319024062640263364951783086923560907216776835485042157036675663719529568519121997200478026304141184810597275543, 1189768012357955450386827626693191057999220508190415783719135619271537446794904663649700073564180453068646130539863, 790522915783756530835443034667719516913120763875831140857606265058871034793645280121113275798239222760522467771184]
qwq = 52437899
qaq = 1455562845228184014106046353081846661166991594741034685342212005778133078550081291411839443612828739
p = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787
pp = 1142978779632379969344384731816162212888551618412329487106182280460437948092775711025967355940728231074890740899064640830398142874211991038883733284039800714505967651759704707992207784798239393362313297134594620014689682614240673537974557609861073306584658917996634844473811713419516903992529010895368959512679762289061068750767272698410215219533780655490415972743692988039833721614365666351993335487907630409251025045193853809748905622077308664180480367745710426032292386656086977067733622324316251529279607679277315460682229036612415671436750122463497232354487970164567780660490851719503274520946852300175626980611392631378809761471008912076867118407483633023972770466259823927186918393298562128724829440836477986155752970694743829209037174635041410726609282526831341517005657513843064438822963889242924262793222516020047446160732380317460354380360631410063425737815245021223478414682926747310466080332446879064402066941673574937629942929233455490274643362453741527197512754992027588837742379352267575132076083027187211706722453314430311004216968206130931288118058422366846939843087867250208877457319655178776062205940749067608893888034471934498471108657546819750267606396282564760741394990056227498915716584453032204001863843912412620387842902864334464379557329439877766499721799090180106521949951507272088709752519109213448727550708629255894136853537524380257318749296652254490078801325565006537513324586727547784991700595087705177455733512116158384067200350557794061293097502070348758198384841013593727341655870858396981828914338167957355150495452710750066169828143717442866112149903974836803397451575951574758654598880735940075788671576674526836994715591739706357057699815597838906674624342854258780099739154689251277228387303286939318942508552968316726162904163233093355404058098725090760924700590208502555303625523880704006432299376446667399608178425319560581147711144539551105861283701119108963169437908720656474728443678191938587615688687790629662300315532804071728862616303844951511490625466845163653129560217890959711300145881339450565190571060840607910845859092526135249208093288167160336376760756304426346191389836338030781150259308295948794598941075005091244070210278000618109506241126900605449640742804019648207423896435466279361456668694686659046783765010159699708381871052284511858609936333837955434251107707443213658437730311109969181952584054470023007587546017226025865786999438913340937349025972249717158120517871211726893902696323141657820845379040062853354814032959005613852245360974457983567350637965684959556717166402357443319038744133853892077940635948927422008055364972815542308398644934412934780783306202098819759411204807373212433398053269281025972467100298781118011559579222633822445452194520775694259907477695015888131044620718709602314026156618474076423869840805574376019023676271040579611999127090671029103930178015883340947208339547
flag = []
for fp in output:
target = pow(fp, qwq, p)
for i in trange(65536):
if pow(i, qwq*qaq, p) == target:
print(i)
flag.append(i)
print(flag)
break
from Crypto.Util.number import long_to_bytes
flag = b''.join([long_to_bytes(i) for i in flag])
print(flag)ECBag
题目如下：
from random import randint, choice
from Crypto.Util.number import *
from secret import flag
p = getPrime(160)
print("p =", p)
a, b = int(input("a =")), int(input("b ="))
assert len(set([a%p, b%p, (a+b)%p, (a-b)%p])) == 4
E1 = EllipticCurve(Zmod(p), [a, b])
E2 = EllipticCurve(Zmod(p), [a+b, a-b])
P, Q = E1.gens()[0], E2.gens()[0]
n = 80
s = [choice([0, bytes_to_long(flag)]) for _ in range(n)]
sP, sQ = [_*P for _ in s], [_*Q for _ in s]
AP, AQ = [randint(0, p) for _ in range(n)], [randint(0, p) for _ in range(n)]
encP, encQ = sum([AP[_]*sP[_] for _ in range(n)]), sum([AQ[_]*sQ[_] for _ in range(n)])
print("A =", [AP, AQ])
print("enc =", [P.xy(), Q.xy(), encP.xy(), encQ.xy()])我不会椭圆曲线啊
数一数发现竟然对于 MT19937 来说数据是够的，但是由于 randint 的原因，可能会有一些数据错位，具体来说就是他会先 getrandbits，如果这个数超过 p 了，那么就会继续生成，此时我们丢失了这个比较大的随机数，那么就得赌他 randint 生成的数据全在 p 以内，这样就跟 getrandbits 一样了。
然后什么 DLP 也不太会，抄一抄代码，做一些优化，避免一下模逆不存在的情况。
每次都会跑出一个 flag mod N，flag 比较大的情况要多出几次做 CRT，实测一般大概 200 次左右出完整的。
远程环境 10 秒一个 getPrime(160)，太逆天了。
一开始跑出来了一个，队友没交直接把容器关了，放生一个 flag，差点 GG，还好又跑出来了，就是一血没了。
非预期图一乐，没啥学习价值。
from pwn import *
from sage.all import *
import ast
from Crypto.Util.number import bytes_to_long, long_to_bytes
import sys
sys.path.append('./MT19937-Symbolic-Execution-and-Solver-master/source')
from MT19937 import MT19937, MT19937_symbolic
from tqdm import trange
import itertools
context.log_level = 'error'
def main():
r = process(['sage', 'task.sage'])
r.recvuntil(b'p =')
p = int(r.recvline().strip())
from sage.parallel.multiprocessing_sage import pyprocessing
def find_ab_worker(*args):
p, attempts = args
import random
for _ in range(attempts):
a = random.randint(1, p-1)
b = random.randint(1, p-1)
try:
E1 = EllipticCurve(Zmod(p), [a, b])
E2 = EllipticCurve(Zmod(p), [a+b, a-b])
E1o = E1.order()
E2o = E2.order()
except:
continue
m1 = prod(list(filter(lambda x: x < 2 ** 32,
(base ** exp for base, exp in factor(E1o)))))
m2 = prod(list(filter(lambda x: x < 2 ** 32,
(base ** exp for base, exp in factor(E2o)))))
ml1 = m1.bit_length()
ml2 = m2.bit_length()
if ml1 > 40 and ml2 > 40 and (ml1 + ml2) > 120:
return (a, b)
return None
def find_ab(p, processes=20, batch_size=2):
parallel_iter = pyprocessing(processes)
P = parallel(p_iter=parallel_iter)
while True:
inputs = [((p, batch_size), {}) for _ in range(processes) ]
results = list(P(find_ab_worker)(inputs))
for res in results:
if res[1] is not None:
return res[1]
a, b = find_ab(p)
r.sendlineafter(b'a =', str(a).encode())
r.sendlineafter(b'b =', str(b).encode())
r.recvuntil(b'A =')
A_data = r.recvline().strip().decode()
AP, AQ = ast.literal_eval(A_data)
r.recvuntil(b'enc =')
enc_data = r.recvline().strip().decode()
enc_points = ast.literal_eval(enc_data)
P_xy, Q_xy, encP_xy, encQ_xy = enc_points
E1 = EllipticCurve(GF(p), [a, b])
E2 = EllipticCurve(GF(p), [a+b, a-b])
P = E1(*P_xy)
Q = E2(*Q_xy)
encP = E1(*encP_xy)
encQ = E2(*encQ_xy)
known = AP + AQ[:45]
data = []
for i in known:
for _ in range(5):
data.append(i & 2**32-1)
i >>= 32
data = data[:624]
try:
rng = MT19937(state_from_data = (data, 32))
except:
r.close()
return None
for tryrev in trange(80, 300):
rng = MT19937(state_from_data = (data, 32))
rng.reverse_states(tryrev)
m_list = [rng() >> 30 for _ in range(tryrev)]
s = []
for i in m_list:
if i <= 1:
s.append(i)
if len(s) == 80:
break
E1o = E1.order()
E2o = E2.order()
def dl(Q, P, n, filnum):
primes = list(filter(lambda x: x < 2 ** 32 and gcd(x, filnum) == 1, (base ** exp for base, exp in factor(n))))
dlogs = []
for fac in primes:
t = int(n) // int(fac)
dlog = discrete_log(t*Q,t*P,operation="+")
dlogs.append(dlog)
k = int(crt(dlogs,primes))
return k, prod(primes)
sAP = sum([s[i]*AP[i] for i in range(80)])
sAQ = sum([s[i]*AQ[i] for i in range(80)])
sum_AP, modA = dl(encP, P, E1o, sAP)
sum_AQ, modB = dl(encQ, Q, E2o, sAQ)
mA = sum_AP * pow(sAP, -1, modA) % modA
mB = sum_AQ * pow(sAQ, -1, modB) % modB
# print(mA, modA)
# print(mB, modB)
try:
m = crt([mA, mB], [modA, modB])
return m, lcm(modA, modB)
except:
print('FUCK')
return (mA, modA) if modA > modB else (mB, modB)
if __name__ == '__main__':
flags = []
modulos = []
for _ in trange(1000):
res = main()
if res is not None:
if res[0] is not None and res[1] is not None:
flags.append(int(res[0]))
modulos.append(int(res[1]))
print("flags =", flags)
print("modulos =", modulos)
lst = list(zip(flags, modulos))
result = []
for i in range(2, len(lst)+1):
for combo in itertools.combinations(lst, i):
result.append(list(combo))
for combo in result:
f, m = map(list, zip(*combo))
try:
flag = long_to_bytes(crt(f, m))
if flag.startswith(b'flag'):
print(flag)
exit()
except Exception as e:
# print(e)
pass