writeup for 2021VNCTF Crypto

Posted on Edited on In Word count in article: 20k Reading time ≈ 18 mins.

这次比赛听说是签到难度, 就做了一下, 结果也没能ak (说简单都是骗人的…)
嗯… 会做的题也没什么收获, 硬要说的话, whitegive的第一层需要通过运算把已知的条件合在一起或者消去一些不可能求出的参数, 这个一直都是密码分析的基础吧, 来看看题吧

0x00 wihtegive

problem

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
from Crypto.Util.number import *
from secret import url
from gmpy2 import *

m = bytes_to_long(url)
p = getPrime(512)
q = getPrime(512)
n = p * q
d = getPrime(256)
e = inverse(d,(p-1)*(q-1))
c = pow(m,e,n)

print(n)
print(c)

m = e
p = getPrime(512)
q = getPrime(512)
n = p * p * q
e = 0x10001
d = inverse(e,lcm(p,lcm(p-1,q-1)))
c = pow(m,e,n)
hint = pow(d,e,n)

print(n)
print(c)
print(hint)

'''
97814568264814384858194701955408461509880555772006698372422205341758322175891474378211599333051180365254844248340812534463000531890490435018379585036704801177155418066770861143206836558793774360498040810255823235715535487716966004194143204900564413879660115112965484824906920141847149888933004740523449213441
86143311788363675684674113699193046781796638913243016152555572150858159500527674063754694514501999791875561142925154991000532628799185608465062814546108160434468098898040769021072007374156546314975240583347468026001633652940408779155579339470960571067652924814623371177901052302005289155305089588204204313261
1246903000089073759886267722667196003041462505274526737638837808213476294697746018085346623497511017543801377442390781101585650581984057653018703031659844145960721073451379508212905335383758157379301019575213158532070229897587088955814288202279949391608732448294591675986989254272257059551622461096394217684402667140362275595245430242117193793913872208576714597860532581116390903216389172132085635891741189355461016795362341416848534340615825023292174042406128959
952508462840095293368043281511747192551431448088755251878915582522463097721381421883702408853564036431155676272901680250701398946525803160765527940151587567521509500006089852079864042238196362897144754722623523621230744820970423076092319608853809407595863195726851921082224085255808985329769890887863865121647796115540376158135632760785321953364738008064130705467326745546629505023549047992509562623348749056757848144371814157305011884825502144329268299851210747
788785744509676701442642497798353940704045062680685297430840370664093043099033424646382070232242765761123110381200239132310785932203252095093993313010883982078216697297202940152563278231011836966627537170460186597134847633828107444548759805274516431300662852153808962421740187067058018192457264083227110866080267684557127718769967184710395811547902947248700889674967381917907905535103547918375731341071557144999864774198881339085314424766509424492349867615604684

'''
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
# Wow, you got here!
# This is the last task, trust me!
from Crypto.Util.number import *
from secret import flag,padding
from gmpy2 import *

m = bytes_to_long(flag)
e = 7 

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

c1 = pow(m,e,n)
c2 = pow(m+padding,e,n)

print(n)
print(c1)
print(c2)

'''
143224951702807798608353389056046982493788310072914995404719898237226283884553121669729599925829562704800197375580487019006702401282671268969358774635337351738915083955659230582177495821699251999928502338923489031347921151957398310960671307216790020399224115377846788378990638367296298663795893865325304226511
74797173657575640598140788410852016843612519588375968190579734420951374103129570637822547217967978911328419808529204143522454142303138959013220811558490951614314306849367068478190797885056922705403028856734095288522290055309880572321557493798362056216783777593386133347693892941928131945986087712737862263761
9209695919437085323423940852135308337887271742988391422139555924185234849146079306139570263602339983687993333013333937719071267190971983543492940032646907167417161479697805991443259327402389097539126399994414628326218438416138199892253597375493026563369334352434282120293396846427418323600336867792587721214

'''

好家伙, 连Crypto都开始套娃了, 一共三层RSA, 做了前两层才能知道第三层

第一层 利用gcd()分解n

  • e : 65537
  • c: 密文
  • hint:

这题不算难, 仔细算一下就能知道这个hint有什么用了
首先看一下d = inverse(e,lcm(p,lcm(p-1,q-1))), 都已经是素数了, 公倍数肯定是

那么我们就有

把hint的式子和这个式子都改写成:

联立一下就有:

取个gcd(e**e * hint - 1,n), 就可以有p了, 分解n就好做了, 这一层还是挺有意思的

第二层 Boneh_Durfee attack

这一层的私钥, 而, 满足使用Boneh_Durfee attack的条件, 直接扔到脚本里跑就能跑出来了
有了直接解密即可

第三层 Coppersmith’s Short-pad Attack

第二层出来一个网站https://dawn-whisper.lanzous.com/iCAv0lod7yj-password:gzjq', 以及密码

打开后还是一道RSA

如题, e够小, 直接上脚本就行

exp

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
49
50
51
52
53
54
55
56
57
58
59
60
from gmpy2 import *
from Crypto.Util.number import long_to_bytes
# 第一层
e = 65537
h = 788785744509676701442642497798353940704045062680685297430840370664093043099033424646382070232242765761123110381200239132310785932203252095093993313010883982078216697297202940152563278231011836966627537170460186597134847633828107444548759805274516431300662852153808962421740187067058018192457264083227110866080267684557127718769967184710395811547902947248700889674967381917907905535103547918375731341071557144999864774198881339085314424766509424492349867615604684
n = 1246903000089073759886267722667196003041462505274526737638837808213476294697746018085346623497511017543801377442390781101585650581984057653018703031659844145960721073451379508212905335383758157379301019575213158532070229897587088955814288202279949391608732448294591675986989254272257059551622461096394217684402667140362275595245430242117193793913872208576714597860532581116390903216389172132085635891741189355461016795362341416848534340615825023292174042406128959
c = 952508462840095293368043281511747192551431448088755251878915582522463097721381421883702408853564036431155676272901680250701398946525803160765527940151587567521509500006089852079864042238196362897144754722623523621230744820970423076092319608853809407595863195726851921082224085255808985329769890887863865121647796115540376158135632760785321953364738008064130705467326745546629505023549047992509562623348749056757848144371814157305011884825502144329268299851210747
ee = pow(e, e)
p = gcd(ee * h - 1, n)
q = n // p ** 2
phi = (p - 1) * p * (q - 1)
d = invert(e,phi)
e = pow(c, d, n)
print(e)

# 第二层
# Boneh_Durfee attack出的结果
# 脚本在https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage
d = 103079922798932082066165266087442072203677117380612800709240732626110126828541
n = 97814568264814384858194701955408461509880555772006698372422205341758322175891474378211599333051180365254844248340812534463000531890490435018379585036704801177155418066770861143206836558793774360498040810255823235715535487716966004194143204900564413879660115112965484824906920141847149888933004740523449213441
assert pow(pow(3,e,n),d,n) == 3

c = 86143311788363675684674113699193046781796638913243016152555572150858159500527674063754694514501999791875561142925154991000532628799185608465062814546108160434468098898040769021072007374156546314975240583347468026001633652940408779155579339470960571067652924814623371177901052302005289155305089588204204313261
print(long_to_bytes(pow(c,d,n)))

# 第三层
def short_pad_attack(c1, c2, e, n):
        PRxy.<x,y> = PolynomialRing(Zmod(n))
        PRx.<xn> = PolynomialRing(Zmod(n))
        PRZZ.<xz,yz> = PolynomialRing(Zmod(n))
        g1 = x^e - c1
        g2 = (x+y)^e - c2
        q1 = g1.change_ring(PRZZ)
        q2 = g2.change_ring(PRZZ)
        h = q2.resultant(q1)
        h = h.univariate_polynomial()
        h = h.change_ring(PRx).subs(y=xn)
        h = h.monic()
        kbits = n.nbits()//(2*e*e)
        diff = h.small_roots(X=2^kbits, beta=0.4)[0]
        return diff
def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2
    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]

n = 143224951702807798608353389056046982493788310072914995404719898237226283884553121669729599925829562704800197375580487019006702401282671268969358774635337351738915083955659230582177495821699251999928502338923489031347921151957398310960671307216790020399224115377846788378990638367296298663795893865325304226511
e = 7
c1 = 74797173657575640598140788410852016843612519588375968190579734420951374103129570637822547217967978911328419808529204143522454142303138959013220811558490951614314306849367068478190797885056922705403028856734095288522290055309880572321557493798362056216783777593386133347693892941928131945986087712737862263761
c2 = 9209695919437085323423940852135308337887271742988391422139555924185234849146079306139570263602339983687993333013333937719071267190971983543492940032646907167417161479697805991443259327402389097539126399994414628326218438416138199892253597375493026563369334352434282120293396846427418323600336867792587721214
diff = short_pad_attack(c1, c2, e, n)
m1 = related_message_attack(c1, c2, diff, e, n)
long_to_bytes(m1)
    
# VNCTF{H4ppyNeWy34r!2021_V&N_figHt1ng!}

0x01 strange function

problem

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
from Crypto.Util.number import *
from hashlib import sha256
from secret import flag
import socketserver
import signal
import string
import random
import os

MENU = br'''[+] 1.function
[+] 2.check_answer
[+] 3.exit
'''

class Task(socketserver.BaseRequestHandler):
    # 为了缩短篇幅, 这部分没有特别意义的函数就省略了

    def proof_of_work(self):
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
        _hexdigest = sha256(proof.encode()).hexdigest()
        self.send(f"[+] sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
        x = self.recv(prompt=b'[+] Plz tell me XXXX: ')
        if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
            return False
        return True

    def function(self, x):
        res = 0
        for i in range(self.lenth):
            numerator = ord(self.token[i])
            denominator = x - self.data[i]
            try:
                tmp = numerator / denominator
            except Exception as e:
                self.send(b'[+] Error!')
                return
            res += tmp
        return res

    def handle(self):
        signal.alarm(1000)
        if not self.proof_of_work():
            return
            
        self.send(b'[+] Welcome!')
        self.send(b'[+] Can you find the flag through the calculating?')

        self.score = 0
        self.token = ''.join(random.sample(string.ascii_letters + string.digits, 16))
        self.lenth = len(self.token)
        self.data = []
        for i in range(self.lenth):
            self.data.append(getRandomInteger(32))
        self.send(str(self.data).encode())

        while True:
            self.send(MENU, newline=False)
            choice = self.recv()
            if(choice == b'1'):
                self.send(b"[+] Plz give me your x: ")
                now = int(self.recv().strip().decode())
                now = self.function(now)
                self.send(("[+] let me show you the answer: "+str(now)).encode())
            elif(choice == b'2'):
                guess = self.recv().strip().decode()
                if(guess == self.token):
                    self.score += 1
                    self.send(b"[+] You win!")
                    self.send(("[!] Now your score: " + str(self.score)).encode())

                    self.token = ''.join([random.choice(string.digits + string.ascii_letters) for i in range((self.score+1)*16)])
                    self.lenth = len(self.token)
                    self.data = []
                    for i in range(self.lenth):
                        self.data.append(getRandomInteger(32))
                    self.send(str(self.data).encode())
                    
                    if(self.score >= 5):
                        self.send(flag.encode())
                else:
                    self.send(b'[+] What do you want to say???')
                    self.send(b'[!] Go away!')
                    break
            else:
                break

        self.request.close()

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10002
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

分析

先理一理这题在干嘛, 要我们干嘛
前面常规的工作量证明就不说了

每次访问服务端的时候, 会从abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789挑出16位作为token

然后将token中的每一位的ascii码都乘一个不同的随机的数(范围在), 作为data然后发给客户端
客户端可以输入一个数让服务端计算:

并返回给客户端

解题的目标就是通过服务端返回的,(可以重复输入不同的获得不同的
猜出五轮的(每一轮的位数都会增加

因为这里的范围比较大, 所以每一个都相差比较远, 当的时候, 会特别大
所以事实上每次输入的时候, 有

把每次的四舍五入之后就是了
所以每一轮把都发送一次, 就能得到了

exp

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
49
50
51
from pwn import *
from hashlib import sha256
import re
printable = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
def proof(END, SHA):
    for i in printable:
        for j in printable:
            for k in printable:
                for l in printable:
                    start = i + j + k + l
                    ensha = sha256((start+END).encode()).hexdigest()
                    if ensha == SHA:
                        print(start)
                        return start

con = remote('node3.buuoj.cn',29406)
resp = con.recvuntil(': ').decode()
END = re.findall('XXXX\+(.*)\)',resp)[0]
SHA = re.findall('== (.*)',resp)[0]


con.send(proof(END,SHA).encode())
resp = con.recvuntil('[-] ').decode()


for _ in range(5):
    token = []
    array = re.findall(r'\d+', resp)
    data = []
    for i in array:
        if len(i) > 1:
            data.append(int(i))

    for i in data:
        con.sendline('1')
        resp = con.recvuntil('[-] ').decode()
        con.sendline(str(i + 1))
        resp = con.recvuntil('[-] ').decode()
        token.append(round(float(re.findall(r'let me show you the answer: (.*)', resp)[0])))
    print(token)
    presend = ''
    for i in token:
        presend += chr(i)

    con.sendline('2')
    resp = con.recvuntil('[-] ').decode()

    con.sendline(presend)
    resp = con.recvuntil('[-] ').decode()
    print(resp)
# flag{66a00c10-773f-4375-8a8e-444f0337bd31}

0x02 strange_function_revenge

problem

跟上一题的区别不大, 就不贴上来了

分析

跟第一题的区别就在于随机数的大小变小了, 这样会导致每个的差距不会太大, 再发送, 返回的四舍五入就不一定是了, 这里的解决办法就是对返回的进行一次修正后再四舍五入

因为是从abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789取的, 这些字符的ascii都是连在一起的, 平均数是86, 每次发送的时候, 把除了的其他都当作86, 这样就可以计算出:

这样就可以有!

跟strange_function一样发送数据就行了
不过这个方法不太稳定, 并不能保证每次都准确的修正, 放一首好运来多跑几次吧
(大概跑了七八次吧….

exp

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
49
50
51
52
53
54
55
56
57
58
59
from pwn import *
from hashlib import sha256
import re
printable = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
A = 86

def proof(END, SHA):
    for i in printable:
        for j in printable:
            for k in printable:
                for l in printable:
                    start = i + j + k + l
                    ensha = sha256((start+END).encode()).hexdigest()
                    if ensha == SHA:
                        print(start)
                        return start

con = remote('node3.buuoj.cn',27609)
resp = con.recvuntil(': ').decode()
END = re.findall('XXXX\+(.*)\)',resp)[0]
SHA = re.findall('== (.*)',resp)[0]


con.send(proof(END,SHA).encode())
resp = con.recvuntil('[-] ').decode()

for _ in range(5):
    token = []
    data = []
    offset = []
    array = re.findall(r'\d+', resp)
    for i in array:
        if len(i) > 1:
            data.append(int(i))
    for i in data:
        psend = i + 1
        sum = 0
        for j in data:
            if i != j:
                sum += A / (psend - j)
        offset.append(sum)
    for i in data:
        con.sendline('1')
        resp = con.recvuntil('[-] ').decode()
        con.sendline(str(i + 1))
        resp = con.recvuntil('[-] ').decode()
        token.append(round(float(re.findall(r'let me show you the answer: (.*)', resp)[0])-offset[data.index(i)]))
    print(token)
    presend = ''
    for i in token:
        presend += chr(i)

    con.sendline('2')
    resp = con.recvuntil('[-] ').decode()

    con.sendline(presend)
    resp = con.recvuntil('[-] ').decode()
    print(resp)
# flag{dfd7a22a-0ac7-4b7a-9dad-9d321fa2fcfa}

0x03 fatcor

对着某个paper写了一下午的algorithm, 没做出来, tcltcltcl…..

等wp出来再总结一下

结果一个师傅教我了hh

problem

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
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag

def get_public_key(d):
    while 1:
        p, q = getPrime(512), getPrime(512)
        N, phi, not_phi = p * q, (p - 1) * (q - 1), (p + 1) * (q + 1)
        try:
            e = inverse(d, not_phi)
            assert gcd(e, phi) == 1
            break
        except:
            pass
    return (N, e)

def encrypt(pubkey, m):
    N, e = pubkey
    c = pow(m, e, N)
    return c

m = bytes_to_long(flag)
d = getPrime(300)
pubkeys = [get_public_key(d), get_public_key(d)]
cs = encrypt(pubkeys[0], m), encrypt(pubkeys[1], m)
print(pubkeys)
print(cs)

'''
[(115483338707853323510117244601663937653032657454816581880428779391136584508645415322441921678179684904267659942318581245589538093236558206867210468172871004098796706517288570963560499418427771831765342801956281881820593084352360716457591198748797415842971188690055630073433785996545367137242661591939632740177, 57942961120648999071495995119939754708884253716257622598699627649519120883383654560602196191747110519111036450217116739928381611061803307053632035548944075112790103258912149703053932492832060534126356062378027983000713091223894604748395826345780826674822582205573649323340945351657354960324397873669889767611), (53622548101803784449246949981043962044702821559359430270342163843702543781580388956841660273746825211912789196955019345268896290156568895362182295889379787233440464948232717888315385094207004043907898658611926470834448875571292174245716821120409044389816082878077188546182422805778560826667364235348059795229, 37629174280947918845570975617525141920002123382327456934545962737176558640617579710289304146119507880547361939594011152968663070025066085778798378563965349218834887746411017240322083056673687330052590220772859205859051875687741541958997904176801239206348298021023694604932588913541173039972303193792987583003)]
(51861394323132582263685584977796608641129485967610029542263453128833142621927008505594685713111162217651119546991411861320042282788909858323941435593508384080858965324662410947546608051702238057613339996124961723578887443100478753831786550701578678090466528863014222331341645240511640398819027209200809466160, 53200507591144017820710284362261363695745231005527161900426580605551005076410241969689161754211964469126847594337121140420040532547631617290907291418063708630323838133357597795892690304405706577096504918510233628396424543417886828387510407109281423448827267022542075484645277275676556239547911837897827866040)
'''

分析

抄了那么久的paper居然是用格子做的! 感谢d33b4t0师傅指点才弄出这题

这题给出了一个300-bit的, 再根据这个生成了两套公钥

关系式为

记, 把式子化一下就有

自己做的时候只用的其中的一个式子造二维格子, 结果死活都规约不出来(也不知道为啥, 以后能造三维就试试造三维吧.

用这两个式子造出一个三维格子

(至于为啥有个, 当然是为了调整一下范数! 向量的长度也是合适的(得靠的位数来判断

通过规约这个格子, 有了, 就能得出

剩下的就是已知求了, 不过这里的有点不太一样注意一下就ok了

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import long_to_bytes as l2b ,isPrime
n1 = 115483338707853323510117244601663937653032657454816581880428779391136584508645415322441921678179684904267659942318581245589538093236558206867210468172871004098796706517288570963560499418427771831765342801956281881820593084352360716457591198748797415842971188690055630073433785996545367137242661591939632740177
n2 = 53622548101803784449246949981043962044702821559359430270342163843702543781580388956841660273746825211912789196955019345268896290156568895362182295889379787233440464948232717888315385094207004043907898658611926470834448875571292174245716821120409044389816082878077188546182422805778560826667364235348059795229
e1 = 57942961120648999071495995119939754708884253716257622598699627649519120883383654560602196191747110519111036450217116739928381611061803307053632035548944075112790103258912149703053932492832060534126356062378027983000713091223894604748395826345780826674822582205573649323340945351657354960324397873669889767611
e2 = 37629174280947918845570975617525141920002123382327456934545962737176558640617579710289304146119507880547361939594011152968663070025066085778798378563965349218834887746411017240322083056673687330052590220772859205859051875687741541958997904176801239206348298021023694604932588913541173039972303193792987583003
half_n = round(sqrt(n))

L = Matrix([[half_n     ,e1  ,e2],
            [0       ,n1  ,0],
            [0       ,0   ,n2]])
res = L.LLL()[0]
assert abs(res[0]) % half_n == 0
d = abs(res[0]) // half_n

if isPrime(d) :
    knophi = e1 *d - 1
    nophi = knophi // (knophi // n1 )
    pq = nophi - n - 1
    phi = n -pq +1
    d1 = inverse_mod(e1,phi)
    print(l2b(pow(cs[0],d1,n1)))
# b'vnctf{7d47956b-bc55-4897-a550-cda0b221ce67}'

后记

这题做完感觉收获还是有的, 不像前面的几题

Lattice是一个神奇的东西, 一定要把所有方程写出来, 该联立的联立, 根据未知量和已知量以及这些数的位数,
造出合适的Lattice才能求出出题人想要我们规约出的那个最短向量来