双线性映射

定义

$G_1,G_2为两个q阶循环群，G_1是F_p椭圆曲线上的点群，G_2是F_{p^2}^*的子群，所以$定义了$f:G_1 ×G_2→G_T$，其中$G_1和G_2$为加法群，$G_T$为乘法群

有$g_1∈G_1,g_2∈G_2,a,b∈Z$，满足：

双线性性：$e(a*g_1,b*g_2)=e(g_1,g_2)^{ab}$

或者定义为：$e(P,Q+R)=e(P,Q)*e(P,R) \\ e(P+S,Q)=e(P,Q)*e(S,Q)$
非退化性：满足$e(g_1,g_2)≠e_{G_T}$，$e_{G_T}$代表 $G_T$的单位元
可计算性：存在有效算法$e(g_1,g_2)$

线性映射

线性映射如:

$$ f(x+y)=f(x)+f(y)\\ f(ax)=af(x) $$

对两个变量，分别单独看都是线性的，合在一起就叫双线性

如果有变量x,y，函数F(x,y)：

固定x,变化y：函数对y是线性的
固定y,变化x：函数对x是线性的

weil配对

Weil对可将椭圆曲线的挠群上的两个点，映射到一个特殊有限域的乘法子群上，借此可将椭圆曲线离散对数问题（ECDLP）投射到一般的离散对数问题（DLP）

$n$-torsion点：如果一个点$P$被“加自己”若干次以后会回到单位元 $\mathcal O$，那它就是torsion点，表现为$nP=\mathcal O$

$E[n]$：所有满足$nP=\mathcal O$的点放在一起，形成一个子群，记作$E[n]$

单位根：满足$\zeta^n=1$的数叫$n$次单位根，比如复数里$1,-1,i,-i$ 是4次单位根

除子：记录函数在哪些点有零、哪些点有极点，以及它们各自重复多少次，记作$\operatorname{div}(f)=n(P)-n(\mathcal O)$，表示在$P$有$n$重零点，在$\mathcal O$有$n$重极点：

$$ 设有理函数f(X) = \frac{a_0 + a_1 X + \cdots + a_n X^n}{b_0 + b_1 X + \cdots + b_m X^m}\\ 在复数范围内进行因子分解：f(X) = \frac{a(X - \alpha_1)^{e_1} (X - \alpha_2)^{e_2} \cdots (X - \alpha_r)^{e_r}} {b(X - \beta_1)^{d_1} (X - \beta_2)^{d_2} \cdots (X - \beta_s)^{d_s}}\\ $$

可写作：

$\operatorname{div}(f(X)) \triangleq e_1[\alpha_1] + e_2[\alpha_2] + \cdots + e_r[\alpha_r]-d_1[\beta_1] - d_2[\beta_2] - \cdots - d_s[\beta_s]$

$表示e_1个\alpha_1零点...在d_1有\beta_1个极点...$

定义

设$P,Q \in E[n]$，选择函数$f_P,f_Q$，满足

$$ \operatorname{div}(f_P) = n(P) - n(\mathcal O)\\ \operatorname{div}(f_Q) = n(Q) - n(\mathcal O) $$

可定义为：

$$ e_n(P,Q) = \frac{f_P(Q+S)}{f_P(S)} \bigg/ \frac{f_Q(P-S)}{f_Q(-S)}. $$

S为辅助点，为E中任意元素，且满足$S \notin \{\mathcal{O}, P,-Q,P,-Q\}\,$

只要输入的两个点P和Q都是n-torsion点，配对的输出$e_n(P,Q)$满足所有$x^n=1$的集合

题

红名谷2025

 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)

E的阶为qaq*qwq^2^,因为flag_part的每个元素为两个字节，也就是16bit，所以表示的范围为（0，$2^{16}$）

1
2


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

这两行代码将p1和p2投影到了qwq^2^阶子群，然后对这两个点进行weil配对，所以输出结果应该为qwq次单位根：

$$ e_{qwq}(p_1,p_2)^{qwq}=1 $$

所以$output=(e_{qwq}(p_1,p_2)^3*c)^{qaq} \ mod \ pp$

两边qwq次幂得到$output^{qwq}=c^{qwq*qaq}$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


from sage.all import *
from Crypto.Util.number import *
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
output = [2258729984869869545899085887518820011795880892632317458813070773270633871398785757696896679887453336507722151037267, 1843407310728065127389586068976768146728145160643439144895915852634291722663455873979176336542780552480617232750208, 1107061034832953338095294459542523703297843192927313275050958753437078121375795698115353665062727895555487155331316, 460337686287218470707660572908024613140030922587867288532588857547792028112129697850035268228038619747643899804437, 1659483062154723617504533638726171721668768657049197025961515070605996080663312140357834824850074607457421362000265, 3150528329201636320206556304125544975332446992414777732425647667048147102509308959254762895094589762017857965981432, 3338854035461286314545186888372727000962778038359519702308782495912356677650264814573463929190025956045491115654437, 3042574495339632074308497406446851120362994432361876743901608172567070991832258762751304397604780567703759317642849, 380771388315580393673388198522357440257018642337119013880143084485482127962577943753495690258532782147018511750175, 507222017133457507399048159541059729302482262298099528096040456818913085187752925782279385808732260473494863290057, 533663958640518878580794848474449572155795564171089765377581587253792204491009275840408579120376539757958097910250, 2681145160205204287930367627648683111546318004811732016137828270063753300095675791698398080219566725174890793619305, 3259478178021541801713314504097142165241891541242669456591074651894459393333167453811425864198267757724232689747676, 3553147298452254907907643059383506744982654808021508866104139240155822133286673657139615950259800036058045049186173, 1778776925369812510137824472396145391840300438509021838870105004154301861222612045533034046889878767915343446874895, 3409071358092535255033136229525415652816479844958949032220987821989305575696869929136493897719813036034016228268240, 571819148781137687997336847709735468532344087614483867682513640750800758034003212746545051127998686475933050072942, 2676666310158795770609746651024766841212271213339384335651155407291004834251914242990757216402110096603729617413168, 2557670339976470006330058052583841683167706755578266425502679937976714609864257535859316483527764340425703004883241, 973319024062640263364951783086923560907216776835485042157036675663719529568519121997200478026304141184810597275543, 1189768012357955450386827626693191057999220508190415783719135619271537446794904663649700073564180453068646130539863, 790522915783756530835443034667719516913120763875831140857606265058871034793645280121113275798239222760522467771184]
flag = []
for i in output:
    flag_part = pow(i,qwq,p)
    for h in range(65537):
        if pow(h,qaq*qwq,p) == flag_part:
            flag.append(h)
            break
flag = b''.join([long_to_bytes(i) for i in flag])
print(flag)