###### tags: `NCTU` `CS` `Course` `SecureProgramming`

HW 0x0A Write Up
==
yysung

## [Lab 10-1] Crypto Lab 1

題目給定 RSA 的公鑰 (n, e) 和以 flag 加密的加密文字 c

並且提供可以解密任意密文並回傳明文 least significant bit (LSB) 的功能

可以建構 c * 2^e = m^e * 2^e = (2m)^e 也就是 2m 的密文並傳送給 server 得到明文的 LSB

假設 0 < m < n/2 可以得知 2m < n

2m % n % 2 = 2m % 2 = 0

假設 n/2 <= m < n 可以得知 2n > 2m >= n

2m % n % 2 = (2m - n) % 2 = (偶 - 奇) % 2 = 1

就可以知道 m 的範圍是 [0, 2/n) 還是 [2/n, n)

接下來可以推廣 c * 2^(ke) = (2^k m)^e

假設 tn / 2^k < m < (t+1)n / 2^k 且 t % 2 == 0

2^k m % n % 2 = 2^k m - tn % 2 = (偶 - 偶) % 2 = 0

假設 tn / 2^k < m < (t+1)n / 2^k 且 t % 2 == 1

2^k m % n % 2 = 2^k m - tn % 2 = (偶 - 奇) % 2 = 1

可以迭代的將 m 的範圍縮小，每代都可以將範圍減少一半，做 1024 次後就會非常接近 m 的值，就可以得到 flag 了

## [Lab 10-2] Crypto Lab 2

題目是將 一段已知的文字 + 未知的 flag 作加密， flag 長度給定 17bytes

可以建構方程式

f(x) = (message * 2 ^ (8 * 17) + x) ^ e - c

並使用 sage 解方程式

解出來的根就是 flag

## [HW 0x0A] Can You Decrypt?

題目先生成三個質數 (p, q1, q2)

p 是隨機選擇數個 3~1024 之間的質數相乘再乘以 2 加 1，並且生成至質數為止

q1 和 q2 是隨機 r = 100 ~ 2^512

並以 (next_prime(r), next_prime(3 * next_prime(r))) 作為兩質數

再用 4 * randint(10, 100) 生成 e 並確保 gcd(e, phi) = 4

用 n = p * q1 * q2 和 e 作為公鑰並加密 flag 為 c

只能拿到 (n, e, c)

需要先將 p, q1, q2 解出

p 的生成方式符合 Pollard's p-1 algorithm 能解的質數

剩下的 q1, q2 可以用二分搜 100 ~ 2^512 來找出

接下來就可以開始還原 m^e

e = 388 = 4 * 97

m^e = (m\^4)^97

可以先對三個質數分別將 m^4 解出

解法是

對於質數 p
m ^ (p-1) % p == 1 (根據費馬小定理)
m ^ x % p == m when x % (p - 1) == 1

設 t = m^4
(t^97)^(invert(97, p - 1)) % p
= t^(97 * invert(97, p - 1)) % p
= t^(k(p - 1) + 1) % p (k > 0)
= (t^(k(p - 1)) % p) * (t % p) 
= t % p
= m^4 % p

接下對三個質數將 m^4 做兩次 modular_sqrt

用 Chinese Remainder Theorem 對 64 種四次方值求解

就可以在其中一種組合中還原出 flag 了

## [HW 0x0A] Yet Another Oracle

這題和 Lab 10-1 很像，只是解密時會提供到 4 bits，並且只能與程式互動 1024 / 4 + 5 次

可以建構 q[-n * t % 16] = t 的值 (0 <= t < 16)

就可以在 16^k m % 16 == -n * t % 16 將回傳值放入 q 確定 t 的值

也就可以知道這次縮小的範圍

從原本的 L, R

到 L = L + (R - L) * k / 16, R = L + (R - L) * (k + 1) / 16

並且每次都縮小 1/16，所以只要 250 次就可以得到 flag 了