## Factorize the module
One of the best known algorithms is the **General Number Field Sieve** (**GNFS**), [cado-nfs](https://gitlab.inria.fr/cado-nfs/cado-nfs).
Use Online Database: [factor.db](http://www.factordb.com/) e tool [YAFU](https://github.com/DarkenCode/yafu).
## Common Prime Attack
`N1 = p * q` and `N2 = p * r`
`p = GCD(N1, N2)`
`q = N1 / p` and `r = N2 / p`
## Common Modules Attack
**Bézout's identity**: Let `a` and `b` be integers with `gcd(a,b) = d`. Then there exist two integers `x` and `y` such that `ax + by = d`.
`(N, e1)` and `(N, e2)` with `gcd(e1, e2) = 1` and same `M`
`gcd, x, y = extended_euclidean(e1, e2)`\
`C1^x * C2^y mod n = M`
**`Note!`** That this can be a problem even with `GCD(e1,e2) > 1` but small! (Low exponent Attack)
## Oracles
### Modulus Recovery
`Scenario`: We have an oracle that encrypts with a secret key.
From [HERE](https://github.com/ashutosh1206/Crypton/blob/master/RSA-encryption/Attack-Retrieve-Modulus/README.md), we can recover the modulus N like this:
* Encrypt `x` and `y`
* Based on the fact that the standard `e = 65537` and noting that `x^e - Enc(x)` is a multiple of N: `gcd(x^e - Enc(x), y^e - Enc(y))` to find small multiples of N (or even N).
* Repeat with different values if necessary.
{% code overflow="wrap" %}
```python
def extractmod_eunknown(_encrypt, limit=4):
try:
assert limit <= 4
except AssertionError:
print("[+] Limit too big!")
return -1
try:
m_list = [2, 3, 5, 7]
ct_list = [_encrypt(m_list[i]**2) for i in range(limit)]
ct_list2 = [_encrypt(m_list[i]) for i in range(limit)]
assert len(ct_list) == len(ct_list2)
mod_list = [(ct_list2[i]**2 - ct_list[i]) for i in range(limit)]
_gcd = mod_list[0]
for i in mod_list:
_gcd = GCD(_gcd, i)
return _gcd
except Exception as ex:
print("[+] Exception: ", ex)
```
{% endcode %}
### Homomorphic properties
`Scenario`: We have an oracle that does not allow decryption of messages containing sensitive information.
* Create `C = x^e * c mod N`
* Get the decryption of `C = P’`
* `P’ = x * c^e` → `c^e = P’ * x^-1`
**`Note!`** Fractions for `x mod n` “make sense” in modular arithmetic, as long as `x` is coprime with `n`.
### LSB
`Scenario`: We have an oracle that performs partial decryption of messages, ex. returns only the Least Significant Bit.
The idea is to perform a “binary search” on the answer using the fact that N is odd.\
We decrypt `2^e * c` → `2m`:\
\&#xNAN;**`= 1`** → `N/2 < m < N` (is located in the second half)\
\&#xNAN;**`= 0`** → `0 < m < N/2` (is located in the first half)\
At this point just repeat with `4^e * c`, `8^e * c`, etc. for 𝑙𝑜𝑔2 𝑁 times (dichotomous search, binary search)
{% code overflow="wrap" %}
```python
LB = 0
UB = n
for i in range(int(math.log(n, 2))): # add to increase precision
if ( pow(2**i, e, N)*ENCFLAG %2 == 0):
UB = (UB + LB)/2;
else:
LB = (UB + LB)/2;
print((UB + LB)/2)
```
{% endcode %}
### Padding
* Coppermith's attack against short padding schemes (1997)
* Bleichenbacher's attack against PKCS#1 v1.5 (1998)
* Manger's attack against PKCS#1 v2.0 (2001)
## Low Public Exponent Attack
If a small exponent is used (ex. `e = 3`) and the message is relatively short (ex. `< 𝑙𝑜𝑔2 𝑁 / 3`) then the modulus has no effect and decrypting the message is trivial.
## Common Low Public Exponent Attack
If we have `X` parts with different RSA keys but the same exponent, and we have the encryption of the same message without padding, then it is possible to trace the message through the Chinese Remainder Theorem and the application of a root. It is important, however, that the parts are equal to the exponent: `X` = `e`
`(N1, e)` `(N2, e)` `(N3, e)`
If `N1`, `N2`, `N3` are coprime, then we can trace `m^3 mod N1*N2*N3`, and hence `m`. If, on the other hand, `N1`, `N2`, `N3` are not coprime, then we can find the gcd between them, break a key, and find the message.
## Low Private Exponent Attack
A large value of `e` (how much `N`) suggests a low value of `d`.
**`Wiener's Attack`**. **`Boneh-Durfee Attack`**.
If `3 * d < N^(1/4)` then `d` can be efficiently recovered. \
`d < N^0.292`
The details of this attack are tedious.
## Prime close to each other
`p = a + b` and `q = a - b`\
`N = (a + b)(a - b) = a^2 * b^2`\
`b^2 = a^2 - N`
If `b` is small enough, we can perform brute force on `a` or `b` to get the factorization.\
This is done through Fermat's factorization method, inplemented in YAFU as the “fermat” function.
{% code overflow="wrap" %}
```python
import gmpy2
def fermat_factorization(n):
a = gmpy2.isqrt(n)
b2 = gmpy2.square(a) - n
while not gmpy2.is_square(b2):
a += 1
b2 = gmpy2.square(a) - n
p = a + gmpy2.isqrt(b2)
q = a - gmpy2.isqrt(b2)
return p, q
```
{% endcode %}
## Franklin–Reiter related-message attack
This attack works in a scenario where two messages differ only by a known fixed difference and are encrypted using the public key and the same module N.
An example might be using a known padding of a and b
$$
cipher\ =\ (a\*m+b)^e\ mod\ n
$$
Code Attack 1
{% code overflow="wrap" %}
```python
import sys
sys.path.append("/Library/Frameworks/Python.framework/Versions/3.11/lib/python3.11/site-packages/")
from sage.all import *
def gcd(a, b):
while b:
a, b = b, a % b
return a.monic()
def franklin(n, pad1, pad2, c1, c2, a1, a2):
R. = PolynomialRing(Zmod(n))
f1 = (a1*X + pad1)^257 - c1
f2 = (a2*X + pad2)^257 - c2
return -gcd(f1, f2).coefficients()[0]
result = franklin(n, b1, b2, ct1, ct2, a1, a2)
```
{% endcode %}
Code Attack 2
{% code overflow="wrap" %}
```python
import sys
sys.path.append("/Library/Frameworks/Python.framework/Versions/3.11/lib/python3.11/site-packages/")
from sage.all import *
def gcd(a, b):
while b:
a, b = b, a % b
return a.monic()
def franklin(n, pad1, pad2, c1, c2):
R. = PolynomialRing(Zmod(n))
f1 = (X + pad1)^3 - c1
f2 = (X + pad2)^3 - c2
return -gcd(f1, f2).coefficients()[0]
result = franklin(n, b1, b2, ct1, ct2, a1, a2)
```
{% endcode %}
## Coppersmith attack (partial know message)
---
# 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://ivalexev.gitbook.io/rednote/pentesting-process/crypto-attacks/rsa.md?ask=
```
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.