FEAT:🚩 Daily-AlpacaHack 「Lazy RSA」Medium

20260707-daily_alpaca-crypto-medium-lazy_rsa

Summary

本問は，与えられた式とRSAの性質を用いて復号する問題です．

• Category: Crypto
• Description: simple RSA challenge
• Tools & TechStack:
  • Python
  • RSA
• Release: 2026/07/07

階層構造

.
├── chall.py
└── output.txt

1 directory, 2 files

---

ソースコードの調査

• 既知の値:
  • 法: $n$，
  • 公開指数: $e$
  • 暗号文: $c$
  • 謎の式: $hint = 12345p + 6789q$

この問題では，以上の値が与えられていました．
RSAの実装に明らかな脆弱性 (Low Public Exponent) 等は見当たりません．
しかし，明らかに怪しい $hint$ という方程式の値が与えられています．

from Crypto.Util.number import bytes_to_long, getPrime
import os

FLAG = os.getenv("FLAG", "Alpaca{DUMMY}").encode()

p = getPrime(512)
q = getPrime(512)

n = p * q
e = 65537
m = bytes_to_long(FLAG)
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")


hint = 12345 * p + 6789 * q
print(f"hint = {hint}")

解法

これ以降 $hint$ は $h$ で表します．

基本的に，$p$ 又は $q$ が求まれば，勝ち確定なのでこれらを求める方法を考えます．
そこで，$h$ と $n$ を用いて式変形を行います．

• $(1)$: $n = p \times q$
• $(2)$: $h = 12345p + 6789q$

まず，$(1)$ を $p$ の式に変形します．これを $(1´)$ とします．

\[\begin{equation} p = \dfrac{n}{q} \tag{1´} \end{equation}\]

$(1´)$ を $(2)$ に代入し，二次方程式の形に変形します．これを $(2´)$ とします．
ここでは，数式の見やすさのために右辺に項をまとめました．

\[\begin{align} h &= \dfrac{12345n}{q} + 6789q && \text{(両辺にqを掛ける)} \tag{_} \\[1em] hq &= 12345n + 6789q^2 && \text{(右辺に項をまとめる)} \tag{_} \\[1.5em] 0 &= 6789q^2 - hq + 12345n && \text{(二次方程式の形になる)} \tag{2´} \end{align}\]

この二次方程式 $(2´)$ の解を求めることで $q$ が求まります．
$q$ が求まれば，$p$ も求まります
よって，オイラーのトーシェント関数 $\phi(n)$ を計算することができるため，公開鍵 $e$ のモジュラ逆元を求めることでペアの秘密鍵 $d$ が求まります．

ソルバを書く

二次方程式のパラメータ

• $a = 6789$
• $b = -h$
• $c = 12345n$

solver.py

from Crypto.Util.number import long_to_bytes
import gmpy2

n = 159466129476563295436347862001255565240940055609384334202080215034063242852861358770517434524498515932986961274901993192106432817519008877999503622745987595254746641156303744954759431379295820380141814296184300394860044108262464658534230769898481575285420352180271132787942798821425677756246493582502747616357
e = 65537
c = 18160494759145339379951302499323594611356138324512166816388060187789981269722579002083153372886981308982631541959285832078221093347791329099993480181958817729342394236230802614594798201847109031654651455924886228031425247207279096267193816152904607098836195791985422178998085249098906675937782774343726361777
hint = 244611475162513490470729413381457653047269592250951392605393462745266220610881377220327603199675933463628766491575241878722215039997853667247644627404966619214

def solve_quadratic(a, b, c):
    d = b**2 - 4*a*c
    sqrt_d = gmpy2.isqrt(d)
    
    if d > 0:
        x1 = (-b + sqrt_d) // (2*a)
        x2 = (-b - sqrt_d) // (2*a)
        return (x1, x2)
    elif d == 0:
        x = -b // (2*a)
        return (x, x)
    else:
        return (0, 0) # 解なし

# 二次方程式を解く
x1, x2 = solve_quadratic(6789, -hint, 12345*n)

# 正しい素因数であるかを確認
if n % x1 == 0:
    p, q = n // x1, x1
else:
    p, q = n // x2, x2

assert p * q == n

phi = (p - 1) * (q - 1)

d = gmpy2.invert(e, phi)

m = pow(c, d, n)
flag = long_to_bytes(m)

print(f"q: {q}")
print(f"p: {p}")
print(f"Flag: {flag}")

---

Post-Mortem & Dead ends

Crypto苦手でも解ける問題でよかったぁ~

References