LA CTF 2026 - smol cats
题目
分类： 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?
（我的猫踩过键盘弄出了这个 RSA 实现，加密了它偷走的零食藏匿位置！但它今天已经吃了两顿了，已经超重需要减肥，所以我不能让它再吃了。你能破解我猫的加密，找到它的秘密零食藏匿处吗？）
nc chall.lac.tf 31224
服务器输出：
*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?
解法总结
使用这个网站的分解质因数就解决了：https://www.alpertron.com.ar/
过程
01 看到 RSA 的题目，回顾一下基础
RSA 核心公式：
- 密钥生成：
n = p × q，φ(n) = (p-1)(q-1)，e × d ≡ 1 (mod φ(n)) - 加密：
c = m^e mod n - 解密：
m = c^d mod n - 公钥：
(n, e)，私钥：(n, d)
02 意识到 60 位十进制数约为 200 位二进制数，是非常不安全的
位数换算原理：
- 一个数 N 用 k 位二进制表示：
k ≈ log₂(N) - 用 m 位十进制表示：
m ≈ log₁₀(N) - 两者关系：
m = k × log₁₀(2) ≈ k × 0.301
直观理解：每 1 个十进制位 ≈ 3.32 个二进制位（因为 2^3.32 ≈ 10）
所以 60 位十进制 ≈ 200 位二进制，远低于安全标准（2048 位）。
03 尝试了多种分解方法，但均失败
- Pollard's p-1 - 失败，p-1 不是光滑数（光滑数是指所有质因子都小于某个界限 B 的数）
- Fermat 分解 - 失败，p 和 q 不接近（Fermat 分解利用 n = a² - b² = (a+b)(a-b)，当 p、q 接近时 a ≈ √n）
- factordb 查询 - 大部分 n 没有记录（factordb 是众包的因数分解数据库）
- GCD 攻击 - 收集 50 个 n，两两计算 gcd，没有公因子（如果多个 n 共享质因子，gcd 可以快速找到）
- primefac / sympy - Python 库分解太慢，不实用
- 暴力枚举小 m - 尝试到 1 亿没命中（猜测 treats 数量很小）
- 试除小因子 - 尝试到 1 亿没找到
04 使用 Alpertron 在线工具分解，成功
https://www.alpertron.com.ar/ECM.HTM
该网站使用 WebAssembly 实现，结合 ECM（椭圆曲线法）和 SIQS（二次筛法），2.8 秒内完成分解。
Python 库失败的原因：实现质量差、缺少 SIQS 算法、参数未优化。