AIS3 Junior 2026 Day3 Writeup : Crypto

n = 5767
p = 73
e = 7
c = 4780
 
# q = n/p
q = int(n/p)
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
m = pow(c,d,n)
 
print("AIS3" + "{" + str(m) + "}")

for p in range(2, int(n**0.5) + 1):
    if n % p == 0:
        q = n // p
        break
 
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
 
print(f"p = {p}")
print(f"q = {q}")
print(f"phi = {phi}")
print(f"d = {d}")
print(f"m = {m}")
print(f"\nFlag: AIS3{{{m}}}")

n = 10000000000000000000000006692600000000000000000000673971373
e = 3
c = 104113716851630291574772668658086347914139279774012288613
 
 
def integer_nth_root(x: int, n: int) -> int:
    """回傳 floor(x^(1/n))，用二分搜尋避免浮點數誤差。"""
    if x == 0:
        return 0
    lo, hi = 0, 1 << ((x.bit_length() // n) + 1)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if mid ** n <= x:
            lo = mid
        else:
            hi = mid - 1
    return lo
 
 
m = integer_nth_root(c, e)
 
assert m ** e == c, "開根失敗，c 可能已對 n 取模，需改用其他攻擊法"
 
pt_bytes = m.to_bytes((m.bit_length() + 7) // 8, byteorder="big")
 
print("m (整數) =", m)
print("明文 (bytes) =", pt_bytes)
print("明文 (str)   =", pt_bytes.decode())

import re
 
def caesar_decode(s, shift):
    result = []
    for c in s:
        if 'a' <= c <= 'z':
            result.append(chr((ord(c) - ord('a') - shift) % 26 + ord('a')))
        elif 'A' <= c <= 'Z':
            result.append(chr((ord(c) - ord('A') - shift) % 26 + ord('A')))
        else:
            result.append(c)
    return ''.join(result)
 
INPUT_FILE = 'challenge.txt'  # 放同一目錄下
 
with open(INPUT_FILE) as f:
    lines = f.readlines()
 
flag_counts = {}
flag_source_line = {}
 
for line in lines:
    line = line.rstrip('\n')
    for shift in range(26):
        dec = caesar_decode(line, shift)
        m = re.search(r'AIS3\{[^}]*\}', dec)
        if m:
            flag = m.group(0)
            flag_counts[flag] = flag_counts.get(flag, 0) + 1
            flag_source_line.setdefault(flag, dec)
            break  # 找到符合格式的位移就停止，換下一行
 
# 出現次數最少（=1）的就是真正的 flag
real_flag = min(flag_counts, key=lambda k: flag_counts[k])
 
print("所有解出的 flag 與出現次數：")
for flag, cnt in sorted(flag_counts.items(), key=lambda x: x[1]):
    print(f"  {cnt:5d}  {flag}")
 
print()
print("真正的 flag：", real_flag)
print("該行解密後內容：", flag_source_line[real_flag])

n = 21968021
p = 5323
q = 4127
e = 17
c = 5854946
 
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
m = pow(c,d,n)
 
print(str(m))

# 檢查 x 是否為負數，RSA 中的密文不能是負數，除非是０，因為０的任何次方根都是０
 
def integer_nth_root(x: int, n: int) -> int:
 
    if x < 0:
        raise ValueError("x must be non-negative")
    if x == 0:
        return 0
 
 # 二分搜尋找ｎ次方根
    lo, hi = 0, 1 << ((x.bit_length() // n) + 1)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if mid ** n <= x:
            lo = mid
        else:
            hi = mid - 1
    return lo
 
 # 立方根攻擊
def cube_root_attack(n: int, e: int, c: int):
 
    root = integer_nth_root(c, e)
 
    if root ** e == c:
        return root
    return None
 
 # 把數字轉 bytes
def int_to_bytes(m: int) -> bytes:
    length = (m.bit_length() + 7) // 8
    return m.to_bytes(length, byteorder="big")
 
def main():
    n = 468359974447286090812229949402868393194905269978966009744154040701149709191284286159384127221110732613
    e = 3
    c = 138390867184400671369429485315529066403913401512756077717260811128013885680231233545090894181
 
 # 計算m
    m = cube_root_attack(n, e, c)
 
 # 嘗試開根
    if m is None:
        print("[-] 直接開根失敗")
        print("c 可能已經對 n 取模過")
        return
 
    print(f"[+] 還原出的明文 m (整數) = {m}")
 
# 嘗試轉文字
    try:
        pt_bytes = int_to_bytes(m)
        print(f"[+] 明文 (bytes) = {pt_bytes}")
        print(f"[+] 明文 (str)   = {pt_bytes.decode()}")
    except Exception as err:
        print(f"[-] 轉換成文字失敗: {err}")
 
 
if __name__ == "__main__":
    main()