RSA

1. RSA ทำงานอย่างไร

RSA สร้างกุญแจจากจำนวนเฉพาะสองตัว p และ q ความปลอดภัยทั้งหมดขึ้นอยู่กับว่า ถ้ารู้แค่ n = p·q (ซึ่งเปิดเผย) จะแยกกลับเป็น p กับ q ได้ยากมากเมื่อ n ใหญ่พอ แต่ถ้ารู้ p และ q จะคำนวณ private key ได้ทันที

1. 1เลือกจำนวนเฉพาะ p, q แล้วคำนวณ n = p·q (n เรียกว่า modulus)
2. 2คำนวณ φ(n) = (p−1)(q−1) — Euler's totient
3. 3เลือก public exponent e ที่ gcd(e, φ(n)) = 1 (นิยม e = 65537)
4. 4คำนวณ private exponent d = e⁻¹ mod φ(n) (modular inverse ของ e)
5. 5public key = (n, e) · private key = (n, d)

2. ขั้นแรกเมื่อเจอโจทย์ RSA

1. 1ตรวจ n: เอาไปค้น factordb.com — ถ้า fully factored แปลว่าจบ
2. 2ดูขนาด e: ถ้า e เล็ก (เช่น 3) → สงสัย small-e / Håstad
3. 3ดูขนาด n: ถ้าเล็ก (< ~512 bit) → ลอง factor ด้วย yafu/msieve ได้จริง
4. 4ดู p, q: ถ้าใกล้กันมาก → Fermat factorization
5. 5ดู d หรือ e ใหญ่ผิดปกติ: e ใหญ่มาก ↔ d เล็ก → Wiener attack
6. 6มีหลาย (n, c) ที่ใช้ e เดียวกัน หรือแชร์ n → common modulus / Håstad

3. การโจมตีด้วยการแยกตัวประกอบ

ถ้าแยก n เป็น p·q ได้ เกมจบทันที เพราะคำนวณ φ(n) แล้วได้ d กรณีที่ factor ได้จริงใน CTF:

• n เล็ก: n ขนาด ≤ ~256–512 bit แยกได้ด้วย yafu, msieve, หรือ SageMath factor(n)
• n อยู่ใน factordb: มีคนแยกไว้แล้ว ดึงมาใช้ได้เลย
• p, q ใกล้กัน: ใช้ Fermat factorization — เร็วมากเมื่อ |p−q| เล็ก
• p หรือ q smooth: Pollard p−1 ได้ผลเมื่อ p−1 มีแต่ตัวประกอบเล็ก

from Crypto.Util.number import inverse, long_to_bytes

# สมมติแยกได้ p, q แล้ว
p = ...
q = ...
e = 65537
c = ...
n = p * q

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

from math import isqrt

def fermat(n):
    a = isqrt(n)
    if a * a < n: a += 1
    while True:
        b2 = a * a - n
        b = isqrt(b2)
        if b * b == b2:
            return a - b, a + b
        a += 1

p, q = fermat(n)

4. Small e / Low exponent

ถ้า e เล็ก (เช่น 3) และ m เล็กพอจน mᵉ < n แล้ว c = mᵉ ตรงๆ โดยไม่มีการ mod ลดค่า — ดังนั้นแค่ถอดราก e ของ c ก็ได้ m คืน ไม่ต้องแยกตัวประกอบเลย

import gmpy2
from Crypto.Util.number import long_to_bytes

c = ...
e = 3
m, exact = gmpy2.iroot(c, e)   # ถอดรากที่ e ของ c
if exact:
    print(long_to_bytes(int(m)))
else:
    # ถ้าไม่ลงตัว m อาจ wrap รอบ n: ลอง c + k*n
    n = ...
    for k in range(10000):
        m, exact = gmpy2.iroot(c + k * n, e)
        if exact:
            print(long_to_bytes(int(m))); break

5. Wiener Attack (d เล็ก)

ถ้า private exponent d เล็กเกินไป (โดยประมาณ d < n^0.25 / 3) จะกู้ d ได้จาก continued fraction expansion ของ e/n สัญญาณคือ e ใหญ่ผิดปกติ (ใกล้ขนาด n) เพราะ e กับ d ผกผันกันใน mod φ(n) — d เล็กมักทำให้ e ใหญ่

# ใช้ไลบรารีสำเร็จ เช่น owiener
# pip install owiener
import owiener
d = owiener.attack(e, n)
if d:
    m = pow(c, d, n)
    print(long_to_bytes(m))
else:
    print("ไม่เข้าเงื่อนไข Wiener")

6. Common Modulus Attack

ถ้า message เดียวกันถูกเข้ารหัสด้วย n เดียวกัน แต่ e ต่างกันสองค่า ที่ gcd(e1, e2) = 1 จะกู้ m ได้โดยไม่ต้องรู้ d ใช้ extended Euclidean หา a, b ที่ a·e1 + b·e2 = 1 แล้ว m = c1ᵃ · c2ᵇ mod n

from Crypto.Util.number import inverse, long_to_bytes
from math import gcd

def egcd(a, b):
    if b == 0: return (a, 1, 0)
    g, x, y = egcd(b, a % b)
    return (g, y, x - (a // b) * y)

# n เดียวกัน, e1 != e2, gcd(e1,e2)=1
g, a, b = egcd(e1, e2)
# จัดการเลขชี้กำลังลบด้วย modular inverse
c1i = inverse(c1, n); c2i = inverse(c2, n)
m = 1
m = (m * pow(c1 if a > 0 else c1i, abs(a), n)) % n
m = (m * pow(c2 if b > 0 else c2i, abs(b), n)) % n
print(long_to_bytes(m))

7. Håstad Broadcast Attack

ถ้า message เดียวกัน ถูกส่งให้ผู้รับ e คน โดยแต่ละคนมี n ต่างกันแต่ใช้ e เดียวกันและเล็ก (เช่น e=3 ส่ง 3 คน) จะรวม ciphertext ด้วย Chinese Remainder Theorem (CRT) ได้ mᵉ mod (n1·n2·n3) ซึ่งเท่ากับ mᵉ จริง (เพราะ m เล็กกว่าทุก n) แล้วถอดรากที่ e

from sympy.ntheory.modular import crt
import gmpy2
from Crypto.Util.number import long_to_bytes

e = 3
ns = [n1, n2, n3]
cs = [c1, c2, c3]

M, _ = crt(ns, cs)          # CRT รวมเป็น m^e mod (n1*n2*n3)
m, exact = gmpy2.iroot(int(M), e)
if exact:
    print(long_to_bytes(int(m)))

8. Decision Tree — เลือกการโจมตี RSA

9. เครื่องมือ

# RsaCtfTool — ลองหลายการโจมตีอัตโนมัติ
git clone https://github.com/RsaCtfTool/RsaCtfTool
pip install -r RsaCtfTool/requirements.txt

# ไลบรารี Python ที่ใช้บ่อย
pip install pycryptodome gmpy2 sympy owiener

# SageMath — สำหรับงานคณิตหนักๆ (factor, lattice)
# ติดตั้งผ่าน conda หรือใช้ sagecell.sagemath.org ออนไลน์

• factordb.com — เช็คว่า n ถูกแยกไว้แล้วหรือยัง (ทำเป็นอย่างแรกเสมอ)
• RsaCtfTool — ด่านแรกแบบอัตโนมัติ
• SageMath — factor, continued fractions, lattice (Coppersmith)
• pycryptodome — inverse, long_to_bytes, จัดการ key

10. Quick Reference

• เช็ค factordb ก่อนเสมอ
• d = e⁻¹ mod φ(n), φ(n)=(p−1)(q−1)
• e=3 + m เล็ก → cube root
• e ใหญ่ → Wiener (d เล็ก)
• n เดียว e สองค่า → common modulus
• ข้อความเดียวหลาย n, e เล็ก → Håstad + CRT
• p≈q → Fermat
• จนมุม → RsaCtfTool ลองหมด

🧭 จับมือทำทีละขั้น (มีแค่ Kali) + ถ้าติดไปไหนต่อ

สมมติเปิดโจทย์มาเจอไฟล์ RSA (pubkey.pem, หรือค่า n/e/c เป็นตัวเลข) มีแค่เครื่อง Kali เปล่าๆ ทำตามลำดับนี้: ระบุว่ามีค่าอะไรบ้าง → ลอง tool อัตโนมัติก่อน → ถ้าได้ผลจบเลย → ถ้าไม่ได้ค่อยมานั่งวิเคราะห์ parameter ว่าอ่อนตรงไหนแล้วเลือก attack เฉพาะทาง → ถ้ายังไม่ได้ค่อยเปลี่ยนมุมมอง

1. 1เปิดไฟล์ดูว่ามีอะไรให้บ้าง: `cat pubkey.pem` หรือ `openssl rsa -pubin -in pubkey.pem -text -noout` เพื่ออ่านค่า n, e ออกมาเป็นตัวเลข
2. 2คัดลอกค่า n ไปค้นที่ https://factordb.com ก่อนเสมอ — ถ้าสถานะขึ้น 'FF' (fully factored) จะได้ p, q มาฟรีทันที ข้ามไปคำนวณ d ได้เลย
3. 3ยังไม่มีใน factordb → ติดตั้ง RsaCtfTool: `git clone https://github.com/RsaCtfTool/RsaCtfTool && pip install -r RsaCtfTool/requirements.txt` แล้วรัน `python3 RsaCtfTool.py --publickey pubkey.pem --uncipherfile flag.enc` ให้มันลองการโจมตีมาตรฐานทั้งหมดอัตโนมัติ
4. 4RsaCtfTool ไม่สำเร็จ → เริ่มวิเคราะห์ parameter เอง ขั้นแรกดูขนาด e: ถ้าเล็กมาก (เช่น e=3) ให้สงสัย low-exponent/Håstad
5. 5ดูขนาด n (bit length): ถ้าเล็ก (≤ ~512 bit) ลอง factor เองด้วย `python3 -c "from sympy import factorint; print(factorint(n))"` หรือใช้ https://www.alpertron.com.ar/ECM.HTM (ECM factorization ออนไลน์ ฟรี ไม่ต้องติดตั้งอะไร)
6. 6ดูว่า e ใหญ่ผิดปกติไหม (ใกล้เคียงขนาด n) → สงสัย d เล็ก → ลอง Wiener attack: `pip install owiener` แล้วรัน `owiener.attack(e, n)`
7. 7มีหลายไฟล์ (n1,c1), (n2,c2), ... ไหม? เช็คว่า n ต่างกันแต่ e เดียวกัน+ข้อความเดียวกัน (Håstad broadcast, ใช้ CRT) หรือ n เดียวกัน e ต่างกัน (common modulus)
8. 8ยังไม่มีจุดอ่อนชัดเจน → เปิด https://sagecell.sagemath.org (SageMath ในเบราว์เซอร์ ไม่ต้องติดตั้ง) รันคำสั่งหนักๆ เช่น `factor(n)`, `continued_fraction`, หรือ Coppersmith/lattice attack ที่ python ธรรมดาทำไม่ได้
9. 9ได้ p, q หรือ d มาแล้ว → คำนวณ `phi=(p-1)*(q-1)`, `d=inverse(e,phi)`, `m=pow(c,d,n)`, `long_to_bytes(m)` ดู flag
10. 10ลองทุกอย่างแล้วยังไม่ได้เลย → ทบทวนว่าโจทย์อาจไม่ใช่ RSA มาตรฐาน (เช่นเป็น key exchange แบบ Diffie-Hellman ที่ทำหน้าตาคล้าย RSA หรือมี custom padding) → กลับไปอ่านโจทย์ใหม่ทั้งหมด