zzZxby's blog

NewStarCTF_2023_WEEK2

发表于
本文字数： 1.1k 阅读时长 ≈ 4 分钟
新生赛第二周

滴啤

题目

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 gmpy2
from flag import flag
def gen_prime(number):
    p = getPrime(number//2)
    q = getPrime(number//2)
    return p,q

m = bytes_to_long(flag.encode())
p,q = gen_prime(1024)
print(p*q)
e = 65537
d = gmpy2.invert(e,(p-1)*(q-1))
print(d%(p-1))
print(pow(m,e,p*q))
# 93172788492926438327710592564562854206438712390394636149385608321800134934361353794206624031396988124455847768883785503795521389178814791213054124361007887496351504099772757164211666778414800698976335767027868761735533195880182982358937211282541379697714874313863354097646233575265223978310932841461535936931
# 307467153394842898333761625034462907680907310539113349710634557900919735848784017007186630645110812431448648273172817619775466967145608769260573615221635
# 52777705692327501332528487168340175436832109866218597778822262268417075157567880409483079452903528883040715097136293765188858187142103081639134055997552543213589467751037524482578093572244313928030341356359989531451789166815462417484822009937089058352982739611755717666799278271494933382716633553199739292089

题解

dp泄露问题，爆破求p就可以了

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

dp = 307467153394842898333761625034462907680907310539113349710634557900919735848784017007186630645110812431448648273172817619775466967145608769260573615221635
c = 52777705692327501332528487168340175436832109866218597778822262268417075157567880409483079452903528883040715097136293765188858187142103081639134055997552543213589467751037524482578093572244313928030341356359989531451789166815462417484822009937089058352982739611755717666799278271494933382716633553199739292089
e = 65537
n = 93172788492926438327710592564562854206438712390394636149385608321800134934361353794206624031396988124455847768883785503795521389178814791213054124361007887496351504099772757164211666778414800698976335767027868761735533195880182982358937211282541379697714874313863354097646233575265223978310932841461535936931

for i in range(1, 65535):
    p = (dp * e - 1) // i + 1
    if n % p == 0:
        q = n // p
        break
print(p)
print(q)
phi_n = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi_n)
m = pow(c, d, n)
flag = long_to_bytes(int(m))
print(flag)

不止一个pi

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from flag import flag
from Crypto.Util.number import *
import gmpy2
p = getPrime(1024)
q = getPrime(1024)
n = p**3*q**2
print("q = ",q)
print("p = ",p)
m = bytes_to_long(flag.encode())
c = pow(m,65537,n)
print("c = ",c)

# q =  115478867870347527660680329271012852043845868401928361076102779938370270670897498759391844282137149013845956612257534640259997979275610235395706473965973203544920469416283181677660262509481282536465796731401967694683575843183509430017972506752901270887444490905891490955975762524187534052478173966117471143713
# p =  171790960371317244087615913047696670778115765201883835525456016207966048658582417842936925149582378305610304505530997833147251832289276125084339614808085356814202236463900384335878760177630501950384919794386619363394169016560485152083893183420911295712446925318391793822371390439655160077212739260871923935217
# c =  4459183928324369762397671605317600157512712503694330767938490496225669985050002776253470841193156951087663107866714426230222002399666306287642591077990897883174134404896800482234781531592939043551832049756571987010173667074168282355520711905659013076509353523088583347373358980842707686611157050425584598825151399870268083867269912139634929397957514376826145870752116583185351576051776627208882377413433140577461314504762388617595282085102271510792305560608934353515552201553674287954987323321512852114353266359364282603487098916608302944694600227628787791876600901537888110093703612414836676571562487005330299996908873589228072982641114844761980143047920770114535924959765518365614709272297666231481655857243004072049094078525569460293381479558148506346966064906164209362147313371962567040047084516510135054571080612077333228195608109065475260832580192321853906138811139036658485688320161530131239854003996457871663456850196483520239675981391047452381998620386899101820782421605287708727667663038905378115235163773867508258208867367314108701855709002634592329976912239956212490788262396106230191754680813790425433763427315230330459349320412354189010684525105318610102936715203529222491642807382215023468936755584632849348996666528981269240867612068382243822300418856599418223875522408986596925018975565057696218423036459144392625166761522424721268971676010427096379610266649911939139451989246194525553533699831110568146220347603627745407449761792135898110139743498767543521297525802809254842518002190381508964357001211353997061417710783337

题解

主要考察欧拉函数的求解方法

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

q = 115478867870347527660680329271012852043845868401928361076102779938370270670897498759391844282137149013845956612257534640259997979275610235395706473965973203544920469416283181677660262509481282536465796731401967694683575843183509430017972506752901270887444490905891490955975762524187534052478173966117471143713
p = 171790960371317244087615913047696670778115765201883835525456016207966048658582417842936925149582378305610304505530997833147251832289276125084339614808085356814202236463900384335878760177630501950384919794386619363394169016560485152083893183420911295712446925318391793822371390439655160077212739260871923935217
c = 4459183928324369762397671605317600157512712503694330767938490496225669985050002776253470841193156951087663107866714426230222002399666306287642591077990897883174134404896800482234781531592939043551832049756571987010173667074168282355520711905659013076509353523088583347373358980842707686611157050425584598825151399870268083867269912139634929397957514376826145870752116583185351576051776627208882377413433140577461314504762388617595282085102271510792305560608934353515552201553674287954987323321512852114353266359364282603487098916608302944694600227628787791876600901537888110093703612414836676571562487005330299996908873589228072982641114844761980143047920770114535924959765518365614709272297666231481655857243004072049094078525569460293381479558148506346966064906164209362147313371962567040047084516510135054571080612077333228195608109065475260832580192321853906138811139036658485688320161530131239854003996457871663456850196483520239675981391047452381998620386899101820782421605287708727667663038905378115235163773867508258208867367314108701855709002634592329976912239956212490788262396106230191754680813790425433763427315230330459349320412354189010684525105318610102936715203529222491642807382215023468936755584632849348996666528981269240867612068382243822300418856599418223875522408986596925018975565057696218423036459144392625166761522424721268971676010427096379610266649911939139451989246194525553533699831110568146220347603627745407449761792135898110139743498767543521297525802809254842518002190381508964357001211353997061417710783337
e = 65537
n = p ** 3 * q ** 2
phi = p ** 2 * (p - 1) * q * (q - 1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

halfcandecode

题目

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

def gen_prime(number):
    p = getPrime(number // 2)
    q = gmpy2.next_prime(p)
    return p * q

def md5_hash(m):
    return md5(m.encode()).hexdigest()
e = 65537
n = gen_prime(1024)
m1 = bytes_to_long(flag[:len(flag) // 2].encode() + os.urandom(8))
c1 = pow(m1, e, n)
m2 = flag[len(flag) // 2:]
with open("out.txt","w") as f:
    f.write(str(n) + '\n')
    f.write(str(c1) + '\n')
    for t in m2:
        f.write(str(md5_hash(t))+'\n')

题解

第一部分的flag，加密的n的两个素数相差较小，可以直接分解

第二部分，就是在字母表中碰撞，然后拼接第二部分flag

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

n = 113021375625152132650190712599981988437204747209058903684387817901743950240396649608148052382567758817980625681440722581705541952712770770893410244646286485083142929097056891857721084849003860977390188797648441292666187101736281034814846427200984062294497391471725496839508139522313741138689378936638290593969
c1 = 43054766235531111372528859352567995977948625157340673795619075138183683929001986100833866227688081563803862977936680822407924897357491201356413493645515962458854570731176193055259779564051991277092941379392700065150286936607784073707448630150405898083000157174927733260198355690620639487049523345380364948649
p = 10631151190024160908870967192522097752991652918777416177941351782447314225123009693276679810786266997133099934443701772661928189884235742113123409596993409
q = n // p
e = 65537
assert p * q == n
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = pow(c1, d, n)
print(long_to_bytes(m))


def md5_hash(m):
    return md5(m.encode()).hexdigest()


c2 = ['4a8a08f09d37b73795649038408b5f33', '03c7c0ace395d80182db07ae2c30f034', 'e1671797c52e15f763380b45e841ec32',
      'b14a7b8059d9c055954c92674ce60032', 'e358efa489f58062f10dd7316b65649e', 'cfcd208495d565ef66e7dff9f98764da',
      'b14a7b8059d9c055954c92674ce60032', '8fa14cdd754f91cc6554c9e71929cce7', '0cc175b9c0f1b6a831c399e269772661',
      '4a8a08f09d37b73795649038408b5f33', 'e358efa489f58062f10dd7316b65649e', 'cfcd208495d565ef66e7dff9f98764da',
      '4b43b0aee35624cd95b910189b3dc231', 'cbb184dd8e05c9709e5dcaedaa0495cf']
flag2 = ''
title = '01234567890qwertyuiopasdfghjklzxcvbnm_}'
for i in c2:
    for j in title:
        if md5_hash(j) == i:
            flag2 = flag2 + j
            break
print(flag2)

Rotate Xor

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from secret import flag
from os import urandom
from pwn import xor
from Cryptodome.Util.number import *
k1 = getPrime(64)
k2 = getPrime(64)
ROUND = 12
ciphertext = xor(flag, long_to_bytes(k1))
def round_rotate_left(num, step):
    return ((num) << step | num >> (64-step)) & 0xffffffffffffffff
def encrypt_key(key):
    
    for _ in range(ROUND):
        key = round_rotate_left(key, 3) ^ k2
    
    return key
print('ciphertext =', ciphertext)
print('enc_k1 =', encrypt_key(k1))
print('k2 =', k2)

# ciphertext = b'\x8dSyy\xd2\xce\xe2\xd2\x98\x0fth\x9a\xc6\x8e\xbc\xde`zl\xc0\x85\xe0\xe4\xdfQlc'
# enc_k1 = 7318833940520128665
# k2 = 9982833494309156947

题解

读懂代码，然后根据异或的性质，逆回去

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

ROUND = 12
ciphertext = b'\x8dSyy\xd2\xce\xe2\xd2\x98\x0fth\x9a\xc6\x8e\xbc\xde`zl\xc0\x85\xe0\xe4\xdfQlc'
enc_k1 = 7318833940520128665
k2 = 9982833494309156947


def round_rotate_left(num, step):
    return ((num) << step | num >> (64 - step)) & 0xffffffffffffffff


def decrypt_key(enc_k1):
    key = enc_k1
    for _ in range(ROUND):
        key = round_rotate_left(key ^ k2, 64 - 3)
    return key


k1 = decrypt_key(enc_k1)
print(k1)
flag = xor(ciphertext, long_to_bytes(k1))
print(flag)

broadcast

题目

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

menu = '''
Welcome to RSA Broadcasting system

please select your option:

1. brocast the flag
2. exit
'''
e = 17
def broadcast_the_flag():
    p = getPrime(256)
    q = getPrime(256)
    n=p*q
    m = bytes_to_long(flag)
    c = pow(m,e,n)
    print('n =', n)
    print('c =', c)
    print('e =', e)
while True:
    print(menu)
    opt = input('> ')
    try:
        opt = int(opt)
        if opt == 1:
            broadcast_the_flag()
        elif opt == 2:
            break
        else:
            print('invalid option')
    except:
        print('oh no, something wrong!')

题解

低加密指数广播攻击

与服务器交互，捕获17组n和c

然后中国剩余定理求解密文，直接开17次方就行

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


context.log_level = 'debug'

p = remote('node4.buuoj.cn', 25102)


def menu():
    p.sendlineafter('> ', '1')
    p.recvuntil('n = ')
    n.append(int(p.recvline()[:-1].decode()))
    p.recvuntil('c = ')
    c.append(int(p.recvline()[:-1].decode()))


n = []
c = []
for i in range(17):
    menu()
p.sendlineafter('> ', '2')
print(len(n), n)
print(len(c), c)
e = 17
# b是密文列表  m是模数列表
def crt(b, m):
    # 传入的参数分别为密文 和 模数n
    # 乘积计算
    M = 1
    for i in range(len(m)):
        M *= m[i]

    Mm = []
    # 求余数 M/m[i]
    for i in range(len(m)):
        Mm.append(M // m[i])

    # 求Mm[i]的乘法逆元
    Mm_ = []
    for i in range(len(m)):
        t, a, _ = gmpy2.gcdext(Mm[i], m[i])
        Mm_.append(int(a % m[i]))

    # 求的累加
    y = 0
    for i in range(len(m)):
        y += (Mm[i] * Mm_[i] * b[i])
    y = y % M
    return y, M


m, mm = crt(c, n)
m = gmpy2.iroot(m, e)
print(long_to_bytes(int(m[0])))


p.interactive()

partial decrypt

题目

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

m = bytes_to_long(flag)
e = 65537
p = getPrime(512)
q = getPrime(512)

n = p*q 

c = pow(m,e,n)

dp = inverse(e, (p-1))
dq = inverse(e, (q-1))
m1 = pow(c,dp, p)
m2 = pow(c,dq, q)
q_inv = inverse(q, p)
h = (q_inv*(m1-m2)) % p
print('m2 =', m2)
print('h =', h)
print('q =', q)

# m2 = 4816725107096625408335954912986735584642230604517017890897348901815741632668751378729851753037917164989698483856004115922538576470127778342121497852554884
# h = 4180720137090447835816240697100630525624574275
# q = 7325294399829061614283539157853382831627804571792179477843187097003503398904074108324900986946175657737035770512213530293277111992799331251231223710406931

题解

主要想考察rsa_crt算法

1
2
3
4
5
6
7
8
9
10
11
import gmpy2


def rsa_crt(c, p, q, dp, dq):
    qinv = gmpy2.invert(q, p)

    m1 = pow(c, dp, p)
    m2 = pow(c, dq, q)
    h = (qinv * (m1 - m2)) % p
    m = m2 + h * q
    return m

推导思路可以参考dp和dq泄露问题

dp，dq泄露问题

1
2
3
4
5
6
7
from Crypto.Util.number import *

m2 = 4816725107096625408335954912986735584642230604517017890897348901815741632668751378729851753037917164989698483856004115922538576470127778342121497852554884
h = 4180720137090447835816240697100630525624574275
q = 7325294399829061614283539157853382831627804571792179477843187097003503398904074108324900986946175657737035770512213530293277111992799331251231223710406931
m = h * q + m2
print(long_to_bytes(int(m)))