✅Jarvis OJ Crypto RSA Series

桃李如旧识www.jarvisoj.com

Jarvis OJ

veryeasyRSA (RSA Decryption Algorithm)

Solution

Since $p$ and $q$ 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 $N$ 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 $e$ 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 $N$.

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 = 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 $N$ is used twice. Moreover, $e_1$ and $e_2$ 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 = 3$ this time. Since the public exponent is small, brute-force attack is possible. We can try all $c + k * N$ (where $k$ is an natural number) until we find a perfect cube. Then the cubic root of $c + k * N$ is exactly the plaintext $m$.

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!