2022GKCTF

Administrator

2023-04-22

Crypto

w_or_m?

hint: 好像是古典密码? 1、a variant&variant zigzag cipher

ez_classic(saved)

hint: 一起来学习密码学吧！(全小写，得到的flag包上SYC{}提交)

拿到题目可以发现是摩斯密码：-.. .-.. .-. --- .-- --- - .--. -.-- .-. -.-. --- .-.. .-.. . ....，解码并全小写可得：dlrowotpyrcolleh。提交显示并不正确，重新观察字符可以发现这是一句倒转过来的话：hellocryptoworld。

flag：SYC{hellocryptoworld}

definitely ez RSA(saved)

hint: 这是…似曾相识的感觉(e好像有一点不寻常?)

知道n,c,e且e十分的小便可以知道是低加密指数攻击中的 m^e^ > n 。上脚本：

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

c = 50072006338339389555118552154159240037219794211505206943873038914830972293138548550568229783754227896661905769853250134014183574039535969574789925550365619292404703617997980492432173682029840923107651199593049684918577536870537471401209938966780904496397505606866028917883152417396458811357069626629334483341
n = 147194403642833538539720995718314310463580322118979932658805936518215523735242613107271741138837389303135352865058107054820876285524238471152015504027014461168105771913435200522726300893493981125032256531337768716089003105857799620333243431585087621669813946444872568719527503184655024233193716871553607529747
e = 6

i = 0
while True:
    if iroot((c + i * n), e)[1]:
        m = iroot((c + i * n), e)[0]
        break
    i += 1

print(long_to_bytes(m))

# b'SYC{0ops_y0u_f1Nd_m3!}'

Pairs(saved)

hint: My twin brother send me a message.Can you decrypt it? 1、 Alice and Bob are twins of Hex

题目中提示了Twin-Hex Cypher，我们便可以使用在线工具直接解密。

flag：SYC{HAHAHA_Tw1n_H3x_Cypher}

StarterRSA(saved)

description: Start Modulo Cryptography!

hint: https://www.bilibili.com/video/BV1PW4y187iB/?spm_id_from=333.999.0.0

题目中给了n,c,e，其中n并不大可以直接分解，这就是一个简单的RSA。

flag：SYC{5t4rt_R5A_ls_1t_3a5y?}

Blind(saved)

hint: I'm blind

这道题与GKCTF2021RRRRsa十分相似，修改数据脚本都能直接套用，这里还是将推理过程写出来。

由题目可得\hfill\\ hint_1 = (2022*p_1+q_1)^{222222}\pmod{n_1}\hfill\\ hint_2 = (2023*p_1+232323)^{q_1}\pmod{n_1}\hfill\\ 化简hint_1(二项式定理 {\color{Red} (a+b)^n = C_n^0*a^n+C_n^1*a^{n-1}b+\cdots+C_n^k*a^{n-k}b^k+\cdots+C_n^n*b^n})\hfill\\ (2022*p_1+q_1)^{222222} \equiv (2022*p_1)^{222222}+\cdots+{q_1}^{222222} \pmod{n_1}\hfill\\ 故hint_1 \equiv 2022*{p_1}^{222222}+{q_1}^{222222}\pmod{n_1}\hfill\\ \qquad\quad\ \equiv 2022*{p_1}^{222222}\pmod{q_1*n_1}\hfill\\ \qquad\quad\ \equiv (2022*p_1)^{222222}+k_1*q_1 \pmod{n_1}①\hfill\\ 化简hint_2(费马小定理 {\color{Red} a^p\equiv a\pmod{p}})\hfill\\ hint_2 = (2023*p_1+232323)^{q_1}\pmod{n_1}\hfill\\ hint_2 = 2023*p_1+232323 \pmod{q_1*n_1}\hfill\\ hint_2 = 2023*p_1+232323+k_2*q_1 \pmod {n_1}\hfill\\ (hint_2 - 232323)^{222222} \equiv (2023*p_1+k_2*q_1)^{222222}\pmod {n_1}\hfill\\ (hint_2 - 232323)^{222222} \equiv (2023*p_1)^{222222}+(k_2*q_1)^{222222}\pmod {n_1}②\hfill\\ \quad②*2022^{222222}-①*2023^{222222}\hfill\\ =(2022*2023*p_1)^{222222}+k_4*q_1-((2022*2023*p_1)^{222222}+k_3*q_1)\pmod{n_1}\hfill\\ =(k_4-k_3)*q_1\pmod{n_1}\hfill\\ =t*q_1+k*n_1\hfill\\ =q_1*(t+k*q_1)\hfill\\ 故gcd(q_1*(t+k*q_1),n1)=q_1\hfill\\ 从而p_1=n_1//q_1\hfill\\ 从而能计算d_2，最终得p\hfill\\\\ 由题目可得\hfill\\ hint_3 = (2022*p_2+2023*q_2)^{222222}\pmod{n_2}\hfill\\ hint_4 = (2023*p_2+2022*q-2)^{232323}\pmod{n_2}\hfill\\ 化简hint_3和hint_4(二项式定理)\hfill\\ hint_3=(2022*p_2)^{222222}+(2023*q_2)^{222222}\pmod{n_2}\hfill\\ hint_4=(2023*p_2)^{232323}+(2022*q_2)^{232323}\pmod{n_2}\hfill\\ (2023^{222222}*hint_3)^{232323}=(2022*2023*p_2)^{{222222}*{232323}}+(2023^2*q_2)^{{222222}*{232323}}\pmod{n_2}①\hfill\\ (2022^{232323}*hint_4)^{222222}=(2022*2023*p_2)^{{222222}*{232323}}+(2022^2*q_2)^{{222222}*{232323}}\pmod{n_2}②\hfill\\ \quad②-①\hfilll\\ =k_1*q_2^{{222222}*{232323}}\pmod{n_2}\hfilll\\ =k_1*q_2^{{222222}*{232323}}+k_2*n_2\hfilll\\ 故q_2=gcd(②-①,n_2)\hfill\\ 得到q_2，则p_2=n_2//q_2\hfill\\ 从而能计算d_2，最终得q\hfill

脚本：

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

c = 
n1 = 
c1 = 
hint1 = 
hint2 = 
n2 = 
c2 = 
hint3 = 
hint4 = 
e = 

# 求p
x1 = (hint1 * pow(2023, 222222, n1)) % n1
x2 = (pow((hint2 - 232323), 222222, n1) * pow(2022, 222222, n1)) % n1
q1 = gcd(x2 - x1, n1)
p1 = n1 // q1
d1 = invert(e, (p1 - 1) * (q1 - 1))
p = pow(c1, d1, n1)

# 求q
x3 = pow(hint3 * pow(2023, 222222, n2), 232323, n2) % n2
x4 = pow(hint4 * pow(2022, 232323, n2), 222222, n2) % n2
q2 = gcd(x4 - x3, n2)
p2 = n2 // q2
d2 = invert(e, (p2 - 1) * (q2 - 1))
q = pow(c2, d2, n2)

# 得到flag
n = p * q
d = invert(e, (p - 1) * (q - 1))
m = pow(c, d, n)
print(long_to_bytes(m))

# b'The_key_I_am_white_Please_continue_decryting'

题中还有一个flag.txt，有密文还给了密钥推测是维吉尼亚密码，经过尝试密钥是Iamwhite，解密后得到flag：syc{2id_y0u_r3a11y_4ind_the_right_an5wer}

link_start(saved)

hint: 害羞的小彭有着非常喜欢的一句话，但他又害怕别人知道。你能帮我找到这句话吗

题中c1 = pow(m + pad1, e, n)，c2 = pow(m + pad2, e, n)指明了FranklinReiter attack，虽然有一点小小的不同。

#sage
from Crypto.Util.number import long_to_bytes

def franklinReiter(n,e,r,c1,c2):
    R.<X> = Zmod(n)[]
    f1 = X^e - c1
    f2 = (X + r)^e - c2

    return Integer(n-(compositeModulusGCD(f1,f2)).coefficients()[0])

def compositeModulusGCD(a, b):
    if(b == 0):
        return a.monic()
    else:
        return compositeModulusGCD(b, a % b)

def FranklinReiter():
    c1 = 3720637940274958886432460233359341402765303073408436397771852426914390218432084755791424796944302399361378059153348441733368574505589165431342734218087692
    c2 = 1857483070190148986251195374434228339562792548542508665250465210130431058280559201968992393617573644598954953409645690993451979549050973992242158354491780
    n = 5106069782765072129956779902712742815006764735937158686628819801242945179548793829832666946413859309545558089370129318039174135569850663668730057188261837
    pad1 = 105932791230388043786415766547423404991945041940365436758701967602353965252168
    pad2 = 927899423531845853332048235055407925992275378422616390929
    e = 3
    recoveredM = franklinReiter(n,e,pad1-pad2,c2,c1)
    print(recoveredM)
    print(long_to_bytes(recoveredM-pad2))
    return True

FranklinReiter()

# b'SYC{1_c4n_d0_th15_a1l_d@y}'

Long_But_Short(saved)

hint: Find the shortcut!

由二项式定理可将加密式展开：

(f+p)^q=C_q^0f^qp^0+C_q^1f^{q-1}p^1+\cdots+C_q^qf^0p^q

可以看到除了第一项不含p外，其余各项都含有p及p的乘方。根据同余式的结合律，后面的项摸p均为0.故原式等于

f^q\equiv a\pmod p

又由费马小定理：f^p-1^ ≡ 1 (mod p),原始还可以化简为

f^q\equiv f^2*f^{q-2}\pmod p\\ \quad\ \equiv f^2*f^{p-1}\pmod p\\ \equiv f^2\pmod p

根据条件f^2^ < p,直接对a开方就是flag了。

#sage
from Crypto.Util.number import *
from math import *

a = 1718205151527213531940354061216609955728503626623437131525315244599535856595391286686273033612529023037466615611832668265075325829196053041494716601943531710744433426780718569225

print(long_to_bytes(isqrt(a)))

#SYC{7ca905c9dbba1ffe7ff0ee3ee93f1ac1}

just lcg(saved)

description: nc 124.71.215.231 2223

hint: 只要一直前进，道路就会延伸

观察题目可以知道是要我们使用python连接远程主机(不用python连接也可以但1000次有点多)，通过 $b = (a * k + c) \% n$ 计算出c1000次便可得到flag。

b \equiv a * k + c \pmod n\\ c \equiv b - a * k \pmod n

from pwn import *
from base64 import *

connect = remote(url, port)
k = 2753645094
n = 17968909282851700307

for i in range(1000):
    info = connect.recvuntil(b'[+] b = (a * k + c) % n')
    a = info[info.find(b'a = ') + 4:info.find(b'\n[+] b')]
    b = info[info.find(b'b = ') + 4:info.find(b'\n[+] b = (a * k + c) % n')]
    c = (int(b) - int(a) * k) % n
    connect.sendafter(b'[+] c = ', str(c).encode())
    print(str(i)+connect.recvline().decode(),end='')

print(b64decode(connect.recvline().decode()[len('the encflag is = b'):-1]))

#b'SYC{1000_LCG_@nd_y0u_kn0w_3he_f1@g}'

Anime picture(saved)

hint: 呐，米娜桑，一起来感受二次元的美好吧！

题目中有

assert a * x + b * y == gmpy2.gcd(a, b)
'''
a = 12071216147395236101
b = 12613118707743158458
'''

题目中给了拓展欧几里得的 $a$ 和 $b$ 我们直接再一次拓展欧几里得得到 $x$ 和 $y$ ，带入题目中的py文件直接的到下面的图片，虽然画质不高但flag已经出来了。

Crypto1957(saved)

hint: 敌国研制了一种新型导弹，请破解情报并获取私钥。

Many-Time-Pad-Atta

import Crypto.Util.strxor as xo
import libnum, codecs, numpy as np

def isChr(x):
    if ord('a') <= x and x <= ord('z'): return True
    if ord('A') <= x and x <= ord('Z'): return True
    return False

def infer(index, pos):
    if msg[index, pos] != 0:
        return
    msg[index, pos] = ord(' ')
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(' ')

def know(index, pos, ch):
    msg[index, pos] = ord(ch)
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(ch)

dat = []

def getSpace():
    for index, x in enumerate(c):
        res = [xo.strxor(x, y) for y in c if x != y]
        f = lambda pos: len(list(filter(isChr, [s[pos] for s in res])))
        cnt = [f(pos) for pos in range(len(x))]
        for pos in range(len(x)):
            dat.append((f(pos), index, pos))

c = [codecs.decode(x.strip().encode(), 'hex') for x in open(r'cipher.txt', 'r').readlines()]

msg = np.zeros([len(c), len(c[0])], dtype=int)

getSpace()

dat = sorted(dat)[::-1]
for w, index, pos in dat:
    infer(index, pos)

know(10, 21, 'y')
know(8, 14, 'n')

print('\n'.join([''.join([chr(c) for c in x]) for x in msg]))

key = xo.strxor(c[0], ''.join([chr(c) for c in msg[0]]).encode())
print(key)

#b'SYC{A1m9_1nfr4k3d_gui=4nc3}'

Crypto20xx(saved)

hint: Next generation RSA but something is wrong.

题目中给了公钥，只是最开始的时候少了两个字母无法在线破解，看c的大小毛估计缺少的部分没什么用，就补两个0上去。然后转为der格式。

der：
302d340d06092a864886f70d0101010500031b00301802110083b8e381522455c17ffc8337aec87023
0203 # e
06699d

e虽然很好分离出来但不知道n的具体大小所以无法分离N，但根据做题经验N和c的数量级相同除非出题人有意设计过。我们将c转为hex发现是32个字符长度，于是从0203往回退32个字符长度便可以得到N，事实上也确实是这样。

der：
302d340d06092a864886f70d0101010500031b003018
0211 # N
0083b8e381522455c17ffc8337aec87023
0203 # e
06699d

解题脚本：

from Crypto.Util.number import *
from base64 import *

x = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'

der2 = 'MC00DQYJKoZIhvcNAQEBBQADGwAwGAIRAIO444FSJFXBf/yDN67IcCMCAwZpnQ=='
der2 = hex(bytes_to_long(b64decode(der2)))
print(der2[2:])
print(0x83b8e381522455c17ffc8337aec87023)
# 175088864422629078008785584658147995683
e = 0x6699d
p = 12865536769562115787
q = 13609137928614252809
n = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
c = 85806005072257465677925369913039323947
print(long_to_bytes(pow(c, d, n)))

# b'Panzer_Vor!'
# SYC{Panzer_Vor!}

Crypto1976

description: nc 124.71.215.231 1145

hint: 突破敌人的敌我识别系统，获取军事基地坐标

Crypto1985

hint: 坎大哈风沙漫天，对加密通信造成干扰。 Learning with error, also known as LWE.