---
# System prepended metadata

title: HW0x01 Writeup (Crypto)
tags: [Computer Security]

---

###### tags: `Computer Security`

# HW0x01 Writeup (Crypto)
[TOC]

## 1. nLFSR

先建出Companion Matrix：
```python=
poly = 0xaa0d3a677e1be0bf
binpoly = str(poly.binary())
F.<x> = PolynomialRing(GF(2))
pList = []

for i in range(len(binpoly)):
    pList.append(-int(binpoly[i]))
pList.append(1)
C = companion_matrix(pList, format = 'bottom')
```
C是64x64的矩陣，所以我們會需要64個bits來解出key，可以先隨便輸出，用一開始給的1.2$得到這些bits（可能錢會不夠但機率不大)
```python=
out = []
previous = 1.2
for i in range(64):
    r.sendline(b'0')
    line = r.recvline().decode()
    money = float(line.split('> ')[1].split('\n')[0])
    if (money > previous): #correct ansewr
        out.append(0)
    else: #wrong answer
        out.append(1)
    previous = money

print(out)
```
又，從server code可以看出output每過43次step會output一次，不是連續的，所以C不能直接拿來用
可以用課程說的方式把真正拿來解key時要用的Matrix建出來

```python=
m = matrix(GF(2), 64)
A = C^42
unit = C^43
for i in range(64):
    row =  A * (unit^(i))
    m[i] = row[0]
# m * key = out
b = vector(out)
kl= m^-1 * b
```
有了key就可以讓它生成一串output，再丟回去給server，拿到flag。
```python=
ans = []
for i in range(64, 64+121):
    outputrow = A * (unit^(i)) * kl
    output = outputrow[0]
    ans.append(output)
print(ans)
```

:::success
:triangular_flag_on_post: FLAG{2iroO742LwA2ES1Cwewx}
:::


---

## 2. Single

題目給了兩個橢圓曲線上的點，可以先用這兩個點把曲線的係數a、b求出來：
```python=
numerator = (((A.y ** 2) % p) - ((B.y ** 2) % p) - 
             (((A.x ** 3) % p) - ((B.x ** 3) % p))) % p
denominator = (A.x - B.x) % p

a = numerator * inverse(denominator, p) % p
b = (((A.y ** 2) % p) - ((A.x ** 3) % p) - ((a * A.x) % p)) % p
```

求出來後就可以發現4a^3^+27b^2^=0(mod p)

:::info
a =
9605275265879631008726467740646537125692167794341640822702313056611938432994
b = 7839838607707494463758049830515369383778931948114955676985180993569200375480
4a^3 + 27b^2 = 0
:::

    
為了得知該Singular曲線是Node型還是Cusp型，可以用Sage的roots()來找根：
```python=
a = 9605275265879631008726467740646537125692167794341640822702313056611938432994
b = 7839838607707494463758049830515369383778931948114955676985180993569200375480
x = PolynomialRing(GF(p), 'x').gen()
eq = x^3 + a * x + b
roots = eq.roots()
```
:::info
[(7925182757193285961316626419940151258451119718064102936455321651294650340555,
  1),
(853242911173207820721903052331400912971957115055181874915218687301323932414,
  2)]
:::
有一根及一二重根，故為Node型。

從講義得知，Node型的曲線可以藉由定義$φ(P(x,y))=\dfrac{y+\sqrt{α-β}(x-α)}{y-\sqrt{α-β}(x-α)}$
來得到φ(dP)=φ(P\)^d^，接著可以用Pohlig-Hellmen把d求出。
```python=
alpha = roots[1][0]
beta = roots[0][0]
t = GF(p)(alpha - beta).square_root()
def phi(P):
    numer = P.y + t * (P.x - alpha)
    denom = P.y - t * (P.x - alpha)
    return (numer / denom) % p

# phi(A) = phi(G)^dA
ca = phi(A)
cb = phi(B)
g = phi(G)
p = 9631668579539701602760432524602953084395033948174466686285759025897298205383
n = factor(p-1)

def pohel(g, c, n):
    f = [fi[0] for fi in n]
    x = []
    for fi in f:
        gi = pow(g, (p-1)//fi, p)
        hi = pow(c, (p-1)//fi, p)
        xi = bsgs(gi, hi, (0, fi))
        x.append(xi)
    k = crt(x, f)
    #pow(g, k, n) == c
    return k

dA = pohel(g, ca, n)
dB = pohel(g, cb, n)
dA, dB
```
:::info
(1532487521612462894579517163606359285989568203515734083099567402780433190052,
3812736493733305483749266829321957602546252009705107605004286667532073783392)
:::
有了dA、dB後就可以把flag解出來了。
```python=
dA = 1532487521612462894579517163606359285989568203515734083099567402780433190052
dB = 3812736493733305483749266829321957602546252009705107605004286667532073783392

#Decryption
k = point_multiply(B, dA).x
k = hashlib.sha512(str(k).encode('ascii')).digest()
flag = bytes(ci ^ ki for ci, ki in zip(enc.ljust(len(k), b'\0'), k))
flag
```
:::success
:triangular_flag_on_post: FLAG{adbffefdb46a99fad0042dd3c10fdc414fadd25c}
:::

---

## 3. HNP-rev

解法與講義上的方法類似，差別在於k多了一項常數md5(b'secret').hexdigest()
令這個常數為α(轉成數字後要再乘2^128^，這邊不小心踩到坑qq)，講義式子的k~1~、k~2~換成k~1~+α、k~2~+α並代入可以得到如下的結果：

$k_1+α-s_1^{-1}h_1-s_1^{-1}r_1s_2r_2^{-1}k_2-s_1^{-1}r_1s_2r_2^{-1}α+s_1r_1r_2^{-1}h_2\equiv0\ (mod\ n)$

只要改令v、u為：
$v=-s_1^{-1}r_1s_2r_2^{-1}k_2$ ， $u=α-s_1^{-1}h_1-s_1^{-1}r_1s_2r_2^{-1}α+s_1r_1r_2^{-1}h_2$
就可以用跟講義一樣的方法解了。

```python=
K = 2^127
L = matrix(ZZ, [[n, 0, 0] ,[t, 1, 0], [u, 0, K]])
v = L.LLL()
k1 = -v[0][0]
v, K
```
LLL之後會有一個vector v在解出的3個vector內，我是利用解出的vector反推回d，再計算dG看看是否與Public Key給出的座標一樣

```python=
crack_k1 = k1 + alpha
d1 = ((s1 * crack_k1 - h1) * inverse_mod(r1, n)) % n
(d1*G).x() == pubkey_x
```

應該是因為上界的問題，不是每次嘗試都會成功，但多試幾次找到dG出來跟公鑰一樣的結果後，就可以用這個d去做簽章得到r、s

```python=
d = d1
k1_real = (inverse_mod(s1, n) * (h1 + d * r1)) % n
k2_real = (inverse_mod(s2, n) * (h2 + d * r2)) % n
pubkey = Public_key(G, d1*G)
prikey = Private_key(pubkey, d1)
h = 'Kuruwa'
h = sha256(h.encode()).digest()
k = int(md5(b'secret').hexdigest() + md5(long_to_bytes(prikey.secret_multiplier) + h).hexdigest(), 16)
sig = prikey.sign(bytes_to_long(h), k)
print(f'sig = ({sig.r}, {sig.s})')
```


:::success
:triangular_flag_on_post: FLAG{adfc9b68bd6ec6dbf6b3c9ddd46aafaea06a97ee}
:::