###### 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}
:::
Sign in with Wallet
Connect another wallet