Jarvis OJ Crypto RSA Series
{"author": ["ret2basic"]}

veryeasyRSA (RSA Decryption Algorithm)

Analysis

Since
pp
and
qq
are given, we could decrypt the message directly with the RSA decryption algorithm.

Exploit

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)

Analysis

The prime factors of modulus
NN
can be easily found with FactorDB . To simplify this process, we could use the factordb-python module.

Exploit

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)

Analysis

Note that the
ee
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
NN
.

Exploit

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)

Analysis

We got
e=2e = 2
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.

Exploit

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)

Source Code

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!

Analysis

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
NN
is used twice. Moreover,
e1e_1
and
e2e_2
are coprime, so this challenge falls into the "common modulus attack" category.

Exploit

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)

Analysis

We have
e=3e = 3
this time. Since the public exponent is small, brute-force attack is possible. We can try all
c+kNc + k * N
(where
kk
is an natural number) until we find a perfect cube. Then the cubic root of
c+kNc + k * N
is exactly the plaintext
mm
.

Exploit

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 6mo ago