Vigenère Cipher

1. หลักการทำงาน

Vigenère คือ Caesar หลายตัวต่อกัน โดยใช้คำกุญแจ (keyword) มากำหนด shift ของแต่ละตำแหน่ง เช่น key = KEY หมายถึง ตัวอักษรตำแหน่งที่ 1 เลื่อนด้วย K(=10), ตำแหน่ง 2 เลื่อนด้วย E(=4), ตำแหน่ง 3 เลื่อนด้วย Y(=24) แล้ววนซ้ำ key ไปเรื่อยๆ จุดแข็งเหนือ Caesar คือตัวอักษรเดียวกันใน plaintext อาจกลายเป็นคนละตัวใน ciphertext ทำให้ frequency analysis แบบ Caesar ใช้ไม่ได้ตรงๆ

สูตร: C_i = (P_i + K_(i mod m)) mod 26 และถอดด้วย P_i = (C_i − K_(i mod m)) mod 26 โดย m คือความยาว key — การโจมตีทั้งหมดเริ่มจากการหา m ให้ได้ก่อน

2. สังเกตอย่างไร

• ข้อความเป็นตัวอักษรล้วน ความยาวคงที่ แต่ frequency แบนกว่าภาษาอังกฤษปกติ (ไม่มีตัวไหนเด่นชัดเหมือน E ใน Caesar)
• ลอง Caesar brute 25 แบบแล้วไม่มีอันไหนอ่านออก — บ่งชี้ polyalphabetic
• โจทย์ใบ้คำว่า key, keyword, passphrase, Vigenère, polyalphabetic
• Index of Coincidence ของข้อความต่ำกว่า ~0.067 (ค่าภาษาอังกฤษ) แต่สูงกว่าข้อความสุ่ม (~0.038)

3. หาความยาว key — Kasiski + Index of Coincidence

Kasiski examination: หาลำดับตัวอักษรที่ซ้ำกันใน ciphertext (เช่น 3 ตัวขึ้นไป) แล้ววัดระยะห่างระหว่างการซ้ำ ความยาว key มักเป็นตัวประกอบร่วม (GCD) ของระยะห่างเหล่านั้น เพราะคำเดียวกันที่ตรงกับตำแหน่ง key เดียวกันจะเข้ารหัสออกมาเหมือนกัน

Index of Coincidence (IC): วัดความน่าจะเป็นที่ตัวอักษรสองตัวสุ่มจะเหมือนกัน ภาษาอังกฤษ IC ≈ 0.067, สุ่ม ≈ 0.038 วิธีใช้: แบ่ง ciphertext เป็นกลุ่มตามความยาว key ที่เดา (ทุกตัวที่ห่างกัน m ตำแหน่ง) แล้วคำนวณ IC เฉลี่ย — ความยาว key ที่ถูกต้องจะให้ IC ใกล้ 0.067

from collections import Counter

def ic(text):
    n = len(text)
    if n < 2: return 0
    counts = Counter(text)
    return sum(c*(c-1) for c in counts.values()) / (n*(n-1))

def avg_ic_for_keylen(ct, m):
    groups = ['']*m
    for i, ch in enumerate(ct):
        groups[i % m] += ch
    return sum(ic(g) for g in groups) / m

ct = "".join(c for c in CIPHERTEXT.upper() if c.isalpha())
for m in range(1, 15):
    print(m, round(avg_ic_for_keylen(ct, m), 4))
# ความยาว key ที่ให้ค่าใกล้ 0.067 ที่สุดคือคำตอบ

4. กู้ key — แตกเป็น Caesar หลายชุด

เมื่อรู้ความยาว key = m แล้ว ปัญหากลายเป็น Caesar m ชุดอิสระ เพราะตัวอักษรทุกตัวที่ตำแหน่ง i, i+m, i+2m, ... ถูกเลื่อนด้วย key ตัวเดียวกัน จับมันมารวมกลุ่ม แล้วแก้แต่ละกลุ่มแบบ Caesar (frequency analysis หรือ brute 26) จะได้ key ทีละตัว

from collections import Counter

ENGLISH_FREQ = "ETAOINSHRDLCUMWFGYPBVKJXQZ"

def best_shift(group):
    best, best_score = 0, -1
    for s in range(26):
        dec = "".join(chr((ord(c)-65-s)%26+65) for c in group)
        # ให้คะแนนจากความถี่ที่ใกล้ภาษาอังกฤษ
        score = sum(dec.count(ch) * (26-i) for i, ch in enumerate(ENGLISH_FREQ))
        if score > best_score:
            best_score, best = score, s
    return best

m = KEY_LENGTH
groups = ['']*m
for i, ch in enumerate(ct):
    groups[i % m] += ch

key = "".join(chr(best_shift(g)+65) for g in groups)
print("recovered key:", key)

5. Decision Tree

6. Quick Reference

• C = (P + K) mod 26 · P = (C − K) mod 26
• หา key length ด้วย Index of Coincidence (เป้าหมาย ~0.067) หรือ Kasiski (GCD ของระยะซ้ำ)
• รู้ key length แล้ว → แตกเป็น Caesar m ชุด แก้ทีละกลุ่ม
• เครื่องมือเร็ว: dcode.fr, CyberChef Vigenère Decode
• ข้อความยิ่งยาว ยิ่งถอดง่าย (สถิตินิ่ง)

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

สมมติ brute Caesar ทั้ง 25 shift แล้วไม่มีอันไหนอ่านออกเลย สงสัยว่าน่าจะเป็น Vigenère มีแค่เครื่อง Kali เปล่าๆ ทำตามนี้ทีละขั้น

1. 1ยืนยันก่อนว่าไม่ใช่ Caesar ธรรมดา: brute 25 shift ไม่มีอันไหนอ่านออกเลย และ histogram ตัวอักษรแบนกว่าภาษาอังกฤษปกติ
2. 2ทางลัดที่เร็วที่สุด: เอา ciphertext ไปวางที่ https://www.dcode.fr/vigenere-cipher แล้วกดปุ่ม 'Automatic' — มันจะลองหา key length และ key ให้อัตโนมัติ
3. 3ถ้า dcode หาไม่ได้ (ข้อความสั้นไป) → เขียน python เอง: ตัดอักขระที่ไม่ใช่ a-z ออกก่อน (`ct = ''.join(c for c in raw.upper() if c.isalpha())`)
4. 4หาความยาว key ด้วย Index of Coincidence: รัน loop m=1..15 ตามโค้ดด้านบน (`avg_ic_for_keylen`) — ดูว่า m ไหนให้ค่าใกล้ 0.067 (ภาษาอังกฤษ) ชัดเจนที่สุด
5. 5ได้ m แล้ว → transpose ciphertext เป็น m กลุ่มตามตำแหน่ง (`i % m`) แล้วรัน `best_shift()` กู้ shift/ตัวอักษร key ทีละตำแหน่ง
6. 6ประกอบตัวอักษร key ที่ได้เป็นคำ — ถ้าออกมาเป็นคำที่มีความหมาย (เช่น SECRET, KEYWORD) ยิ่งมั่นใจว่าถูก
7. 7ใช้ key ที่ได้ถอดทั้งข้อความด้วยสูตร P = (C − K) mod 26 แล้วดูว่าอ่านออกเป็นภาษาอังกฤษ/มี flag{ ไหม
8. 8รู้ plaintext บางส่วนอยู่แล้ว (crib เช่นขึ้นต้นด้วย 'flag{' หรือ 'the') → กู้ key ตรงๆ จากส่วนนั้นด้วย K = C − P แล้วเช็คว่า pattern ซ้ำเป็น key เดียวกันไหม
9. 9ผลไม่อ่านออก → ลองความยาว key อันดับรองจาก IC (อันดับ 2, 3 ที่ได้จาก loop) แทนอันดับ 1
10. 10ยังไม่ได้เลยหลังลองทุกทาง → อาจไม่ใช่ Vigenère มาตรฐาน (key ซ้ำ) แต่เป็น Autokey/running-key cipher (key ไม่ซ้ำ ยากกว่ามาก) — ลองหา context อื่นในโจทย์ (ชื่อไฟล์ คำใบ้) ก่อนลงมือคำนวณหนักๆ