# 2025-12-21_"Buggy RSA (my_pow)": 251221 Level: Medium Type: Crypto Solved day: 2025-12-21 ## Solution ### Observation: `my_pow` は「累乗」ではなく加算 `problem.py` の `my_pow(a, n, m)` は繰り返し二乗法を意図しているが、更新式が掛け算ではなく足し算になっている。 - 本来: `result = (result * a) % m` - 実際: `result = (result + a) % m` - 本来: `a = (a * a) % m` - 実際: `a = (a + a) % m` このため、ビット分解した $n$ に対して $a$ を倍々にしながら足し込む「加算的な処理」になり、初期値 $result=1$ が残ることから $$\mathrm{my\_pow}(a, n, m) \equiv 1 + a \cdot n \pmod{m} \quad (n \ge 0)$$ が成立する。 --- ### Apply to encryption 暗号化は $$c = \mathrm{my\_pow}(\mathrm{flag}, e, N)$$ である。よって上の性質から $$ c \equiv 1 + \mathrm{flag} \cdot e \pmod{N} $$ が成り立つ。両辺を整理すると $$ \mathrm{flag} \equiv (c - 1) \cdot e^{-1} \pmod{N} $$ ここで $e^{-1}$ は法 $N$ における $e$ の逆元。 --- ### Recover the flag (given $N, e, c$) `output.txt` より - $N = 1421524\ldots$ - $e = 257$ - $c = 1032307\ldots$ したがって $$ \mathrm{flag} \equiv (c - 1)\, e^{-1} \pmod{N} $$ を計算し、整数からバイト列へ変換すればよい。 ```python # solve.py N = 142152419619953056039030613006300356362328489550709389999387369748296278181079224756839343268342516013642694413617303501060708009652311527189475960379078488611592094334453807443536588862100338035073773947550237167141330041879985706663975671411606265404764401055491939553565105755943917581461262323010934286591 e = 257 c = 1032307400372525030420319173259503709384961767939821142794251896087430140750696054688678035256705431662987859651860033467060026426212901209540363 # flag ≡ (c-1) * e^{-1} (mod N) flag_int = ((c - 1) * pow(e, -1, N)) % N # int -> bytes flag = flag_int.to_bytes((flag_int.bit_length() + 7) // 8, "big") print(flag.decode()) ``` 出力: ``` TSGLIVE{g0od_Mult1plic4t10N-Algor1thm_6y_ru55iAn_Pea5ants} ``` --- ## How I thought ### 重要な観察 1. `my_pow` の更新式が乗算ではなく加算 - `result = (result + a) % m` - `a = (a + a) % m` 2. これは「ビットに応じて倍々の $a$ を足す」加算的処理（Russian peasant multiplication の加算版） 3. 初期値 $result=1$ が残るため $$ \mathrm{my\_pow}(a, n, m) = 1 + a n \pmod{m} \quad (n \ge 0) $$ ### 暗号化が一次式に崩壊 $$ c = \mathrm{my\_pow}(\mathrm{flag}, e, N) \implies c \equiv 1 + \mathrm{flag}\cdot e \pmod{N} \] \[ \therefore\ \mathrm{flag} \equiv (c-1)\cdot e^{-1} \pmod{N} $$ ### 実装上のバグメモ 復号側で `d = my_pow(e, -1, phi)` としているが、`while n > 0` のため $n=-1$ ではループに入らず $1$ を返す。 結果として $d=1$ となり、復号チェックが失敗して `"there is a bug i guess lol"` が出る。