1
2
3
4
5
6
7
8
9
title: 双线性配对补充及陇剑杯rsa.io复现
date: 2025-9-11 12:00:00
tags: 
  - crypto
  - 复现
  - 区块链
categories: crypto
banner_img: /img/xulun.jpg
banner_img_height: 150px

双线性配对补充＋陇剑杯-rsa.io复现

双线性配对

  • 双线性配对在最初的学习密码学的时候已经接触过，不过当时不是很能理解一些东西，现在重新写一下顺便进行总结。

双线性映射

  • 线性映射

    这里做简单的解释：线性映射

    给定域$F$ 上的线性空间$V$和$U$。如果有映射$f:V->U$满足: 对于任意向量$v_1,v_2∈V,标量c_1,c_2∈F$都有

    $f(c_1v_1+c_2v_2)=c_1f(x_1)+c_2f(x_2)$

    则称作$f$是V到U的一个线性映射$(linear .~mp)$ 也叫做线性变换

    上述满足的条件也可以叫做加性与齐加性

    $f(u+v)=f(u+v)$ $f(cu)=c[f(u)]$

双线性映射：

双线性性意味着

对于给定域$k$的向量空间 ，$X,Y,Z$ 或者交换环的模$X,Y,Z$，有

$f:X\times Y\longrightarrow Z$ 这样的映射

$f$是双线性映射，指$f$关于x,y都是线性的。也就是说，若固定$y∈Y,x∈X$

则映射$f(x,y)$ 是$X$到Z的线性映射。固定X同理

weil配对

  • 在很久之前我写的里面写过，这里做些补充，懒TT。weil的配对的是基于

    设$P,Q∈E[m]$,也就是说P和Q是群E上阶为m的点。$f_p$和$f_Q$是群E上的有理函数

    ，满足

    $div(f_p)=m[P]-m[O],divf(_{Q})=m[Q]-m[O]$

    则$P$和$Q$的weil Pairing的定义为

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

    式里面的S是E中的任意元素，且$S\notin {Q，P,Q,-Q,-P}$ 。而且$e_m(P,Q)的值不依赖于f_p.f_Q,S$的选择

    满足双线性的性质和特征这里不多做赘述。之前的文章已经说过。

陇剑杯-rsa.iso

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from Crypto.Util.number import *
from secret import flag

f = open("output.txt", "w")

def get_Prime(bits):
    from random import choices
    bytes = [long_to_bytes(x) for x in range(1, 256)]
    while True:
        num = b''.join(choices(bytes, k=bits//8))
        if is_prime(bytes_to_long(num)):
            return bytes_to_long(num)

def gen_para():
    while True:
        a = randint(50, 70)
        r = getPrime(10)
        if is_prime(2**a * r * lcm(range(1, 256)) - 1):
            return a, r

a, r = gen_para()
f.write(f'{a = }\n')
f.write(f'{r = }\n')

p = 2**a * r * lcm(range(1, 256)) - 1
F.<i> = GF(p^2, modulus=[1, 0, 1])
E = EllipticCurve(F, [0, 1])
E.set_order((p+1)**2)

P, Q = E.gens()[0], E.gens()[1]

f.write(f'P = {(P.x(), P.y())}\n')
f.write(f'Q = {(Q.x(), Q.y())}\n')

pp = get_Prime(1024)
qq = get_Prime(1024)
n = pp * qq
e = 65537

gift = []

while pp:
    x = pp & 0xff
    assert x != 0
    pp = pp >> 8
    k = randint(1, 2**a * x)
    R = P + k * Q
    K = (p + 1) // (2**a * x) * R
    phi = E.isogeny(K, algorithm="factored")
    tmp1 = phi(P)
    tmp2 = phi(Q)
    gift.append([(tmp1.x(), tmp1.y()), (tmp2.x(), tmp2.y())])

f.write(f'gift = {gift}\n')

m = bytes_to_long(flag)
c = pow(m, e, n)

f.write(f'n = {n}\n')
f.write(f'c = {c}\n')
  • 我们需要找到x，利用$2*ax$

$phi = E.isogeny(K, algorithm=”factored”)$

进行了一个同源映射，进行了群同态(由K生成核)，因为核子群的阶和域f的特征p互素，那么我们可以知道

ker(k)=der(phi)，同源映射的度等于这个核子群的阶。

同态映射的度，是指的这个映射的核群=k.order()(k的阶)=der(phi)。那么

我们可以利用weil配对der(phi)=d

$e_m(phi(P),phi(Q))=e_m(P,Q)^d$之后再利用discrete_log求解除p

不过呢。我们还需要计算一下同态映射后的椭圆曲线E2具体计算见WP。

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
35
36
37
38
39
40
41
42
43
from sage.all import *
from Crypto.Util.number import *
aa = 58
r = 677
p = 1626863075383233617973114208257225766167963541697680166689538585027790888344497393319393220115606426479054738139191706757627903999
F.<i> = GF(p^2, modulus=[1, 0, 1])
E = EllipticCurve(F, [0, 1])
P = E(1480902412624330128467265433604967924879175621324778721822553791992483165650313334065712892856426887628203798402227946111937619985*i + 248280033442212078026584729381629912663660842264732233544133931088920517333558326483592439680557530508869168630141184328058575487, 1063473267082463348943776983826670708619445017230835195844111648761226238767209731540252058515506618539450166188109440566086315438*i + 1477214491399359292603355035977428268773417965220883548847591474468057528862252443133638716703507083176807648546588008345161697639)
Q = E(254336484714918197927485057298709531964473530684332223357900471713016451491419116513817849296332713866136292050578743336482952063*i + 336569779925581133673425296270934299380299004021997431211455336955947557460506916625576473941830956381008213287862958120734974088, 672798403906655690530129932893570217632405529086858027624968144934702132760440998323563013877307454993136939248872471610804174868*i + 978599551527900215169394972113017743837581044055673443208277943573091308364000557275120262619669438354499782419523067775829261358)
gift = []
n = 1702964505167542294309894624134040051985456000751301895681450703711209123273929347840767189769333598802007931175534183099577982055982094813045245735950771056151798358709294596212693586845327740981840974734260947504192849082082247982531638166723519817368621543647358361718962016975501235560072299206879455551179363257011645248897834786135688841937320538329157671950684987955303502005404340327657787221436015711630895743615195023754086594138352253842575921303048726058807135221950653758612234421493377641405846466416194921001135032171697695572842723082164349170706748881797912294462023414297556608213847345725952421549
c = 1029114088686337892631302678503751809542083988891442035793586975372895407547705418982466289898928319560409880414514578474791488427127025559202986548834389826420682378231639934214095320267479088288097862850583409973649066883523716495624685075221287755197089845642475957655326217081767651038275947961474613737339181490066613632071544485135542705782597487288176673605371342372887413483451432315489970957375439078944009120957142560963596958126921713605049998752504003069481700268168699099735284558580028754084228031725395039694427728930164273683375216610222208763440193601962605329874384315938196365292841272339652972630
N =p+1
a = P.weil_pairing(Q, p+1)
pp=0
xs=[]
for idx, item in enumerate(gift):
    (x1, y1), (x2, y2) = item
    S1 = y1*y1 - x1*x1*x1
    S2 = y2*y2 - x2*x2*x2
    dx = x1 - x2
    A1 = (S1 - S2) / dx
    B1 = S1 - A1*x1
    E1 = EllipticCurve(F,[A1, B1])
    phiP=E1(x1,y1)
    phiQ=E1(x2,y2)
    a1=phiP.weil_pairing(phiQ,N)
    d=discrete_log(a1,a,N)
    x=int(d)//(2**aa)
    print(x)
    xs.append(x)
for i,b in enumerate(xs):
    pp|=(b<<(8*i))
if n % pp != 0:
    raise RuntimeError("pp 不能整除 n，可能解析出错。")
print(f'pp={pp}')
qq = n // pp
phi_n = (pp - 1) * (qq - 1)
dd = inverse(0x10001, phi_n)
m = pow(c, dd, n)
flag = long_to_bytes(m)
print("flag =", flag)

http://example.com/2025/09/12/双线线性配对及相关题目/
Beitragsautor
fox
Veröffentlicht am
September 12, 2025
Urheberrechtshinweis