Classic Ciphers: Cryptoanalysis in Crypto CTF Tasks
Almost every Jeopardy-CTF includes a couple of tasks on classic wildcards. The point is to weed out those who do not know the basic tools. Spending more than five minutes on them is stealing time from the tucks, which give real points.
Submarinage Ciphers and Frequency Analysis
Monoalphavite substitution - Caesar's cipher (fixed shift), Atbash (mirror alphabet), ROT13 - breaks down the selection of 25 variants. CyberChef for CTF closes the task in seconds: download the cipher text, apply ROT13 Brute Force, see all the options at once. If you are not a simple shift, but an arbitrary substitution (each letter is replaced by a fixed other), a frequency analysis will be required.
The principle is simple to indecency: in natural language, letters appear with predictable frequency. In English, the most frequent is “e” (~12.7%), behind it “t” (~9.1%) and “a” (~8.2%). For Russian - "o" (~10.9%), "e/ё" (~8.5%), "a" (~8.0%). When in a cipher text the symbol “X” occupies ~12% of all positions – it almost certainly corresponds to “e”. Qipqiup.com and dcode.fr solvers combine frequency analysis with a dictionary search and return the answer in seconds, even on short text.
On the CTF, the main skill when working with wildcards is the type recognition speed. Uniformly distorted text without spaces and signs → try Base64/hex through CyberChef. The spaces are saved, the length of the words is plausible → monoalphavite substitution, quipqiup. Set of numbers → check ASCII codes, decimal or eighth.
Vigener chips – from frequency analysis to hacking
The Vigener cipher is a polyalphavite cipher, where each letter of open text shifts to the value of the corresponding key symbol. The keyword “KEY” sets the cyclic sequence of shifts: 10, 4, 24 (positions K, E, Y in the alphabet). The first letter shifts to 10, the second to 4, the third to 24, the fourth again by 10. Direct frequency analysis is powerless – the same letter is encrypted differently depending on the position.
But the cryptanalysis of classical ciphers of this type was worked out in the XIX century. Attack in two stages.
Step 1 – determining the length of the key. The Kasski method searches for recurring trigrams in the cipher text. If QXR occurs at positions 7 and 37, the distance is 30. The length of the key is highly likely to be a divider of 30 (2, 3, 5, 6, 10, 15 or 30). Having collected distances for several repetitions and calculating the NOD, we get a candidate.
The alternative is the index of coincidence (Index of Coincidence, IC). For each estimated length, k break the cipher text into k subsequentials (symbols at positions 0, k, 2k, 3k... are the first; 1, k+1, 2k+1... are the second). We believe that if it is close to 0.065 (English) or 0.055 (Russian) - the length of the guess, because the subsequence turns into an ordinary monoalphavite cipher with a predictable distribution.
Step 2 – Determination of each letter of the key. Knowing the length, we process each subsequence separately: the most frequent symbol is compared with "e" (or "o" for the Russian), we calculate the shift - here is the letter of the key.
On the CTF for the Vigener cipher, there are automatic solvers: dcode.fr/vigenere-cipher performs both steps and returns the key with the public text. But when the organizers use a non-standard alphabet (Cyrillic, Base64-symbols, extended ASCII) - the automation breaks, and you need your script. In Python, the basic implementation through collections.Counter with the selection of key lengths from 2 to 30 and the IC count is laid in 20-25 lines. That's enough for the eyes.
RSA Vulnerabilities in CTF: Small Exhibitor e=3
RSA is the unqualified leader in the number of crypto CTFs of medium and high complexity tasks. Key parameters: two prime numbers p and q, module N = p*q, public exponent e, private exponent d (multiplicatively inverse to e by module λ(N)). Encryption: c = m^e mod N. Decryption: m = c^d mod N. Public key – pair (N, e), private – (N, d).
In reference implementation — key 2048+ bits, padding OAEP, e = 65537 — cryptosystem is stable. But CTF tasks (and unfortunately, real production code) systematically deviate from the standard. Trail of Bits puts it bluntly: “RSA is an intrinsically intrinsically fragile system contained crypto crypto-gun it is something something software algorithm money can be expected to be expected.” Developers choose e = 3 to save on encryption and signature verification – and open a whole class of attacks. It is the low public exponent e=3 that generates the most frequent RSA vulnerabilities on the CTF.
Hacking RSA CTF: extracting the cubic root
The most elementary case: e = 3, padding is missing, the message m is small enough to m^3 < N. Operation mod N here does nothing - the cipher text c is literally equal to m^3. Decoding – extracting an integer cubic root:
from gmpy2 import iroot
c = 10648
e = 3
m, exact = iroot(c, e)
if exact:
flag = m.to_bytes((m.bit_length() + 7) // 8, 'big')
print(flag.decode())
# iroot(10648, 3) → (22, True)
gmpy2 performs an integer extraction of the root of arbitrary accuracy - standard math.isqrt For cubic roots is not suitable. Function iroot(c, e) returns the motorcade: result and precision flag. If exact == True The task is closed.
Variation: m^3 a little more N. Then c = m^3 mod N, and m^3 = c + k*N for a small k. We go from 0 to several thousand, checking iroot(c + k*N, 3) to accuracy. For CTF-tasks, k usually does not exceed 10^4 – overkill takes a fraction of a second.
How to recognize on CTF: in the condition given (N, e, c), the exponent e is 3 (or 5, 7, sometimes 17). The first action is to try the root of the e-th degree. Didn't work directly - go over k. This is 15 seconds of work, and it is from this step that you should start any RSA-task with a small e.
Attack by Hastada on RSA with a small exhibit
The Hastad Attack is an extension of the previous idea in case the same message m is encrypted by multiple recipients with different modules, but the same small e. Let’s say e = 3, there are three pairs (Ni, ci):
c1 = m^3 mod N1
c2 = m^3 mod N2
c3 = m^3 mod N3
The Chinese Residue Theorem (CRT) restores m^3 mod (N1 * N2 * N3). Since m < min(Ni), correctly m^3 < N1 N2 N3 – CRT gives an exact value of m^3 without a modular wrapper. Next is the cubic root:
from sympy.ntheory.modular import crt
from gmpy2 import iroot
moduli = [n1, n2, n3]
remainders = [c1, c2, c3]
m_cubed, _ = crt(moduli, remainders)
m, exact = iroot(int(m_cubed), 3)
if exact:
print(m.to_bytes((m.bit_length() + 7) // 8, 'big'))
On the CTF attack, Hastad is masked: the task is presented as “intercepted messages from three servers” or “three public certificates for one domain.” The identification feature is the same e, different N, one plain text. Formally, the attack requires e ciphertexts: for e = 3 you need three, for e = 17 - seventeen. In practice, e=17 with 17 servers is exotic, so that Hastad is most common at e=3 or e=5.
Related attack – Franklin-Reiter: if two messages are associated with a known linear ratio (m2 = a*m1 + b for known a and b), then at e=3 both are recovered from ciphertexts. In the CTF context, these are two versions of the flag with minimal distinctions – for example, an incremented counter at the end of the line. Trail of Bits describes this attack in its review of RSA weaknesses.
RSA Factorization and Wiener Attack
The second major RSA vulnerability class on the CTF is not associated with the exponent, but with the N module or the private key d.
When RSA Factorization is Trivial
Small multiplier. If one of the simple q < 10^20, it will find yafu or even a selection of dividers. The mandatory first step is to check N on factordb.com. The database stores the factorization of millions of numbers: the module from the CTF task is often already laid out by someone before you. On picoCTF it works surprisingly often (I stopped wondering after the third time).
Close p and q. If |p - q| little, the Farm method works. We start with a = ceil(sqrt(N)), we go over a until a^2 - N becomes the exact square b^2. Then p = a + b, q = a - b. In Python – five lines with gmpy2.isqrt.
Total multiplier between modules (common modulus attack RSA). Two RSA-tasks with different modules N1 and N2, but a common simple multiplier p? GCD(N1, N2) = p. One line: math.gcd(n1, n2). Organizers mask tasks as “independent” – the key is to always try GCD for each pair of modules in the set.
In 2012, about 1% of TLS traffic used RSA modules with common multipliers due to defective random number generators (Trail of Bits data). Not an abstract threat: in terms of MITRE ATT&CK, weakening cryptography through incorrect parameters — Weaken Encryption (T1600, Defense Evasion) technique, Reduce Key Space (T1600.001) subtechnics.
Wiener Attack – Small Private Exhibitor D
Sometimes developers choose a small d to speed up decryption – especially on smart cards and IoT. Wiener proved: if d < N^(1/4) / 3, the private key is completely restored.
Method – decomposition of fraction e/N into chain fraction (continued). Suitable fractions (convergents) contain a pair of k/d. The attacker moves convergents and for each candidate d checks whether N is factored into two simple with the desired properties.
How to identify on CTF: abnormally large e, comparable in bits with N. If e = 65537, the Wiener RSA attack is not applicable. If e takes almost as much bit as N — try immediately.
Tools: module owiener in Python or built-in attack in RsaCtfTool (--attack wiener). Bonech and Durphy have expanded the boundary to d < N^0.292, but their method requires latticed algorithms (LLLs) – this is the SageMath level. Most of the standard Wiener's CTFs have enough.
Tools for Crypto CTF: RsaCtfTool and SageMath
RsaCtfTool – automatic Hacking of RSA
RsaCtfTool is chasing dozens of attacks on the transferred RSA parameters. From the documentation (attack list on ctf101.org): factorization of weak keys, Wiener attack, Hastad attack, small q (q < 100 000), total multiplier, farm method for close and q, Bonech-Durphy method, Pollard p-1 method, elliptic curve method and SIQS through yafu.
Typical Challenges: python3 RsaCtfTool.py -n <N> -e <e> --uncipher <c> for decryption, python3 RsaCtfTool.py --publickey pub.pem --private to extract the private key, python3 RsaCtfTool.py -n <N> -e <e> --attack wiener for a specific attack.
The instrument is not universal - custom protocols and non-standard mathematics it will not be done. But as the first automatic passage on any RSA-Tack – saves critical minutes. Tip: Run RsaCtfTool in parallel with manual analysis. While the script is going through the attacks, you are already studying the parameters and think what can work. Two processes are one brain, one CPU.
SageMath and Supporting Arsenal
SageMath is indispensable where you need to work with lattices, elliptical curves and end fields. The main application is the attack of Coppersmith through small_roots(): with partially known open text and small e SageMath finds the roots of polynomial by module N. Advanced level, but on serious CTFs (Google CTF, hxp, DEF CON Quals) such tasks are regular guests.
CyberChef for CTF is useful in the exploration stage: determine the encoding (Base64, hex, URL-encoding), try XOR with the key, apply ROT13/ROT47. For serious mathematics, his power is not enough.
openssl from the command line will be useful for working with PEM keys: openssl rsa -pubin -in pub.pem -text -noout will show the parameters of the public key (N and e in the readable form), and openssl rsautl -decrypt -inkey priv.pem -in ct.bin decrypt the file with a private key. Sometimes openssl – the only thing that is on the CTF task server.
Almost every Jeopardy-CTF includes a couple of tasks on classic wildcards. The point is to weed out those who do not know the basic tools. Spending more than five minutes on them is stealing time from the tucks, which give real points.
Submarinage Ciphers and Frequency Analysis
Monoalphavite substitution - Caesar's cipher (fixed shift), Atbash (mirror alphabet), ROT13 - breaks down the selection of 25 variants. CyberChef for CTF closes the task in seconds: download the cipher text, apply ROT13 Brute Force, see all the options at once. If you are not a simple shift, but an arbitrary substitution (each letter is replaced by a fixed other), a frequency analysis will be required.
The principle is simple to indecency: in natural language, letters appear with predictable frequency. In English, the most frequent is “e” (~12.7%), behind it “t” (~9.1%) and “a” (~8.2%). For Russian - "o" (~10.9%), "e/ё" (~8.5%), "a" (~8.0%). When in a cipher text the symbol “X” occupies ~12% of all positions – it almost certainly corresponds to “e”. Qipqiup.com and dcode.fr solvers combine frequency analysis with a dictionary search and return the answer in seconds, even on short text.
On the CTF, the main skill when working with wildcards is the type recognition speed. Uniformly distorted text without spaces and signs → try Base64/hex through CyberChef. The spaces are saved, the length of the words is plausible → monoalphavite substitution, quipqiup. Set of numbers → check ASCII codes, decimal or eighth.
Vigener chips – from frequency analysis to hacking
The Vigener cipher is a polyalphavite cipher, where each letter of open text shifts to the value of the corresponding key symbol. The keyword “KEY” sets the cyclic sequence of shifts: 10, 4, 24 (positions K, E, Y in the alphabet). The first letter shifts to 10, the second to 4, the third to 24, the fourth again by 10. Direct frequency analysis is powerless – the same letter is encrypted differently depending on the position.
But the cryptanalysis of classical ciphers of this type was worked out in the XIX century. Attack in two stages.
Step 1 – determining the length of the key. The Kasski method searches for recurring trigrams in the cipher text. If QXR occurs at positions 7 and 37, the distance is 30. The length of the key is highly likely to be a divider of 30 (2, 3, 5, 6, 10, 15 or 30). Having collected distances for several repetitions and calculating the NOD, we get a candidate.
The alternative is the index of coincidence (Index of Coincidence, IC). For each estimated length, k break the cipher text into k subsequentials (symbols at positions 0, k, 2k, 3k... are the first; 1, k+1, 2k+1... are the second). We believe that if it is close to 0.065 (English) or 0.055 (Russian) - the length of the guess, because the subsequence turns into an ordinary monoalphavite cipher with a predictable distribution.
Step 2 – Determination of each letter of the key. Knowing the length, we process each subsequence separately: the most frequent symbol is compared with "e" (or "o" for the Russian), we calculate the shift - here is the letter of the key.
On the CTF for the Vigener cipher, there are automatic solvers: dcode.fr/vigenere-cipher performs both steps and returns the key with the public text. But when the organizers use a non-standard alphabet (Cyrillic, Base64-symbols, extended ASCII) - the automation breaks, and you need your script. In Python, the basic implementation through collections.Counter with the selection of key lengths from 2 to 30 and the IC count is laid in 20-25 lines. That's enough for the eyes.
RSA Vulnerabilities in CTF: Small Exhibitor e=3
RSA is the unqualified leader in the number of crypto CTFs of medium and high complexity tasks. Key parameters: two prime numbers p and q, module N = p*q, public exponent e, private exponent d (multiplicatively inverse to e by module λ(N)). Encryption: c = m^e mod N. Decryption: m = c^d mod N. Public key – pair (N, e), private – (N, d).
In reference implementation — key 2048+ bits, padding OAEP, e = 65537 — cryptosystem is stable. But CTF tasks (and unfortunately, real production code) systematically deviate from the standard. Trail of Bits puts it bluntly: “RSA is an intrinsically intrinsically fragile system contained crypto crypto-gun it is something something software algorithm money can be expected to be expected.” Developers choose e = 3 to save on encryption and signature verification – and open a whole class of attacks. It is the low public exponent e=3 that generates the most frequent RSA vulnerabilities on the CTF.
Hacking RSA CTF: extracting the cubic root
The most elementary case: e = 3, padding is missing, the message m is small enough to m^3 < N. Operation mod N here does nothing - the cipher text c is literally equal to m^3. Decoding – extracting an integer cubic root:
from gmpy2 import iroot
c = 10648
e = 3
m, exact = iroot(c, e)
if exact:
flag = m.to_bytes((m.bit_length() + 7) // 8, 'big')
print(flag.decode())
# iroot(10648, 3) → (22, True)
gmpy2 performs an integer extraction of the root of arbitrary accuracy - standard math.isqrt For cubic roots is not suitable. Function iroot(c, e) returns the motorcade: result and precision flag. If exact == True The task is closed.
Variation: m^3 a little more N. Then c = m^3 mod N, and m^3 = c + k*N for a small k. We go from 0 to several thousand, checking iroot(c + k*N, 3) to accuracy. For CTF-tasks, k usually does not exceed 10^4 – overkill takes a fraction of a second.
How to recognize on CTF: in the condition given (N, e, c), the exponent e is 3 (or 5, 7, sometimes 17). The first action is to try the root of the e-th degree. Didn't work directly - go over k. This is 15 seconds of work, and it is from this step that you should start any RSA-task with a small e.
Attack by Hastada on RSA with a small exhibit
The Hastad Attack is an extension of the previous idea in case the same message m is encrypted by multiple recipients with different modules, but the same small e. Let’s say e = 3, there are three pairs (Ni, ci):
c1 = m^3 mod N1
c2 = m^3 mod N2
c3 = m^3 mod N3
The Chinese Residue Theorem (CRT) restores m^3 mod (N1 * N2 * N3). Since m < min(Ni), correctly m^3 < N1 N2 N3 – CRT gives an exact value of m^3 without a modular wrapper. Next is the cubic root:
from sympy.ntheory.modular import crt
from gmpy2 import iroot
moduli = [n1, n2, n3]
remainders = [c1, c2, c3]
m_cubed, _ = crt(moduli, remainders)
m, exact = iroot(int(m_cubed), 3)
if exact:
print(m.to_bytes((m.bit_length() + 7) // 8, 'big'))
On the CTF attack, Hastad is masked: the task is presented as “intercepted messages from three servers” or “three public certificates for one domain.” The identification feature is the same e, different N, one plain text. Formally, the attack requires e ciphertexts: for e = 3 you need three, for e = 17 - seventeen. In practice, e=17 with 17 servers is exotic, so that Hastad is most common at e=3 or e=5.
Related attack – Franklin-Reiter: if two messages are associated with a known linear ratio (m2 = a*m1 + b for known a and b), then at e=3 both are recovered from ciphertexts. In the CTF context, these are two versions of the flag with minimal distinctions – for example, an incremented counter at the end of the line. Trail of Bits describes this attack in its review of RSA weaknesses.
RSA Factorization and Wiener Attack
The second major RSA vulnerability class on the CTF is not associated with the exponent, but with the N module or the private key d.
When RSA Factorization is Trivial
Small multiplier. If one of the simple q < 10^20, it will find yafu or even a selection of dividers. The mandatory first step is to check N on factordb.com. The database stores the factorization of millions of numbers: the module from the CTF task is often already laid out by someone before you. On picoCTF it works surprisingly often (I stopped wondering after the third time).
Close p and q. If |p - q| little, the Farm method works. We start with a = ceil(sqrt(N)), we go over a until a^2 - N becomes the exact square b^2. Then p = a + b, q = a - b. In Python – five lines with gmpy2.isqrt.
Total multiplier between modules (common modulus attack RSA). Two RSA-tasks with different modules N1 and N2, but a common simple multiplier p? GCD(N1, N2) = p. One line: math.gcd(n1, n2). Organizers mask tasks as “independent” – the key is to always try GCD for each pair of modules in the set.
In 2012, about 1% of TLS traffic used RSA modules with common multipliers due to defective random number generators (Trail of Bits data). Not an abstract threat: in terms of MITRE ATT&CK, weakening cryptography through incorrect parameters — Weaken Encryption (T1600, Defense Evasion) technique, Reduce Key Space (T1600.001) subtechnics.
Wiener Attack – Small Private Exhibitor D
Sometimes developers choose a small d to speed up decryption – especially on smart cards and IoT. Wiener proved: if d < N^(1/4) / 3, the private key is completely restored.
Method – decomposition of fraction e/N into chain fraction (continued). Suitable fractions (convergents) contain a pair of k/d. The attacker moves convergents and for each candidate d checks whether N is factored into two simple with the desired properties.
How to identify on CTF: abnormally large e, comparable in bits with N. If e = 65537, the Wiener RSA attack is not applicable. If e takes almost as much bit as N — try immediately.
Tools: module owiener in Python or built-in attack in RsaCtfTool (--attack wiener). Bonech and Durphy have expanded the boundary to d < N^0.292, but their method requires latticed algorithms (LLLs) – this is the SageMath level. Most of the standard Wiener's CTFs have enough.
Tools for Crypto CTF: RsaCtfTool and SageMath
RsaCtfTool – automatic Hacking of RSA
RsaCtfTool is chasing dozens of attacks on the transferred RSA parameters. From the documentation (attack list on ctf101.org): factorization of weak keys, Wiener attack, Hastad attack, small q (q < 100 000), total multiplier, farm method for close and q, Bonech-Durphy method, Pollard p-1 method, elliptic curve method and SIQS through yafu.
Typical Challenges: python3 RsaCtfTool.py -n <N> -e <e> --uncipher <c> for decryption, python3 RsaCtfTool.py --publickey pub.pem --private to extract the private key, python3 RsaCtfTool.py -n <N> -e <e> --attack wiener for a specific attack.
The instrument is not universal - custom protocols and non-standard mathematics it will not be done. But as the first automatic passage on any RSA-Tack – saves critical minutes. Tip: Run RsaCtfTool in parallel with manual analysis. While the script is going through the attacks, you are already studying the parameters and think what can work. Two processes are one brain, one CPU.
SageMath and Supporting Arsenal
SageMath is indispensable where you need to work with lattices, elliptical curves and end fields. The main application is the attack of Coppersmith through small_roots(): with partially known open text and small e SageMath finds the roots of polynomial by module N. Advanced level, but on serious CTFs (Google CTF, hxp, DEF CON Quals) such tasks are regular guests.
CyberChef for CTF is useful in the exploration stage: determine the encoding (Base64, hex, URL-encoding), try XOR with the key, apply ROT13/ROT47. For serious mathematics, his power is not enough.
openssl from the command line will be useful for working with PEM keys: openssl rsa -pubin -in pub.pem -text -noout will show the parameters of the public key (N and e in the readable form), and openssl rsautl -decrypt -inkey priv.pem -in ct.bin decrypt the file with a private key. Sometimes openssl – the only thing that is on the CTF task server.
