↓Skip to main content

notes of CryptoCTF 2023

·984 words·5 mins
Table of Contents

https://github.com/ljahum/crypto-challenges/tree/main/2023/cryptoCTF2023

Barak #

椭圆曲线狠活

Hessian Curve

$$ x^3 + y^3 +c - Dxy =0 \ (mod \ p) $$

先检查是什么曲线

https://www.hyperelliptic.org/EFD/

Hessian curves: x3+y3+1=3*d*x*y

所以理論上可以找 paper 看看有沒有寫轉回 Weierstrass form 的公式

常规ECC曲线
Short Weierstrass curves: y2=x3+a*x+b

EllipticCurve_from_cubic #

可以用 sage 內建的 EllipticCurve_from_cubic 來做

但这个函数只能接受a homogeneous cubic in three variables with rational coefficients 才行。

所以我们要先建立一个又三参数的cubic式子，然后利用投影的方法

将其变换到只需要x y也能够找到点的形式

先增加一个Z参数然后利用在考数一之前学习的体积分的技巧，

将 F(x,y,z)映射到Fz(x,y)

计算表达式 $$ (X’,Y’,Z’) $$

用偏微分的表达式计算投影方程x和y的表达式

令z=1

$$ x = x’/z’ \\ y = x’/z’ \\ z = 1 \\ z’/z’ = 1 $$

from Crypto.Util.number import long_to_bytes

p = 73997272456239171124655017039956026551127725934222347
d = 68212800478915688445169020404812347140341674954375635
c = 1

F = GF(p)

x, y, z = QQ["x,y,z"].gens()
eq = x ^ 3 + y ^ 3 + c * z ^ 3 - d * x * y * z
phi = EllipticCurve_from_cubic(eq)
E = phi.codomain().change_ring(GF(p))
P = (
    71451574057642615329217496196104648829170714086074852,
    69505051165402823276701818777271117086632959198597714,
)
Q = (
    40867727924496334272422180051448163594354522440089644,
    56052452825146620306694006054673427761687498088402245,
)

fx, fy, fz = map(lambda f: f.change_ring(F), phi.defining_polynomials())

// 设置x y z 进去函数后的运算方法
phiP = lambda x, y, z=1: E(fx(x, y, z) / fz(x, y, z), fy(x, y, z) / fz(x, y, z))
EP = phiP(*P)
EQ = phiP(*Q)
x = discrete_log(EQ, EP, operation="+")
print(x)
od = EP.order()  # the generator doesn't have full order
print(
    [
        flag
        for i in range(E.order() // od)
        if (flag := long_to_bytes(int(x + od * i))).isascii()
    ]
)
# CCTF{_hE5S!4n_f0rM_0F_3CC!!}

通式 #

$$ D = d3 \\ a = -27D(D^3 + 8) \\ b = 54(D^6 - 20D^3 - 8) \\ $$

p = 73997272456239171124655017039956026551127725934222347
G = GF(p)
d = G(68212800478915688445169020404812347140341674954375635)
D = d/3
c = 1
# Hessian Curve:
# x³ + y³ + 1 = 3Dxy
 
# Weierstrass equivalent
a = -27*D*(D^3 + 8)
b = 54*(D^6 - 20*D^3 - 8)
E2 = EllipticCurve(G, [a, b])
print(E2)
# Elliptic Curve defined by y^2 = x^3 + 44905983883632632311912975168565494049729462391119290*x + 4053170785171018449128623853386306889464200866918538 over Finite Field of size 73997272456239171124655017039956026551127725934222347
 
order = E2.order()
# 73997272456239171124655016995459084401465136460086688

Keymoted #

p 和 q有两个bit不一样，但位置已知，而且是flip的关系

逻辑

P->|flip两个bit|->S->|next pri|->Q

弯弯爷的思路

由于nbit - 1位置一定是1，flip相当于减去 $$ nbit-1=a\ 2^{nbit-1}=2^a $$

中间变量 $$ p’ = p-2^a $$

可以有灯饰 $$ p =p’+2^a\ p =p’\plusmn 2^a\ q = 2s+t+1\ $$ 1+t很小，爆一下就是解方程了

sage

from Crypto.Util.number import long_to_bytes

pkey = (
    6660938713055850877314255610895820875305739186102790477966786501810416821294442374977193379731704125177528590285016474818841859956990486067573436301232301,
    65537,
    5539256645640498184116966196249666621079506508209770360679460869295427007578,
    20151017657582479433586370393795140515103572865771721775868586710594524816458,
)
encx = 6641320679869421443758875467781930795132746694454926965779628505713445486895274490835545942727970688359873955019634877304270220728625521646208912044469433
ency = 2856872654927815636828860866843721158889474116106462420201092148493803550131351543372740950198853438539317164093538508795630146854596724019329887894933972

n, e, a, b = pkey
nbit = 256
pp = ZZ["pp"].gen()
p = 2 ** (nbit - 1) + pp
s = pp + 2 ** (nbit // 2)  # guess
for t in range(1000):
    q = 2 * s + 1 + t
    f = p * q - n
    rs = f.roots()
    if rs:
        print(t, rs)
        break
p = 2 ** (nbit - 1) + rs[0][0]
q = n // p
assert p * q == n
Z = Zmod(n)
E = EllipticCurve(Z, [a, b])
C = E(encx, ency)
Ep = EllipticCurve(GF(p), [a, b])
Eq = EllipticCurve(GF(q), [a, b])
od = Ep.order() * Eq.order()
d = pow(e, -1, od)
M = d * C
print(long_to_bytes(int(M.xy()[0])))

Z3

pkey = (6660938713055850877314255610895820875305739186102790477966786501810416821294442374977193379731704125177528590285016474818841859956990486067573436301232301, 65537, 5539256645640498184116966196249666621079506508209770360679460869295427007578, 20151017657582479433586370393795140515103572865771721775868586710594524816458)
enc = (6641320679869421443758875467781930795132746694454926965779628505713445486895274490835545942727970688359873955019634877304270220728625521646208912044469433,2856872654927815636828860866843721158889474116106462420201092148493803550131351543372740950198853438539317164093538508795630146854596724019329887894933972,1)
nbit = 256
n,e,a,b = pkey 
 
 
from z3 import *
 
 
k1 = 2 ** (nbit - 1)
k2 = 2 ** (nbit // 2)
for i in range(0,2000,2):
    print(i)
    s= Solver()
    p = BitVec('p', 256)
    q = 2*(p+k1+k2)+1+i     #4种情况 第1种情况i=2有解
    s.add(p*q == n)
    if s.check() == sat:
        tp = s.model()[p].as_long()
        if n%tp == 0:
            print(tp)
        
 
p = 93511613846272978051774379195449772332692693333173612296021789501865098047641    
q = 71231138455229760679977773382211636812795966734548537479512744210680602878261

ASIv1 #

三进制好活

记一下 别忘了GF(p)矩阵的传统手艺

from output import *
 
MR = matrix(GF(3), R)
MS = matrix(GF(3),12100,1, S)
 
a = MR.solve_right(MS)
flag = ''.join([str(a[i,0]) for i in range(110)])
#'12200101122112210002110212001112001011210012200110200221111110001002012120200110211202001221221020201121010111'
bytes.fromhex(hex(int(flag,3))[2:])
b'3Xpl0i7eD_bY_AtT4ck3r!'
 
#CCTF{3Xpl0i7eD_bY_AtT4ck3r!}

求ecc上的Q/2 #

没有设置 gf(P)就无所谓什么离散性了

# y^2 = x^3 - 76479349401*x
# Q = (2740238460026645848168554718863025/9496587522097110856052646144 : -40938233945632940227696869615241088990456963438185/925446596757862314622073825244539026870272 : 1)


E = EllipticCurve(QQ, [-76479349401, 0])
Q = E(
    2740238460026645848168554718863025 / 9496587522097110856052646144,
    -40938233945632940227696869615241088990456963438185
    / 925446596757862314622073825244539026870272,
)
for x in Q.division_points(2):
    print(",".join(map(str, x.xy())))
# CCTF{H4lVin9_pO!ntS_0n_3lLipT1C_cuRve5!}

An efficient key recovery attack on SIDH #

Supersingular Isogeny Diffie-Hellman protocol (SIDH)

这是什么？不知道

打就完事了

特征参数

$$ y^2=x^3+x\ y^2=x^3+6x^2+x\ $$

a, b = gen_param(190)
p = 2**a * 3**b - 1

F.<x> = GF(p^2, modulus = x**2 + 1)
EC = EllipticCurve(F, [0, 6, 0, 1, 0])
P, Q, R, S = gen_tpt(EC, a, b)

print(f'P = {P.xy()}')
print(f'Q = {Q.xy()}')
print(f'R = {R.xy()}')
print(f'S = {S.xy()}')

skey, _phi_dom, _phi_P, _phi_Q = keygen(EC, b, P, Q, R, S)

22年的狠活

examlp:

https://github.com/GiacomoPope/Castryck-Decru-SageMath/blob/main/baby_SIDH.sage

examlp

from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from hashlib import md5
from public_values_aux import generate_distortion_map

load("./castryck_decru_shortcut.sage")

x = QQ["x"].gen()
P = (
    3799366067639160994711391413511701264777392349807255916259320256251336249666 * x
    + 633884628131689177031068067897867565283026098415356709331881575255526844055,
    3967348484864888240941807454988077684669074109524399477973520952727771366997 * x
    + 2712354532382043232096058211997452093712477916671679907467703464009558475387,
)
Q = (
    560486392227142181240528415381730657098132581407794833013161975335122628946 * x
    + 3215971074127995409351672272900519761566156375365764079386358523254177565572,
    2231746347912007096335360835242707156884468521076802738444724241125548841199 * x
    + 1147378568798166954853288670809304301194478550602719730593160186622788033023,
)
R = (
    2656280316115888204975052029900945854050191685154131031859911335618240136443 * x
    + 1127449111197960889758916770042950976852995868310602942974825430779982061546,
    3477289737920472771668877366806058236254602770820629911886593813749930497839 * x
    + 4646016633241840360901490323351236375375727836768954121794139000985805816564,
)
S = (
    2403139149412141532587482679318245468078604585804423116505024414375742701912 * x
    + 2772488504607240668919423445309052101443116827322741849326656561794480962717,
    3356599382898540527962106232860239304405841217130774924490318752448476310798 * x
    + 2818004736373436361527915593539097434287090434842750370886675729711731978922,
)
# def eq(x, y):
#     return y^2  -(x^3+6*x^2+1*x)
# eqs = [eq(*P) for P in (P, Q, R, S)]
# pmul = gcd(eqs[0].resultant(eqs[1]), eqs[2].resultant(eqs[3]))
# print(factor(pmul))

p = 4651852759096127491733667803074539573102288457512521355046899661762757394431
a = valuation(p + 1, 2)
b = valuation(p + 1, 3)
F = GF(p ^ 2, "a", modulus=x ^ 2 + 1)
E_start = EllipticCurve(F, [0, 6, 0, 1, 0])
E_start.set_order((p + 1) ^ 2)
P, Q, R, S = [E_start(P) for P in (P, Q, R, S)]

a2 = 6
a4 = (
    2070374075904221348548347954672740119972290047985052548426161483408084160515 * x
    + 896749506444795652787374405713981306103783874504413776724865996633074195878
)
a6 = (
    2497300913991521538985990865799426081199023429830552981773916386651958830387 * x
    + 4243320791854592301388975795466391442631117041175807728844738724691845270777
)
E_end = EllipticCurve(F, [0, a2, 0, a4, a6])
E_end.set_order((p + 1) ^ 2)
_phi_P = (
    76437828586489590038329193939006186966443918785230388533883401536928551274 * x
    + 1854701339851606878866613257086348330205980107370562791121360193846610915298,
    3614996124089236146025194675467338095830005859290616536023140003816221458491 * x
    + 1308394538776387115295908857102539180825411698539070801598965381200026966383,
)
_phi_Q = (
    2350346337927935568113772636838467488287314266120334638991371449749383548230 * x
    + 3389994457403704259291228848441313337916860864318549296438418403582347527289,
    3514523396038039657181009561828298688334341559779027220238590888980836781356 * x
    + 1132784636339236588815425424619354807485262558088269015122405460656452137103,
)
phi_P, phi_Q = [E_end(P) for P in (_phi_P, _phi_Q)]

P2 = P
Q2 = Q
P3 = R
Q3 = S

two_i = generate_distortion_map(E_start)
skey = CastryckDecruAttack(E_start, P, Q, E_end, phi_P, phi_Q, two_i, 4)

ct = bytes.fromhex(
    "50d8ed352ccf3ce6d64b25e50ed67b832dcbcd94dcb7dc8293e813e0c83ace541abb61618d5f971ff5d24fab8a2e"
)

key = md5(long_to_bytes(skey)).digest()
iv = md5(str(skey).encode()).digest()

cipher = AES.new(key, AES.MODE_CFB, iv=iv)
flag = cipher.decrypt(ct)
print(flag)
# CCTF{3FfiC!En7_k3Y_R3c0vErY_4tTacK_ON_SIDH!!!}

ECDSA LLL attack #

https://blog.maple3142.net/2023/07/09/cryptoctf-2023-writeups/#marjan