Attack by Hastada RSA: Chinese theorem on residues
The Hastad attack is an increase in the previous approach for a case where m^e > n and direct root extraction does not work. Condition: the same message m is encrypted with the same exponent e, but different modules n_1, n_2, ..., n_e.
When one message is a few codetexts
A typical script in crypto CTF tasks: the server sends one flag to several recipients, each with its own public key (n_i, e). If e=3 and we have three pairs (n_1, c_1), (n_2, c_2), (n_3, c_3) – the attack is guaranteed to work.
Mathematics of modular arithmetic cryptography:
c_1 ≡ m^3 (mod n_1)
c_2 ≡ m^3 (mod n_2)
c_3 ≡ m^3 (mod n_3)
According to the Chinese residue theorem (CRT), if the modules are pairwise simple, you can find the only value of x ≡ m^3 (mod n_1 × n_2 × n_3). Since m < each n_i, then m^3 < n_1 × n_2 × n_3. So, x = m^3 without residue - we extract the cubic root and get an open text. Beautiful, right?
Step-by-step disassembly with the code
from sympy.ntheory.modular import crt
from gmpy2 import iroot
moduli = [n1, n2, n3]
remainders = [c1, c2, c3]
# CRT: находим x = m^3 (mod n1*n2*n3)
result = crt(moduli, remainders)
if result is None:
raise ValueError('moduli not coprime')
x, N = result
m, exact = iroot(x, 3)
if exact:
print(bytes.fromhex(hex(int(m))[2:]))
crt of sympy.ntheory.modular accepts the list of modules and balances, returns the general module N and the value x. After – standard root extraction of the third degree.
Nuance: The Hastada attack works for any e, not just for 3. But for e=65537, 65537 pairs (n_i, c_i) will be required - this does not happen on the CTF. According to jorianwoltjer.com, for e=257 and 1024-bit keys, the script works out in about 40 seconds. At competitions usually give e = 3, 5 or 7 that the participants will meet in timing.
Wiener RSA Attack: Continuous Fractions vs. Small d
The Wiener attack exploits the case where the private exhibitor d is too small. Formally: the classic attack (Wiener, 1990) works at d < (1/3) × n^(1/4); the condition q < p < 2q (balanced simple) is used in later boundary refinements. On CTF, this manifests as an unusually large public exponent e – close in length to the module n itself.
Why Big E Means Small D
From the ratio e × d ≡ 1 (mod φ
) it follows that e and d are multiplicative reverses by module φ. If d is small, then e ≈ φ / d, which makes e huge. In the condition of the task, it looks like e with hundreds or thousands of digits – comparable in length to n.
The normal value of e in RSA is 65537 (0x10001). You see an e 256+ byte length, that's a signal to Wiener's attack. Directly red flag.
How does continuous fraction work in cryptoanalysis
Wiener proved that the decomposition of the fraction e/n into a continuous fraction contains d among the suitable fractions (convergents). Recovery algorithm:
Calculate a continuous fraction for e/n.
Select suitable fractions k/d.
For each check: calculate φ = (e × d − 1) / k, then make sure that n is folded into two simple multipliers with the resulting φ.
If the check is passed - d found, the task is solved.
In Python, continuous fractions are calculated through sympy and function continued_fraction_periodic. The finished implementation of the Wiener attack is in the package owiener - after pip install owiener enough to call d = owiener.attack(e, n). The function will return d or None, if d goes beyond the border of Wiener. For automation, RsaCtfTool with a flag is also suitable --attack wiener.
But understanding the mechanism is more important than the instrument. At competitions, the task can be modified - the author will slightly increase d beyond the threshold of the classic Wiener attack, and then an extended version will be required (the Bonet-Durphy attack through the LLL-reduction of the lattices in SageMath). The finished tul will simply say “attack failed” and the manual script can be adapted.
How to recognize the type of attack by the condition of crypto CTF task
The main skill in CTF cryptography for beginners is not the knowledge of all attacks, but the ability to determine the necessary parameters. Here is a summary table I keep in front of my eyes on each CTF:
Sign in condition The attack First action
e=3 (or 5, 7), c much less n Small exhibitor iroot(c, e)
e=3, several pairs (n_i, c_i) Hastad (CRT) crt() + iroot()
e huge, comparable to n Wiener owiener.attack(e, n)
n < 512 bits Factorization FactorDB or yafu
Two different n in one task GCD math.gcd(n1, n2)
Part of the open text is known Coppersmith SageMath small_roots()
e=1 Trivially c = m, decode
Given all except d Standard decryption pow(c, d, n)
Algorithm of actions when meeting with RSA-task:
Read all the data – what is given: n, e, c, p, q, d? What's missing?
Estimate size – e small? e huge? n short? c significantly less n?
Check FactorDB — perhaps the factorization of the RSA module has already been carried out by someone earlier.
Try GCD if multiple modules are given.
Apply the attack from the table.
This algorithm covers about 80% of RSA tasks at entry- and mid-range competitions. The remaining 20% is the Coppersmith attack (requires SageMath), partial key recovery (on jorianwoltjer.com is described as an analysis of a partially edited PEM key through ASN.1-headers) and non-standard author's tasks.
Tools for solving crypto CTF problems
RsaCtfTool: RSA CTF hack automation
RsaCtfTool (github.com/RsaCtfTool/RsaCttTool) is a Python utility with dozens of built-in attacks. The tool automatically goes through vulnerabilities in key generation. Key flags:
--publickey FILE – download the public key from the PEM file
-n N -e E – set the module and the exhibitor manually (integer or 0xhex)
--uncipher C – decrypt the code text
--private – withdraw the private key when successful
--attack ATTACK – indicate a specific attack: wiener, hastads, smallq, small_e and others
Example: python3 RsaCtfTool.py -n 12345... -e 3 --uncipher 6789... --private – goes over attacks and outputs open text. Launch with --attack all drives the whole arsenal.
Restriction (and it is serious): at normal competitions, tasks are designed so that automatic solvers cannot cope. The authors add non-standard modifications - their own padding, custom parameters, combinations of several weaknesses. You need a hand script.
PyCryptodomome, gmpy2 and SageMath
Three libraries for manual cryptanalysis:
PyCryptodomome (pip install pycryptodome>=3.21.0 – earlier versions contain known vulnerabilities, including integer overflow (GHSA-hgg3-g7gr-66r7, fixed in 3.19.1) and side-channel leakage at OAEP decryption (GHSA-j225-cvw7-qrx7, fixed in 3.21.0) — module Crypto.PublicKey.RSA parsit PEM keys and pulls n, e, d. Module Crypto.Util.number contains long_to_bytes and bytes_to_long to convert between numbers and bytes – without them, the calculation of the RSA key is converted into manual hex-juggling.
gmpy2 (pip install gmpy2) – fast arithmetic of large numbers. iroot(x, n) for an integer root and gcd(a, b) for NOD work on orders of magnitude faster than standard Python when working with numbers in 2048+ bit.
SageMath (sagemath.org) is a mathematical system for advanced attacks. Method small_roots() to attack Coppersmith, LLL reduction of bars for Wiener's extended attack is all out of the box. Setting up is pain (especially on Windows), but there is no alternative for lattice attacks.
Typical workflow at competitions: parsing keys through PyCryptodome → computing through gmpy2 → if standard attacks did not work, transition to SageMath. CyberChef for classic ciphers, Python stacks for RSA – this separation saves time on each CTF.
The Hastad attack is an increase in the previous approach for a case where m^e > n and direct root extraction does not work. Condition: the same message m is encrypted with the same exponent e, but different modules n_1, n_2, ..., n_e.
When one message is a few codetexts
A typical script in crypto CTF tasks: the server sends one flag to several recipients, each with its own public key (n_i, e). If e=3 and we have three pairs (n_1, c_1), (n_2, c_2), (n_3, c_3) – the attack is guaranteed to work.
Mathematics of modular arithmetic cryptography:
c_1 ≡ m^3 (mod n_1)
c_2 ≡ m^3 (mod n_2)
c_3 ≡ m^3 (mod n_3)
According to the Chinese residue theorem (CRT), if the modules are pairwise simple, you can find the only value of x ≡ m^3 (mod n_1 × n_2 × n_3). Since m < each n_i, then m^3 < n_1 × n_2 × n_3. So, x = m^3 without residue - we extract the cubic root and get an open text. Beautiful, right?
Step-by-step disassembly with the code
from sympy.ntheory.modular import crt
from gmpy2 import iroot
moduli = [n1, n2, n3]
remainders = [c1, c2, c3]
# CRT: находим x = m^3 (mod n1*n2*n3)
result = crt(moduli, remainders)
if result is None:
raise ValueError('moduli not coprime')
x, N = result
m, exact = iroot(x, 3)
if exact:
print(bytes.fromhex(hex(int(m))[2:]))
crt of sympy.ntheory.modular accepts the list of modules and balances, returns the general module N and the value x. After – standard root extraction of the third degree.
Nuance: The Hastada attack works for any e, not just for 3. But for e=65537, 65537 pairs (n_i, c_i) will be required - this does not happen on the CTF. According to jorianwoltjer.com, for e=257 and 1024-bit keys, the script works out in about 40 seconds. At competitions usually give e = 3, 5 or 7 that the participants will meet in timing.
Wiener RSA Attack: Continuous Fractions vs. Small d
The Wiener attack exploits the case where the private exhibitor d is too small. Formally: the classic attack (Wiener, 1990) works at d < (1/3) × n^(1/4); the condition q < p < 2q (balanced simple) is used in later boundary refinements. On CTF, this manifests as an unusually large public exponent e – close in length to the module n itself.
Why Big E Means Small D
From the ratio e × d ≡ 1 (mod φ
) it follows that e and d are multiplicative reverses by module φ. If d is small, then e ≈ φ / d, which makes e huge. In the condition of the task, it looks like e with hundreds or thousands of digits – comparable in length to n.The normal value of e in RSA is 65537 (0x10001). You see an e 256+ byte length, that's a signal to Wiener's attack. Directly red flag.
How does continuous fraction work in cryptoanalysis
Wiener proved that the decomposition of the fraction e/n into a continuous fraction contains d among the suitable fractions (convergents). Recovery algorithm:
Calculate a continuous fraction for e/n.
Select suitable fractions k/d.
For each check: calculate φ
= (e × d − 1) / k, then make sure that n is folded into two simple multipliers with the resulting φ.If the check is passed - d found, the task is solved.
In Python, continuous fractions are calculated through sympy and function continued_fraction_periodic. The finished implementation of the Wiener attack is in the package owiener - after pip install owiener enough to call d = owiener.attack(e, n). The function will return d or None, if d goes beyond the border of Wiener. For automation, RsaCtfTool with a flag is also suitable --attack wiener.
But understanding the mechanism is more important than the instrument. At competitions, the task can be modified - the author will slightly increase d beyond the threshold of the classic Wiener attack, and then an extended version will be required (the Bonet-Durphy attack through the LLL-reduction of the lattices in SageMath). The finished tul will simply say “attack failed” and the manual script can be adapted.
How to recognize the type of attack by the condition of crypto CTF task
The main skill in CTF cryptography for beginners is not the knowledge of all attacks, but the ability to determine the necessary parameters. Here is a summary table I keep in front of my eyes on each CTF:
Sign in condition The attack First action
e=3 (or 5, 7), c much less n Small exhibitor iroot(c, e)
e=3, several pairs (n_i, c_i) Hastad (CRT) crt() + iroot()
e huge, comparable to n Wiener owiener.attack(e, n)
n < 512 bits Factorization FactorDB or yafu
Two different n in one task GCD math.gcd(n1, n2)
Part of the open text is known Coppersmith SageMath small_roots()
e=1 Trivially c = m, decode
Given all except d Standard decryption pow(c, d, n)
Algorithm of actions when meeting with RSA-task:
Read all the data – what is given: n, e, c, p, q, d? What's missing?
Estimate size – e small? e huge? n short? c significantly less n?
Check FactorDB — perhaps the factorization of the RSA module has already been carried out by someone earlier.
Try GCD if multiple modules are given.
Apply the attack from the table.
This algorithm covers about 80% of RSA tasks at entry- and mid-range competitions. The remaining 20% is the Coppersmith attack (requires SageMath), partial key recovery (on jorianwoltjer.com is described as an analysis of a partially edited PEM key through ASN.1-headers) and non-standard author's tasks.
Tools for solving crypto CTF problems
RsaCtfTool: RSA CTF hack automation
RsaCtfTool (github.com/RsaCtfTool/RsaCttTool) is a Python utility with dozens of built-in attacks. The tool automatically goes through vulnerabilities in key generation. Key flags:
--publickey FILE – download the public key from the PEM file
-n N -e E – set the module and the exhibitor manually (integer or 0xhex)
--uncipher C – decrypt the code text
--private – withdraw the private key when successful
--attack ATTACK – indicate a specific attack: wiener, hastads, smallq, small_e and others
Example: python3 RsaCtfTool.py -n 12345... -e 3 --uncipher 6789... --private – goes over attacks and outputs open text. Launch with --attack all drives the whole arsenal.
Restriction (and it is serious): at normal competitions, tasks are designed so that automatic solvers cannot cope. The authors add non-standard modifications - their own padding, custom parameters, combinations of several weaknesses. You need a hand script.
PyCryptodomome, gmpy2 and SageMath
Three libraries for manual cryptanalysis:
PyCryptodomome (pip install pycryptodome>=3.21.0 – earlier versions contain known vulnerabilities, including integer overflow (GHSA-hgg3-g7gr-66r7, fixed in 3.19.1) and side-channel leakage at OAEP decryption (GHSA-j225-cvw7-qrx7, fixed in 3.21.0) — module Crypto.PublicKey.RSA parsit PEM keys and pulls n, e, d. Module Crypto.Util.number contains long_to_bytes and bytes_to_long to convert between numbers and bytes – without them, the calculation of the RSA key is converted into manual hex-juggling.
gmpy2 (pip install gmpy2) – fast arithmetic of large numbers. iroot(x, n) for an integer root and gcd(a, b) for NOD work on orders of magnitude faster than standard Python when working with numbers in 2048+ bit.
SageMath (sagemath.org) is a mathematical system for advanced attacks. Method small_roots() to attack Coppersmith, LLL reduction of bars for Wiener's extended attack is all out of the box. Setting up is pain (especially on Windows), but there is no alternative for lattice attacks.
Typical workflow at competitions: parsing keys through PyCryptodome → computing through gmpy2 → if standard attacks did not work, transition to SageMath. CyberChef for classic ciphers, Python stacks for RSA – this separation saves time on each CTF.
