← Back to Writeups
CUSTOMEasyCrypto
Bookmark

Ни в чём не ошибся

XESXOR9/10/20263 min read
#crypto#custom#easy#prime_factor_leak#trivial_factorization

Ни в чём не ошибся

Platform: duckerz | Category: Crypto | Type: Challenge | Difficulty: Easy | OS: NA | Author: XESXOR | Date: 2026-01-09 | Status: Solved Techniques: prime_factor_leak, trivial_factorization

Summary

Task: RSA encryption with encoder.py and out.txt files. Solution: Discovered that e_output = e + p leaks the prime factor; recovered p by subtracting standard e=65537, then trivially factored n and decrypted the flag.

Ни в чём не ошибся — duckerz CTF

Description

"Я реализовал классический алгоритм шифрования RSA, но у меня ощущение, что в конце я немного ошибся..."

Provided files:

  • encoder.py — encryption script
  • out.txt — encrypted output

Analysis

Source code encoder.py

 python 
from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag

FLAG = bytes_to_long(flag)

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 2**16 + 1
ct = pow(FLAG, e, n)

print(f'n: {n}')
print(f'e: {e + p}')  # <-- BUG!
print(f'ct: {ct}')

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Vulnerability

Critical error on line 13: instead of the public exponent e, the value e + p is output.

This is an information leak — knowing the standard value e = 65537, we can recover the prime p:

p = e_output - 65537

Having p, we trivially find q = n / p and completely break RSA.

Vulnerability Indicators

  1. The e value in output is anomalously large (~309 bits instead of the usual 17 bits)
  2. In the code e = 2**16 + 1, but the output contains a completely different number
  3. The task name hints at an error: "Ни в чём не ошибся" (irony — "Made no mistakes") ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

 python 
#!/usr/bin/env python3
"""
duckerz CTF - Ни в чём не ошибся
RSA with prime factor leak via e + p
"""
from Crypto.Util.number import long_to_bytes

# Data from out.txt
n = 18798751967178426381504731083645551181218121488252117174796390511662473223223405610358317360347533449725615650254937132757565862618074878444613133832079916631885992852274828236728617177721086544314236544562012971734513398321560619671317933405328568764783210898904175003033756768051691521868667268800572467570661416685980520830365227303101263220236115846257527363406328867070133263900860663213557708577848719178814761347152620792372847762483281132577137885981623016382936239562664037534610728652936498358752385455426412465419275613674679023680184197311118816809602224346016670679758338521715152362623465755928516580959
e_output = 166612997784562961050427402417959231610727289110449701096278048384004974210290958240913379674222687635734122544375614765473080442343653698415642775890353274310399072042600668814731842221602949909207395384402750419354408938463901094165980590478308424439117927846922386509060315654925327343542424625687693632068
ct = 17273356561619461078492198358303284146147837550026408083524518067748963714274545090109597771904129978632339754019199704530534497145745599609523527982760088915455559056009877592308177940333975618592015789383850494306210308069932391687742058641729313031291497958105019656727012043907079761118369894363732951513833446149610076031667795704343794624910397891428467219520881918134803714315257669793473836503542698570979981732999911129987227518836611490653123917494699687532642255114180923045867064695532251042613174669465051256868327606783121329453124577844785770741291338048163170224764870183574855853190001231864675756254
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Standard RSA exponent
e = 65537  # 2^16 + 1

# Recover p from the leak: e_output = e + p
p = e_output - e
print(f"[+] Recovered p: {p}")

# Find q
q = n // p
assert p * q == n, "Factorization failed!"
print(f"[+] Recovered q: {q}")

# Compute private key
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

# Decrypt
m = pow(ct, d, n)
flag = long_to_bytes(m)
print(f"[+] Flag: {flag.decode()}")

Output

[+] Recovered p: 166612997784562961050427402417959231610727289110449701096278048384004974210290958240913379674222687635734122544375614765473080442343653698415642775890353274310399072042600668814731842221602949909207395384402750419354408938463901094165980590478308424439117927846922386509060315654925327343542424625687693566531
[+] Recovered q: 112821...
[+] Flag: DUCKERZ{REDACTED}

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Theory

Why This Is Critical

RSA is secure as long as factorization of n = p * q is computationally hard. Any information leak about p or q can completely compromise the system.

In this case the leak is trivial: p = e_leaked - e_known, which gives instant factorization.

Similar Vulnerabilities

  • Leak of d mod (p-1) or d mod (q-1)
  • Leak of p + q (solved via quadratic equation)
  • Leak of high bits of p (Coppersmith attack) ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍