# Jarvis OJ Crypto RSA Series

{% embed url="<https://www.jarvisoj.com>" %}
Jarvis OJ
{% endembed %}

## veryeasyRSA (RSA Decryption Algorithm)

### Solution

Since $$p$$ and $$q$$ are given, we could decrypt the message directly with the RSA decryption algorithm.

### Implementation

```python
#!/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](http://factordb.com/) . To simplify this process, we could use the [factordb-python](https://github.com/ryosan-470/factordb-python) module.

### Implementation

```python
#!/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

```python
#!/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

```python
#!/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

```python
#!/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

```python
#!/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

```python
#!/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!


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ret2basic.gitbook.io/ctfwriteup/web2-ctf/jarvis-oj-crypto-rsa-series.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.