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 d

• rsa/common_modulus.py

• Common modulus attack

• rsa/fermat.py

• Fermat factorization for close primes

Classical Ciphers

• classic/caesar.py

• Caesar cipher bruteforce

• classic/vigenere.py

• Vigenere cipher with IC analysis

• classic/xor_single_byte.py

• Single-byte XOR bruteforce

• classic/xor_repeating_key.py

• Multi-byte XOR key recovery

• classic/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