Basic Mod 1
Challenge
1
2
3
4
We found this weird message being passed around on the servers, we think we have a working decrpytion scheme.
Download the message here.
Take each number mod 37 and map it to the following character set: 0-25 is the alphabet (uppercase), 26-35 are the decimal digits, and 36 is an underscore.
Wrap your decrypted message in the picoCTF flag format (i.e. picoCTF{decrypted_message})
message.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
91
322
57
124
40
406
272
147
239
285
353
272
77
110
296
262
299
323
255
337
150
102
Solution
1
2
3
4
5
6
7
8
#!/usr/bin/env python
flag = ''
map = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','0','1','2','3','4','5','6','7','8','9','_']
with open('message.txt','rb') as file:
for char in file.readlines():
char = int(char) % 37
flag = flag + map[char]
print(flag)
Output:
1
R0UND_N_R0UND_ADD17EC2
Basic Mod 2
Challenge
1
2
3
4
A new modular challenge!
Download the message here.
Take each number mod 41 and find the modular inverse for the result. Then map to the following character set: 1-26 are the alphabet, 27-36 are the decimal digits, and 37 is an underscore.
Wrap your decrypted message in the picoCTF flag format (i.e. picoCTF{decrypted_message})
message.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
104
290
356
313
262
337
354
229
146
297
118
373
221
359
338
321
288
79
214
277
131
190
377
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/usr/bin/env python
def modinv(x,y):
for i in range(y):
if (x*i)%y==1:
return i
flag = ''
map = ['','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','0','1','2','3','4','5','6','7','8','9','_']
with open('message.txt','rb') as file:
for char in file.readlines():
char = int(char)
char = char % 41
char = modinv(char,41)
flag = flag + map[char]
print(flag)
Output:
1
1NV3R53LY_H4RD_8A05D939
Cred Stuff
Challenge
1
2
3
We found a leak of a blackmarket website's login credentials. Can you find the password of the user cultiris and successfully decrypt it?
Download the leak here.
The first user in usernames.txt corresponds to the first password in passwords.txt. The second user corresponds to the second password, and so on.
The files provided are a list of username and a list of password
Solution
1
2
3
4
$ grep -n cultiris usernames.txt
378:cultiris
$ sed -n '378p' passwords.txt
cvpbPGS{P7e1S_54I35_71Z3}
Use Cyberchef to decode ROT13 encoded flag: cvpbPGS{P7e1S_54I35_71Z3} = picoCTF{C7r1F_54V35_71M3}
Very Smooth
Challenge
We are given 2 files:
- gen.py
- output.txt
gen.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
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
#!/usr/bin/python
from binascii import hexlify
from gmpy2 import *
import math
import os
import sys
if sys.version_info < (3, 9):
math.gcd = gcd
math.lcm = lcm
_DEBUG = True
FLAG = open('flag.txt').read().strip()
FLAG = mpz(hexlify(FLAG.encode()), 16)
SEED = mpz(hexlify(os.urandom(32)).decode(), 16)
STATE = random_state(SEED)
def get_prime(state, bits):
return next_prime(mpz_urandomb(state, bits) | (1 << (bits - 1)))
def get_smooth_prime(state, bits, smoothness=16):
p = mpz(2)
p_factors = [p]
while p.bit_length() < bits - 2 * smoothness:
factor = get_prime(state, smoothness)
p_factors.append(factor)
p *= factor
bitcnt = (bits - p.bit_length()) // 2
while True:
prime1 = get_prime(state, bitcnt)
prime2 = get_prime(state, bitcnt)
tmpp = p * prime1 * prime2
if tmpp.bit_length() < bits:
bitcnt += 1
continue
if tmpp.bit_length() > bits:
bitcnt -= 1
continue
if is_prime(tmpp + 1):
p_factors.append(prime1)
p_factors.append(prime2)
p = tmpp + 1
break
p_factors.sort()
return (p, p_factors)
e = 0x10001
while True:
p, p_factors = get_smooth_prime(STATE, 1024, 16)
if len(p_factors) != len(set(p_factors)):
continue
# Smoothness should be different or some might encounter issues.
q, q_factors = get_smooth_prime(STATE, 1024, 17)
if len(q_factors) != len(set(q_factors)):
continue
factors = p_factors + q_factors
if e not in factors:
break
if _DEBUG:
import sys
sys.stderr.write(f'p = {p.digits(16)}\n\n')
sys.stderr.write(f'p_factors = [\n')
for factor in p_factors:
sys.stderr.write(f' {factor.digits(16)},\n')
sys.stderr.write(f']\n\n')
sys.stderr.write(f'q = {q.digits(16)}\n\n')
sys.stderr.write(f'q_factors = [\n')
for factor in q_factors:
sys.stderr.write(f' {factor.digits(16)},\n')
sys.stderr.write(f']\n\n')
n = p * q
m = math.lcm(p - 1, q - 1)
d = pow(e, -1, m)
c = pow(FLAG, e, n)
print(f'n = {n.digits(16)}')
print(f'c = {c.digits(16)}')
output.txt
1
2
n = 6c5f4a08d820579e606aeb3800d1602c53825167d01bd7c87f43041afdc82877c50bbcc7830a0bf8c718fc9016e4a9e73ff0dfe1edd38688acb6add89b2bd6264d61e2ce0c9b3b0813b46b0eb1fcfc56b9f7f072ba2e1e986e6420f8ad9063e10fa9bca464b23fcf0135f95dc11a89bfddf2e81572c196f4362ea551aee18b343638d9d703b234e788bff4ddc3e885da77c7940a0fa670ddc1604646871f0739199fa7fa01f9ed7d84fb9f0cc82965450e7c97153fec84ef8e10a7fceb37a90e847a012528c733070e9ab751215b13a7e2d485089c0c4d00b81dbab382ef7681c717c76c2b14ce6495ef121540653561c3dd519c5f6e2ead18e9d90f3769a029
c = 42cbc15285a307d86ac5184c89d6bea5ebdc0a7546debedfe40af69fa6813eaf11ef86543349062587621b845e82817cf7f154c067733ee8b23a75e45861ee0c45a07e702dcb199adffa4ca0892fcd85abfe9e9b59c2ac2df7811a656a3fda16f385972107481409e33e820a19864233b8a35bc49734dc337786dc06c0460a4ec9fc06d16fd66a43654390a526ab0a6239b14427a9868399f6e4863ac04539690357e9a4fa67450286febd9a97dd07864f516f6756c2ffad0b1ba5882980f0089605f0def91120a80a448f77ec272be41de0e11695ba7d0c8899b1d9e8905a1b5e95a755e584dead086f35844052f261e8dcd0d6cffdce38cd5181235dfa0745
Solution
The solution for this challenge is some basic RSA maths. We have n,c (public modulus, ciphertext) from output.txt and e (public exponent) from gen.py. It’s pretty clear that we have to recover plaintext from ciphertext. Steps for solving:
- Generate public key with n,e
- Factor n to get p,q
- Decrypt ciphertext with pt = c ** d % e
For sake of simplicity, I used goRsaTool for the first steps
solve.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
import subprocess
import re
from Crypto.Util.number import *
from gmpy2 import *
with open('output.txt','r') as file:
output = file.read()
n = mpz('0x'+re.compile('n = ([0-9a-f]*)').search(output).groups()[0])
c = mpz('0x'+re.compile('c = ([0-9a-f]*)').search(output).groups()[0])
e = 0x10001
# Generate public key from n,e
pubkey = subprocess.run(['goRsaTool','-n',str(n),'-e',str(e),'-createkey'], capture_output=True)
pubkeyfile = open('pub.key','w')
pubkeyfile.write(str(pubkey.stdout.decode()))
pubkeyfile.close()
# Generate private key using Pollard's p-1 attack
privkey = subprocess.run(['goRsaTool','-key','./pub.key','-attack','pollardsp1'], capture_output=True)
privkeyfile = open('priv.key','w')
privkeyfile.write(str(privkey.stdout.decode()))
privkeyfile.close()
# Extract n,d,p,q,e from private key output
privparams = subprocess.run(['goRsaTool','-key','./priv.key','-dumpkey'], capture_output=True)
priv_n = mpz(re.compile('n = ([0-9]*)').search(privparams.stdout.decode()).groups()[0])
priv_d = mpz(re.compile('d = ([0-9]*)').search(privparams.stdout.decode()).groups()[0])
priv_p = mpz(re.compile('p = ([0-9]*)').search(privparams.stdout.decode()).groups()[0])
priv_q = mpz(re.compile('q = ([0-9]*)').search(privparams.stdout.decode()).groups()[0])
priv_e = mpz(re.compile('e = ([0-9]*)').search(privparams.stdout.decode()).groups()[0])
# Check if maths are ok
assert priv_n == n
assert n == priv_p * priv_q
# Decrypt c to get the flag
pt = pow(c, priv_d, priv_n)
print("Flag: " + str(long_to_bytes(pt)))
Thanks for reading <3
h3x