---
tags: 資訊安全實務
---
# HW2

## RSA

這題n為三個質數乘起來，一開始看到想說到底是啥，三個大質數感覺也沒有明顯的漏洞讓我鑽到底是怎樣，但是看了很久的code後發現next_prime可以用數學的形式來表達：
$$
q1 = next\_prime(2 \times p) = 2p + x_1 \\
q2 = next\_prime(3 \times q1) = 6 \times p + 3x_1 + x_2 \\
n=p \times q_1 \times q_2 = p \times (2p + x_1) \times (6p + 3x_1 + x_2)
$$
那用上述得到的n的新的表達式後，我們可以找出n一定會大於某個跟p有關的數字，因為q1跟q2一定也是質數所以x1跟x2一定會大於0，所以我如果將x1跟x2帶0進去，可以得到
$$
12p ^ 3 < n
$$
至於為什麼要帶0呢，因為n我們是已知的，p不知到，而他的q1跟q2又是有p就能夠得到的，所以我想知道n到底跟p有甚麼關係，是不是可以用n來推出p可能是多少這樣，沒錯在得到上面的關係之後我就又得到了一件事情，將上面的那個改寫一下就會變成
$$
p < (\frac{n}{12})^\frac{1}{3}
$$
所以我現在至少得到了n除上12後再開三方會大於p，但是我不知到跟p會差多少，所以我就寫了code跑了一萬次去觀察這兩個的差距

max = -1
min = getPrime(513)
for i in range(10000):
    p = getPrime(512)
    q1 = next_prime(2 * p)
    q2 = next_prime(3 * q1)
    n = p * q1 * q2
    p_ = n // 12
    p_ = gmpy2.iroot(p_, 3)[0]
    if p_ - p > max:
        max = p_ - p
    if p_ - p < min:
        min = p_ - p
print(max, min)

最後得到的max為1054、min為1，發現差距好像不會到很大，雖然我只跑1萬次可能不夠但我覺得應該也是能找到大致上的區間所以最後再找p的時候我就用了這樣的想法下去解flag，因為n已知，所以寫起來很簡單

p = n // 12
p = gmpy2.iroot(p, 3)[0]
for i in range(1054):
    p = p - 1
    if n % p == 0:
        break

找到p後flag也可以很快的解出來

q1 = next_prime(2 * p)
q2 = next_prime(3 * q1) 
phi = (p - 1) * (q1 - 1) * (q2 - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

FLAG：

FLAG{Ew9xeANumjDr6bXemHsh}

---

## LSB

這題基本上就是把上課中LSB提到的解法二拿來改一下就能夠解出來了，原本課堂上講到的是每次能拿到最後一個bit，而題目中是每次能拿到m模3下的結果，也就是說其實就是從原本能拿到**2進制下的最後一位變成3進制下的最後一位**

* 原本我們為了要一個bit慢慢出來所以要一直乘在模n下的2的e次方的inverse
* 但是因為現在是3進制所以變成要乘在模n下的3的e次方的inverse

base = 3
inv  = inverse(base, n)
inv_pow_e = pow(inv, e, n)

接下來再用一個做log3(n)次的迴圈來慢慢解出flag的3進制下最後一位的值，**原本模2的都改成模3**，每次得到解果後再對cipher乘上上面的inv_pow_e，為了要運算下一個bit我們需要把每次得到的bit加上去後再乘上模n下的3的inverse，不太會講解，借上課投影片的一部分來用，就是要解以下的等式
所以最後code寫起來就會變成

x = 0
flag = ''
for i in range(int(math.log(n,base)) + 1):
    r.sendline(str(cipher))
    r.recvuntil("m % 3 = ")
    last_bit = int(str(r.recvline().strip()).split("b'")[1][:-1])
    last_bit = (last_bit - x) % base
    x = (x + last_bit) * inv
    x = x % n
    flag = str(last_bit) + flag
    cipher = (cipher * inv_pow_e) % n

得到3進制下的flag後我們要再把他轉成整數後再轉乘byte後就能順利拿到FLAG了

flag = int(flag,base)
print(long_to_bytes(flag))

FLAG：

FLAG{nF9Px2LtlNh5fJiq3QtG}