There are many RSA attacks, I will write about the solutions of common attacks about RSA

# Small N or known factor

For N (modulus) that is small can use a website that collect factors of all numbers: factordb, or can download yafu to factorize the modulus on your own machine, or can use this webiste: Integer factorization calculator

Once you found the factors then you can calculate d (private key) to decrypt the message

# N with 3 more primes

Modulus with 3 or more primes are easy to factorize, therefore can use the website I mentioned previously to find the factors

Then find the $$\phi(n)$$ by multiply all factors-1 together

For example if N with 3 primes:

$N=pqr$ $\phi(N)=(p-1)(q-1)(r-1)$

# Small e

## Case $$m^e < N$$

If e is small and $$m^e < N$$ (message less then modulus) then we can calculate the root of the encrypted message c because $$m^e$$ is not large enough

For example, when $$e=3$$:

$N=11 \times 13=143$ $e=3$ $m=4$ $c \equiv m^e \mod N$ $c= m^e = 64$ $m=\sqrt[3]{64}=4$

In the example above, we can calculate the cube root of the c cipher text to get the message

## Case $$m^e > N$$

If e is small but $$m^e > N$$ and we need to brute force the number of k, where $$m=\sqrt[e]{c+kN}$$, if k is small we can calculate m in a short amount of time

For example, when $$e=3$$:

$N=11 \times 13=143$ $e=3$ $m=7$ $c \equiv m^e \mod N$ $\equiv 7^3 \mod 143$ $\equiv 57$ $m=\sqrt[3]{57+(2\times 143)}$ $=\sqrt[3]{343}$ $=7$

In the example above, we use k=2 to calculate the cube root of c+kN to get the message

# Large e or small d

If e is large, may indicates d to be small

We can use Wiener’s attack or Boneh Durfee which is extension of wiener’s attack

Wiener’s Attack only works when $$d<\frac{1}{3}\sqrt[4]{N}$$ and Boneh Durfee works when $$d < N^{0.292}$$

If we have multiple cipher text c with different modulus N, and number of cipher text equals e then it may vulnerable to Håstad Broadcast Attack!

For example when $$e=3$$, with 3 different modulus $$n1,n2,n3$$ and all use same e to encrypt:

$c_1\equiv m^3 \mod n_1$ $c_2\equiv m^3 \mod n_2$ $c_3\equiv m^3 \mod n_3$

Then we can use the Chinese Remainder Theorm to calculate $$m^3$$ where $$m^3\equiv C \mod n_1n_2n_3$$, then calculate cube root to get m: $$\sqrt[3]{C}=m$$

Tutorial for CRT

Can look at the implementation on sage

Note: all modulus should be coprime to each other, if not then we can factorize N and calculate d

# Close Prime

If both primes are very close (or half high bits is same), we can use Fermat Factorization Method

The closer the prime the faster the factorize process

## Code implementation

• https://www.geeksforgeeks.org/fermats-factorization-method/
• https://facthacks.cr.yp.to/fermat.html

# Known High Bits

If we known >=50% high bits of a factor of N, we can calculate the remaining bits using coppersmith method (More details here)

## Code implementation

• https://github.com/mimoo/RSA-and-LLL-attacks#factoring-with-high-bits-known

Example sage code implemented in starCTF:

from Crypto.Util.number import *
PR.<x> = PolynomialRing(Zmod(n))
f=x+p
roots=f.small_roots(X=2**430,beta=0.4)
p=int(p+roots[0])
assert n%p==0
q = n//p
phi = (p-1)*(q-1)
d = inverse(65537, phi)
print(long_to_bytes(pow(c,d,n)))
# b'*CTF{St.Diana_pls_take_me_with_you!}'


# Known partial bits

If know the partial bits of p, we can recover the corresponding bits of q by calculate the modular inverse and divide N

For example: $p=????1111_2$ $q=1011????_2$ $n=34189$ $pq\equiv n \mod 2^4$ $q\equiv np^{-1} \mod 2^4$ $15\equiv p^{-1} \mod 2^4$ $34189(15)\equiv q \mod 2^4$ $q\equiv 512835 \mod 2^4$ $\equiv 3 \mod 2^4$ $\equiv 0011_2 \mod 2^4$ $q=10110011_2=179$

The example above shown when we know low bits of p but not q, we can calculate $$p^{-1} \mod 2^k$$ (modular inverse) then multiply by $$N \mod 2^k$$ we can get the low bit of q too

Example CTF writeup from HSCTF

Note: This only works when the modular inverse exists