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

Attacks

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}\)

Broadcast Attack

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 *
n = 0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
p = 0xf376c68d76f4ab9b4d247852ef07159a09eeac920ac89148a8dee4f3c359a291b6bf03ab9258ca64783c416fcfeade13cf3c18a7677c29283c7fc6bfcdbba1d6fecbe9e243cc2e3ef0fe60035e1dbc727f3522bfab2bc28d5e29bfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
c = 0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1
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

See also

  • https://ctf-wiki.org/crypto/asymmetric/rsa/rsa_theory/
  • https://hal.archives-ouvertes.fr/hal-03045663/document
  • https://medium.com/@hva314/some-basic-rsa-challenges-in-ctf-part-2-applying-theoretical-attack-55a2cc7baa11
  • https://blog.csdn.net/q851579181q/article/details/90645041