20210920-CTFSHOW月饼杯-CryptoSecWriteUp

Posted on 2021-10-09 Edited on 2022-10-17 In CTF-Crypto , WriteUp Views: Symbols count in article: 12k Reading time ≈ 11 mins.

我的木头啊！！！

MTJJ！（bushi

我的宝贝木头怎么被别人拿去做了栅栏，该怎么让他把我的宝贝木头换回来

c6_I_@t216MG_0q_Uf673JTYYzBXs{31QJmTTg=hw63XZFZiHho5GzE}

W型栅栏 6

ctfshow{626173653136_MJQXGZJTGI_YmFzZTY0_qzTiEHgB_@UX=h}

ctfshow{base16_base32_base64_base58_base}

切记务必一定要简单

考点

费马分解

在分解模数N的时候，除了yafu、factorDB之类现成的工具，我们还要学习一些经典算法背后的思想

from Crypto.Util.number import *
import random, sys

def get_prime(base, offset):
    l = base - (1 << offset)
    r = base + (1 << offset)
    p = random.randrange(l, r) | 1
    while (not isPrime(p)):
        p += 2
    return p

if __name__ == "__main__":
    p = getPrime(1127)
    q0 = p * 13 // 17
    q = get_prime(q0, 573) # Konami
    with open('flag.txt', 'rb') as f:
        flag = bytes_to_long(f.read())
    N = p * q
    assert isPrime(p) and isPrime(q) and flag < N
    e = 0x10001
    c = pow(flag, e, N)
    print(f"N = {N}")
    print(f"e = {e}")
    print(f"c = {c}")

1
2
3

N = 2537578464060405716805986209629349306801585799475566769629753550869939275098596985321844853409568013133264210149682740766024366488982429837531169509250859483526118776072099712258599263748732430570800661306460224380741403478451009927665855604092871949705081574682507168392533782265954982321389235080917435497979848348321877319477780053855288297818739223795823021264136388271573286209636548206594797813576810688640228747147522219625866870777713858310084857747151891233766790129427051420839675334815589489194938107230004427317376438129284740257550482956744843496127593401991789197386269415091390162278183972481279010769071314265529328954115911712467352483233380953386631332500882467
e = 65537
c = 1595212140002311449986774328911538131302021292459414446518934463751924694901681197719356391632660947700772362140375795419149621042035212501260054901239960931458611414432758551692762707025705203714868544808208482382713403084945106505851948109261999900909705955010772382362799626266428855540493176898287751627555377040483120618564113186968911259319525250268854097054159722810266326281435235140862840574780793343440289233893489065111751815693510473980454574606688640074455096644717769189843656600438932454630073349737743755427817726253307163184245099133341515200474243399626081459226215410055396366269535409932990065250476999485239927630147382130648035686165068584532121265385100009

p是1127位的素数，q与p有关，是$[\lfloor13p/17\rfloor-2^{573},\ \lfloor13p/17\rfloor+2^{573}]$中的一个质数

参考模数相关攻击-|p-q|较小

首先对于RSA里的模数N，显然可以写成$N=pq=(\frac{p+q}{2})^2-(\frac{p-q}{2})^2$，当然别的素合数也可以这样拆解

如果p和q很接近，$(\frac{p-q}{2})^2$肯定很小，变换一下上面的等式
$$
(\frac{p+q}{2})^2-N=(\frac{p-q}{2})^2\notag
$$
我们枚举$a,\ a=\frac{p+q}{2}$，可以从$\sqrt{N}$开始（我的理解是要看p和q具体差多少，$\sqrt{N}$只是幌子），如果$|N-a^2|$是完全平方数，说明我们找到了，之后就是解个方程的事

但是这里略有不同，娇小的不是|p-q|，而是
$$
|13p-17q|\notag
$$
先照搬照抄费马分解的
$$
(\frac{13p+17q}{2})^2-13\times 17N=(\frac{13p-17q}{2})^2\notag
$$
把N乘以一个221，就和费马分级完全一样了，写两个脚本

这是一般的费马

from Crypto.Util.number import *
from gmpy2 import *
from sympy import *

P = getPrime(512)
Q = next_prime(P)
N = P * Q
a = iroot(N, 2)[0]
while True:
    if iroot(abs(a ** 2 - N), 2)[1]:
        x = iroot(abs(a ** 2 - N), 2)[0]
        p = symbols('p')
        q = symbols('q')
        ans = solve([p * q - N, p - q - 2 * x], [p, q])[0]
        p = abs(ans[0])
        q = abs(ans[1])
        print(p, q)
        break
    a += 1

稍微改一下

#!/usr/bin/env sage
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
from gmpy2 import *
from sympy import *

N = 2537578464060405716805986209629349306801585799475566769629753550869939275098596985321844853409568013133264210149682740766024366488982429837531169509250859483526118776072099712258599263748732430570800661306460224380741403478451009927665855604092871949705081574682507168392533782265954982321389235080917435497979848348321877319477780053855288297818739223795823021264136388271573286209636548206594797813576810688640228747147522219625866870777713858310084857747151891233766790129427051420839675334815589489194938107230004427317376438129284740257550482956744843496127593401991789197386269415091390162278183972481279010769071314265529328954115911712467352483233380953386631332500882467
e = 65537
c = 1595212140002311449986774328911538131302021292459414446518934463751924694901681197719356391632660947700772362140375795419149621042035212501260054901239960931458611414432758551692762707025705203714868544808208482382713403084945106505851948109261999900909705955010772382362799626266428855540493176898287751627555377040483120618564113186968911259319525250268854097054159722810266326281435235140862840574780793343440289233893489065111751815693510473980454574606688640074455096644717769189843656600438932454630073349737743755427817726253307163184245099133341515200474243399626081459226215410055396366269535409932990065250476999485239927630147382130648035686165068584532121265385100009

N = 221 * N
a = iroot(N, 2)[0]
while True:
    if iroot(abs(a ** 2 - N), 2)[1]:
        x = iroot(abs(a ** 2 - N), 2)[0]
        p = symbols('p')
        q = symbols('q')
        ans = solve([221 * p * q - N, 13 * p - 17 * q - 2 * x], [p, q])[0]
        p = int(abs(ans[0]))
        q = int(abs(ans[1]))
        assert p * q == N // 221
        print(long_to_bytes(pow(c, int(invert(e, (p-1)*(q-1))), N // 221)))
        break
    a += 1

一封信

有一天，小明收到了一封名为mooncake的信，你可以帮他破解吗？

馃檭馃挼馃尶馃帳馃毆馃審馃悗馃馃毇馃槅鉁咅煈夝煍勷煄ゐ煈屸尐馃憫馃巺馃槏馃崕馃毇鈽傪煒€馃榾馃悩馃悕馃檭馃ぃ鈽€馃崕馃敩鈽傪煡嬸煄堭煃庰煒傪煃岎煇庰煂婐煍勷煄咅煔煂忦煈岎煄凁煍煒○煈ｐ煔煃答煔梆煢擆煏桂煒嗮煈夆劰鈴┾湁馃洨馃寜馃搨馃尶馃攧馃榾馃崒馃尶馃槑鈴煠ｐ煒傪煃庰煆庰煍勨尐馃尶鉁夆尐馃檭鈽凁煃庘槂馃毇馃崓馃槀馃槀鈱煑掟煑�

直接搜索无果，而且会出来一堆乱七八糟的东西；然后想到昨天的长城杯，虽然没意思，但有时候思路很重要，我觉得应该不会有个加密的结果是这样的，这可能是乱码，所以utf-8编码试了试，得到

🙃💵🌿🎤🚪🌏🐎🥋🚫😆✅👉🔄🎤👌⌨👑🎅😍🍎🚫☂😀😀🐘🐍🙃🤣☀🍎🔬☂🥋🎈🍎😂🍌🐎🌊🔄🎅🚫🌏👌🎃🔬😡👣🚪🍴🚰🦓🕹😆👉ℹ⏩✉🛩🌉📂🌿🔄😀🍌🌿😎⏩🤣😂🍎🏎🔄⌨🌿✉⌨🙃☃🍎☃🚫🍍😂😂⌨🗒🗒

emoji编码，但只知道base100编码是不对滴，参考2021 NewsCTF 新春赛-EMOJI，说是aes emoji，需要key，结合hint中有mooncake

沐沐子倒拔垂杨柳

沐沐子相了一相，走到树前，把直掇脱了，用右手向下，把身倒缴着；却把左手拔住上截，把腰只一趁，将那株绿杨树带根拔起。

众菜鸡见了，一齐拜倒在地，只叫：”沐沐子非是凡人，正是真汉子！身体无千万斤气力，如何拔得起！”

1	cipher = AES.new(self.willow, AES.MODE_CBC, iv=self.willow)

参考Yusa的密码学课堂—CBC第三课

flag总共有三段，change是选择哪一段密文，Shake是加密，Kick是解密，密文明文由我们send，加密解密的key和iv都来自flag，主要的流程是

def handle(self):

    self.send(banner)
    self.willow = self.select_level()

    while True:
        self.send("1: Shake the willow")
        self.send("2: Kick the willow")
        self.send("3: Change a willow")
        self.send("4: Give up")
        choice = self.receive().decode()
        if choice == "1":
            self.shake_willow()
        elif choice == "2":
            self.kick_willow()
        elif choice == "3":
            self.willow = self.select_level()
        elif choice == "4":
            self.send("886!")
            return

key和iv是相同的，只要一次解密和一次加密就可以得到一段flag

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from pwn import *

BLOCK_SIZE = 16
port = 28083

context.log_level = 'debug'
sh = remote('pwn.challenge.ctf.show', port)

plaintext = b'\x00' * 32


def attack(tip):
    sh.recvuntil(b'>')
    sh.sendline(tip)
    sh.recvuntil(b'>')
    sh.sendline(b'1')
    sh.recvuntil(b'>')
    sh.sendline(plaintext.hex())
    sh.recvline()
    cipher = bytes.fromhex(sh.recvline()[:-1].decode())
    c3, c4 = cipher[:16], cipher[16:32]
    sh.recvuntil(b'>')
    sh.sendline(b'2')
    sh.recvuntil(b'>')
    sh.sendline(c4.hex())
    sh.recvline()
    res = bytes.fromhex(sh.recvline()[:-1].decode())
    key = xor(res, c3)
    sh.recvuntil(b'>')
    sh.sendline(b'3')
    return key


flag = ''
for i in range(3):
    flag += attack(str(i).encode()).decode()
print(flag)

最关键的代码

def verify_token(username, r, s, y):
    u = bytes_to_long(username) & MASK
    # No cheating
    if any([x <= 0 or x >= p - 1 for x in (u, r, s)]):
        return False
    return pow(g, u, p) == (pow(y, r, p) * pow(r, s, p)) % p

也就是要满足
$$
g^u\equiv_py^r\cdot r^s
$$
其中

$p$
$g=7$
$y=g^x\ (mod\ p)$

$u$由我们指定，至少包含一个题目中提供的花名，$r$和$s$产生自以下函数，也就是题目提示丢失的私钥

def generate_token(username, x):
    while True:
        u = bytes_to_long(username) & MASK
        k = randint(2, p - 2)
        if GCD(k, p - 1) != 1:
            continue
        r = pow(g, k, p)
        s = (u - x * r) * inverse(k, p - 1) % (p - 1)
        if s == 0:
            continue
        return (r, s)

即$r=g^k\ (mod\ p)$

$s=(u-x\cdot r)\cdot k^{-1}\ mod\ (p-1)$

该密码系统基于DLP

思路1

要让$g^u\equiv_py^r\cdot r^s$成立，$r$和$s$都是由我们指定的，如果让$r=g^iy^j$，代入$(1)$，则
$$
g^u\equiv_py^{g^iy^j}g^{si}y^{sj}\notag
$$
显然，如果要让$u\equiv_{p-1}si$成立

只要满足
$$
1\equiv_{p}y^ry^{sj}\notag
$$
那么只要
$$
y\equiv_{p-1}sj\notag
$$
（why

之后就可以通过计算随机数$i$和$j$，算出$r$和$s$还有$u$，就可以拿去伪造了

此外，$u$必须包含一个花名

1 2	def check_login(username): return any([mem in username for mem in CTFSHOW_MEMBERS])

比如就ZM.J@CTFshow，放在前面，后1024才是我们真正的$u$

思路2

二次剩余，

如果$a$是$p$的二次剩余，那么$(\frac{a}{p})=1$

如果$a$不是$p$的二次剩余，那么$(\frac{a}{p})=-1$
欧拉准则

$a^\frac{p-1}{2}\equiv_p(\frac{a}{p})$

回到$g^u\equiv_py^rg^s$，比较自然的想法，每个变量之间有这样或那样的联系，很烦；但既然要同余式两边相同，就会想如果可以变成1就好了

所以首先想到是让$u$的低1024位和$r$还有$s$等于$p-1$，由费马小定理易解

但是有限制条件

1 2	if any([x <= 0 or x >= p - 1 for x in (u, r, s)]): return False

最大也就是$p-2$；进而想到的二次剩余和欧拉准则

$a^{p-1}\ mod\ p$太大不行，那么我们求个二次剩余，也就是让$u=r=s=\frac{p-1}{2}$，这样既符合了条件，结果也只能是1或-1

最后注意下输入输出

username = input('username (in hex): ')
username = bytes.fromhex(username)
r = int(input('r (in hex): '), 16)
s = int(input('s (in hex): '), 16)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from pwn import *
from Crypto.Util.number import *
from re import *

# context.log_level = 'debug'
while True:
    u = bytes_to_long(b'ZM.J@CTFshow') << 1024
    sh = remote('pwn.challenge.ctf.show', 28066)
    content = sh.recvuntil(b'username (in hex):').decode()
    p, y = findall(r"\d+", content)
    p, y = int(p), int(y)
    u, r, s = long_to_bytes(u + (p - 1) // 2), (p - 1) // 2, (p - 1) // 2
    sh.sendline(u.hex())
    sh.recvuntil(b'r (in hex):')
    sh.sendline(hex(r))
    sh.recvuntil(b's (in hex):')
    sh.sendline(hex(s))
    flag = sh.recvline()
    if b'ctfshow' in flag:
        print(flag)
        break

张八炫CTFshow三结义

考点

Gröbner基

from Crypto.Util.number import *
from secret import zang, ba88, xuan, p, q, e

# F91 is my wife forever
assert isPrime(e) and (e < 91)

N = p*q
ps = list(map(bytes_to_long, (zang, ba88, xuan)))
cs = [pow(i,e,N) for i in ps]
s = sum(ps) # UNITE
print(f"N = {N}")
print(f"cs = {cs}")
print(f"s = {s}")

hint

此题可能需要一定的算力以及耐心。

如果你觉得当前容器所给出的问题太难解出，不妨重开一个容器。

已知明文之和、所有的密文，即
$$
\begin{cases}
m_1^e\equiv c_1\ (mod\ N)\\
m_2^e\equiv c_2\ (mod\ N)\\
m_3^e\equiv c_3\ (mod\ N)\\
s=m_1+m_2+m_3
\end{cases}
\notag
$$
e很小，但N和c位数接近，满足条件的e如下

1	e = [17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89]

理想

对于一个多项式集合$F=f_1,\cdots,f_k$，其生成的理想为集合元素的线性组合，la佬的latex在我这里显示有点问题，应该是这样
$$
\langle f_1,\cdots,f_k \rangle=\bigg({ \sum\limits_{i=1}^k g_if_i \vert g_1,\cdots,g_k \in K[x_1,\cdots,x_n] \bigg)}\notag
$$
其中$R=K[x_1,\cdots,x_n]$是在域$K$上的多项式环，g是多项式环中的一个多项式，x是多项式g的系数，是属于有限域$K$上的，也就是说f的系数是多项式，而由f组成的线性组合就是理想

什么是多项式环，我先理解成系数在$[0,\ R]$上的多项式集合吧，那域$K$就是$Z_K^*$

$x_i$是数
$g_i$是系数为$x_i$的多项式
$f_i$是系数为多项式$g_i$的多项式

Gröbner基

Gröbner基就是单项式序下的多项式环$K[x_1,\cdots,x_n]$，其理想$I$满足一定条件的有限生成集$G=g_1,g_2,_\cdots,g_t$

已知理想求Gröbner基，其实可以看做解多元多次的方程组

定义三元多项式

1	P.<x, y, z> = PolynomialRing(Zmod(N))

构造理想

1	G = [x+y+z-s, x^e-cs[0], y^e-cs[1], z^e-cs[2]]

然后调用sage封装的函数

1	B = Ideal(G).groebner_basis()

求出来的Gröbner基是一元的，也就是$x+x_0,\ y+y_0,\ z+z_0$，他们都等于N

得到

[x + 
26662827782051464615976567684752925677467881725332575738209359733512862160799560732998203503511148730687717124305275025073641447585135831097416975699029611753775395118044337114687461451203396381780284280332279054412946883024040851932234340654069479840307590336431065451668520879110676315718029797292361072793366910857300705975725867933068706498317130739553540485217415514125547447045647449411275827867898811663393269578679727735421639780469843184306978152618597198612892115614024042436618084049774644761224850091459122581613735095060947960942929699069451075614514322230810345965639861985343385928596524291866515457506,
y + 
26662827782051464615976567684752925677467881725332575738209359733512862160799560732998203503511148730687717124305275025073641447585135831097416975699029611753775395118044337114687461451203396381780284280332279054412946883024040851932234340654069479840307590336431065451668520879110676315718029797292361072793366910857300705975725867933068706498317130739553540485217415514125547447045647449411275827867898811663393269578679727735421639780469843184306978152618597198612892115614024042436618084049774644761224850091459122581613735095060947960942929699069451075614514322230810345965639868618012628867112994837267731290388,
z +
 26662827782051464615976567684752925677467881725332575738209359733512862160799560732998203503511148730687717124305275025073641447585135831097416975699029611753775395118044337114687461451203396381780284280332279054412946883024040851932234340654069479840307590336431065451668520879110676315718029797292361072793366910857300705975725867933068706498317130739553540485217415514125547447045647449411275827867898811663393269578679727735421639780469843184306978152618597198612892115614024042436618084049774644761224850091459122581613735095060947960942929699069451075614514322230810345965509879226494955760912958428560544399675]

然后N减去后面这个数字，转字节

Reference

ZM.J-[CTF秀] CTFshow 第二届月饼杯 Crypto部分个人writeup