RSA

1
2
3
4
5
6
7
8
9
10
11
from secret import flag
p = getPrime(128)
q = getPrime(128)
n = p*q
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f"n = {n}")
print(f"p = {p}")
print(f"q = {q}")
print(f"c = {c}")

基础rsa，计算d解密即可

1
2
3
4
5
6
7
8
e = 65537
n = 33108009203593648507706487693709965711774665216872550007309537128959455938833
p = 192173332221883349384646293941837353967
q = 172282016556631997385463935089230918399
c = 5366332878961364744687912786162467698377615956518615197391990327680664213847

d=inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))

SYC{RSA_is_easy}

共模攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
from secret import flag
p,q = [getPrime(1024) for _ in range(2)] 
n = p*q
e = [getPrime(10) for _ in range(2)]

m = bytes_to_long(flag)

c = [pow(m, e[i], n) for i in range(2)]
print(f'n = {n}')
print(f'e1 = {e[0]}')
print(f'e2 = {e[1]}')
print(f'c1 = {c[0]}')
print(f'c2 = {c[1]}')

共模攻击板子题，不多说了

1
2
3
4
5
6
7
8
9
10
n = 
e1 = 911
e2 = 967
c1 = 
c2 = 

_,s1,s2=gmpy2.gcdext(e1,e2)

m=pow(c1,s1,n)*pow(c2,s2,n)%n
print(long_to_bytes(m))

SYC{U_can_really_attack}

inPEM

解压文件，发现给了公钥私钥文件，加密后的key.enc，以及一个mixHoyo文件夹，里面发现是Ginshen.exe。exe是一个解压程序，需要解压密码，去看rsa。

查看私钥文件，发现前半部分是缺失的，但是可以复原出dp，dq和inv_q。

查看公钥文件，没有异常。

既然已知dp，直接dp攻击即可

1
2
3
4
5
6
7
8
9
10
11
12
13
dp=int('ba5beaf382f586bf044615f3ec8bf35e0ad0a41cecb213930a86ac35a80d90319a05aa56da311ee8435abe6317eb6d15904fc787d37b34c48daad75d2b77a41d5cec4c27cced07cbda891fefa0d9d7025023bcb865c16c000266a090640032752acce73a3358060c056723e788f42edc8e120e0f58f5e24f327fff1c56687fb1',16)
dq=int('00a146448c980fcf49be5640ea8cfb6278f3b270e54ead35b5ddf65c0bb0eb67594075a68359e90b762dcc59604f2358d907a539b9abcb2736bc59f15614d87035c52d0c2b5fc5f9615e00ac5000972cf1a4dcd83f30c7adda8b0fa3e1314fb046e1d53f202d341b0bd0dfa681072c58926f9e04931e0f3a9093a51e536e2c11a1',16)
P_invQ=int('1621b7551fa5b9b70fbd739502f92df9cf2b17aa9c99795bd8e83484dc03276ae85fdf1aa8e572a7901618fa00d6c888e3f44f229d4295f13028c8eb6ae9f5649b3f8ca7a669093685d856910fba4229ef5096c0d4baa64dc46629ad5e998fd4e88f1c7ba37af5eeef7abd4357823fba049a8499594ff251c85e6a8f5b9567f9',16)

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

成功获得密码

1
\x02y,0\\\x9b\x13\xceg\x1do`\x90p\xa1q\xffg\xe1\x0f9\xbe\xad\xc3\x7f\xf1\xc2\x1bF\xd1\xcd\xf3"8\xff\xd9%nj\xa8\x8f\x11\xfb\xa0\xde\xcb\x8a\xbe\xe8\\\x8c6\x93\xb6#\xbe\xab\xdcFU;\xcf\xdc\xe9\xd7\xef!\xb8r\xc9\x82\x9eg\x95\x88o)O\x84\x1e`b\xc2\xa2\xa6\x83\xe1\x03\xc5\xb9Py\x0b\xf0\xf0l\x90\x10\x19\x93\xdf@\xd5\xc2\xd4\x06\xc6\xdf\x90\xc7\xbc\xc4{\xc9X\x98j_,o\xf3\x1b\xe6\xa5\xee\x06NO\xb8\xbaE)a\x07\x12b\xcb\x83\x16P\x8a\xa7\x950\x8c\x0c\xe5}\xcb\x85-\xe7#\xe7[-\x03\x8f\xe2\xa7\x00You_are_r1ght_bu7_Genshin_Impact_1s_@_brand_new_open_wor1d_@dventure_gam3_dev3loped_6y_miHoYo.

exe输入密码，得到txt文件，末尾得到flag

SYC{OVvanSh3nO_Q1D0ng!}

ezRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from secret import flag
m = bytes_to_long(flag)
assert m.bit_length()<500
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 3
c = pow(m, e, n)
bits = 150
m = (m >> bits) << bits
h = (2024*m-2023) % n
print('n =',n)
print('c =',c)
print('h =',h)

2024*m-2023数量级小于n，相当于已知m高位攻击

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
n = 
c = 
h = 
mh=(h+2023)//2024

PR.<x>=Zmod(n)[]
f=(x+mh)^3-c
ml=f.small_roots(X=2^150,beta=0.4)[0]
m=int(mh+ml)
print(long_to_bytes(m))

SYC{crypto_is_very_interesting_why_dont_you_join_us}

RnoCRT

1
2
3
4
5
6
7
8
9
10
11
import hashlib
from Crypto.Util.number import *
from secret import x

m = [getRandomNBitInteger(256) for i in range(10)]
u = hashlib.sha256(x).hexdigest()
assert u[:5]==b'6a651'
flag = b'SYC{'+u+b'}'
c = [x % i  for i in m]
print(m)
print(c)

提示Also gcd!=1 ，找到了扩展中国剩余定理，基本是原题，看看原理改改脚本即可

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
m=[207867980504656835313307696396607264603, 245036212212570610987366430554968489325, 270836744824069537438646110613439698666, 319275775495422875474878625752594133023, 254268823435329877199449670714528712873, 213093607196415232366564484229844568444, 246921085368773491003187313772615702950]
c=[150031581047390726903711035932621949276, 21260202376534810598778595491323328519, 144049733622518360270048059408969512643, 236920143187836025924037873968303507493, 99781504248790469459151935530031893836, 69236016568483424294966410179787943383, 20613188366058016717435734248097940419]

def exgcd(a, b):
    if b==0: return 1, 0
    x, y = exgcd(b, a%b)
    return y, x - a//b*y

def uni(P, Q):
    r1, m1 = P
    r2, m2 = Q

    d = gmpy2.gcd(m1, m2)
    assert (r2-r1) % d == 0

    l1, l2 = exgcd(m1//d, m2//d)
    
    return (r1 + (r2-r1)//d*l1*m1) % gmpy2.lcm(m1, m2), gmpy2.lcm(m1, m2)

def CRT(eq):
    return reduce(uni, eq)

m, mod = CRT(zip(c, m))
for i in range(2**15):
    x = hashlib.sha256(str(m + i*mod).encode()).hexdigest()
    if "6a651" in x:
        flag = "SYC{" + x + "}"
        print(flag)
        break

SYC{6a651b7ce47b35cc1aca565028fb633fab9e35ca08e45d5ce987a6caeb500465}

X0R

1
2
3
4
5
6
7
8
9
10
11
12
key = b'...'
flag = b'...'
assert len(key)==4

enc = bytes_to_long(xor(flag,key))

f1 = 4585958212176920650644941909171976689111990
f2 = 3062959364761961602614252587049328627114908
e1 = enc^f1
e2 = e1^f2
print(e2)

先异或回去获得enc

pwn的xor函数是从左往右密钥补齐的，逐个爆破出密钥即可。

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
f1 = 4585958212176920650644941909171976689111990
f2 = 3062959364761961602614252587049328627114908
e2=10706859949950921239354880312196039515724907

enc=long_to_bytes((e2^f2)^f1)

str=string.ascii_letters + string.digits + string.punctuation
key=''
for k in str:
    dexor=xor(enc,(key+k).encode()).decode()
    if dexor[0]=='S':
        key+=k
        break
for k in str:
    dexor=xor(enc,(key+k).encode()).decode()
    if dexor[1]=='Y':
        key+=k
        break
for k in str:
    dexor=xor(enc,(key+k).encode()).decode()
    if dexor[2]=='C':
        key+=k   
        break    
for k in str:
    dexor=xor(enc,(key+k).encode()).decode()
    if dexor[3]=='{': 
        key+=k
        break
print(key)
print(xor(enc,key.encode()))

“><0R” SYC{a_part_0f_X0R}

ncoCRT

还是扩展中国剩余定理，不过是普通一些的情况，直接脚本解密即可。

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
def exgcd(a, b):
    if b==0: return 1, 0
    x, y = exgcd(b, a%b)
    return y, x - a//b*y

def uni(P, Q):
    r1, m1 = P
    r2, m2 = Q

    d = gmpy2.gcd(m1, m2)
    assert (r2-r1) % d == 0

    l1, l2 = exgcd(m1//d, m2//d)
    
    return (r1 + (r2-r1)//d*l1*m1) % gmpy2.lcm(m1, m2), gmpy2.lcm(m1, m2)

def CRT(eq):
    return reduce(uni, eq)


m = [1921232050179818686537976490035, 2050175089402111328155892746480, 1960810970476421389691930930824, 1797713136323968089432024221276, 2326915607951286191807212748022]
c = [1259284928311091851012441581576, 1501691203352712190922548476321, 1660842626322200346728249202857, 657314037433265072289232145909, 2056630082529583499248887436721]

x=CRT(zip(c,m))
print(long_to_bytes(x[0]))

SYC{wha+s_wr0n9!_CRT_bu+n0+<0mpr1me!}

LLL

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 *

flag = b'******'
m = bytes_to_long(flag)

assert m.bit_length() == 327
p = getPrime(1024)
a = getPrime(1024)
c = getPrime(400)

b = (a*m + c) % p

print(f'a = {a}')
print(f'b = {b}')
print(f'p = {p}')

'''
a = 
b = 
p = 
'''

根据式子 造格求解即可。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
a = 
b = 
p = 

M=matrix(ZZ,[
    [1  ,0  ,-a],
    [0  ,2^200  ,b],
    [0  ,0  ,p]
])

L=M.LLL()
print(L)
print(long_to_bytes(abs(L[0][0])))

SYC{1e989433efffd767589e989ad0f091075c06}

Number theory

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
m = bytes_to_long(flag)
q = getPrime(1024)
p = getPrime(1024)
q1 = getPrime(1024)
p1 = getPrime(1024)
n = p * q
n1 = p1 * q
h0 = pow(1012 * q + 2024, p1, n1)

print(f"h0 = {h0}")
print(f"n1 = {n1}")

n2 = p * q1
h1 = getPrime(128)*p+getPrime(13)*q1
h2 = getPrime(128)*p+getPrime(13)*q1

print(f"h1 = {h1}")
print(f"h2 = {h2}")
print(f'n2 = {n2}')

e = 65537
c = pow(m, e, n)
print(f'c = {c}')

题目分为两部分，分别还原p和q求解rsa。

第一部分给出 和 。 将展开：将不含的一项减掉，和求最大公因数即可得到 此时已经可以单q求解rsa了

1
2
3
4
5
6
7
8
h0 = 
n1 = 

e=65537
q=GCD(h0-pow(2024,n1,n1),n1)
print(f'q={q}',n1%q)
d=inverse(e,q-1)
print(long_to_bytes(pow(c,d,q)))

后半部分给出了

1
2
3
n2 = p * q1
h1 = getPrime(128)*p+getPrime(13)*q1
h2 = getPrime(128)*p+getPrime(13)*q1

其中两个13位的系数很小，可以试着爆破 和求最大公因数即可得到

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
h0 = 
n1 = 
h1 = 
h2 = 
n2 = 
c = 
e=65537
q=GCD(h0-pow(2024,n1,n1),n1)
print(f'q={q}',n1%q)


# d=inverse(e,q-1)
# print(long_to_bytes(pow(c,d,q)))
found=False
for b in tqdm(range(2**11,2**13)):
    for d in range(2**11,2**13):
        if n2%GCD(h1*d-h2*b,n2)==0 and GCD(h1*d-h2*b,n2)!=1:
            p=GCD(h1*d-h2*b,n2)
            print(f'p={p}')
            found = True
            break
    if found:
        break
    
d=inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,p*q)))

SYC{492aebb6-9c16-4b1a-ac42-fc608bf6063f}

dp

1
2
3
4
5
6
7
8
9
10
11
12
13
p,q = getPrime(512),getPrime(512)
n = p * q
e = 65537
d = pow(e,-1,(p-1) * (q-1))
dp = d % (p-1)
m = bytes_to_long(flag)
c = pow(m, e, n)


print("c = ",c)
print("n = ",n)
print("e = ",e)
print("dp = ",dp)

常规dp攻击，直接解即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
c =  
n =  
e =  65537
dp =  
for i in range(1,e):                   
    if(dp*e-1)%i == 0:
        if n%(((dp*e-1)//i)+1) == 0:   
            p=((dp*e-1)//i)+1
            q=n//(((dp*e-1)//i)+1)
            phi=(q-1)*(p-1)            
            d=inverse(e,phi)         
            m=pow(c,d,n)  

print(long_to_bytes(m))

SYC{welcome_to_crypto}

ecc

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

p = getPrime(256)
a = getPrime(256)
b = getPrime(256)
E = EllipticCurve(GF(p),[a,b])
m = E.random_point()
G = E.random_point()
k = getPrime(256)
K = k * G
r = getPrime(256)
c1 = m + r * K
c2 = r * G

cipher_left = bytes_to_long(flag[:len(flag)//2]) * m[0]
cipher_right = bytes_to_long(flag[len(flag)//2:]) * m[1]

print(f"p = {p}")
print(f"a = {a}")
print(f"b = {b}")
print(f"k = {k}")
print(f"E = {E}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")
print(f"cipher_left = {cipher_left}")
print(f"cipher_right = {cipher_right}")

常规ecc解密过程，求解m还原flag即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
p = 
a = 
b = 
k = 
E = EllipticCurve(GF(p),[a,b])
c1 = E( , )
c2 = E( , )
cipher_left = 
cipher_right = 

m=c1-k*c2
m1=cipher_left//m[0]
m2=cipher_right//m[1]
print(long_to_bytes(int(m1))+long_to_bytes(int(m2)))

SYC{Ecc$is!sO@HaRd}