ctfwriteup.com
Search
K

# Jarvis OJ Crypto RSA Series

{"author": ["ret2basic"]}
Jarvis OJ
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:
N = key.n
e = key.e
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. 1.
The message is much smaller than the modulus, so we can simply compute m = sympy.root(c, 2).
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:
N = key.n
e = key.e
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:]
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
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')
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.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--------#
e1 = 17
e2 = 65537
with open("flag.enc1","rb") as f1, open("flag.enc2", "rb") as f2:
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:
N = key.n
e = key.e
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!