NSSCTF Round11

最后 rank 排第 4，差一道 AK，可惜。

ez_enc

题目描述说了不是培根加密，所以考虑 AB 为二进制情况，192 位数判断，8 位为一组，简单写个脚本跑就行。NSSCTF{mS4gT1Kv9L8NjPzx}

MyMessage(2🩸)

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
import os

flag = os.getenv('FLAG')

e = 127

def sign():
    msg = input("Input message：")
    p = getPrime(512)
    q = getPrime(512)
    n = p*q
    c = pow(bytes_to_long((msg + flag).encode()), e, n)
    print(f"n: {n}")
    print(f"Token: {hex(c)}")

def main():
    while True:
        sign()

main()

题解

分析一下发现是 CRT，e 是 127，不算很大，pwntools 远程连一下就出了，用 127 组 n、c 就能出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2
from sympy.ntheory.modular import crt
from Crypto.Util.number import long_to_bytes
from pwn import *
r=remote("node1.anna.nssctf.cn",'28993')
r.recv()
n=[]
c=[]
for i in range(127):
    r.send(b'\n')

    n0=int(r.recvline()[3:])
    n.append(n0)
    c0=int(r.recvline()[7:],16)
    c.append(c0)
    r.recv()
    print(i)

e=127
resultant,mod= crt(n, c)
print(gmpy2.iroot(resultant, e))
print(long_to_bytes(2806865643354785603324943800380811808524058654491089619946085108629974212427336755928938684569729653368445))

MyGame(3🩸)

题目

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
from Crypto.Util.number import *
import os
import random
import string

flag = os.getenv('FLAG')

def menu():
    print('''=---menu---=
1. Guess
2. Encrypt
''')

p = getPrime(512)
q = getPrime(512)
n = p*q

def randommsg():
    return ''.join(random.choices(string.ascii_lowercase+string.digits, k=30))

mymsg = randommsg()
def guess():
    global mymsg
    msg = input()

    if msg == mymsg:
        print(flag)
    else:
        print(mymsg)
        mymsg = randommsg()

def encrypt():
    e = random.getrandbits(8)
    c = pow(bytes_to_long(mymsg.encode()), e, n)
    print(f'Cipher_{e}: {c}')

def main():
    print(f'n: {n}')
    while True:
        opt = int(input())

        if opt == 1:
            guess()
        elif opt == 2:
            encrypt()

main()

题解

仔细读代码，发现是共模攻击，找两组 c、e 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
from Crypto.Util.number import long_to_bytes
c1=20432531576155215888154008856470023176716331725918571318249616529204088736445989550189654688043730733020564485947864747196975750100435327664656429806649525534120919148246123023379811466301511729993913961801030758822865877036889575149918981442195476030813460030620757387049663845188034750154180593983566582520
e1=27
c2=49343226468934676124103999715864898108289119770186347123043696311071406231664645680952259061776732950065396078048353154283241280855775618011869819311337805185923169181212309315036973967627008736733179896379120366510464553630612190775773048857991437285631208686684892260979310870861832511307571472115286628517
e2=20

n=120132192877694910217679507021165646332695827464809117195210649277384674795669034856718931569263574670286802451973300796012519337781757661938081109028300520380652830599013093103694871345527473374707911919217651889156901714534844579748040213772147486709217128429189246896619833922990939367369152675847389673607

r,s1,s2=gmpy2.gcdext(e1,e2)
m=(pow(c1,s1,n) * pow(c2,s2,n)) %n
print(long_to_bytes(m))

ez_signin(3🩸)

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from secret import flag

p = getPrime(512)
q = getPrime(512)
assert p > q
n = p*q
e = 65536
m = bytes_to_long(flag)
num1 = (pow(p,e,n)-pow(q,e,n)) % n
num2 = pow(p-q,e,n)
c = pow(m,e,n)

print("num1=",num1)
print("num2=",num2)
print("n=",n)
print("c=",c)

题解

从 num1 和 num2 入手进行推导，这种类似推导在seccon中的pqpq也遇到过，遇到 p 和 q 和与差的次方时要善于展开。 \[num1=p^e - q^e \; mod \;n\] \[num2=(p-q)^e \; mod \;n=p^e + q^e \;mod\;n\] \[num1-num2=2q^e \;mod\;n\] 与 n 求 gcd 即可得到 q。后续又发现gcd(e,phi)=4 我直接用phi//4就出了，但看别的师傅题解是使用了 16 次 rabin。App1e_Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
import gmpy2
e=65536

num1= 77257223159958079981390137355142080015023010733827990250504328622199243866334208454700846525239387121424870112593354883264915110401096320266418705582162604997618363889158629900108704858615247007992567853124974343579594813658250285927213124866151010168331988825030114602867745638435653619050902109851045530048
num2= 8670006639226140401848502013409874417778806171787684181700490726088123676562019413771703217181880276367622310216897452417434923879832976569809207272273038152452280440576111149210141624539176252808510923727718037881253248639329799746808602221142415191253040793180318625834835539461350068653267738595818142033
n= 139312918646958911643614106477250346542938203733216645101706250934506039430465265284553776989331472694107269641055499427941102923536860105801322441769366401061519774361630724222802972762597316259472094210197432833307534335146157789503227756546698356309143161714893413713163015318965716763931005983883676146349
c= 117425520472164947185011060551908800156070555958546948883959815215678093994397105451763661641181472902919466937760258731806408698523865490809605237116064587181672662857632969568595375221472415619173606876351479605389472618536640276793037520925913907146004116095678083180079715242304920764573160813391671768563
q=GCD(n,num1-num2)
p=n//q
phi=(p-1)*(q-1)
print(GCD(phi,e))
d=gmpy2.invert(e,phi//4)
print(long_to_bytes(pow(c,d,n)))

NTR(4❄️)

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import gmpy2
from flag import flag
from Crypto.Util.number import *

def init():
    p = getPrime(2048)
    while True:
        x = getRandomNBitInteger(1024)
        y = getPrime(768)
        z = gmpy2.invert(x, p) * y % p
        return (p, x, y, z)

def encrypt(cipher, p, z):
    message = bytes_to_long(cipher)
    r = getRandomNBitInteger(1024)
    c = (r * z + message) % p
    return c

p, x, y, z = init()
c = encrypt(flag, p, z)
with open("cipher.txt", "w") as f:
    f.write("binz = " + str(bin(z)) + "\n")
    f.write("binp = " + str(bin(p)) + "\n")
    f.write("binc = " + str(bin(c)) + "\n")

题解

基础 NTRU 格密码，具体推导可看前几篇博客 DUTCTF 的 ez_RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
from Crypto.Util.number import *
z=0b10101100101100011011110010110100101000101001111100110011110110010001000011100001001001111000111110000010010010111110001011111100111101010111001100100111100100111001011011110010100010100010110111101101011101111111110010000000010110011010011110000011000001111110001110111111001100001100101001010101100011100001101001101011011101110001000111001010111111110000010111100111011010011001111100111111101000010111111011010100110111000001011000001111010100000000101010110000100000111000000010001101110001101000111001010111111101100111110000011001110100011100011101000101111010111000111100010001101001101100000111010110100000001101100010001000011111100111110001010000010110110110010001110010100000000101111101100010000111011011101111110100001000011001101001110110011110000110011100010010011010011001110100010110001011110100100101110101001000011100100100000001001011010011001110001000111101101110110010011110000010110000110111000111100010101100010100100101101100000111100001010000101010111001000111111000111100111011111110011001000000110000000110111101000010111001100111100010010100010001111011100110110111101111001010101110001000001110101110101100101001101100100101011010000011111111110111101001100001000111010000111110000001010100100101111010110001000111010100011110100000000100100001101001000101100111001110010010011110010000101101010011101000110000001101010010011000010110111101001011010011010000001010110001100100000001111001100000000100100100010010101011110100001010010110001101001111000100100110001011111000101110011100110010111001110100010000111001110101000101110101110110100100110110111000100110011111110011100111100111100011001101010011110000101000100110010000000000111101111000001100000100110010100100111001011011011100100011110001010001111011111011000010010011101110000011101101110001111100011100101011001000101110010110011100110000100101010001010111011001000011001101000011111100010001111001100001111100011001010111010010110001110110111111010011010111011010000110110100100011010111000110011010010001100011011010100111011101011000010110000110001010
p=0b10111111010111000101011100010100001001011110111101011011010110110000010011111101110011100111001101110111010101000001111111111000101100111000110010000110101001110100000000011100001111101000101110010101110011110101100011111111110000110001101101110100100111100101101100110001001101110010010100010011100011111000001000001100001110000011010000111001000000111010000001001101101100110111001111110000111000110001011111000010011101110010101011100110011000111100111100000001100101011001000110001111000010011111110010101010111001111000111011011110110100011011010110000011100101100100010001011011111100100011001101011110100100000011011110110110011111000110001000010010001111001111100101000101101011011110111010111101110000011100000100010001010100000011000110001011001000101011101011101011111010010010110101000111111110011010100000010001000011111100100110001000010011111000111010100111000101100011100111110100111000101011010101010101111111010011101001110011101101001100100010100000110011101111100000011101010001010001011000101011001111010000000000010100001101010010011011000000010000111010000001000111101001001000011000011100101100011010100111010010111110110100011101100000000110001011101110100100011011110101010010010001101100001011000001101010110110101110100110110011110011110011100001000000011101000000010011101001001001111111001010100111111110101000110011010110001101011101011111100100001011001111100010001100011011010100111100111000100010000011100100001010111100001100011001010001111001001001110011100100010111000001110001000110101110011100100000101000100010011011011001011010010101111001110101000011001111000101111011011101001101001111100111001111011100110100100011000010010100000110001010110000100111110101001111100100101001101101000100001001011011011000101100111101100011110011011101001010110101001100100100010010100011111000010110101010101011110100011000011000001111001100000110010110101110100101100010100010001001101000110110111101110100000001001001000010010001101101001011000101111101011110001101010101110111111101101100101110011011010000100110111011
c=0b1100000111101010011111101100110110001100001111110010001011011110011111000011111010010111110100010001110000101100101010100010001001011110001100000101100111010010001001000011010110100100100100101010001100011010111111010101011010111000010010111101110101001010110000101101010010011100000100010110011011010001111101000111000100101011011011101100001011100101001101100000010100001100010111010110101001100110101000000101110111111001011000011100100101110010000000110010111100001000111110111011111011011111100101011000110000000011001101010111001101010100011000011100001000010000001100011100110110000010111100101011110010110011100000111001010000101010001000001101101100010000101100111111100110010100001011110101111001000101111111010100100110011011001101101000010000111110010100100100111100110100110011011000011101110010111011111110100110011010110100010101000011111001111000100001000011011000010000001010011111001111010000000110111011000110001100110010101000101110110101000001101001000001011000110011011011010111011011101100101011101010110101111100010101000010100001010011101010101001100000010000000001111111100100100011011110001001010010110001000101111011101010101100001011111101100101000100010100010100000001111101000111110101111111100001011111001010101001011000011011100001011100010100111100100110101111011001011001011100001011111110100001111011101001000001110110011101111101011000010110011111011001100011000111010101111000101001100010010001101110111011111101110111110001000111111001111010101110100111001001001000100111111111111100010100111110110001111010011001111010001000010110000000101100001000111010101010100000111110111110011010001100001101111010111110010010011001111001100111010010011010010101100111011100001011110111100001000101101000111001000001011000010111010101011110011100001010001100110011101011000000110001010011110010100011100000101111000110110110000001011010110010000001001111100001010010010001101111011010111000100001011111010111001000000011101001001111001011101010100001100010101001011010110111011010010100100100101011111100110111110111
h=z

M = Matrix([[1, h], [0, p]])
fg = M.LLL()[0]
f, g = abs(fg[0]), abs(fg[1])
a = f * c % p
E = a * gmpy2.invert(f, g)%g
print(f.bit_length())
print(long_to_bytes(E))

ez_fac(未出)

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
import random
from secret import flag,a0,a1,b0,b1

p = getPrime(512)
q = getPrime(512)
e = getPrime(128)
n = p*q
assert pow(a0,2) + e * pow(b0,2) == n
assert pow(a1,2) + e * pow(b1,2) == n
m = bytes_to_long(flag)
c = pow(m,e,n)

print("c=",c)
print("n=",n)
print("a0=",a0)
print("a1=",a1)
print("b0=",b0)
print("b1=",b1)

题解

赛后自己推了一下，欧拉公式分解 因此有 \[a-c=kl\] \[d-b=km\] \[a+c=hm\] \[d+b=hl\] 推到这步之后，运用Brahmagupta-Fibonacci恒等式，得到 \[n=((\frac{k}{2})^2+(\frac{h}{2})^2)(l^2+m^2)\]

\[khl^2+khm^2=(a-c)(d+b)+(a+c)(d-b)\] \[kh(l^2+m^2)=2ad-2bc\] \[l^2+m^2=GCD(ad-bc,n)\] 所以对应到本题当中，p=GCD((a0*b1-a1*b0),n)

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

c= 59318036714789752844006238692725062195097217062554867007780992204804450969142204391316045272560233388274742342095873063037352032862624199553582149985170237070779964129236530514163078045059943014170914727745788332060644178009630719416607144479458704906477608582501903047686165816474471957589874497851401996299
n= 137668242641076635664648797843242668120238355343016879645699934379078238840410583671764334209483740737808707460147728851168032552228765759429988090828780489149204937220494635170377998778905602318559649339660536303852604291303891241968251882157710174648060585737047441793290567655691681568937436184102493026497
a0= 11733211096757640611023179466137568647194748846209714362630723124944554158026265927220172817593295793460531810586641675319307669405413132181412592532359680
a1= 11733211096757640611023178103076370448537803344455852236399317962314322115993820094669322043912570063235179770967045735659217853855020241135449964093477392
b0= 16952448082892650701908860033061048276853071047612576981620233993855951344312992860690440851309510652705695741073983670611
b1= 307989142448102248940629255335003301679438459116674689074678317519163453142223887826928430255723118986268767245966808235987
e=(n-pow(a0,2))//pow(b0,2)
assert pow(a0,2) + e * pow(b0,2) == n
p=GCD((a0*b1-a1*b0),n)
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
print(long_to_bytes(pow(c,d,n)))

CTF
NSSCTF Round11
https://sch01ar.github.io/2023/04/08/NSSCTFRound11/
作者
Roo1e
发布于
2023年4月8日
许可协议