G36maid Cryptography Tools and Techniques
When to Use
Load this skill when:
- Solving cryptography CTF challenges
- Attacking weak RSA implementations
- Breaking classical ciphers (Caesar, Vigenere, XOR)
- Performing frequency analysis
- Analyzing encrypted data with unknown algorithms
RSA Attacks
Small Exponent Attack (e=3)
#!/usr/bin/env python3
"""Attack RSA with small public exponent"""
import gmpy2
def small_e_attack(c, e, n):
"""
If e is small (typically e=3) and message is short,
we can take the e-th root directly
"""
# Try taking e-th root
for k in range(1000):
m, exact = gmpy2.iroot(c + k * n, e)
if exact:
return int(m)
return None
# Example
c = 12345678901234567890
e = 3
n = 98765432109876543210
m = small_e_attack(c, e, n)
if m:
print(f"Message: {bytes.fromhex(hex(m)[2:])}")
Wiener's Attack (Small Private Exponent)
#!/usr/bin/env python3
"""Wiener's attack for small d"""
from fractions import Fraction
def wiener_attack(e, n):
"""
Attack RSA when d < N^0.25
Returns private key d if vulnerable
"""
convergents = continued_fraction(Fraction(e, n))
for k, d in convergents:
if k == 0:
continue
phi = (e * d - 1) // k
# Check if phi is valid
s = n - phi + 1
discr = s * s - 4 * n
if discr >= 0:
t = gmpy2.isqrt(discr)
if t * t == discr and (s + t) % 2 == 0:
return d
return None
def continued_fraction(frac):
"""Generate continued fraction convergents"""
convergents = []
n, d = 0, 1
for _ in range(1000):
a = int(frac)
convergents.append((n + a * 1, d + a * 1))
frac = frac - a
if frac == 0:
break
frac = 1 / frac
return convergents
Common Modulus Attack
#!/usr/bin/env python3
"""Attack RSA when same message encrypted with different e, same N"""
import gmpy2
def common_modulus_attack(c1, c2, e1, e2, n):
"""
Given:
c1 = m^e1 mod n
c2 = m^e2 mod n
And gcd(e1, e2) = 1
Recover m without knowing phi(n)
"""
# Extended Euclidean algorithm
gcd, s, t = gmpy2.gcdext(e1, e2)
if gcd != 1:
raise ValueError("e1 and e2 must be coprime")
# Handle negative exponents
if s < 0:
c1 = gmpy2.invert(c1, n)
s = -s
if t < 0:
c2 = gmpy2.invert(c2, n)
t = -t
m = (pow(c1, s, n) * pow(c2, t, n)) % n
return m
Fermat's Factorization (Close Primes)
#!/usr/bin/env python3
"""Fermat factorization when p and q are close"""
import gmpy2
def fermat_factor(n):
"""
Factor n when p and q are close: |p - q| is small
Much faster than trial division
"""
a = gmpy2.isqrt(n) + 1
b2 = a * a - n
for _ in range(1000000):
b = gmpy2.isqrt(b2)
if b * b == b2:
p = a + b
q = a - b
return int(p), int(q)
a += 1
b2 = a * a - n
return None, None
# Example
n = 123456789012345678901234567890
p, q = fermat_factor(n)
if p and q:
print(f"p = {p}")
print(f"q = {q}")
RSA Common Template
#!/usr/bin/env python3
"""Standard RSA operations"""
import gmpy2
def rsa_decrypt(c, d, n):
"""Decrypt ciphertext with private key"""
m = pow(c, d, n)
return m
def rsa_encrypt(m, e, n):
"""Encrypt message with public key"""
c = pow(m, e, n)
return c
def factor_n(p, q):
"""Compute n from primes"""
return p * q
def compute_phi(p, q):
"""Compute Euler's totient"""
return (p - 1) * (q - 1)
def compute_d(e, phi):
"""Compute private exponent from public exponent"""
return int(gmpy2.invert(e, phi))
# Full RSA key recovery from factors
def recover_key_from_factors(p, q, e):
"""Given p, q, e, compute d"""
n = factor_n(p, q)
phi = compute_phi(p, q)
d = compute_d(e, phi)
return d, n
# Example
p = 1234567890123456789
q = 9876543210987654321
e = 65537
d, n = recover_key_from_factors(p, q, e)
print(f"n = {n}")
print(f"d = {d}")
# Decrypt
c = 12345678901234567890
m = rsa_decrypt(c, d, n)
print(f"Message: {m}")
Classical Ciphers
Caesar Cipher
#!/usr/bin/env python3
"""Caesar cipher brute force"""
def caesar_decrypt(ciphertext, shift):
"""Decrypt Caesar cipher with given shift"""
result = ""
for char in ciphertext:
if char.isalpha():
base = ord('A') if char.isupper() else ord('a')
result += chr((ord(char) - base - shift) % 26 + base)
else:
result += char
return result
def caesar_bruteforce(ciphertext):
"""Try all 26 possible shifts"""
print("Caesar Cipher Bruteforce:")
for shift in range(26):
plaintext = caesar_decrypt(ciphertext, shift)
print(f"Shift {shift:2d}: {plaintext}")
# Example
ciphertext = "Khoor Zruog"
caesar_bruteforce(ciphertext)
Vigenere Cipher
#!/usr/bin/env python3
"""Vigenere cipher attack"""
def vigenere_decrypt(ciphertext, key):
"""Decrypt Vigenere cipher"""
result = ""
key_index = 0
key = key.upper()
for char in ciphertext:
if char.isalpha():
base = ord('A') if char.isupper() else ord('a')
shift = ord(key[key_index % len(key)]) - ord('A')
result += chr((ord(char) - base - shift) % 26 + base)
key_index += 1
else:
result += char
return result
def guess_key_length(ciphertext):
"""Use Index of Coincidence to guess key length"""
ic_values = []
for key_len in range(1, 21):
ic_sum = 0
for i in range(key_len):
substring = ciphertext[i::key_len]
ic_sum += index_of_coincidence(substring)
ic_values.append((key_len, ic_sum / key_len))
# Sort by IC (higher is better, ~0.065 for English)
ic_values.sort(key=lambda x: x[1], reverse=True)
return ic_values[0][0]
def index_of_coincidence(text):
"""Calculate Index of Coincidence"""
text = ''.join(c.upper() for c in text if c.isalpha())
n = len(text)
if n <= 1:
return 0
freq = {}
for char in text:
freq[char] = freq.get(char, 0) + 1
ic = sum(f * (f - 1) for f in freq.values()) / (n * (n - 1))
return ic
XOR Cipher
#!/usr/bin/env python3
"""XOR cipher attacks"""
def xor_single_byte(data, key):
"""XOR data with single-byte key"""
return bytes([b ^ key for b in data])
def xor_bruteforce_single_byte(ciphertext):
"""Bruteforce single-byte XOR key"""
results = []
for key in range(256):
plaintext = xor_single_byte(ciphertext, key)
score = english_score(plaintext)
results.append((key, score, plaintext))
results.sort(key=lambda x: x[1], reverse=True)
return results[:5] # Top 5 candidates
def english_score(data):
"""Score text based on English letter frequency"""
try:
text = data.decode('ascii', errors='ignore').lower()
except:
return 0
freq = {
'e': 12.70, 't': 9.06, 'a': 8.17, 'o': 7.51, 'i': 6.97,
'n': 6.75, 's': 6.33, 'h': 6.09, 'r': 5.99, ' ': 13.00,
}
score = sum(freq.get(c, 0) for c in text)
return score / len(text) if len(text) > 0 else 0
def xor_repeating_key(data, key):
"""XOR data with repeating key"""
return bytes([data[i] ^ key[i % len(key)] for i in range(len(data))])
def find_xor_key_length(ciphertext):
"""Find XOR key length using Hamming distance"""
distances = []
for keysize in range(2, 41):
chunks = [ciphertext[i:i+keysize] for i in range(0, len(ciphertext), keysize)]
if len(chunks) < 4:
continue
# Compare first 4 chunks
dist = 0
comparisons = 0
for i in range(3):
dist += hamming_distance(chunks[i], chunks[i+1])
comparisons += 1
normalized_dist = dist / comparisons / keysize
distances.append((keysize, normalized_dist))
distances.sort(key=lambda x: x[1])
return distances[0][0]
def hamming_distance(b1, b2):
"""Calculate Hamming distance between two byte strings"""
return sum(bin(x ^ y).count('1') for x, y in zip(b1, b2))
Frequency Analysis
#!/usr/bin/env python3
"""Frequency analysis for ciphertexts"""
from collections import Counter
def frequency_analysis(text):
"""Analyze letter frequency in text"""
# Clean text
text = ''.join(c.upper() for c in text if c.isalpha())
# Count frequencies
freq = Counter(text)
total = len(text)
# Calculate percentages
freq_percent = {char: (count / total) * 100
for char, count in freq.items()}
# Sort by frequency
sorted_freq = sorted(freq_percent.items(),
key=lambda x: x[1], reverse=True)
# English reference frequencies
english_freq = {
'E': 12.70, 'T': 9.06, 'A': 8.17, 'O': 7.51,
'I': 6.97, 'N': 6.75, 'S': 6.33, 'H': 6.09,
}
print("Frequency Analysis:")
print("-" * 40)
print("Char | Count | % | English %")
print("-" * 40)
for char, percent in sorted_freq[:10]:
count = freq[char]
eng = english_freq.get(char, 0)
print(f" {char} | {count:5d} | {percent:5.2f} | {eng:5.2f}")
Quick Reference
| Attack | Condition | Tool |
|---|---|---|
| Small e | e=3, short message | rsa/small_e.py |
| Wiener | d < N^0.25 | rsa/wiener.py |
| Common Modulus | Same N, diff e | rsa/common_modulus.py |
| Fermat | |p-q| small | rsa/fermat.py |
| Caesar | Shift cipher | classic/caesar.py (bruteforce 26 shifts) |
| Vigenere | Repeating key | classic/vigenere.py (IC analysis) |
| XOR Single | 1-byte key | classic/xor_single_byte.py |
| XOR Repeating | Multi-byte key | classic/xor_repeating_key.py |
Bundled Resources
RSA Tools
rsa/rsa_common.py- Common RSA operations (encrypt/decrypt/factor)rsa/small_e.py- Small public exponent attack (e=3)rsa/wiener.py- Wiener's attack for small drsa/common_modulus.py- Common modulus attackrsa/fermat.py- Fermat factorization for close primes
Classical Ciphers
classic/caesar.py- Caesar cipher bruteforceclassic/vigenere.py- Vigenere cipher with IC analysisclassic/xor_single_byte.py- Single-byte XOR bruteforceclassic/xor_repeating_key.py- Multi-byte XOR key recoveryclassic/frequency_analysis.py- Letter frequency analysis tool
External Tools
# RsaCtfTool (comprehensive RSA attack suite)
git clone https://github.com/Ganapati/RsaCtfTool.git
python3 RsaCtfTool.py -n <N> -e <E> --private
# CyberChef (web-based encoding/crypto tool)
# https://gchq.github.io/CyberChef/
# FactorDB (check if N is already factored)
# http://factordb.com/
Keywords
cryptography, crypto, RSA, RSA attacks, small exponent, wiener attack, common modulus, fermat factorization, classical cipher, caesar cipher, vigenere cipher, XOR, XOR cipher, frequency analysis, index of coincidence, public key cryptography, modular arithmetic, CTF crypto