Weil paIring

• 前言

编者对群的了解比较基础，可能一些证明不太会

借鉴crypt03-15.tex.dvi

双线性映射

• 在数学中，一个双线性映射是由两个向量空间上的元素，生成第三个向量空间上一个元素之函数，并且该函数对每个参数都是线性的。例如矩阵乘法就是一个例子。

• 线性性

x,x’∈V,y’∈W,以及标量a,b为整数，双线性映射$f:V×W→K$

必须满足:

$f(ax+bx’,y)=af(x,y)+bf(x’,y)$
$f(x,ay+by’)=af(x,y)+bf(x,y’)$

双线性配对的性质:设映射e:

双线性映射可以用五元组(p,G1,G2,GT,e)来描述，G1，G2，GT是三个素数阶乘法循环群，阶数皆为p，定义在这三个三个群上的一个映射关系e：G1*G2 —>GT，满足以下性质：

• 双线性性

对于任意$a，b∈Zp$ ,有，有，有$e(Ra, Sb) = e(R, S)ab$

e(P,Q+R)=e(P,Q)*e(P,R)

• 非退化性：

存在R∈G2，S∈G1，使得e(R, S) ≠ 1（1∈G2代表G2群的单位元）

• 可计算性质

存在有效的算法对任意的R∈G2，S∈G1，计算e(R, S)的值。

Weil Pairing

• 挠点 指在椭圆曲线上具有有限阶的点。即存在正整数 m≥1m≥1，使得对于椭圆曲线 EE 上的点 PP，有 mP=Om**P=O，其中 OO 是曲线的单位元（无穷远点）。点 P 的阶即为 m，此时 P 被称为挠点。

将所有阶为m的倍数的点集合起来，就构成了m-挠群，定义为

$E[m]={P∈E：mP=O}$

挠群 E[m] 是椭圆曲线 E 的一个加法子群，其中单位元是无穷远点 O。如果 P,Q∈E[m]，则 P+Q 和 Q−P 也属于 E[m]，说明挠群具有封闭性和存在逆元，因此构成一个群结构.

当椭圆曲线定义在域 K上时，m-挠群记为 E(K)[m]。例如，定义在 Fp上的 E的 m-挠群写作 E(Fp)[m]

• 除子

是椭圆曲线上点的形式和，可以看作是一种“加权”点的概念，用于追踪有理函数上的零点和极点。如果在 α1 处有 e 个零点，就记为 $e1[α1]$；如果在 β1处有 d1 个极点，就记为 $−d1[β1$，然后再把它们形式的加起来（不是普通的加法运算）：

$div(f)=e1[α1]+…+e_r[α_r]-d_1[β_1]-…-d_t[β_t]$

$E[m]=Z/mZ×Z/mZ$

E[m]表示有两个阶为m的循环周期组成。

选取一组基{$T_1,T_2$}，定义映射：

det:$E[m]×E[m]→Z/mZ$ det$(aT_1+bT_2,cT_1,dT_2)=ad−bc$

这一段原理验证借鉴的别人的博客和论文(抽象代数大概看了基础群环域也还是看不太懂，以后学到一定程度了再看看)

设P,Q∈E[m],也就是说P和Q是群E上阶为m的点。f_P和f_Q 

$div(f_p)=m[P]-m[O]$,$div(f_Q)=m[Q]-m[O]$

可知 f∘[m] 与 g**m 有相同的除子, 因此在差一个常数的意义下 f∘[m]=$g^m$. 对任意 S∈E[m] 及 X∈E, 我们有

$g(X+S)m=f([m]X+[m]S)=f([m]X)=g(X)^m.$

因此对任意 X 有 g(X+S)/g(X) 都是 m-次单位根, 且 E→P1 不是满射, 只能是常值映射. 因此

$e_m:E[m]×E[m]→u_m, $

$*e_m S,T=g(X)\over g(X+S)$

Weil 配对有如下性质：

• 双线性：

$e_m(S_1+S_2,T)=e_m(S_1,T)e_m(S2,T),e_m(S,T_1+T_2)=e_m(S,T_1)+e_m(S,T_2)$

$e_m(s_1^a,T^b)^{ab}$

• 反对称:

$e_m(S,T)=e_m (T,S)^{-1}.$

• 非退化

若对任意 S∈E[m] 有 $e_m$(S*,*T)=1, 则有 T=O.

• Galois不变:

对任意 a∈GKˉK, 有 $e_m(S,T)^a=e_m(S^a,T^a).$

• Compatibility:

If$ P ∈ E[mn]$ and$ Q ∈ E[n]$, the$n e_{mn}(P, Q) = e_n(mP, Q)$.

• 阶的性质

如果P和Q的阶为 o*o,则 $e(P,Q)^o=1$

SU_signin

SU_signin

题目源码

from Crypto.Util.number import *
from secret import flag

bit_length = len(flag) * 8

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K = GF(p)
E = EllipticCurve(K, (0, 4))
o = 793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289
n1, n2 = 859267, 52437899

while(1):
    G1, G2 = E.random_element(), E.random_element()
    if(G1.order() == o and G2.order() == o):
        P1, P2 = (o//n1)*G1, (o//n2)*G2
        break

cs = [(randrange(0, o) * P1 + randrange(0, o) * G2).xy() if i == "1" else (randrange(0, o) * G1 + randrange(0, o) * P2).xy() for i in bin(bytes_to_long(flag))[2:].zfill(bit_length)]
print(cs)

第一眼看上去就是普通的ECC，但是这里给了两组阶相容的G1，G2

然后生成P1和P2的阶分别为n1和n2

然后如果二进制位为1，(randrange(0, o) * P1 + randrange(0, o) * G2)=w

如果二进制位为0，(randrange(0, o) * G1 + randrange(0, o) * P2)=u

n1*w=W,

n2*u=U

E(W,G2)=1,E(U,G1)=1

所以可以利用G1和G2判断，这里G1和G2也是未知的，我们假设cs[0]=0,cs[1]=1

G1=n2*Cs[0] *

G2=n1Cs[1]

最后如下脚本解出

import ast
from binteger import Bin
from Crypto.Util.number import long_to_bytes

p = 0x1A0111EA397FE69A4B1BA7B6434BACD764774B84F38512BF6730D2A0F6B0F6241EABFFFEB153FFFFB9FEFFFFFFFFAAAB
K = GF(p)
E = EllipticCurve(K, (0, 4))
n1, n2 = 859267, 52437899
C1=E(3352313779859460801486003925032655136993856710790727105363441252341552956083285634840018349420910752791594969280380, 2427629935062136228505338781822031098060538648527098540077074467697895064173228853125697497410079713420476853660385)
C2=E(2032510133375718031059693186824253736676017099152335002107480680688541061384422204257433121826049241452388039124165, 2686417581815542117120994330320923056212034586374942390097827699544930213612843423746022765194966762867963235937975)
G1=n2*C1
G2=n1*C2
o=793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289

P1, P2 = (o//n1)*G1, (o//n2)*G2
cs = []
a = b''
for q in cs:
    x,y=q
    Q=E(x,y)
    Q1=n1*Q
    if Q1.weil_pairing(G2, o)==1:
        a=a+b'1'
    else:
        a=a+b'0'
print(a)
flag = long_to_bytes(int(a,2))
print(flag)
‘’‘
b'01010011010101010100001101010100010001100111101101010111011001010011000101100011011011110110110101100101010111110101111101010100001100000101111101011111010100110101010101000011010101000100011001011111010111110011001000110000001100100011010101111101'
b'SUCTF{We1come__T0__SUCTF__2025}''
’‘’