Jarvis OJ Crypto RSA Series

Jarvis OJ
Jarvis OJ
veryeasyRSA (RSA Decryption Algorithm)
Solution
Since ppp
 and qqq
 are given, we could decrypt the message directly with the RSA decryption algorithm.
Implementation
#!/usr/bin/env python3
from Crypto.Util.number import inverse
​
#--------Data--------#
​
p = 3487583947589437589237958723892346254777 
q = 8767867843568934765983476584376578389
e = 65537
​
#--------RSA--------#
​
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
​
print(d)
Easy RSA (Small Modulus)
Solution
The prime factors of modulus NNN
 can be easily found with FactorDB . To simplify this process, we could use the factordb-python module.
Implementation
#!/usr/bin/env python3
from Crypto.Util.number import inverse, long_to_bytes
from factordb.factordb import FactorDB
​
#--------Data--------#
​
N = 322831561921859
e = 23
c = 0xdc2eeeb2782c
​
#--------FactorDB--------#
​
f = FactorDB(N)
f.connect()
factors = f.get_factor_list()
​
#--------RSA Decryption--------#
​
phi = 1
for factor in factors:
    phi *= factor - 1
​
d = inverse(e, phi)
m = pow(c, d, N)
flag = long_to_bytes(m).decode()
​
print(flag)
Medium RSA (Wiener's Attack)
Solution
Note that the eee
 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 NNN
.
Implementation
#!/usr/bin/env python3
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long
from Crypto.PublicKey import RSA
from factordb.factordb import FactorDB
​
#--------Data--------#
​
with open("pubkey.pem","r") as f1, open("flag.enc", "rb") as f2:
    key = RSA.import_key(f1.read())
    N = key.n
    e = key.e
    c = bytes_to_long(f2.read())
    print(f"{N = }")
    print(f"{e = }")
    print(f"{c = }")
​
#--------FactorDB--------#
​
f = FactorDB(N)
f.connect()
factors = f.get_factor_list()
​
#--------RSA Decryption--------#
​
phi = 1
for factor in factors:
    phi *= factor - 1
​
d = inverse(e, phi)
m = pow(c, d, N)
flag = long_to_bytes(m)
​
print(flag)
hard RSA (Rabin Cryptosystem)
Solution
We got e=2e = 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.
Implementation
#!/usr/bin/env python3
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long
from Crypto.PublicKey import RSA
from factordb.factordb import FactorDB
​
#--------Data--------#
​
with open("pubkey.pem","r") as f1, open("flag.enc", "rb") as f2:
    key = RSA.import_key(f1.read())
    N = key.n
    e = key.e
    c = bytes_to_long(f2.read())
    print(f"{N = }")
    print(f"{e = }")
    print(f"{c = }")
​
#--------FactorDB--------#
​
f = FactorDB(N)
f.connect()
factors = f.get_factor_list()
​
p = factors[0]
q = factors[1]
​
#--------Rabin Cryptosystem--------#
​
inv_p = inverse(p, q)
inv_q = inverse(q, p)
​
m_p = pow(c, (p + 1) // 4, p)
m_q = pow(c, (q + 1) // 4, q)
​
a = (inv_p * p * m_q + inv_q * q * m_p) % N
b = N - int(a)
c = (inv_p * p * m_q - inv_q * q * m_p) % N
d = N - int(c)
​
plaintext_list = [a, b, c, d]
​
for plaintext in plaintext_list:
    s = str(hex(plaintext))[2:]
​
    # padding with 0
    if len(s) % 2 != 0:
        s = "0" + s
    print(bytes.fromhex(s))
very hard RSA (Common Modulus)
Code Review
#!/usr/bin/env python
​
import random
​
N = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L
​
def pad_even(x):
    return ('', '0')[len(x)%2] + x
​
e1 = 17
e2 = 65537
​
​
fi = open('flag.txt','rb')
fo1 = open('flag.enc1','wb')
fo2 = open('flag.enc2','wb')
​
​
data = fi.read()
fi.close()
​
while (len(data)<512-11):
    data  =  chr(random.randint(0,255))+data
​
data_num = int(data.encode('hex'),16)
​
encrypt1 = pow(data_num,e1,N)
encrypt2 = pow(data_num,e2,N)
​
​
fo1.write(pad_even(format(encrypt1,'x')).decode('hex'))
fo2.write(pad_even(format(encrypt2,'x')).decode('hex'))
​
fo1.close()
fo2.close()
Solution
Take a look at this snippet:
encrypt1 = pow(data_num,e1,N)
encrypt2 = pow(data_num,e2,N)
Note that same modulus NNN
 is used twice. Moreover, e1e_1e1​
 and e2e_2e2​
 are coprime, so this challenge falls into the "common modulus attack" category.
Implementation
#!/usr/bin/env python3
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long
from Crypto.PublicKey import RSA
from sympy import gcdex
from sys import exit
​
#--------Data--------#
​
N = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929
e1 = 17
e2 = 65537
​
with open("flag.enc1","rb") as f1, open("flag.enc2", "rb") as f2:
    c1 = bytes_to_long(f1.read())
    c2 = bytes_to_long(f2.read())
    print(f"{c1 = }")
    print(f"{c2 = }")
​
#--------Common Modulus--------#
​
r, s, gcd = gcdex(e1, e2)
r = int(r)
s = int(s)
​
# Test if e1 and e2 are coprime
if gcd != 1:
    print("e1 and e2 must be coprime")
    exit()
​
m = (pow(c1, r, N) * pow(c2, s, N)) % N
flag = long_to_bytes(m)
​
print(flag)
Extremely hard RSA (Low Public Exponent Brute-forcing)
Solution
We have e=3e = 3e=3
 this time. Since the public exponent is small, brute-force attack is possible. We can try all c+k∗Nc + k * Nc+k∗N
 (where kkk
 is an natural number) until we find a perfect cube. Then the cubic root of c+k∗Nc + k * Nc+k∗N
 is exactly the plaintext mmm
.
Implementation
#!/usr/bin/env python3
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.PublicKey import RSA
from sympy import integer_nthroot
​
#--------Data--------#
​
with open("pubkey.pem","r") as f1, open("flag.enc", "rb") as f2:
    key = RSA.import_key(f1.read())
    N = key.n
    e = key.e
    c = bytes_to_long(f2.read()
    print(f"{N = }")
    print(f"{e = }")
    print(f"{c = }")
​
#--------Brute-forcing--------#
​
while True:
    # Example: integer_nthroot(16, 2) -> (4, True)
    # Note that the True or False here is boolean value
    result = integer_nthroot(c, 3)
    if result[1]:
        m = result[0]
        break
    c += N
​
flag = long_to_bytes(m).decode()
​
print(flag)
God Like RSA
Todo!
Pwn - Previous
Jarvis OJ Pwn Xman Series
Next - picoCTF
picoCTF 2020 Mini-Competition
Last modified 4mo ago