22-11-16-YD

Posted on Edited on In Symbols count in article: 6.2k Reading time ≈ 6 mins.

1115-YD-GAME.

Write Up about crypto and misc.

AK the crypto~

rrrrsa

  • Euler’s totient function
  • $e$ and $phi$ are not relatively-prime

Euler’s totient function

Mainly use the Euler 3, which has the equation that:
$$
\varphi(p^{k}\cdot q^{r}) = \varphi(p^{k})\cdot \varphi(q^{r})
$$

$$
\Longrightarrow \varphi(p) \times p^{k-1} \times \varphi(q) \times q^{r-1}
$$

$$
\Longrightarrow (p-1)\times p^{k-1} \times (q-1)\times q^{r-1}
$$

Main

task.py

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


p=getPrime(256)
q=getPrime(256)
r=getPrime(256)
s=getPrime(256)
n=p**2*q**3*r**4*s**5
e=14
m=bytes_to_long(flag)
c=pow(m,e,n)
print(p,q,r,s,c,sep='\n')
……

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
p=82740843489176005842917905237448676902781319326096412115804401131397466993701
q=85263643568597752465513069151877689268453731648228759206805083081972094635829
r=79374890087283111247783732293463483039814224158289962524595401321277418666013
s=102732199362754952069273055525350226201958416532282326662545431277468292741447
c=209764158198100932214155089968863460960764115788843889450050526143389381127082813487813848764081174468416915862387829518066498286649325136938861327501126507330636283194491774843852097326223633337209701533553768182215060190222820102775941550334063704345167980872865539263669078518722589070762176421658193780663489275300987379291331254855029837613791180120722762611589441493216729829935815928668091245317003984177304991150484204972754604505926951762889894890977781284204135659968910559636276248002638001257927724627172934291321960032984200304503486457400466222152687435733385861015747679424548570249193669289227091923991244140876236848584520997920469772887694030202115298206597699720631193271607873611648764756487112169968220121850963271008810056644983219771177431102811348959976986368053544506721049809904407594329574573889027703243130484608315308768672733480521699846869769824733283356920305979098527936478174996930553057717113709689343835430493021845720498504798696915665856537146177480318328251379204246844497037689723120344053581795715706628542369652261282102647414868089

from gmpy2 import *
from Crypto.Util.number import *
n = p**2*q**3*r**4*s**5
print(n)
N = (p-1)*p**(2-1) * (q-1)*q**(3-1) * (r-1)*r**(4-1) * (s-1)*s**(5-1) # key 1
e = 14
d = invert(e//2, N) # key2-1
m = iroot(powmod(c, d, n), 2)[0] # key2-2
print(m)
print(long_to_bytes(m))
# 46327402297749589082353363703523801418931778189802600046922737992686461676413
# b'flag{YqcbT7kcyeciLpEE3YQuRsLzJk}'

ASR

Reference: [CryptoCTF2022]PolyRSA

  • Polynomial solving

task.py

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

def genprime():
	while True:
		r = getRandomNBitInteger(64)
		p = r**6 + 8*r**4 - 41*r**3 + 14*r**2 - 116*r + 31387
		q = r**5 - 9*r**4 + 17*r**3 - 311*r**2 - 16*r + 14029
		if isPrime(p) and isPrime(q):
			return p, q

def enc(flag, n):
	m = bytes_to_long(flag)
	return pow(m, 31337, n)

p, q = genprime()
n = p * q
c = enc(flag, n)
print(n)
print(c)

exp.py

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
n = 73553176031506251642448229714220151174734540964434813056145000616720019024269982417494553771890010861489245572362590935764438928110836109730139595790550323300572059713433794357690270439325805603980903813396260703
c = 19209686331218755173713714974036153099675780768506975193406617712945126866438211292560144823093347834048813455853960982766572556698881387553177980003129346158494272297017876567974550982519632403844694686184532804
e = 31337

from sympy import *
from gmpy2 import *
from Crypto.Util.number import *
def Original_RSA(p,q,e,c,n):
    N = (p-1)*(q-1)
    d = int(invert(e, N))
    m = powmod(c, d, n)
    return m
r = Symbol('r')
p = lambda r: r ** 6 + 8 * r ** 4 - 41 * r ** 3 + 14 * r ** 2 - 116 * r + 31387
q = lambda r: r ** 5 - 9 * r ** 4 + 17 * r ** 3 - 311 * r ** 2 - 16 * r + 14029
n0 = p(r) * q(r)
f = n - n0
# print(f)
sol = solve([f], [r])
x = sol[0][0]
p = mpz(p(x))
q = mpz(q(x))
m = Original_RSA(p, q, e, c, n)
print(m)
print(long_to_bytes(m).decode())
# 642921858775320553662877496454459277194994123046130653667709
# flag{G3t_m0re_fuN_RSA!!!}

# or sage to solve out p, q
PR.<k> = PolynomialRing(ZZ) # define k
p = k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
q = k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011
n0 = p*q
# k^11 - 8*k^10 + 26*k^9 - 409*k^8 + 451*k^7 + 10850*k^6 + 44939*k^5 - 158301*k^4 + 71237*k^3 - 9651273*k^2 - 2036532*k + 439623147
f = n - n0
sol = f.roots() # solve the root of the equation
# print(sol)
# [(9291098683758154336, 1)]
x = sol[0][0]
p = p(x)
q = q(x)

ezmisc

Download: ezmisc

  • Archive pseudo-encryption
  • Repair the file header
  • Extract the hidden files
  • Unzip nested packages
  • Properties area steganation && Brute force
  • Blast file height or width

Archive pseudo-encryption

Winhex

Use winhex to find 504B0102, and the keypoint 09 which is the 5th behind the 504B0102. Edit it to 00 and unzip the zip.

And get the output 1.png.

Repair the file header

Winhex

Find the 1.png cannot open well. Check the file header, we find that the header is 000000000D0A1A0A which is different to 89504E470D0A1A0A. Thus, use winhex to edit and get the real 1.png.

Extract the hidden files

binwalk

foremost

Use binwalk to check if there are hidden files in the picture. If yes, and we execute the foremost to get the hidden files.

Make the output file empty!

Unzip nested packages

ExtractNow

Download: ExtractNow

After using the tool ExtractNow, we get the flag.zip and password.zip both of which are encrypted.

Properties area steganation && Brute force

ARCHPR

From the password.zip ‘s properties, we get the hint that 8 digits. We brute the zip’s password by ARCHPR.

Unzip the password.zip, we get the password.txt. By this dictionary, we can also brute the flag.zip by ARCHPR and obtain the final picture flag.png.

Blast file height or width

stegsolve

python

winhex

By the stegsolve, we can make a conclusion that the picture’s height or width has been edited from the Calculated CRC.

Use a script for blasting, remember that the script has its rules. 

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 struct
import zlib
def hexstr2bytes(s):
    b = b''
    for i in range(0, len(s), 2):
        temp = s[i:i+2]
        b += struct.pack('B', int(temp, 16))
    return b
str1 = '49484452'   # HEX/IHDR
str2 = '0802000000' # Bit depth，ColorType，Compression method，Filter method，Interlace method
bytes1 = hexstr2bytes(str1)
bytes2 = hexstr2bytes(str2)
wid, hei = 507, 507  # width height

crc32 = '0xe440b49a' # CRC32
for w in range(wid, wid+2000):
    for h in range(hei, hei+2000):
        width = hex(w)[2:].rjust(8, '0')
        height = hex(h)[2:].rjust(8, '0')
        bytes_tmp = hexstr2bytes(width+height)
        if eval(hex(zlib.crc32(bytes1+bytes_tmp+bytes2))) == eval(crc32):
            print(hex(w), hex(h))
            
# 0x260 0x1fb

Edit the width, and we will get the true flag.png.

-------------THE END-------------