2025红明谷

ouo

拼尽全力只能做出来一道,唉还是太菜了

qaq

题目

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
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)

做这道题蛮重要的一点是要知道双线性对的特点

OSLYO1.png

首先我们知道

1
2
P1 = qaq*E.random_element()
P2 = qaq*E.random_element()

因为计算weil_pairing可以判断P1和P2是否线性相关,即存在k,使P1=kP2,那么我们不难得到e(p1,p2)=1,即(e(p1,p2)$^{qwq}$)$^3$=1 mod pp,所以((e(p1,p2)$^{qwq}$)$^{3*qaq}$ =1 mod p,即pow(pow(int(P1.weil_pairing(P2, qwq)**3), qaq, pp), qwq, p)=1。

且有

1
out = P1.weil_pairing(P2, qwq)**3*c,

即有

1
pow(pow(out, qaq, pp), qwq, p)=(1⋅c^qaq)^qwq mod p=c^(qaq⋅qwq)modp=pow(c,qaq*qwq,p)

由费马小定理,c$^{qaq⋅qwq mod(p−1)}$≡c $^{qaq⋅qwq}$modp ,我们令d=inv(qaq⋅qwq,p−1),这里因为qaq⋅qwq与p-1有公因数。我们除去公因数后才能求解逆元。

c≡(out$^{qaq⋅qwq}$)$^d$ mod p.解出c后建立字典进行每两字节的映射还原flag即可。

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
32
33
34
from Crypto.Util.number import inverse, long_to_bytes,bytes_to_long
import gmpy2
from gmpy2 import invert
from string import printable
from tqdm import *
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
order = E.order()
qwq_sq = qwq ** 2
qaq = order // qwq_sq
outputs=[2258729984869869545899085887518820011795880892632317458813070773270633871398785757696896679887453336507722151037267, 1843407310728065127389586068976768146728145160643439144895915852634291722663455873979176336542780552480617232750208, 1107061034832953338095294459542523703297843192927313275050958753437078121375795698115353665062727895555487155331316, 460337686287218470707660572908024613140030922587867288532588857547792028112129697850035268228038619747643899804437, 1659483062154723617504533638726171721668768657049197025961515070605996080663312140357834824850074607457421362000265, 3150528329201636320206556304125544975332446992414777732425647667048147102509308959254762895094589762017857965981432, 3338854035461286314545186888372727000962778038359519702308782495912356677650264814573463929190025956045491115654437, 3042574495339632074308497406446851120362994432361876743901608172567070991832258762751304397604780567703759317642849, 380771388315580393673388198522357440257018642337119013880143084485482127962577943753495690258532782147018511750175, 507222017133457507399048159541059729302482262298099528096040456818913085187752925782279385808732260473494863290057, 533663958640518878580794848474449572155795564171089765377581587253792204491009275840408579120376539757958097910250, 2681145160205204287930367627648683111546318004811732016137828270063753300095675791698398080219566725174890793619305, 3259478178021541801713314504097142165241891541242669456591074651894459393333167453811425864198267757724232689747676, 3553147298452254907907643059383506744982654808021508866104139240155822133286673657139615950259800036058045049186173, 1778776925369812510137824472396145391840300438509021838870105004154301861222612045533034046889878767915343446874895, 3409071358092535255033136229525415652816479844958949032220987821989305575696869929136493897719813036034016228268240, 571819148781137687997336847709735468532344087614483867682513640750800758034003212746545051127998686475933050072942, 2676666310158795770609746651024766841212271213339384335651155407291004834251914242990757216402110096603729617413168, 2557670339976470006330058052583841683167706755578266425502679937976714609864257535859316483527764340425703004883241, 973319024062640263364951783086923560907216776835485042157036675663719529568519121997200478026304141184810597275543, 1189768012357955450386827626693191057999220508190415783719135619271537446794904663649700073564180453068646130539863, 790522915783756530835443034667719516913120763875831140857606265058871034793645280121113275798239222760522467771184]
flag = b''
print(gcd(qaq*qwq,p-1))#15132376222941642753
print(gcd(qaq*qwq//15132376222941642753,p-1))#96192362849
d=invert(qaq*qwq//(15132376222941642753*96192362849),p-1)
m = []
for output in outputs:
result = pow(pow(output, qwq, p), d, p)
m.append(result)
gcd=15132376222941642753*96192362849
dic={}
for i in tqdm(printable):
for j in printable:
k = (i+j).encode()
dic[int(pow(bytes_to_long(k), gcd, p))] = k
for t in m:
print(dic[int(t)].decode(), end='')
#flag{530830fe-3b65-416a-8488-b9b8c06ba66d}

ECBag

等着有wp了复现吧