Game Hacking
redpwnCTF
Hack The Box
Jarvis OJ Crypto RSA Series
{"author": ["ret2basic"]}
Jarvis OJ
Jarvis OJ
veryeasyRSA (RSA Decryption Algorithm)
Solution
Since
and
are given, we could decrypt the message directly with the RSA decryption algorithm.
Implementation
1
#!/usr/bin/env python3
2
from Crypto.Util.number import inverse
3
​
4
#--------Data--------#
5
​
6
p = 3487583947589437589237958723892346254777
7
q = 8767867843568934765983476584376578389
8
e = 65537
9
​
10
#--------RSA--------#
11
​
12
phi = (p - 1) * (q - 1)
13
d = inverse(e, phi)
14
​
15
print(d)
Copied!
Easy RSA (Small Modulus)
Solution
The prime factors of modulus
can be easily found with FactorDB . To simplify this process, we could use the factordb-python module.
Implementation
1
#!/usr/bin/env python3
2
from Crypto.Util.number import inverse, long_to_bytes
3
from factordb.factordb import FactorDB
4
​
5
#--------Data--------#
6
​
7
N = 322831561921859
8
e = 23
9
c = 0xdc2eeeb2782c
10
​
11
#--------FactorDB--------#
12
​
13
f = FactorDB(N)
14
f.connect()
15
factors = f.get_factor_list()
16
​
17
#--------RSA Decryption--------#
18
​
19
phi = 1
20
for factor in factors:
21
phi *= factor - 1
22
​
23
d = inverse(e, phi)
24
m = pow(c, d, N)
25
flag = long_to_bytes(m).decode()
26
​
27
print(flag)
Copied!
Medium RSA (Wiener's Attack)
Solution
Note that the
is really large. This is an indication for Wiener's Attack. However, this challenge is even simpler than that: FactorDB knows the prime factors of
.
Implementation
1
#!/usr/bin/env python3
2
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long
3
from Crypto.PublicKey import RSA
4
from factordb.factordb import FactorDB
5
​
6
#--------Data--------#
7
​
8
with open("pubkey.pem","r") as f1, open("flag.enc", "rb") as f2:
9
key = RSA.import_key(f1.read())
10
N = key.n
11
e = key.e
12
c = bytes_to_long(f2.read())
13
print(f"{N = }")
14
print(f"{e = }")
15
print(f"{c = }")
16
​
17
#--------FactorDB--------#
18
​
19
f = FactorDB(N)
20
f.connect()
21
factors = f.get_factor_list()
22
​
23
#--------RSA Decryption--------#
24
​
25
phi = 1
26
for factor in factors:
27
phi *= factor - 1
28
​
29
d = inverse(e, phi)
30
m = pow(c, d, N)
31
flag = long_to_bytes(m)
32
​
33
print(flag)
Copied!
hard RSA (Rabin Cryptosystem)
Solution
We got
in this challenge. There are two possibilities here:
- 1.The message is much smaller than the modulus, so we can simply compute
m = sympy.root(c, 2). - 2.This is a Rabin cryptosystem.
This challenge falls into category 2.
Implementation
1
#!/usr/bin/env python3
2
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long
3
from Crypto.PublicKey import RSA
4
from factordb.factordb import FactorDB
5
​
6
#--------Data--------#
7
​
8
with open("pubkey.pem","r") as f1, open("flag.enc", "rb") as f2:
9
key = RSA.import_key(f1.read())
10
N = key.n
11
e = key.e
12
c = bytes_to_long(f2.read())
13
print(f"{N = }")
14
print(f"{e = }")
15
print(f"{c = }")
16
​
17
#--------FactorDB--------#
18
​
19
f = FactorDB(N)
20
f.connect()
21
factors = f.get_factor_list()
22
​
23
p = factors[0]
24
q = factors[1]
25
​
26
#--------Rabin Cryptosystem--------#
27
​
28
inv_p = inverse(p, q)
29
inv_q = inverse(q, p)
30
​
31
m_p = pow(c, (p + 1) // 4, p)
32
m_q = pow(c, (q + 1) // 4, q)
33
​
34
a = (inv_p * p * m_q + inv_q * q * m_p) % N
35
b = N - int(a)
36
c = (inv_p * p * m_q - inv_q * q * m_p) % N
37
d = N - int(c)
38
​
39
plaintext_list = [a, b, c, d]
40
​
41
for plaintext in plaintext_list:
42
s = str(hex(plaintext))[2:]
43
​
44
# padding with 0
45
if len(s) % 2 != 0:
46
s = "0" + s
47
print(bytes.fromhex(s))
Copied!
very hard RSA (Common Modulus)
Code Review
1
#!/usr/bin/env python
2
​
3
import random
4
​
5
N = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L
6
​
7
def pad_even(x):
8
return ('', '0')[len(x)%2] + x
9
​
10
e1 = 17
11
e2 = 65537
12
​
13
​
14
fi = open('flag.txt','rb')
15
fo1 = open('flag.enc1','wb')
16
fo2 = open('flag.enc2','wb')
17
​
18
​
19
data = fi.read()
20
fi.close()
21
​
22
while (len(data)<512-11):
23
data = chr(random.randint(0,255))+data
24
​
25
data_num = int(data.encode('hex'),16)
26
​
27
encrypt1 = pow(data_num,e1,N)
28
encrypt2 = pow(data_num,e2,N)
29
​
30
​
31
fo1.write(pad_even(format(encrypt1,'x')).decode('hex'))
32
fo2.write(pad_even(format(encrypt2,'x')).decode('hex'))
33
​
34
fo1.close()
35
fo2.close()
Copied!
Solution
Take a look at this snippet:
1
encrypt1 = pow(data_num,e1,N)
2
encrypt2 = pow(data_num,e2,N)
Copied!
Note that same modulus
is used twice. Moreover,
and
are coprime, so this challenge falls into the "common modulus attack" category.
Implementation
1
#!/usr/bin/env python3
2
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long
3
from Crypto.PublicKey import RSA
4
from sympy import gcdex
5
from sys import exit
6
​
7
#--------Data--------#
8
​
9
N = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929
10
e1 = 17
11
e2 = 65537
12
​
13
with open("flag.enc1","rb") as f1, open("flag.enc2", "rb") as f2:
14
c1 = bytes_to_long(f1.read())
15
c2 = bytes_to_long(f2.read())
16
print(f"{c1 = }")
17
print(f"{c2 = }")
18
​
19
#--------Common Modulus--------#
20
​
21
r, s, gcd = gcdex(e1, e2)
22
r = int(r)
23
s = int(s)
24
​
25
# Test if e1 and e2 are coprime
26
if gcd != 1:
27
print("e1 and e2 must be coprime")
28
exit()
29
​
30
m = (pow(c1, r, N) * pow(c2, s, N)) % N
31
flag = long_to_bytes(m)
32
​
33
print(flag)
Copied!
Extremely hard RSA (Low Public Exponent Brute-forcing)
Solution
We have
this time. Since the public exponent is small, brute-force attack is possible. We can try all
(where
is an natural number) until we find a perfect cube. Then the cubic root of
is exactly the plaintext
.
Implementation
1
#!/usr/bin/env python3
2
from Crypto.Util.number import long_to_bytes, bytes_to_long
3
from Crypto.PublicKey import RSA
4
from sympy import integer_nthroot
5
​
6
#--------Data--------#
7
​
8
with open("pubkey.pem","r") as f1, open("flag.enc", "rb") as f2:
9
key = RSA.import_key(f1.read())
10
N = key.n
11
e = key.e
12
c = bytes_to_long(f2.read()
13
print(f"{N = }")
14
print(f"{e = }")
15
print(f"{c = }")
16
​
17
#--------Brute-forcing--------#
18
​
19
while True:
20
# Example: integer_nthroot(16, 2) -> (4, True)
21
# Note that the True or False here is boolean value
22
result = integer_nthroot(c, 3)
23
if result[1]:
24
m = result[0]
25
break
26
c += N
27
​
28
flag = long_to_bytes(m).decode()
29
​
30
print(flag)
Copied!
God Like RSA
Todo!
Last modified 3mo ago
Copy link
Contents
veryeasyRSA (RSA Decryption Algorithm)
Solution
Implementation
Easy RSA (Small Modulus)
Solution
Implementation
Medium RSA (Wiener's Attack)
Solution
Implementation
hard RSA (Rabin Cryptosystem)
Solution
Implementation
very hard RSA (Common Modulus)
Code Review
Solution
Implementation
Extremely hard RSA (Low Public Exponent Brute-forcing)
Solution
Implementation
God Like RSA