这次 medium 分类题量是最多的，内容方面是最丰富的，两极分化比较严重。

有脑筋急转弯的，有考察 SageMath API 使用的，有 MISC 题目混进来的……

总之 medium 分类最难的比 tough 还要更难……

Derik

题目描述

已知 $O_0, O_1, O_2, O_3$ 的值，以及 $C_0, C_1, C_2, C_3, C_4, C_5, C_6, C_7$ 的值，未知 $e, d, p, q, r$ 的值。

有如下条件：

  • $e, d, p, q, r$ 均为素数
  • $C_0 p - C_1 q \ge 0$
  • $C_2 p - C_3 r \ge 0$
  • $C_4 r - C_5 p \ge 0$
  • $(C_0 p - C_1 q) ^ e + (C_2 q - C_3 r) ^ e + (C_4 r - C_5 p) ^ e = d (C_0 p - C_1 q) (C_2 q - C_3 r) (C_4 r - C_5 p)$
  • $C_6 e - C_7 d = O_3$

RSA 中，$N = edpqr$，加密指数为 65537，对 flag 加密得到 $c$，试求 flag。

我的解答

首先从最后一个式子出发：因为 $e, d$ 均为素数，所以两者互素。

代入具体值分析：$C_6 = 10543, C_7 = 4, O_3 = 31337$，直接枚举 $e$，并求得 $d$，并作素性检验，会发现有很多组 $(e, d)$ 满足等式。这种题一般是要求最简单的，所以应该是 $(e, d) = (3, 73)$

然后记

就有：

这是三次齐次方程，等价于一个椭圆曲线。更多可以参考 SageMath 手册：

https://doc.sagemath.org/html/en/reference/arithmetic_curves/sage/schemes/elliptic_curves/constructor.html#sage.schemes.elliptic_curves.constructor.EllipticCurve_from_cubic

然后就可以依葫芦画瓢地构造一个椭圆曲线并求得生成元：

1
2
3
4
5
6
7
8
9
R.<x,y,z> = QQ[]
cubic = x^3 + y^3 + z^3 - 73 * x * y * z
P = [1,-1,0]
E = EllipticCurve_from_cubic(cubic, P, morphism=False)
f = EllipticCurve_from_cubic(cubic, P, morphism=True)
finv = f.inverse()
R = E.gens()[0]
PP = f(P)
print(finv(R))

注意 $(A, B, C) = (1, -1, 0)$ 仍然为我们三次齐次方程的非零解。并且，三次齐次方程关于未知量 $(A, B, C)$ 对称。

然后很惊讶地发现，结果为：

1
(2848691279889518/1391526622949983 : 89200900157319/1391526622949983 : 1)

也就是恰好为题目所给的 $O$ 数组的 $O_0, O_1, O_2$！

也就是说，即使(e, d)还有那么多组解，即使椭圆曲线上还有其他的点（生成元的倍点），我们都不 care，只 care 这个能跟出题的对上脑电波的这一组解 WTF

至此，我们有 3 个关于 $(p, q, r)$ 的线性方程，直接枚举 $(O_0, O_1, O_2)$ 作为所有的排列作为右边的东西解线性方程就行了（事实上连排列都压根不用做，他那个等式和 O 的顺序完全就是对上的）

1
2
3
4
5
6
7
8
9
10
11
12
13
import itertools

O = [1391526622949983, 2848691279889518, 89200900157319]
C = [5960650533801939766973431801711817334521794480800845853788489396583576739362531091881299990317357532712965991685855356736023156123272639095501827949743772, 6521307334196962312588683933194431457121496634106944587943458360009084052009954473233805656430247044180398241991916007097053259167347016989949709567530079, 1974144590530162761749719653512492399674271448426179161347522113979158665904709425021321314572814344781742306475435350045259668002944094011342611452228289, 2613994669316609213059728351496129310385706729636898358367479603483933513667486946164472738443484347294444234222189837370548518512002145671578950835894451, 8127380985210701021743355783483366664759506587061015828343032669060653534242331741280215982865084745259496501567264419306697788067646135512747952351628613, 5610271406291656026350079703507496574797593266125358942992954619413518379131260031910808827754539354830563482514244310277292686031300804846114623378588204, 10543, 4]

A = matrix(ZZ, [[ C[0], -C[1],     0],
                [    0,  C[2], -C[3]],
                [-C[5],     0,  C[4]]])

for op in itertools.permutations(O):
    b = vector(ZZ, op)
    x = A.solve_right(b)
    print(x)

最后只用老老实实解密就行了：

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *

p, q, r = (9758621034843917661145412977193922808892309951663464821517963113005483457886774294910761723767526582514514505278091600074371768233672585649562672245905811, 8919642442779618620315315582249815126044061421894622037450496385178083791083142991676417756698881509754110765444929271564991855378540939292428839562446571, 6736304432663651651650099104581016800112378771266600017972326085742513966258250417227421932482058281545032658577816441378170466639375931780967727070265551)
e, d = (3, 73)

c = 80607532565510116966388633842290576008441185412513199071132245517888982730482694498575603226192340250444218146275844981580541820190393565327655055810841864715587561905777565790204415381897361016717820490400344469662479972681922265843907711283466105388820804099348169127917445858990935539611525002789966360469324052731259957798534960845391898385316664884009395500706952606508518095360995300436595374193777531503846662413864377535617876584843281151030183895735511854

N = e * d * p * q * r
phi = (e-1)*(d-1)*(p-1)*(q-1)*(r-1)

d = inverse(65537, phi)
m = pow(c, d, N)
print(long_to_bytes(m))

得到 flag 为：

1
CCTF{____Sylvester____tHE0r3m_Of_D3r!va7i0n!}

Barak

题目描述

题目在 $\mathbb{Z}/p\mathbb{Z}$ 上定义了一个曲线：

并定义该曲线上的加法运算：假设点为 $P_1(x_1, y_1)$ 和 $P_2(x_2, y_2)$，定义 $P_3 = P_1 + P_2$，且 $P_3(x_3, y_3)$：

  • 若 $P_1 = P_2$：
  • 若 $P_1 \ne P_2$：

在这条曲线上，有两个点：随机点 $P$ 和倍点 $Q = m P$ 已知，求未知倍数 $m$。

我的解答

首先尝试对这条曲线做一定的分析：把 $c$ 和 $d$ 设为比较小的值，然后随机弄一个曲线上的点不断乘倍数，求阶，发现如下性质：

  • 在分母为 0 的时候，求和运算会报错，因此猜测这条曲线上的零点应该是这时候的点（无法用 $(x, y)$ 表示出）
  • 如果 $P$ 为 $(x, y)$，那么 $-P$ 为 $(y, x)$

但是折腾了一番，并没有发现什么可以等价到椭圆曲线 Weierstrass 形式上的映射。等风哥哥提出可以作代换 $u = x+y, v = xy$，但是 $v^2$ 这一项出不来，而且这也不满足上面提到的第二个性质。

然后查了下 SageMath 的手册发现，和 Derik 类似，只需要用到 SageMath 中关于三次齐次方程的椭圆曲线构造法就行了：

https://doc.sagemath.org/html/en/reference/arithmetic_curves/sage/schemes/elliptic_curves/constructor.html#sage.schemes.elliptic_curves.constructor.EllipticCurve_from_cubic

不过我们这里只有一个二次的，需要再引入一个变量 $z$ 来把它变成齐次式：

当 $z=1$ 时即为原方程。

然后就通过映射，将原曲线中的点映射到椭圆曲线上，看了一下构造出来的椭圆曲线的阶是光滑的，所以直接求个离散对数就行了。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
p = 73997272456239171124655017039956026551127725934222347
c = 1
d = 68212800478915688445169020404812347140341674954375635


Zp = Zmod(p)
R.<xx,yy,zz> = Zp[]
cubic = xx^3 + yy^3 + c * zz^3 - d * xx * yy * zz
EC = EllipticCurve_from_cubic(cubic, morphism=False)
mf = EllipticCurve_from_cubic(cubic, morphism=True)

print(EC.order())
P = (71451574057642615329217496196104648829170714086074852, 69505051165402823276701818777271117086632959198597714)
Q = (40867727924496334272422180051448163594354522440089644, 56052452825146620306694006054673427761687498088402245)

PP = mf(P)
QQ = mf(Q)
dd = PP.discrete_log(QQ)
print(f'{PP.order() = }')

from Crypto.Util.number import *
print(dd)

不过要注意，直接把上面求得的 dd 作 long_to_bytes 会得到乱码，这是因为随机点 PP 不是椭圆曲线的生成元。所以我们还需要加上 PP 阶的倍数去枚举：

1
2
3
4
5
6
n = 1780694557271320552511299360138314441283923223949197
p = 73997272456239171124655017039956026551127725934222347
o = 3083219685676632130193959041477461850061047352503612
from Crypto.Util.number import *
for i in range(100):
    print(long_to_bytes(n + i * o))

得到 flag 为：

1
CCTF{_hE5S!4n_f0rM_0F_3CC!!}

学习一个：椭圆曲线的 Hessian 形式

https://en.wikipedia.org/wiki/Hessian_form_of_an_elliptic_curve

所以直接拿那个给出的形式代回 Weierstrass 形式也彳亍

Risk

题目描述

未知 $p, q, r, s, m$ 满足：

  • $m \ge 2$
  • $p, q$ 均为 1024 位素数
  • $p = a^m + r$
  • $q = b^m + s$
  • $r, s$ 均为 $m^2 - m + 2$ 位正整数

RSA 中，$N=pq$，$e=rs$，加密明文得到密文 $c$，试求明文。

我的解答

首先 $N = pq = (a^m+r)(b^m+s) = (ab)^m + r b^m + s a^m + rs > (ab)^m$

如果 $m \ge 3$，只要 $m$ 不是太大，那么 $(ab+1)^m = (ab)^m + m(ab)^{m-1} + 3m (ab) + 1$ 是能够大过 $N$ 的，所以此时对 $N$ 开 $m$ 次方根，就能得到 $ab$ 的值。

如果 $m=2$，虽然对 $N$ 开 $m$ 次方根不是 $ab$，但是也差得不远了。

但是我们还是需要知道具体的 $a$ 或者 $b$，还得对 $ab$ 的所有约数进行遍历，如果 $ab$ 难分解的话一下子就……（坠痛苦的）

另一个思路是枚举 $m$ 的同时，去枚举 $r$ 的值，通过 $p$ 是 $N$ 的约数，用 Coppersmith 方法求出 $p$。

而且我们有 $e=rs$ 也是已知的，那么我们就可以知道 $m$ 是多少，才能生成出 $e$ 来，并枚举 $r$ 的值。

题目中的 $e$ 是 28 位，$28 = 2 (m^2 - m + 2)$ 解得 $m=4$。

然后枚举 $e$ 的所有 14 位因子，发现就两个：

然后一开始想着是拿一个作为 $r$ 去跑 Coppersmith 方法，但是注意了：别看着这里的 $a$ 和 $b$ 是小的，但是它们的次数 $m$ 比较大；而 Coppersmith 方法所适用的 $x$ 所满足的条件是：

而这里 $\delta$ 就是 Coppersmith 中原本多项式的次数。好家伙，这一来一去，Coppersmith 了个寂寞，所以这里是不能用 small_roots 滴。

所以这个时候需要回看 $N$ 的表示式：因为 $ab$ 知道 $r$ 知道 $s$ 知道，所以可以关于 $a^m$ 和 $b^m$ 建立方程并解方程。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
pkey = (150953688, 373824666550208932851344358703053061405262438259996622188837935528607451817812480600479188884096072016823491996056842120586016323642383543231913508464973502962030059403443181467594283936168384790367731793997013711256520780338341018619858240958105689126133812557401122953030695509876185592917323138313818881164334490044163316692588337720342646339764174333821950301279825316497898035760524780198230860089280791887363472060435443944632303774987556026740232641561706904946900169858650106994947597642013168757868017723456208796677559254390940651802333382820063200360490892131573853635471525711894510477078934343423255983)
enc = 275574424285842306309073814038154403551700455145115884031072340378743712325975683329051874910297915882286569143815715537085387363420246497061870251520240399514896001311724695996978111559476733709139080970977190150345474341853495386364275702356438666152069791355990718058189043717952080875207858163490627801836274404446661613239167700736337269924479349700031535265765885064606399858172168036794462235707003475360358004643720927563261787867952228496769300443415094124132722170498229611285689671203272698693505808912907778910378274197503048226322090611405601517624884408718689404556983397217070272851442351897456769883

e, N = pkey

m = 4
r = 10728
s = 14071

ab = floor(N^(1/m))

PR.<x, y> = PolynomialRing(ZZ)

f1 = x * y - ab^m
f2 = (x + r) * (y + s) - N

# print(Ideal([f1, f2]).groebner_basis())

PR.<y> = PolynomialRing(ZZ)
f3 = 10728*y^2 - 511086150867555670991182215716996884365017094048011334498502864759458604412974525192545554902255616748785034586283311417267948637161905335789524940513213807388789747893057116518524986565352587286484213819873973314973576845522082944759362821020072842990178502502907835104629002180230922192278601476281549539304919*y + 5260086883027989894151266471310659627033447768756412470819138590823035454528439414529342666788115829348723355876515825478765835689971978836816254977610642160178724965865849006430519169265825342385264354073331979931090503900140796473000025308521505151693828876495191201072094916519467807477939653879213738285370121752035575512256453146199781476491291347483720934255498391686419228296642359873666276793532997868425427822887434754439647641247870006446823852067931010198965229083394533490439946570165059178219301430708237320778256595039419216917256059584687394490563748927035618459815041808985900104721604927460617006077696
print(f3.roots())

然后就能解得 $b^m$，也就求得 $q=b^m + s$……到这里还没完！

然后就是会发现 $p-1$ 和 $e$ 不互素，以及 $q-1$ 和 $e$ 不互素！所以还要套用一个开方+中国剩余定理解密。具体操作原理详见：

[*CTF 2021] Crypto - little case (x) - ZM.J 的文章 - 知乎
https://zhuanlan.zhihu.com/p/345235655

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
from Crypto.Util.number import *
import itertools

pkey = (150953688, 373824666550208932851344358703053061405262438259996622188837935528607451817812480600479188884096072016823491996056842120586016323642383543231913508464973502962030059403443181467594283936168384790367731793997013711256520780338341018619858240958105689126133812557401122953030695509876185592917323138313818881164334490044163316692588337720342646339764174333821950301279825316497898035760524780198230860089280791887363472060435443944632303774987556026740232641561706904946900169858650106994947597642013168757868017723456208796677559254390940651802333382820063200360490892131573853635471525711894510477078934343423255983)
enc = 275574424285842306309073814038154403551700455145115884031072340378743712325975683329051874910297915882286569143815715537085387363420246497061870251520240399514896001311724695996978111559476733709139080970977190150345474341853495386364275702356438666152069791355990718058189043717952080875207858163490627801836274404446661613239167700736337269924479349700031535265765885064606399858172168036794462235707003475360358004643720927563261787867952228496769300443415094124132722170498229611285689671203272698693505808912907778910378274197503048226322090611405601517624884408718689404556983397217070272851442351897456769883

e, N = pkey

m = 4
r = 10728
s = 14071

bm = 15040222622096320078383580808680733765955114958694997949647342925417877088612792495485641348591026281373930569798925789027166056695954731923306109646611840570310396750856642056018981080439916663195842593441587057719678555907050674529272376248049062724657792390788687452049496308886252188791975094655675924736
q = bm + s
p = N // q

def get_oneroot(p, e):
    while True:
        Zp = Zmod(p)
        g = Zp.random_element()
        g = g^((p-1) // e)
        for mult in divisors(e):
            if (mult != e):
                g2 = g^mult
                if (g2 == 1):
                    break
        else:
            return g

def decrypt(p, c, e):
    w = gcd(e, p-1)
    e1, p1 = e // w, (p-1) // w
    d = inverse_mod(e1, p1)
    c1 = pow(c, d, p)
    g, a, b = xgcd(p1, w)
    g = get_oneroot(p, w)
    m = pow(c1, b, p)
    return [ZZ(m * g^i) for i in range(w)]

mp_list = decrypt(p, enc, e)
print('Find root p OK')
mq_list = decrypt(q, enc, e)
print('Find root q OK')
for mp, mq in itertools.product(mp_list, mq_list):
    m = crt([mp, mq], [p, q])
    msg = long_to_bytes(int(m))
    if (b'CCTF' in msg):
        print(msg)

得到 flag 为：

1
CCTF{S!mP1E_A7t4cK_0n_SpEc1aL-5trucTur3D_RSA_pR1me5!}