文章 - [SUSCTF 2022]SpecialCurve3 WP by pcspcs

Problem: [SUSCTF 2022]SpecialCurve3


from Crypto.Util.number import *
from secret import flag,getMyPrime
import hashlib
import random

class SpecialCurve:
    def __init__(self,p,a,b):
        self.p=p
        self.a=a
        self.b=b

    def __str__(self):
        return f'SpecialCurve({self.p},{self.a},{self.b})'

    def add(self,P1,P2):
        x1,y1=P1
        x2,y2=P2
        if x1==0:
            return P2
        elif x2==0:
            return P1
        elif x1==x2 and (y1+y2)%self.p==0:
            return (0,0)
        if P1==P2:
            t=(2*self.a*x1-self.b)*inverse(2*y1,self.p)%self.p
        else:
            t=(y2-y1)*inverse(x2-x1,self.p)%self.p
        x3=self.b*inverse(self.a-t**2,self.p)%self.p
        y3=x3*t%self.p
        return (x3,y3)

    def mul(self,P,k):
        assert k>=0
        Q=(0,0)
        while k>0:
            if k%2:
                k-=1
                Q=self.add(P,Q)
            else:
                k//=2
                P=self.add(P,P)
        return Q

def problem(size,k):
    p=getMyPrime(size)
    x=random.randint(1,p-1)
    y=random.randint(1,p-1)
    e=random.randint(1,p-1)
    a=k*random.randint(1,p-1)**2%p
    b=(a*x**2-y**2)*inverse(x,p)%p
    curve=SpecialCurve(p,a,b)
    G=(x,y)
    Q=curve.mul(G,e)
    print(f'curve={curve}')
    print(f'G={G}')
    print(f'Q={Q}')
    return e

e1=problem(128,1)
e2=problem(256,0)
e3=problem(512,-1)
enc=bytes_to_long(hashlib.sha512(b'%d-%d-%d'%(e1,e2,e3)).digest())^bytes_to_long(flag.encode())
print(f'enc={enc}')
'''
curve=SpecialCurve(233083587295210134948821000868826832947,73126617271517175643081276880688551524,88798574825442191055315385745016140538)
G=(183831340067417420551177442269962013567, 99817328357051895244693615825466756115)
Q=(166671516040968894138381957537903638362, 111895361471674668502480740000666908829)
curve=SpecialCurve(191068609532021291665270648892101370598912795286064024735411416824693692132923,0,58972296113624136043935650439499285317465012097982529049067402580914449774185)
G=(91006613905368145804676933482275735904909223655198185414549961004950981863863, 96989919722797171541882834089135074413922451043302800296198062675754293402989)
Q=(13504049588679281286169164714588439287464466303764421302084687307396426249546, 110661224324697604640962229701359894201176516005657224773855350780007949687952)
curve=SpecialCurve(52373730653143623993722188411805072409768054271090317191163373082830382186155222057388907031638565243831629283127812681929449631957644692314271061305360051,28655236915186704327844312279364325861102737672471191366040478446302230316126579253163690638394777612892597409996413924040027276002261574013341150279408716,42416029226399083779760024372262489355327595236815424404537477696856946194575702884812426801334149232783155054432357826688204061261064100317825443760789993)
G=(15928930551986151950313548861530582114536854007449249930339281771205424453985946290830967245733880747219865184207937142979512907006835750179101295088805979, 29726385672383966862722624018664799344530038744596171136235079529609085682764414035677068447708040589338778102975312549905710028842378574272316925268724240)
Q=(38121552296651560305666865284721153617113944344833289618523344614838728589487183141203437711082603199613749216407692351802119887009907921660398772094998382, 26933444836972639216676645467487306576059428042654421228626400416790420281717654664520663525738892984862698457685902674487454159311739553538883303065780163)
enc=4161358072766336252252471282975567407131586510079023869994510082082055094259455767245295677764252219353961906640516887754903722158044643700643524839069337
'''

定义了曲线:

a x^{2} - b x = y^{2}

考核a分别为二次剩余，0，非二次剩余的三种情形
实际上稍加转换仍然是 $x^{2} - D y^{2} = 1$ 的情形，所以相似的有:

1、当 $λ (a) = 1$ 时：

做映射：

(x, y) - > t = \frac{y + a x}{y - a x}

则问题转换为 $F_{p}$ 上的DLP问题:

k = Q_{t} . l o g (G_{t})

2、当 $λ (a) = 0$ 时：

做映射：

(x, y) - > t = \frac{x}{y}

则问题转换为 $F_{p}$ 上的除法问题

k = \frac{Q _{t}}{G _{t}}

3、当 $λ (a) = - 1$ 时：

与第一种情形相似，只是这里a不是二次剩余，没有直接的 $a$ ,但可以换成在 $F_{q^{2}}$ 域下的 $a$ （类似于扩展到复数域上去，大概原理是搞到 $F_{q^{2}}$ 域上经一番约化后回到和 $λ (a) = 1$ 相同的情形），一样做映射：

(x, y) - > t = \frac{y + a x}{y - a x}

则问题转换为 $F_{p}$ 上的DLP问题:

k = Q_{t} . l o g (G_{t})


#!/bin/env python
#[SUSCTF 2022]SpecialCurve3
from sage.all import *
from Crypto.Util.number import *
import hashlib

p,a,b = (233083587295210134948821000868826832947,73126617271517175643081276880688551524,88798574825442191055315385745016140538)
Gx,Gy = (183831340067417420551177442269962013567, 99817328357051895244693615825466756115)
Qx,Qy = (166671516040968894138381957537903638362, 111895361471674668502480740000666908829)
w=sqrt(GF(p)(a))
Gt=(Gy+w*Gx)/(Gy-w*Gx)
Qt=(Qy+w*Qx)/(Qy-w*Qx)
e1=Qt.log(Gt)
print(f'{e1 = }')

p,a,b = (191068609532021291665270648892101370598912795286064024735411416824693692132923,0,58972296113624136043935650439499285317465012097982529049067402580914449774185)
Gx,Gy = (91006613905368145804676933482275735904909223655198185414549961004950981863863, 96989919722797171541882834089135074413922451043302800296198062675754293402989)
Qx,Qy = (13504049588679281286169164714588439287464466303764421302084687307396426249546, 110661224324697604640962229701359894201176516005657224773855350780007949687952)
Gt=GF(p)(Gx)/Gy
Qt=GF(p)(Qx)/Qy
e2=Qt/Gt
print(f'{e2 = }')
    
p,a,b=(52373730653143623993722188411805072409768054271090317191163373082830382186155222057388907031638565243831629283127812681929449631957644692314271061305360051,28655236915186704327844312279364325861102737672471191366040478446302230316126579253163690638394777612892597409996413924040027276002261574013341150279408716,42416029226399083779760024372262489355327595236815424404537477696856946194575702884812426801334149232783155054432357826688204061261064100317825443760789993)
Gx,Gy=(15928930551986151950313548861530582114536854007449249930339281771205424453985946290830967245733880747219865184207937142979512907006835750179101295088805979, 29726385672383966862722624018664799344530038744596171136235079529609085682764414035677068447708040589338778102975312549905710028842378574272316925268724240)
Qx,Qy=(38121552296651560305666865284721153617113944344833289618523344614838728589487183141203437711082603199613749216407692351802119887009907921660398772094998382, 26933444836972639216676645467487306576059428042654421228626400416790420281717654664520663525738892984862698457685902674487454159311739553538883303065780163)

w=sqrt(GF(p**2)(a))
Gt=(Gy+w*Gx)/(Gy-w*Gx)
Qt=(Qy+w*Qx)/(Qy-w*Qx)
e3=Qt.log(Gt)
print(f'{e3 = }')

enc=4161358072766336252252471282975567407131586510079023869994510082082055094259455767245295677764252219353961906640516887754903722158044643700643524839069337
flag=long_to_bytes( bytes_to_long(hashlib.sha512(b'%d-%d-%d'%(e1,e2,e3)).digest())^enc )
print(flag.decode())
#e1 = 184572164865068633286768057743716588370
#e2 = 131789829046710687154053378348742202935151384644040019239219239301007568911745
#e3 = 23331486889781766099145299968747599730779731613118514070077298627895623872695507249173953050022392729611030101946661150932813447054695843306184318795467216
#SUSCTF{Y0u_kNow_c0n1c_curv3_anD_discrete_l0g_vEry_we11~}

另外虽然a不是二次剩余，没有直接的整数值解，但事实上在sage中sqrt若无法解出直接值则会将 $a$ 标定为一个符号量而不是求出值，这样导致虽然对数计算过程中有符号值，但解完被约掉了，所以就算将w=sqrt(GF(p**2)(a))也写为w=sqrt(GF(p)(a))一样能得到正确结果，所以情形1和情形3虽然原理不同，但在解题代码上却可以完全一样。

若暂时时找不到合适映射的处置方法：

sage中有检测要求不能定义奇异椭圆曲线，所以虽然第三段是个平滑阶攻击，但无法直接定义ECC并最终利用内置discrete_log进行求解，假若我们暂时无法找到合适映射将ECC问题转换为DLP，又不想去重复造discrete_log轮子时，可以像如下构造类来利用内置discrete_log进行攻击(虽然代码还是显得有些复杂，要定义一堆内置函数，但终于还是能用了，是个较通用的方法；另注意第一段因阶p-1不太光滑此方法耗时太长不适用)：


class SpecialCurve:
    def __init__(self,xy): (self.x,self.y)=[GF(p)(x) for x in xy]
    __str__ = lambda self: f'SpecialCurve({self.x},{self.y})'
    order = lambda self: ZZ(p - jacobi_symbol(a,p))  
    __eq__=lambda self,P2: self.x==P2.x and self.y==P2.y    
    parent = lambda self: (idtf:=lambda x:SpecialCurve((0,0)))    
    is_zero = lambda self: self.x==0    
    __hash__ = lambda self: hash((self.x,self.y))
    __neg__ = lambda self: SpecialCurve((self.x,-self.y))

    def __add__(self,P2):
        P1=SpecialCurve((self.x,self.y))
        x1,y1=P1.x,P1.y
        x2,y2=P2.x,P2.y
        if x1==0:
            return P2
        elif x2==0:
            return P1
        elif x1==x2 and (y1+y2)==0:
            return SpecialCurve((0,0))
        if P1==P2:
            t=(2*a*x1-b)/(2*y1)
        else:
            t=(y2-y1)/(x2-x1)
        x3=b/(a-t**2)
        y3=x3*t%p
        return SpecialCurve((x3,y3))

    def __mul__(self,k):
        assert k>=0
        Q=SpecialCurve((0,0))
        P=SpecialCurve((self.x,self.y))
        while k>0:
            if k%2:
                k-=1
                Q=Q+P
            else:
                k//=2
                P=P+P
        return Q
    
p,a,b=(52373730653143623993722188411805072409768054271090317191163373082830382186155222057388907031638565243831629283127812681929449631957644692314271061305360051,28655236915186704327844312279364325861102737672471191366040478446302230316126579253163690638394777612892597409996413924040027276002261574013341150279408716,42416029226399083779760024372262489355327595236815424404537477696856946194575702884812426801334149232783155054432357826688204061261064100317825443760789993)
G=(15928930551986151950313548861530582114536854007449249930339281771205424453985946290830967245733880747219865184207937142979512907006835750179101295088805979, 29726385672383966862722624018664799344530038744596171136235079529609085682764414035677068447708040589338778102975312549905710028842378574272316925268724240)
Q=(38121552296651560305666865284721153617113944344833289618523344614838728589487183141203437711082603199613749216407692351802119887009907921660398772094998382, 26933444836972639216676645467487306576059428042654421228626400416790420281717654664520663525738892984862698457685902674487454159311739553538883303065780163)
e3=discrete_log(SpecialCurve(Q),SpecialCurve(G),operation='+')
print(f'{e3 = }')
#e3 = 23331486889781766099145299968747599730779731613118514070077298627895623872695507249173953050022392729611030101946661150932813447054695843306184318795467216


NSSCTF{Y0u_kNow_c0n1c_curv3_anD_discrete_l0g_vEry_we11~}

[SUSCTF 2022]SpecialCurve3 WP by pcspcs

1、当λ(a)=1时：

2、当λ(a)=0时：

3、当λ(a)=−1时：

若暂时时找不到合适映射的处置方法：

1、当 $λ (a) = 1$ 时：

2、当 $λ (a) = 0$ 时：

3、当 $λ (a) = - 1$ 时：