← Back to Posts
LA CTF 2026 - smol cats

LA CTF 2026 - smol cats

Updated Feb 6, 2026 · Created Feb 6, 2026

Challenge

Category: Crypto

My cat walked across my keyboard and made this RSA implementation, encrypting the location of the treats they stole from me! However, they already got fed twice today, and are already overweight and needs to lose some weight, so I cannot let them eat more treats. Can you defeat my cat's encryption so I can find their secret stash of treats and keep my cat from overeating?

nc chall.lac.tf 31224

Server output:

*meow*
Welcome to my cat cafe!

I'm a hungry kitty and I've hidden my treats in a secret place.
I will let you know where I hid them if you can defeat my encryption >.<
I encrypted the number of treats I want with RSA... but my paws are small, so I used tiny primes.
*purrrrr*

n = 660289671266058737386056037755899774496778046642488625721661
e = 65537
c = 618497865818120176989295124586476350685787000447688005721525

*mrrrow?*
How many treats do I want?

Solution Summary

Solved by using this online factorization tool: https://www.alpertron.com.ar/

Process

01 Reviewing RSA basics

RSA in a nutshell:

  • Key generation: n = p × q, φ(n) = (p-1)(q-1), e × d ≡ 1 (mod φ(n))
  • Encrypt: c = m^e mod n
  • Decrypt: m = c^d mod n
  • Public key: (n, e), Private key: (n, d)

To break RSA: factor n into p and q → compute φ(n) → compute d → decrypt

02 Realizing 60 decimal digits ≈ 200 bits, which is very weak

How to convert between decimal and binary digits:

  • Binary digits ≈ log₂(N)
  • Decimal digits ≈ log₁₀(N)
  • Relationship: decimal digits ≈ binary digits × 0.301

Simply put: 1 decimal digit ≈ 3.32 binary bits (because 2^3.32 ≈ 10)

So 60 decimal digits ≈ 200 bits, way below the safe standard (2048 bits).

03 Tried many factorization methods, all failed

  1. Pollard's p-1 - Failed. p-1 is not smooth (a smooth number has only small prime factors)
  2. Fermat factorization - Failed. p and q are not close to each other
  3. factordb lookup - Most n values had no record in the database
  4. GCD attack - Collected 50 different n values, computed pairwise gcd, found no common factors
  5. primefac / sympy - Python libraries were too slow
  6. Brute force small m - Tried up to 100 million, no match
  7. Trial division for small factors - Tried up to 100 million, found nothing

04 Used Alpertron online factorizer, succeeded

https://www.alpertron.com.ar/ECM.HTM

This website uses WebAssembly with ECM (Elliptic Curve Method) and SIQS (Self-Initializing Quadratic Sieve). It factored the 200-bit number in 2.8 seconds.

Why Python libraries failed: poor implementation, missing SIQS algorithm, unoptimized parameters.