Automne's Shadow.

HackZone CTF 2019 MeSS WriteUp

rsa sage
2019/04/18 Share

Crypto

参考WriteUp: https://github.com/ziyedbe/hackzone2019/tree/master/MeSS

提供的压缩包里包含了140个key文件和1个cipher文件

Crypto_.zip

key文件内容形如：

automne

cipher内容为Decimal形式。

使用如下脚本去寻找所有key文件里是否有相同n的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#encoding:utf-8

import glob
import subprocess

for filename in glob.glob('Crypto_/*.key'):
    f = open(filename,"r")
    content=f.readlines()
    n=int(content[0].split(" ")[2],16)
    for filename1 in glob.glob('Crypto_/*.key'):
        g = open(filename1,"r")
        content1=g.readlines()
        n1=int(content1[0].split(" ")[2],16)
        if(n==n1 and filename!=filename1):
            print(filename+":"+filename1)

找到了两个相同n的key：

automne

9hpUS3qszH.key

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = 00b3d6bd85c58f72c351318961a9bc77b5c27e93a37eebaf66ccf9daa31d6dc0e6ab03e55c6ba06bbf31c77bb9e4eb3b245abeb8750ea9eabe2a2f0a761d72c9ea58a84bf6131ea2c4610418dded3a659829c42bba3ecac7160297cc9227c9267260bbf61d93fc8ce755a284f3135568e571b453d5fe40f64c2c897446a089c47683a21662d50353236ee9cd8ccff24407fda2af4fc3fde5e56ae83b6c4dfa7c51ef962d295a289364ce7b14373d1f784f406baedf32774873334bca1321555981848684337fc6080f0f8ff20710775029974b40601ab1b9953370af7466510db4603a482b1fd35eba28dd9ae2141c16ef2f0b1a219fd3ac69f4dc8bd71ef722a9

e = 65537

d = 43fe2a858b1e231ba974fb260b90900a0e50e0ecedad9a1159ea15399a84c66befb8775d2bebe910ce7747560f30c899841d9b8bd65173c91615d6f4b5499301a1277020c735cc004755cf3908da0d532c6758c8ffb896f0c16637180326cffc6a8a6610e4c49559594d2acae44264786b36ec8379af81ef66df4930f2bd63a370f475ce2353a8cb20f91e74ce7f418841fdd075aab74782b793669290549e3725355461027429e59487b5490f20495a50a086076a829d5c9e82ef16d4f9739a4fbc52954a1609b2d69daf02fd8ddaf65e9308f3b9324c79b7fc12acc0847914c0a4b7bfa2249a1f887894516fac570d7f854e898b1b70bb21fd9d2f5a5ec849

First prime = b5349890aea227801b284c3ddda57602

Second prime = 590e9df02867430e6c1e10dd913e860f

Exp_1 = e02813cc1f8ac0810000d546        

Exp_2 = 78d1a6f7d6c534d70000fc47        

Coef = db280abd494a5f50

f3elfj6rlU.key

1
2
3
n = 00b3d6bd85c58f72c351318961a9bc77b5c27e93a37eebaf66ccf9daa31d6dc0e6ab03e55c6ba06bbf31c77bb9e4eb3b245abeb8750ea9eabe2a2f0a761d72c9ea58a84bf6131ea2c4610418dded3a659829c42bba3ecac7160297cc9227c9267260bbf61d93fc8ce755a284f3135568e571b453d5fe40f64c2c897446a089c47683a21662d50353236ee9cd8ccff24407fda2af4fc3fde5e56ae83b6c4dfa7c51ef962d295a289364ce7b14373d1f784f406baedf32774873334bca1321555981848684337fc6080f0f8ff20710775029974b40601ab1b9953370af7466510db4603a482b1fd35eba28dd9ae2141c16ef2f0b1a219fd3ac69f4dc8bd71ef722a9

e = 257

可见两个key的n一致，而且f3elfj6rlU.key没有私钥(n , d)
于是可以猜想cipher文件可能就是f3elfj6rlU.key文件加密生成的。

因此可以通过9hpUS3qszH.key分解n求得p和q用于f3elfj6rlU.key
分解之前首先使用在线转换工具将上面的Hex形式的n和d转换为Decimal形式
推荐使用https://www.rapidtables.com/convert/number/hex-to-decimal.html

直接使用yafu或者sage等分解n在这里是行不通的
这里知道了e,d,n可以使用下面的脚本进行分解。

脚本摘录如下：

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
import fractions #for gcd function (or easily implementable to avoid import)
import random #for random elements drawing in RecoverPrimeFactors

def failFunction():
	print("Prime factors not found")

def outputPrimes(a, n):
	p = fractions.gcd(a, n)
	q = int(n / p)
	if p > q:
		p, q = q, p
	print("Found factors p and q")
	print("p = {0}".format(str(p)))
	print("q = {0}".format(str(q)))
	return p,q


def RecoverPrimeFactors(n, e, d):
	"""The following algorithm recovers the prime factor
		s of a modulus, given the public and private
		exponents.
		Function call: RecoverPrimeFactors(n, e, d)
		Input: 	n: modulus
				e: public exponent
				d: private exponent
		Output: (p, q): prime factors of modulus"""

	k = d * e - 1
	if k % 2 == 1:
		failFunction()
		return 0, 0
	else:
		t = 0
		r = k
		while(r % 2 == 0):
			r = int(r / 2)
			t += 1
		for i in range(1, 101):
			g = random.randint(0, n) # random g in [0, n-1]
			y = pow(g, r, n)
			if y == 1 or y == n - 1:
				continue
			else:
				for j in range(1, t): # j \in [1, t-1]
					x = pow(y, 2, n)
					if x == 1:
						p, q = outputPrimes(y - 1, n)
						return p, q
					elif x == n - 1:
						continue
					y = x
					x = pow(y, 2, n)
					if  x == 1:
						p, q = outputPrimes(y - 1, n)
						return p, q

if __name__ == "__main__":
	n = 22702548988585639637851431705875336575429862255188645528887111724338807108889571748597184000150880723937377646354782096179701969674522159233980700069669264159299994181571326564481560158416010897880474527515788236201435179106261470748150803007008802283045789226818457497417965570752028940845456738725432663418600719742841282343631476474796788118645986891324395254581787259492873305556198898579932343345978999277950429982957945557756158193790593989493517773943223087713762372788006918693003764533210155652090146152802657740521088243457672570665828910803472880085783454809883948635370279397426446590104641086404651590313
	e = 65537
	d = 8583300408001205104699372488947908657186034254834128185830368407245784252316490055796588570666013436344665506833983715750502088966466424485398687555522300797093782990234132316320919444058042297140277977978641086967654315392754424557085014524736623631983590421626069851702432990708970094698700384090494995715071183650922088075193246723137605407860036257002232313278864050794322031813665828387902387594617981849621559689493473674817599252679718986483691803809453381924322783193113102258652902805929559824002574465193743370946566891428836357847005942547746759368450889782252295496543534609564235482473199601293945915465
	RecoverPrimeFactors(n, e, d)

得到p和q

root@automne:/Pentest/CTF# python RecoverPrimeFactors.py 
Found factors p and q
p = 147504216621469380189409215874248864722589246550249379639840285872093233515595729240033319188381256063459342484480536624408619622982123945727439636240158758189207656414303429995920517843643171968009969688682973266810282225644661133313966156163713808164749325692764355471603647680864498925757106384432867755327
q = 153911186463541828405348779050505772007052654252098126319906724330785601180476549150297007215613778549116636075023789423035124242659679051063611847192928471457949573015601406901727072212522607132879243268324932705944030880046781379065510811111157918933296379352833989404101863466218445331033866033394766583319

然后使用sage

首先计算欧拉函数phi

sage: phi = (p-1)*(q-1)
sage: phi
22702548988585639637851431705875336575429862255188645528887111724338807108889571748597184000150880723937377646354782096179701969674522159233980700069669264159299994181571326564481560158416010897880474527515788236201435179106261470748150803007008802283045789226818457497417965570752028940845456738725432663418299304339756271135036718479872033481916344990522047748622040249289994470860126620189602016941983964665374451423453619510312414328148790992702466290510135858066605143358102081795356174477044376551200933195794751767766775137766230058286351943528601152987737749764285603759664768250343502333313668668577017251668

接着求出d

sage: e = 257
sage: d = inverse_mod(e,phi)
sage: d
6536920720448783397669283837489396523664629598770271475243759796113119556645246340063002396930603788215431695837563716409719633291496652853364092627064301742366535289635323602224262458065310530907218346444234745054109740287406026596743810982562845793561822578928271808595056234379961640554722952006544813591261278292381183128376331391091558278839725794936309468474828709912294127796301050171325094372400052082637001577181197835654158211217939818910437764582685033061979691083655852345744579421405773792952797885170473271652690117489109044020194723039363756113200752850416866452199193970916027909203157515465755940169

最后根据密文c得到flag

sage: flag = pow(c,d,n)
sage: flag
225867495516870385052319556599900461280701497334325927913753050855739983596381901143880117407592338807453086386821505176563420351178669173584377213

此时的结果是Decimal形式，直接转ASCII是乱码，需要先转为Hex形式
推荐使用：https://www.rapidtables.com/convert/number/decimal-to-hex.html

最后再将Hex转为ASCII，即可得到flag
https://www.rapidtables.com/convert/number/hex-to-ascii.html

automne

flag为：

HZVII{uN7rUst3D_uniQue_k3yZ_0bViousLy_CoMMoN_m0Dulu5_A77aCk5}

原文作者: Automne

原文链接: https://ce-automne.github.io/2019/04/18/HackZone-CTF-2019-Mess-WriteUp/

发表日期: April 18th 2019, 12:43:00 am

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 62
2021
2020
2019
2018
2017
lfsr z3 python reverse fat git broadcastreceiver sha-1 cbc sqli sqlite golang race condition luks hashcat photorec MAC sso oauth 2.0 padding oracle csp xss abe vdex ransomware frida ndk pwntools hashpumpy sourceleakhacker ecb socat fastjson JdbcRowsetImpl idea servlet volatility inet_aton boneh durfee lcg rabin egcd cipolla's algorithm spi snakeyaml ScriptEngineManager malware codereflect mysql yara plugin deserialization log4j rsa binary javascript prototype pollution nodejs shiro ysoserial primefac rsatool ssl AES tshark gmpy2 RsaCtfTool Hex flask ssti ecc Modular operation WebGoat8 order by tomcat nim game .iso gpg outguess sage google cloud sdk zsteg base58 fermat multi-primes prng rmi jndi Paillier Cryptosystem rsa lsb oracle SQL Injection ping delay xor CAS 单点登录 渗透测试 weblogic xxe reflect 010 editor gcd
Crypto Android Web Forensics Misc