Sophie German
Sophie German
Platform: hackerlab | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-01-02 | Status: Solved Techniques: related_prime_factorization, quadratic_equation_solving, rsa_decryption
Summary
Flag format: CODEBY{...}
Sophie German — HackerLab
Description
Как же удивительны простые числа, а вот 2*p+1 ещё круче!) Но наш криптограф, что-то напутал, и использовал два таких числа, покажи ему, что он сделал слабую защиту и найди флаг!)
(How amazing prime numbers are, and 2*p+1 is even cooler!) But our cryptographer messed something up and used two such numbers, show him that he made weak protection and find the flag!)
Flag format: CODEBY{...}
Files: task.txt with RSA parameters (n, e=65537, c)
Analysis
Sophie Germain Primes
Sophie Germain prime is a prime number p for which 2p+1 is also prime. The number 2p+1 is called a safe prime.
Examples:
- p = 2 → 2*2+1 = 5 (prime) ✓
- p = 3 → 2*3+1 = 7 (prime) ✓
- p = 5 → 2*5+1 = 11 (prime) ✓
- p = 11 → 2*11+1 = 23 (prime) ✓
Vulnerability
The cryptographer used related primes: q = 2p + 1
This creates a mathematical dependency:
n = p × q = p × (2p + 1) = 2p² + p
Factorization via Quadratic Equation
From the relation n = 2p² + p we get a quadratic equation:
2p² + p - n = 0
Solution using the quadratic formula (ax² + bx + c = 0):
a = 2, b = 1, c = -n
D = b² - 4ac = 1 + 8n
p = (-b + √D) / 2a = (-1 + √(1 + 8n)) / 4
Since p must be positive, we take the root with the "+" sign.
Solution
python read-only • copy allowed#!/usr/bin/env python3 """ Sophie German - HackerLab CTF RSA with related primes: q = 2p + 1 Vulnerability: n = p * (2p + 1) = 2p² + p Solving quadratic equation: 2p² + p - n = 0 p = (-1 + sqrt(1 + 8n)) / 4 """ from Crypto.Util.number import long_to_bytes import gmpy2 # RSA parameters from task.txt n = 352267140385944585171420515870872468773797975237357863243961220254584923362538915696303814596250763050621871546683691450696852813611655954985339973903527313192139967424027780018860330689942211225916258965517337953511007408146018860821525022586803085406214204800198643138257476826269283729863154512014329665730133019452596180147248461474481343845937543818480121035402440766801573871580369137709694932837026457747872836746642935990832554450931817459596619407628431966500059082889834541304012374252400869153990049385425620169218312204289616856339596594311061915644258612287581237638018403826747282646712639477293536777612251046884203668676440137258629937440685299021901167450503784922212080283718627246198664933918736105467566324994321361605580213880809911216458347149294421147863457866505066189114670871780545736218323387057103900415193169195623053344299706115515220326692561131333168881509232153682679213671204485615685848722703598732849524996752957178528459558420306180662168573664424047005436401238010505024325924426776873858513627213633520162998650033329824802860081708068765625066900150067570447072463307135566872628924601536667079944479628334134824306325134422839491067157969845642344830536161736420740187372735987330541867936021 e = 65537 c = 133742754610235151196692984417306935434412055963945477190070146909090445704136901171799552593992535091721987388257058415096662151908729284239773302439474199756076477837468763640186250109972655279021748897441890754196280079713988712105531940049755842353873471672722233623571012266613383053717141726772779853531278628706981884313588048150682190858541696929228869685946799551801831002372211852820331132147074406108606426751531332899827066391307031217691409515157419302227908505246927090348428507154273601723306507140778138293728160489526747723548194770230523966888500031821135790425490778158439333726124054104937662158474699149648286380803190475852245229064085525316154955960107075876161494680650359450410949556749124276046876965883874722670911860523724108165867342764235811841478141514775601550107280157313626435221603733167201478651746997079407265077187635421721853986538749142396139151199421946005111600282966850293028412760818988681382690193552746986565975734199723210698951710679941068291186141179479380327811906943587652560774078578419866085699812846206151959786836390697399740272968071925708207897100969346098804458470760515928835681874032008255125073056208838516988394754791329973797148788089573486257130341203309180572806759882 # Factor n using q = 2p + 1 relationship # n = p * (2p + 1) = 2p² + p # Quadratic equation: 2p² + p - n = 0 # Discriminant: D = 1 + 8n # p = (-1 + sqrt(D)) / 4 discriminant = 1 + 8 * n sqrt_disc = gmpy2.isqrt(discriminant) # Verify perfect square assert sqrt_disc * sqrt_disc == discriminant, "Discriminant is not a perfect square!" p = int((sqrt_disc - 1) // 4) q = int(n // p) # Verify factorization assert p * q == n, "Factorization failed!" assert q == 2 * p + 1, "q != 2p + 1" print(f"[+] Factorization successful!") print(f"[+] p = {p}") print(f"[+] q = {q}") print(f"[+] Verified: q = 2p + 1 = {2*p + 1}") # Standard RSA decryption phi = (p - 1) * (q - 1) d = pow(e, -1, phi) m = pow(c, d, n) # Convert to bytes flag = long_to_bytes(m) print(f"\n[+] Flag: {flag.decode()}")
Output
[+] Factorization successful!
[+] p = 13271...
[+] q = 26542...
[+] Verified: q = 2p + 1 = 26542...
[+] Flag: CODEBY{REDACTED}
Mathematical Background
Why Does This Work?
-
Relationship between p and q: If q = 2p + 1, then n = p(2p+1) = 2p² + p
-
Quadratic equation: 2p² + p - n = 0
- a = 2, b = 1, c = -n
- D = 1 - 4(2)(-n) = 1 + 8n
- p = (-1 ± √D) / 4
-
Uniqueness of solution: Since p > 0, we take the positive root
-
Computational complexity: O(log n) for computing the square root — instant even for large n
Comparison with Standard RSA
| Parameter | Standard RSA | Sophie Germain RSA |
|---|---|---|
| Relationship of p and q | Independent | q = 2p + 1 |
| Factorization | Exponential | O(log n) |
| Security | High | None |
Alternative Approaches
Via FactorDB
Sometimes such n values are already factored in public databases.
Via Fermat's Factorization
If p and q are close (which is true for q = 2p + 1), Fermat's method also works quickly.
Useful Resources
- Sophie Germain prime - Wikipedia
- Safe prime - Wikipedia
- RSA with related primes