Jarvis OJ Crypto RSA Series
{"author": ["ret2basic"]}
Jarvis OJ
Jarvis OJ
Since
and
are given, we could decrypt the message directly with the RSA decryption algorithm.
#!/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)
The prime factors of modulus
can be easily found with FactorDB . To simplify this process, we could use the factordb-python module.
#!/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)
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
.
#!/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)
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.
#!/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))
#!/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()
Take a look at this snippet:
encrypt1 = pow(data_num,e1,N)
encrypt2 = pow(data_num,e2,N)
Note that same modulus
is used twice. Moreover,
and
are coprime, so this challenge falls into the "common modulus attack" category.
#!/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)
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
.
#!/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)
Todo!
Last modified 11mo ago