---
# System prepended metadata

title: M11115043 何亮牖 writeup

---

# M11115043 何亮牖 writeup



# <font color = 'red'>[Hw]LSB</font>

## 題目
``` python=
from Crypto.Util.number import bytes_to_long, getPrime
import os

from secret import FLAG

p = getPrime(1024)
q = getPrime(1024)
n = p * q
phi = (p - 1) * (q - 1)
e = 65537
d = pow(e, -1, phi)

m = bytes_to_long(FLAG + os.urandom(256 - len(FLAG)))
assert m < n
enc = pow(m, e, n)
print(n)
print(e)
print(enc)
while True:
    inp = int(input().strip())
    pt = pow(inp, d, n)
    print(pt % 3)
```

## 解題思路
1. 首先，他會回傳給我解密後 mod 3 的最後一個bit
2. 那我們是不是可以透過不斷除3去一步一步破解他
![](https://i.imgur.com/FLbXqu6.png)
就如同上圖，只是圖片是 mod2 而題目是 mod3

## 解法

```python=
from pwn import *
from Crypto.Util.number import *

r = remote('edu-ctf.zoolab.org',10102)

n = int(r.recvline())
enc = r.recvline()
enc = int(r.recvline())
e = 65537
inverseNum = inverse(3,n)

i = 0
x = 0
ans = 0
count = 0

while True:
    str1 = str(pow(inverseNum,i*e,n)*enc%n).encode()
    r.sendline(str1)
    receive = r.recvline()
    tmp = (int(receive.split()[-1])-inverseNum*x%n)%3
   
    x = (inverseNum*x+tmp)%n
    ans = 3**i*tmp+ans

    i += 1
    count += 1
    print(count)
    if count > 3000:
        break

print('final: ',ans)
print('byte: ',long_to_bytes(ans))


```
* 第6、8、10行分別得到 n、enc、與 n 在模3下的逆元
* 而第 18 行就是不斷除三，也就是 $$3^{-n}\ m$$
* 第 19 行我們將除完3的結果傳給 server，第20行得到 server 回傳得 lsb
* 這時我們得到的結果會是
    $$3^{-n}x_0+3^{-n-1}x_1+...+x_n$$
* 為了得到 Xn 我們必須將前面扣掉，也就是第21行做的事
* 最後就把得到的結果不斷用3的指數乘回去，也就是24行的結果
* 最後我讓他跑3000次得到結果


![](https://i.imgur.com/GWNkH5O.png)



# <font color = 'red'>[Hw] XOR</font>

## 題目
```python=
import random

from secret import FLAG

state = random.randint(0, 1 << 64)

def getbit():
    global state
    state <<= 1
    if state & (1 << 64):
        state ^= 0x1da785fc480000001
        return 1
    return 0

flag = list(map(int, ''.join(["{:08b}".format(c) for c in FLAG])))
output = []
for _ in range(len(flag) + 70):
    for __ in range(36):
        getbit()
    output.append(getbit())

for i in range(len(flag)):
    output[i] ^= flag[i]

print(output)

```
## 解題思路

* 根據題目所示，首先題目隨機生成 state 
* getbit() 會將state向左 shift 1格並且判斷第65位是0還是1
* 若是1則與 0x1da785fc480000001(我們簡稱為P) 做 xor
* 根據題目17行可得知最後的70bit 是沒有被汙染過的，因此可以利用他來幫助我們還原
* 這題需要利用到 相伴矩陣 companion matrix 如同投影片裡提到的
    
![](https://i.imgur.com/8f4IfAN.png)

## 解法

```python=
import copy

output_array = [1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0]
output_array = vector(output_array)
F.<x> = PolynomialRing(GF(2))

def contruct_poly(poly):
    for i in range(64):
        poly = x ^ i * int(bin(P)[-i-1]) + poly
    return poly
    
P = 0x1da785fc480000001
poly = x^64

poly = contruct_poly(poly)

matrix = companion_matrix(poly, format='bottom')
coef = copy.deepcopy(matrix)

for i in range(64):
        tmp = matrix ^ (37 * (i + 337))
        coef[i] = tmp[0]

initState = output_array * coef.inverse()
ans=""

for k in range(0,336):
    tmp = initState * matrix ^ (37 * (k+1))
    ans += str(tmp[0])

print(ans)
```
* 首先我們先從沒被汙染過的70bit 當中取64bit出來，也就是上圖的第3行
* 再來建構一個相伴矩陣，也就是第5行
* 由於 
    $$ Matrix∗initState=outputArray$$

    $$ initState=coefMatrix−1∗outputArray $$

* 這樣我們就能反推得到 initState
* 但由於題目是每做37次才會收到 getbit 因此要以 matrix^37 為單位
* 因此在第20~22行，我們蒐集了相伴矩陣的元素
* 並且在第24行 透過乘上逆矩陣得到 initState
* 最後在將 initState 不斷乘上 matrix^37 就可以得到結果，下圖為跑出的結果
![](https://i.imgur.com/7hHEAjH.png)


```text=
000010001011110011101011110111101001111011111101111011101111111101111100001110001110100111000001110010001011001000011101110010101001000110001111001000101010001101000111011000100110101111110011100011000000111010101011001110001111101110100111100111111111010100011001010010100001010101000010111001110110000110100110100101111000000100101000
```

* 最後在將此結果與題目給的 output 做xor，即可得到答案

```python=

str1 = '111000011000011111110000001000110001100110101011011110111111011001001011101111001000100010010010110001101111101000001011010000000001000000101000001101100111010001010000000100010010001000011101001001101001001000011011011010111001110010011101000111000100000100111001110110111111100000101000001010110111100101100110110000001101101101011011'
ttt = [1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0]

str2=''

for i in range(336):
    str2+=str(int(str1[i])^^int(ttt[i]))
print(str2)
```

FLAG{Y0u_c4N_nO7_Bru73_f0RCe_tH15_TiM3!!!}



# <font color = 'red'>[Hw] DH</font>


## 題目
```python=

from Crypto.Util.number import bytes_to_long, getPrime
import random

from secret import FLAG

p = getPrime(1024)
assert bytes_to_long(FLAG) < p
print(p)

g = int(input().strip())
g %= p
if g == 1 or g == p - 1:
    print("Bad :(")
    exit(0)

a = random.randint(2, p - 2)
A = pow(g, a, p)
if A == 1 or A == p - 1:
    print("Bad :(")
    exit(0)

b = random.randint(2, p - 2)
c = pow(A, b, p) * bytes_to_long(FLAG) % p
print(c)

```

## 解題思路
* 這題在題目第7行會產生一個隨機質數
* 並且隨機產生 a 和 b，同時讓我們輸入 g
* 在第18行計算 $A=g^a\ mod P$ 
* 最後回傳給我們 $A^b\ mod P\ *Flag\ \%p$

* 根據費馬小定理 若 a,p 互質，則 $a^{p-1}\ modp \equiv 1$
* 透過該定理，若我們讓輸入為$k^{p-1}$則回傳會是$k^{(p-1)*ab}*Flag\ modP$，又因為定理，所以在模P下$k^{(p-1)*ab}\equiv 1$，因此就能得到 flag

## 解題

```python=
from pwn import *
from sympy import *
from Crypto.Util.number import long_to_bytes
while(1):
    r = remote('edu-ctf.zoolab.org', 10104)
    
    p = int(str(r.readline())[2:-3])

    try:
        g = pow(2,(p-1)//3,p)
        
        r.sendline(str.encode(str(g)))
        flag = long_to_bytes(int(str(r.readline())[2:-3]))
        if flag[0] == ord('F'):
            print(flag)
            break

    except:
        pass

```
* 第7行得到 P 
* 為了減少運算量，與P互質之數我們選擇2
* 但我們不能直接傳 $2^{p-1}\ mod P$，因為會回傳 bad
* 因此在第10行我們故意傳 $2^{(p-1)/3} modP$，這樣只要運氣好 ab 若可以整除3，那就可以得到答案了
* 最後用一個無窮迴圈跑，只要得到F開頭即為 flag

![](https://i.imgur.com/O1xMXCu.png)
FLAG{M4yBe_i_N33d_70_checK_7he_0rDEr_OF_G}


# <font color = 'red'>[Hw] node</font>

## 題目

```python=

from Crypto.Util.number import inverse, bytes_to_long, isPrime
from collections import namedtuple
import random
import os

from secret import FLAG

p = 143934749405770267808039109533241671783161568136679499142376907171125336784176335731782823029409453622696871327278373730914810500964540833790836471525295291332255885782612535793955727295077649715977839675098393245636668277194569964284391085500147264756136769461365057766454689540925417898489465044267493955801
a = -3
b = 2

Point = namedtuple("Point", "x y")
O = 'Origin'

def check_point(P):
    if P == O:
        return True
    else:
        return (P.y**2 - (P.x**3 + a*P.x + b)) % p == 0 and 0 <= P.x < p and 0 <= P.y < p

def point_inverse(P):
    if P == O:
        return P
    return Point(P.x, -P.y % p)

def point_addition(P, Q):
    assert check_point(P)
    assert check_point(Q)
    if P == O:
        return Q
    elif Q == O:
        return P
    elif Q == point_inverse(P):
        return O
    else:
        if P == Q:
            lam = (3*P.x**2 + a)*inverse(2*P.y, p)
            lam %= p
        else:
            lam = (Q.y - P.y) * inverse((Q.x - P.x), p)
            lam %= p
    Rx = (lam**2 - P.x - Q.x) % p
    Ry = (lam*(P.x - Rx) - P.y) % p
    R = Point(Rx, Ry)
    assert check_point(R)
    return R

def double_and_add(G, k):
    P = G
    R = O
    while k > 0:
        if k % 2 == 1:
            R = point_addition(R, P)
        P = point_addition(P, P)
        k = k // 2
    assert check_point(R)
    return R

flag = bytes_to_long(FLAG + os.urandom(120 - len(FLAG)))
x, y = 101806057140780850544714530443644783825785167075147195900696966628348944447492085252540090679241301721340985975519224144331425477628386574016040358648752353263802400527250163297781189749285392087154377684890287451078937692380556192126971669069015673662635561425735593795743852141232711066181542250670387203333, 21070877061047140448223994337863615306499412743288524847405886929295212764999318872250771845966630538832460153205159221566590942573559588219757767072634072564645999959084653451405037079311490089767010764955418929624276491280034578150363584012913337588035080509421139229710578342261017441353044437092977119013
G = Point(x, y)
F = double_and_add(G, flag)
print(F.x, F.y)
```


## 解題思路
這題是投影片裡提到的，如果一個橢圓曲線 a,b 滿足$4a^3+27b^2=0\ modb$ ，那他就會是一個 singular curve
![](https://i.imgur.com/N4WHTU8.png)
題目給 a = -3，b = 2 剛好可以滿足上面方程式，因此該方程式就可以寫成$y^2=(x-\alpha)^2(x-\beta)$
這個方程式可以簡單解一下，發現 alpha=1,beta=-2，最後用離散對數解出 flag
![](https://i.imgur.com/R6aRIrg.png)
如上圖 d 即是 flag

## 解題
```python=
from collections import namedtuple
import math

def phi(alpha,belta,x,y):
    return ((y+mod((alpha-belta),p).sqrt()*(x-alpha))/((y-mod((alpha-belta),p).sqrt())*(x-alpha)))%p

p = 143934749405770267808039109533241671783161568136679499142376907171125336784176335731782823029409453622696871327278373730914810500964540833790836471525295291332255885782612535793955727295077649715977839675098393245636668277194569964284391085500147264756136769461365057766454689540925417898489465044267493955801

g_x=101806057140780850544714530443644783825785167075147195900696966628348944447492085252540090679241301721340985975519224144331425477628386574016040358648752353263802400527250163297781189749285392087154377684890287451078937692380556192126971669069015673662635561425735593795743852141232711066181542250670387203333
g_y=21070877061047140448223994337863615306499412743288524847405886929295212764999318872250771845966630538832460153205159221566590942573559588219757767072634072564645999959084653451405037079311490089767010764955418929624276491280034578150363584012913337588035080509421139229710578342261017441353044437092977119013
f_x=98015495932907076864096258407988962007376328849899810250322002325625359735922937686533359455570369291999900476297694445557845368802830788062976760815467239661283157094425185337540578842851843497177780602415322706226426265515846633379203744588829488176045794602858847864402137150751961826536524265308139934971
f_y=87166136054299272658534592982430361675520319206099499992529237663935246617561944716447831162561604277568397630920048376392806047558420891922813475124718967889074322061747341780368922425396061468851460185861964432392408561769588468524187868171386564578362923777824279396698093857550091931091983893092436864205

alpha = 1
belta = -2

discrete_log(mod(phi(alpha,beta,f_x,f_y),p),mod(phi(alpha,belta,g_x,g_y),p))
```
* 上圖第4到第5行我們建構出 phi 函式
* 第14、15行，我們算出 alpha 以及 belta的值
* 最後17行算出 discrete log
![](https://i.imgur.com/K92aHBS.png)
* 最後再將結果轉乘byte
![](https://i.imgur.com/Jx2WEkB.png)


FLAG{I_h3arD_th47_ECDlp_1s_h4rDEr_THaN_dlp}

# <font color = 'red'>[Lab] cor</font>
## 題目
```python=
import random

from secret import FLAG

class LFSR:
    def __init__(self, tap, state):
        self._tap = tap
        self._state = state

    def getbit(self):
        f = sum([self._state[i] for i in self._tap]) & 1
        x = self._state[0]
        self._state = self._state[1:] + [f]
        return x

class triLFSR:
    def __init__(self, lfsr1, lfsr2, lfsr3):
        self.lfsr1 = lfsr1
        self.lfsr2 = lfsr2
        self.lfsr3 = lfsr3

    def getbit(self):
        x1 = self.lfsr1.getbit()
        x2 = self.lfsr2.getbit()
        x3 = self.lfsr3.getbit()
        return x2 if x1 else x3

lfsr1 = LFSR([0, 13, 16, 26], [random.randrange(2) for _ in range(27)])
lfsr2 = LFSR([0, 5, 7, 22], [random.randrange(2) for _ in range(23)])
lfsr3 = LFSR([0, 17, 19, 24], [random.randrange(2) for _ in range(25)])
cipher = triLFSR(lfsr1, lfsr2, lfsr3)

flag = map(int, ''.join(["{:08b}".format(c) for c in FLAG]))

output = []

for b in flag:
    output.append(cipher.getbit() ^ b)

for _ in range(200):
    output.append(cipher.getbit())

print(output)

```

## 解題思路
* 題目給出三個 LFSR，這三個LFSR 在每一輪中都會給出一個 bit  然後判斷LFSR1 的值，若是1則回傳 LFSR2 的值，若是0則回傳LFSR3的值
* 而在output.txt 中最後200個 bit 是沒有被汙染過的，因此我們可以利用它來解題
* ![](https://i.imgur.com/3fIAwR6.png)
* 而我們可以暴力破解 x2,x3 根據上一張圖片，只要輸出結果與 output 高達75%相似，那就有可能是我們的答案


## 解題
```cpp=

#include<iostream>
#include<vector>
#include<math.h>
#include<string>
using namespace std;

int ans[] = {1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1};

struct Find{
	unsigned long long S_state;
	string str;
} typedef Find;

class LFSR{
	public:
		unsigned long long state,tap,size;
		LFSR(unsigned long long state,unsigned long long tap,unsigned long long size){
			this->state = state;
			this->size = size;
			this->tap = tap;
		}
		int getBit(){
			int carry = 0;
			int output = 0;
			if(__builtin_popcount(state&tap)%2 == 1){
				carry = 1;
			}
			output = state & 1;
			state >>= 1;
			state |= carry << (size-1);
			return output;
		}
}; 

float rate(int result[]){
	int count = 0;
	for(int i =0;i < 200;i++){
		if(result[i] == ans[i+232]){
			count++;
		}
	}
	return float(count/200.0);
}

vector<Find> getState(unsigned long long tap, int size){
	int result[200],tt;
	vector<Find> tmp;
	Find find;
	/////////////////////////////////////////////////
	for(int state = 0;state < pow(2,size)-1;state++){
		LFSR ll = LFSR(state,tap,size);
		for(int i=0;i<432;i++){
			if(i<232){
				tt = ll.getBit();
				continue;
			}	
			else{
				result[i-232] = ll.getBit();
			}
		}
		float cr = rate(result);
		///////////////////////////////////////
		if(cr >= 0.7){
			find.S_state = state;
			string s;
			for(int i=0;i<200;i++){
				s.push_back(result[i]+'0');
			}
			find.str = s;
			tmp.push_back(find);
		}
	}
	return tmp;
}

void getAns(unsigned long long state0,unsigned long long state1,unsigned long long state2){
	unsigned long long tap[3],size[3]={27,23,25};
	tap[0] = (1<<26)|(1<<16)|(1<<13)|1;
	tap[1] = (1<<22)|(1<<7)|(1<<5)|1;
	tap[2] = (1<<24)|(1<<19)|(1<<17)|1;
	
	LFSR l0 = LFSR(state0,tap[0],size[0]);
	LFSR l1 = LFSR(state1,tap[1],size[1]);
	LFSR l2 = LFSR(state2,tap[2],size[2]);
	int x0,x1,x2;
	int res[232],answer[232];
	string str = "";
	for(int i =0 ;i < 232;i++){
		x0 = l0.getBit();
		x1 = l1.getBit();
		x2 = l2.getBit();
		res[i] = x0?x1:x2;
	}
	for(int i = 0;i < 232;i++){
		str.push_back((res[i] ^ ans[i])+'0');
		if(i%8==7){
		
			int x = stoi(str,nullptr,2);
			cout << char(x);
			str = "";
		}
	}
	
}


int main(){
	unsigned long long state[3],tap[3],size[3]={27,23,25};
	bool flag = false;
	vector< vector<Find> > states;
	int check[200];
	tap[0] = (1<<26)|(1<<16)|(1<<13)|1;
	tap[1] = (1<<22)|(1<<7)|(1<<5)|1;
	tap[2] = (1<<24)|(1<<19)|(1<<17)|1;
	for(int i = 1; i < 3 ;i++){
		states.push_back(getState(tap[i],size[i]));
	}
	
	for(int state1 = 0; state1 < states[0].size();state1++){
		for(int state2=0;state2 < states[1].size();state2++){
			////////////////////////////////////
			for(int state0 = 0;state0 < pow(2,size[0])-1;state0++){
				LFSR l0 = LFSR(state0,tap[0],size[0]);
				int x0,x1,x2;
				for(int i = 0;i < 432;i++){
					if(i < 232){
						x0 = l0.getBit();
					}
					else{
						x0 = l0.getBit();
						x1 = states[0][state1].str[i-232]-'0';
						x2 = states[1][state2].str[i-232]-'0';
						check[i-232] = x0?x1:x2;
					}
				}
				float cr = rate(check);
				//////////////////////////////////////////////////
				if(cr >= 0.95){
					
					getAns(state0,states[0][state1].S_state,states[1][state2].S_state);
					flag = true;
					break;
				}
			}
			if(flag){
				break;
			}
				
		}
		if(flag){
			break;
		}
			
	}()

    return 0;
}
```

* 在上面程式碼中的第46行 getState()的函式就是在暴力找 state,直到找到有高達70%相似度
* 若該 state 有大於70%的相似度，那我們就把它存起來
* 對於 LSFR2，LSFR3 我們都做上述的事情，找到可疑的 state 併存起來
* 最後我們透過第77行的 getAns() 把找到的可疑得 state 拿出來跑，若結果跟答案一樣則找到答案
![](https://i.imgur.com/ahvvtOv.png)


FLAG{W0W_you_Kn0w_COR_477ACK}


# <font color = 'red'>[Lab] POA</font>

## 題目
```python=
from Crypto.Cipher import AES
import os

from secret import FLAG

def pad(data, block_size):
    data += bytes([0x80] + [0x00] * (15 - len(data) % block_size))
    return data

def unpad(data, block_size):
    if len(data) % block_size:
        raise ValueError

    padding_len = 0
    for i in range(1, len(data) + 1):
        if data[-i] == 0x80:
            padding_len = i
            break
        elif data[-i] != 0x00:
            raise ValueError
    else:
        raise ValueError

    return data[:-padding_len]

key = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC)
ct = cipher.encrypt(pad(FLAG, AES.block_size))
iv = cipher.iv
print((iv + ct).hex())

while True:
    try:
        inp = bytes.fromhex(input().strip())
        iv, ct = inp[:16], inp[16:]
        cipher = AES.new(key, AES.MODE_CBC, iv)
        pt = unpad(cipher.decrypt(ct), AES.block_size)
        print("Well received :)")
    except ValueError:
        print("Something went wrong :(")

```

## 解題思路
* 如上題目所述，題目再做 padding 的方法是加上 0X80，再看是否總長度為16的倍數，若不是則加0X80到 16的倍數為止
* 最後再用 CBC 加密
* 由於CBC有一個特點，不同 block 之間加解密不會互相干擾，因此可以用 前面塞亂碼，只保留最後一位，然後暴力去看最後一位的結果
* 因為 server 會回傳 Unpad 結果正確與否，所以我們可以利用它來找出 flag
![](https://i.imgur.com/9Yu3Xhn.png)


## 解題
```python=
from pwn import *
r = remote('edu-ctf.zoolab.org',10101)
ct = r.readline()[:-1].decode()
ct = bytes.fromhex(ct)
ans = b""
for block_index in range(1,int(len(ct)/16)):
    block_pt = b""
    block_ct = ct[block_index * 16: (block_index+1)*16]
    former_ct = ct[(block_index-1) * 16: block_index*16]
    for index in range(15,-1,-1)::ㄆ
        clear = bytes([i^j for i,j in zip(block_pt , former_ct[index+1:])])
        for i in range(128,256):
            now = former_ct[:index] + bytes([i^former_ct[index]]) + clear + block_ct
            r.sendline(now.hex().encode("ascii"))
            res = r.readline()
            if res == b"Well received :)\n":
                block_pt = bytes([i^0x80]) + block_pt
                break
        else:
            block_pt = bytes([0x80]) + block_pt
    ans+=block_pt
print(ans)
```
FLAG{ip4d_pr0_iS_r3ally_pr0_4Nd_f1aT!!!!}


# <font color = 'red'>[Lab] dlog</font>

## 題目
```python=
from Crypto.Util.number import isPrime, bytes_to_long
import os

from secret import FLAG

p = int(input("give me a prime").strip())
if not isPrime(p):
    print("Do you know what is primes?")
if p.bit_length() != 1024:
    print("Bit length need to be 1024")

b = int(input("give me a number").strip())
flag = bytes_to_long(FLAG + os.urandom(p.bit_length() // 8 - len(FLAG)))

print('The hint about my secret:', pow(b, flag, p))
```

## 解題思路

* 題目要我們輸入一個 1024bit 的質數 p，然後 server 會將p 的flag 次方再 mod p 給我們
* ![](https://i.imgur.com/QgHuaU4.png)
* 首先找質數，我們按照助教的方法，用一堆質數相乘+1，最後找到一個1024的質數


## 解題
```python=
import os
import random
from sympy import *

prime = [2,3,5]
p = 1
while(1):
    p *= prime[random.randint(0,2)]
    temp = p+1
    if temp.bit_length() == 1024 and isprime(temp)==True:
        p = temp
        break
    elif temp.bit_length()>1024:
        p=1
print(p)
```
* 上面程式碼找到一個大質數
* ![](https://i.imgur.com/3Tz6Lnu.png)
* 我找到得質數為 99492903377739648396126958853091298719025168913425135392031005329979226587264173895290327140761600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

```python=
from pwn import *
from Crypto.Util.number import long_to_bytes
r = remote('edu-ctf.zoolab.org',10103)

b = 11
p = 99492903377739648396126958853091298719025168913425135392031005329979226587264173895290327140761600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

r.readuntil(b"give me a prime")
r.sendline(str(p).encode())
r.readuntil(b"give me a number")
r.sendline(str(b).encode())
r.readuntil(b"The hint about my secret:")
ct = int(r.readline().strip())

print(ct)
```

* 透過上程式碼我們得到ct
* ![](https://i.imgur.com/hWX1WUM.png)
* ct = 89099191239225695758213019786509668974488180950329145868886107168387663725496347319654774488168150741583599388050323803201534994180534767475655680128857374038793101536333218936079312442784594983342266465161012933180137807810263945843966791419768214739832455192268261374457934726087985953250799192117705369647


* 最後透過 sagemath 找 discrete_log
```
ct= 89099191239225695758213019786509668974488180950329145868886107168387663725496347319654774488168150741583599388050323803201534994180534767475655680128857374038793101536333218936079312442784594983342266465161012933180137807810263945843966791419768214739832455192268261374457934726087985953250799192117705369647
p = 99492903377739648396126958853091298719025168913425135392031005329979226587264173895290327140761600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
b=11
b= Mod(b,p)
ct = Mod(ct,p)
discrete_log(ct,b)
```
* 得到 49364843843516391046524858268527194975796465451738728838358032889241583861681330662835498865164988147008120528038183931512322940903551445259350069807426250994134592399472836913637798063459476519584753944421605698112606596529915301859105754751328649962108247195678424852766579560744551395311349262676166455450
* 最後將結果 long to byte
* ![](https://i.imgur.com/H2lwYNC.png)

FLAG{D0_No7_SLiP!!!1t'5_SM0o7h_OwO}