FEAT:🚩 Daily-AlpacaHack 「Small e」Easy

20260604-daily_alpaca-crypto-easy-small_e

Summary

本問は，RSA暗号において指数部である $e$ が非常に小さいこと (Low Public Exponent) を利用する問題です．

• Category: Crypto
• Description: eがちいさe
• Tools & TechStack:
  • python
  • gmpy2
• Release: 2026/06/04

階層構造

.
├── output.txt
└── prob.py

1 directory, 2 files

---

ソースコードの調査

ソースコードを見ると，e の値が 5 という本来はあり得ない小さい値に設定されています．(本来は $e = 65537$ が一般的) これは，典型的な低指数攻撃が可能な状態です．

import os
from Crypto.Util.number import *

FLAG = os.environ.get("FLAG", "Alpaca{dummy}")
assert len(FLAG) < 50

p = getPrime(1024)
q = getPrime(1024)

n = p * q

e = 5 # what????????

m = bytes_to_long(FLAG.encode())
c = pow(m, e, n)

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

Low Public Exponent Attack

この手法は，暗号化式 $c \equiv m^e \pmod n$ において，$m$ が小さい，または $n$ が大きい場合に使えます．

• 仕組み:
  • もし $m^e < n$ である場合，モジュロ演算 $\pmod n$ が機能せず，$c = m^e$ となります．
  • このとき、$c$ の $e$ 乗根を通常の計算で求めるだけで簡単に $m$ が判明してしまいます．
• 対策:
  • 暗号化の際に，パディング (RSA-OAEPなど) を施すことで，$m$ を強制的に大きく (ランダム化) します．
  • これにより，$m^e$ が必ず $n$ を超えるようにし，単なるべき乗根計算では復号できないようにします．

復号

• n は $1024$ bitの巨大素数の積なのでサイズは，$n = 2048$ bit
• FLAG は $50$ 文字未満なので，データサイズにすると最大でも $50 \times 8 = 400$ bit程度
• 暗号化指数 $e = 5$

元の数を $5$ 乗するとビット数も約 5 倍になるため，$m^5$ は最大でも $400 \times 5 = 2000$ bit 程度に収まります． 今回 $n$ は 2048 bit であるため，確実に $m^5 < n$ が成立し，暗号化式のモジュロ演算$\pmod n$ が意味をなさなくなります．

ある数，$m$ を $N$ 乗したときの，2進数での桁数 は，対数の性質 $\log_2(m^5) = 5 \log_2 m$ より，元の桁数の $N$ 倍 になります．

RSA暗号のように非常に大きな数（多倍長整数) を扱う場合，Pythonの標準的な浮動小数点数 (float 型) を使用すると，精度限界や誤差により，正しいべき乗根を計算できません． そこで，gmpy2 ライブラリを使用して，整数としてのべき乗根を求めます．

from Crypto.Util.number import *
import gmpy2

e = 5
c = 64426504087303951813246838078441662275222839708900359133341615671136342522173619331456628167122546441601604084831803481393964091908425281568746434522937994926680805728974560373917459735665811835839800559253331009380339923486729675042508940809673293031690986041297853338860088143997503137266972063924345287607333207047324410623795727456034926116681588542164755751442528534922088003628572923240330092448273804434443462174179583212626649843445735888430144970416125998013969727919556751231951554897102023125257208495501

m, exact = gmpy2.iroot(c, e)

if exact:
    print(f"Plain text m: {long_to_bytes(m).decode()}")
else:
    print("No exact integer roots were found.")

$ python3 decrypt.py
Plain text m: Alpaca{REDACTED}

---

Post-Mortem & Dead ends

数弱にやさしい問題…嬉しい… 説明間違ってたらごめんね… ~_~

References