Introduction
In CTF competitions, the RSA encryption system is a very common examination point. Because the RSA encryption and decryption algorithm is based on number theory problems, if not designed properly, it can easily lead to vulnerabilities that allow plaintext to be leaked. This article summarizes common exploitation scenarios and code analysis for CTF-RSA, providing references for learning and teaching.
01 Introduction to RSA Algorithm
RSA is an asymmetric encryption algorithm proposed by Ron Rivest, Adi Shamir, and Leonard Adleman in 1977, hence the name RSA. It is widely used in data encryption, digital signatures, public key infrastructure (PKI), and other security scenarios, making it one of the most classic and important algorithms in cryptography.
1.1 Basic Principles
Select two large prime numbers p and q, and calculate the modulus n = p * q
Calculate Euler’s totient function φ(n) = (p-1)(q-1)
Select a public key exponent e that is coprime to φ(n) (1< e <φ(n))
02 Common Attack Points for CTF-RSA
The main flaws of RSA usually stem from improper implementation or usage, rather than errors in the algorithm itself. Below are common attack points for CTF-RSA.
2.1 Modulus Factorization
2.1.1 Scenario
During RSA key generation, the modulus n = p * q can be factored into its prime factors p and q through brute force or rapid factorization. Common reasons include:
|
1 |
Prime factors are too small |
|
2 |
p and q are too close in value |
|
3 |
Unsafe random number generator, leading to repeated or predictable prime factors |
2.1.2 Principle
The security of RSA is based on the difficulty of factoring large integers. Once an attacker successfully factors the two prime factors p and q of n, they can compute the private key exponent d using Euler’s function φ(n) = (p-1)(q-1), thus completing the decryption.
Typical tools: yafu, msieve, factordb.
2.1.3 Analysis Script
from factordb.factordb import FactorDB
n = # Modulus n
def factor_and_compute_phi(n):
# Connect to FactorDB to query the factorization of n
fdb = FactorDB(n)
fdb.connect() # Establish connection
# Get the list of factors
factors = fdb.get_factor_list()
# If no factors are obtained, raise an exception
if not factors:
raise ValueError("Failed to obtain factors from FactorDB")
print(f"Modulus n = {n}")
print("Factors:")
for idx, factor in enumerate(factors, 1):
print(f" Factor {idx}: {factor}")
# Calculate Euler's function φ(n)
phi = 1
for p in factors:
phi *= (p - 1)
print(f"Euler's function φ(n) = {phi}")
# Return the list of factors and φ(n)
return factors, phi
# Main entry point
if __name__ == "__main__":
# Call the function to factor and compute Euler's function
factor_list, phi_n = factor_and_compute_phi(n)2.2 Common Modulus Attack
2.2.1 Scenario
The same plaintext message m is encrypted using different public key exponents e, sharing the modulus n.
2.2.2 Principle
2.2.3 Analysis Script
import libnum
import gmpy2
n = # Modulus n
e1 = # Public key exponent e1
e2 = # Public key exponent e2
c1 = # Ciphertext c1 obtained from e1 encryption
c2 = # Ciphertext c2 obtained from e2 encryption
# Common modulus attack main function
def common_modulus_attack(e1, e2, c1, c2, n):
g, s1, s2 = gmpy2.gcdext(e1, e2) # Use extended Euclidean algorithm to find g = gcd(e1, e2), and integers s1, s2 such that s1*e1 + s2*e2 = g
assert g == 1 # Ensure e1 and e2 are coprime, otherwise the attack cannot proceed (i.e., must satisfy g=1)
# If s1 is negative, need to take the modular inverse of c1 to convert to positive exponentiation
if s1 < 0:
c1 = gmpy2.invert(c1, n) s1 = -s1
# Similarly, handle the case where s2 is negative
if s2 < 0:
c2 = gmpy2.invert(c2, n) s2 = -s2
# Calculate plaintext m: m = pow(c1, s1, n) * pow(c2, s2, n) % n
return int(m) # Return plaintext m as an integer
# Call common modulus attack function to get plaintext in integer form
m = common_modulus_attack(e1, e2, c1, c2, n)
print("m：", m) # Use libnum to convert integer m to original string (decoded in ASCII)
flag_bytes = libnum.n2s(m)
# Output the final recovered plaintext (e.g., flag), decoded as UTF-8, ignoring illegal characters
print("Recovered plaintext：", flag_bytes.decode('utf-8', errors='ignore')2.3 Low Exponent Attack
2.3.1 Scenario
The RSA encryption uses a public key exponent e that is too small (e.g., 3, 5, 7), and the encrypted message m is not large enough.
2.3.2 Principle
2.3.3 Analysis Script
import libnum
import gmpy2
e = # Public key exponent e
n = # Modulus n
c = # Ciphertext
# Low exponent attack function
def low_exponent_attack(n, e, c):
k = 0 # Initialize a counter variable k, representing the number of attempts
while True: # Infinite loop until a solution is found or the limit is reached
m1 = k * n + c # Construct m1 = me = c + k * n (me ≡ c mod n)
m, exact = gmpy2.iroot(m1, e) # Attempt to take the e-th root, returning (root value, whether it is an integer root)
if exact: # If the root result is an integer (i.e., me = m1 holds)
print(f"Found k: {k}")
print(f"Decrypted m: {m}")
print(f"Flag: {libnum.n2s(int(m))}")
break # Exit the loop after finding the plaintext
k += 1 # If not found, continue to the next k
if k > 100000: # Set a maximum number of attempts to avoid infinite loops
print("No solution found for k < 100000")
break
# Execute attack function
low_exponent_attack(n, e, c)2.4 Chinese Remainder Theorem
The modulus n of RSA is obtained by multiplying two large prime numbers p and q. If an attacker already knows the ciphertext c modulo p and c modulo q, and knows p and q, they can use the Chinese Remainder Theorem (CRT) to recover the ciphertext c, and thus decrypt the plaintext m.
2.4.1 Principle
The Chinese Remainder Theorem is a mathematical method for solving systems of congruences. It provides a way to recover unknowns through known congruences with multiple moduli. In RSA, the decryption task can be broken down into decrypting modulo p and modulo q, obtaining mp and mq respectively, and then combining the two results using CRT to obtain the original ciphertext c.
2.4.2 Analysis Script
# Implementation of the Chinese Remainder Theorem (CRT)
def CRT(aList, mList):
M = 1
for mod in mList:
M *= mod # Calculate the product of the moduli
x = 0
for ai, mi in zip(aList, mList):
Mi = M // mi # M divided by the current modulus
Mi_inverse = gmpy2.invert(Mi, mi) # Find the inverse of Mi with respect to the current modulus
x += ai * Mi * Mi_inverse # Update the value of the solution
return x % M # Result modulo M
if __name__ == "__main__":
cList = [c_mod_p, c_mod_q] # Pass in c mod p and c mod q
nList = [p, q] # Pass in p and q
c = CRT(cList, nList) # Combine to obtain c using CRT2.5 Low Encryption Broadcast Attack
2.5.1 Scenario
The same plaintext message m is encrypted using the same public key exponent e and multiple different moduli (n1, n2, n3, …). If the attacker can collect enough ciphertexts, they can launch a low encryption broadcast attack.
2.5.2 Principle
After intercepting multiple ciphertexts, the attacker can use the Chinese Remainder Theorem (CRT) to combine these ciphertexts, obtaining a combined equation regarding the original plaintext m:
2.5.3 Analysis Script
import libnum
import gmpy2
e = # Public key exponent e
n = [n1, n2, n3] # List of moduli
c = [c1, c2, c3] # List of ciphertexts
def rsa_gb_def(c, n, e):
m1 = libnum.solve_crt(c, n) # solve_crt() method returns the solution of the Chinese Remainder Theorem, here m1 is the combined value
m, s = gmpy2.iroot(m1, e) # iroot() calculates the e-th root of m1 and checks if it is an integer. s is a boolean indicating whether there is an integer solution
m = int(m) # Convert m to an integer, removing the decimal part
return m # Return the recovered plaintext integer m
m = rsa_gb_def(c, n, e)
print(libnum.n2s(m))2.6 Private Key Information Leakage dp or dq
2.6.1 Scenario
In the RSA encryption system, if part of the private key information is leaked, such as dp = d mod (p-1), the attacker can use this partial information to mathematically derive the complete private key.
2.6.2 Principle
According to dp = d mod (p-1), we know: d = k * (p−1) + dp (k is an integer).
To deduce p from dp, we need to utilize the relationship between dp and e, which can be derived from the RSA algorithm: d * e ≡ 1 mod (p−1).
Thus, we have: (k * (p−1) + dp) * e ≡ 1 mod (p−1)
⇒ dp * e ≡ 1 mod (p−1)
⇒ p = (dp * e – 1) // i + 1 (i is an integer)
2.6.3 Analysis Script
import gmpy2
from Crypto.Util.number import *
n = # Modulus n
e = # Public key exponent e
c = # Ciphertext c
dp = # Leaked private key information dp
# Attempt to brute force restore p and q based on dp = d mod (p - 1)
for i in range(1, dp * e - 1): # Iterate over i values to enumerate divisors that satisfy the condition
# Using the formula: dp * e ≡ 1 mod (p - 1)
# Derive p ≈ (dp * e - 1) // i + 1
p = (dp * e - 1) // i + 1
# Check if p is a factor of n, if so, we have found the correct p
if n % p == 0:
q = n // p print("p =", p) print("q =", q) break # Decrypt
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))2.7 High Degree Polynomial Modulus Attack
2.7.1 Scenario
The RSA’s p and q are generated through high degree polynomials. Based on the high degree polynomial, approximate values can be generated to brute force p and q, thus recovering the plaintext m. For example, the following high degree polynomial:
p = nextprime(p1)
q = nextprime(q1)
n = p * q
2.7.2 Principle
2.7.3 Analysis Script
from gmpy2 import *
from sympy import nextprime
e = # Public key exponent e
n = # Modulus n
c = # Ciphertext c
r_prox = iroot(n, 10)[0] # Calculate the 10th root of n as the initial guess for r
# Brute force iterate r to find suitable p and q
for r in range(r_prox - 2000, r_prox + 2000): # Iterate around r
# Calculate p1 and q1 through polynomial
p1 = r ** 5 + r ** 4 - r ** 3 + r ** 2 - r + 2025
q1 = r ** 5 - r ** 4 + r ** 3 - r ** 2 + r + 2025
p = nextprime(p1)
q = nextprime(q1)
if p * q == n: # If p and q's product equals n, then p and q have been successfully found
# Decrypt
phi = (p - 1) * (q - 1)
d = invert(e, phi)
m = pow(c, d, n)2.8 Modulus Reconstruction Attack
2.8.1 Scenario
The attacker knows the public key parameters e and n in the RSA key, as well as a set of biased information in the form of linear combinations of unknown p and q, such as: Z = x * p − y * q.
2.8.2 Principle
To solve for p (similarly for q):
Initial equation:
Known:
Z = x * p − y * q
This can be rewritten as:
Z + y * q = x * p
Introduce modular arithmetic:
Introduce modular arithmetic to eliminate q:
(Z + y * q ) mod y = (x * p ) mod y
This simplifies to:
Z mod y = (x * p ) mod y
Thus the equation:
Z ≡ x * p mod y
Introduce modular inverse:
Multiply by the modular inverse of x to eliminate x:
p = Z * x-1 mod y
q = -Z * y-1 mod x (similarly)
2.8.3 Analysis Script
import gmpy2
import libnum
# Known parameters
e =
x =
y =
Z = # Z = x * p − y * q
c =
# Solve for p and q
p = (Z * gmpy2.invert(x, y)) % y
q = (-Z * gmpy2.invert(y, x)) % x
# Decrypt
n = p * q
d = gmpy2.invert(e, (q - 1) * (p - 1))
m = pow(c, d, n)
print(libnum.n2s(int(m)))2.9 Bitwise Encryption Attack
2.9.1 Scenario
Plaintext characters are encrypted bit by bit, and the plaintext space is small.
2.9.2 Principle
Enumerate all possible plaintext character sets, calculate their encryption values, and establish a dictionary mapping for the ciphertext list to restore the original characters one by one.
2.9.3 Analysis Script
from Crypto.Util.number import *
import string
e = # Public key exponent e
n = # Modulus n
c = [c1,c2,c3,c4,.....] # List of ciphertexts
# Dictionary character set, can be expanded as needed
charset = string.printable
# Establish dictionary mapping
char_map = {pow(ord(ch), e, n): ch for ch in charset}
# Brute force restore plaintext
m = ''.join(char_map.get(ci, '?') for ci in c)
print("Plaintext m:", m)2.10 Finite Field Square Root e
2.10.1 Scenario
e is not coprime to φ(n), and e does not have a modular inverse and is relatively small.
2.10.2 Principle
It is impossible to obtain the private key d through the normal RSA algorithm: d * e = 1 mod φ(n).
Given the formula:
n = p * q
c ≡ me mod n
We can obtain:
2.10.3 Analysis Script
# sage, requires the use of sage mathematical tools
import libnum
e = # Public key exponent e
n = # Public key modulus n
p = # Prime factor p
q = # Prime factor q
c = # Ciphertext c
# Construct a univariate polynomial ring over the finite field mod p, and define variable x
R.<x> = Zmod(p)[]
# Construct polynomial f(x) = x^e - c (mod p)
f = x ^ e - c
# Convert f to monic (standard form with leading coefficient 1 for easier root finding)
f = f.monic()
# Find all roots of f(x) ≡ 0 mod p (i.e., m ≡ ? mod p)
res1 = f.roots()
# Construct a univariate polynomial ring over the finite field mod q, and define variable x
R.<x> = Zmod(q)[]
f = x ^ e - c
f = f.monic()
res2 = f.roots()
# Enumerate all possible root combinations (m_p, m_q) mod p and mod q
for i in res1:
for j in res2:
# Use the Chinese Remainder Theorem to restore m mod n for each pair (m mod p, m mod q)
m = crt(int(i[0]), int(j[0]), p, q)
print(m)</x></x>
Scan to Join Group for Daily Industry Reports
Report Sharing | Technical Discussion | Industry Communication
Hot Topics
Exciting Recommendations
-
Full Text Collection | The National Cryptography Administration releases the “Requirements for Cryptographic Applications in Critical Information Infrastructure” standard, officially implemented from July 1, 2025
-
Attached Application Form | 2025 Shanghai Excellent Cryptographic Application Solutions Collection and Evaluation
-
Original Download | The Canadian government releases the post-quantum cryptography (PQC) migration roadmap (ITSM.40.001)
-
Original Download | “Post-Quantum Cryptography Technology White Paper (2025 Edition)”
-
Original Download | “Responding to Quantum Threats: SIM System Anti-Quantum Cryptography Migration White Paper”
-
Direct Download | The latest 19 cryptographic industry standards implemented
-
Original Download | The World Digital Academy releases the first AI agent security testing standard
-
Including competition results | The 2025 Cryptographic Security Forum and the third “Entropy Cup” Cryptographic Security Challenge successfully concluded, with Feng Dengguo attending and delivering a keynote speech
-
New theories and protection systems for AI security from a cryptographic perspective, selected as one of the “Top 10 Frontier Scientific Issues of 2025”
-
Official Interpretation | “Management Regulations for Commercial Cryptography Usage in Critical Information Infrastructure”