# HITCON CTF 2022 -- [Crypto] babySSS
author: Ching367436 (111652037 王博靚)

## 題目

from random import SystemRandom
from Crypto.Cipher import AES
from hashlib import sha256
from secret import flag

rand = SystemRandom()


def polyeval(poly, x):
    return sum([a * x**i for i, a in enumerate(poly)])


DEGREE = 128
SHARES_FOR_YOU = 8  # I am really stingy :)

poly = [rand.getrandbits(64) for _ in range(DEGREE + 1)]
shares = []
for _ in range(SHARES_FOR_YOU):
    x = rand.getrandbits(16)
    y = polyeval(poly, x)
    shares.append((x, y))
# print(shares)

secret = polyeval(poly, 0x48763)
key = sha256(str(secret).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CTR)
print(cipher.encrypt(flag))
print(cipher.nonce)

題目首先會生成一個 `128 次式` (`:16`)
而其係數會是屬於 $[0, 2^{64})$ 這個區間的整數
（由 `rand.getrandbits(64)` 生成
他的 `rand` 使用了 `SystemRandom()` 所以看起來不會是從亂數生成這個地方下手

為了方便說明
這邊會把這個式子寫成以下形式

$$
f(x)=y=a_0x^0+a_1x^1+...+a_{128}x^{128}
$$

接著到 `:18`
題目會把 $8$ 個在這個式子上的點送給我們
也就是會給我們 $8$ 組以下的序對
$$
(k_t, f(k_t))
$$
其中因為 $k_t$ 的生成方式如後面 (`rand.getrandbits(16)`) 所以
$$
k_t \in [0,2^{16})
$$

接著 `:24` 會用 $f(0x48763)$ 這個數字把 `flag` 加密

所以只要取得 $f(0x48763)$ 就可以直接解密

而要取得 $f(0x48763)$
第一個想法就是取得 $f(x)$
然後把 $0x48763$ 帶入

## 嘗試取得 $f(x)$
### 取得 $a_0$
要取得 $f(x)$ 就會想試著取得他的係數
$$
f(k_t)=a_0+a_1k_t^1+...+a_{128}k_t^{128}
$$
可以觀察到除了 $a_0$ 這一項之外
每一項都有 $k_t$ 這個因數
所以
$$
f(k_t) \equiv a_0 \mod k_t
$$

所以我們就有 $a_0 \% k_t$ 了

而題目有 $8$ 組 $k_t$
所以我們有 $8$ 組 $a_0 \% k_t$

因為
$$
k_t \in [0,2^{16})
$$
$$
a_0 \in [0,2^{64})
$$
我們可以透過 `chinese remainder theory` 來用那 $8$ 組 $a_0 \% k_t$ 來復原 $a_0$
然後就有 $a_0$ 了

### 取得 $a_1$
這邊令
$$
f_1(k_t)=\frac{f(k_t)-a_0}{k_t}
$$

上面提到
除了 $a_0$ 這一項之外
$f(k_t)$ 每一項都有 $k_t$ 這個因數

所以把 $a_0$ 這一項剪掉
剩下的係數一定可以被 $k_t$ 整除
所以 $f_1(k_t)$ 仍然是整數

而
$$
f_1(k_t) = a_1+a_2k_t^1+...+a_{128}k_t^{127}
$$
是不是發現跟上面的 $f(x)$ 很像？
所以我們一樣照著上面的作法
$$
f_1(k_t) \equiv a_1 \mod k_t
$$
一樣取得 $8$ 組 $a_1 \% k_t$
然後用 `crt` 來還原 $a_1$

### 取得 $a_i$
這邊令
$$
f_i(k_t)=\frac{f_{i-1}(k_t)-a_{i-1}}{k_t}
$$
我們假設前面已經取得 $f_{i-1},a_{i-1}$
很顯然的可以取得 $f_i$
而
$$
f_i(k_t) = a_i+a_{i+1}k_t^1+...+a_{128}k_t^{128-i}
$$
一樣照著上面的作法
$$
f_i(k_t) \equiv a_i \mod k_t
$$
一樣取得 $8$ 組 $a_i \% k_t$
然後用 `crt` 來還原 $a_i$

> 一些有感而發：
> 這邊有種數學歸納法的感覺
> 很多人直覺上都認為數學歸納法是正確的
> 不過那並不能證明「數學歸納法是正確的」
> 來到了數學系
> 我有了證明「數學歸納法是正確的」的能力
> 甚至可以推廣到自然數之外
> 只要是良序集都可以使用（因為證明的過程只需要自然數是良序集這個條件
> 來數學系讓我看到了不一樣的世界
> 也很高興能夠在應用數學系取得許多科目的班上第一
> [name=國立陽明交通大學 應用數學系大一 王博靚]

這樣就可以從 $i=1$ 一路做到 $i=128$
這樣我們就有 $f(x)$ 了

有了 $f(x)$ 就有 $f(0x48763)$
接著只要拿著 $f(0x48763)$ 去解密就可以拿到 `flag` 了

以下附上我的解題的 `script`
### `sol.py`

from Crypto.Cipher import AES
from hashlib import sha256
from sage.all import crt

# https://blog.maple3142.net/2022/08/01/uiuctf-2022-writeups/#wringing-rings
shares = [
    (41458, 3015894889650529600470920314593280408459518223054415623846810748413393737686521849609926975694824777687791824408686652245102687392987299828716863372946074882798754477101786150262288970710451710086966378817944448615584285684364802621112755627795146504720812935041851556318832824799502759754100408717888912062197676588256634343721633045179136302533777168978134770315363985448879229514802330846792965525004570768212871252658334277172395338054448791891165981203069346039654617938169527772805687564575525262812469960675835101499054296722994451502140787064163668418661661374437567033971648550576296023422536253955229),
    (3389, 188433716494377932944071544153838579057591833387651830021721770473524507947811754295899393634645349682360212761145039355690817927625249659010181081209481357850193656763556243022791637306094953982811471415645267589939465925098159204147714779617946431727015863707468081949286110249296858079354949234074465541940264775783884708819566758872542606519408358277173683256608326688673226933790117016596834640875497643330432185114931410656582728964222203181026468387428893233826461),
    (20016, 100434774699078525844435127144579870564983915777345068724291926367405061427748836490810414860997895358378538088786283372231649911113841061354335739776409724471256377867811133591349442950556374825868587940833009529662869081130218551306459690738900795035660420986807973542512081415453215211908130387754214098414826747340962722685373241806099462750595976574593799013733614097923338311883793416643213898201680852118540438376386415411317989072583126108177482838299109479175882214603698768498421016054035672774286507312986602290254323930575001551875601243671354491241420409219),
    (50683, 444545881882748849210617532697661279371689521082184772844723908765173319859389018743414369945234307906596253496624659734919646710483514374218993496994560985318096082923429834553341897367168830049334302307406087637232329348570485341223211629167329394484624055745054495405880099706580380696671879365741197827080224977821589102425678989782880274304484630899425664722718972847034030888019348402685383311095030884356731112886316823960378572796288532824588478234949384868912708000223119984161992105752059185137674711077940232530298853451166664700609238496874366152042676602089571801873748042888046623717879084695143810047335029),
    (6445, 101461065764578261241074518788237888467081270902741849861528201922043223477790661159690684156056890167304291810116447916457265705130707166062372766839626095333813681671546097679623755546322833727082145873422243641505450049118758544298328784536759107951763715458884889255549767465897671061295486677353893450789955616926292534325337544782386120469581214993770910137353221116457111551538222138388416162630076391624447865248920466274175229034129561913505977209131490066291917549232913771218316393849495621818397),
    (1359, 301175604076484656987097022479686300460199620068959954988990822483114048418823291831080744590394713639405681060973359346474547015206086229256524657214311815578895906855833813636970640902962286472992468394831014254279137613828904924898823470285520515090889491445149243620044782726415898188702226878029241518020146726699446397961112596830223444821094650508662477147134721631935528182772284099429814417490160457082241680661),
    (45286, 244867719210730952183489456726726432791149629831242968845409984537752132549250274779516590253042559196452609852176114909791657154092483479876795482861784431886143414585698773882088948703730268947925790809436449512089696895048994874003651088538416399435467483409931121063976149037130454114161175715871108284419975118570732022104749321213013756795645219060997019373915339235627535694458093194617642834806820772479160496966470147893963746139947337914575231526069667124822677688977724313174612816604463495630041075005651663546036363128325535621487658461744362098985183050127661470315454320073092665472364666768205258769),
    (5649, 4766101906865350375503575239791521167258753430948472304582908507542293595346756303331383584550516424087839316050412570112796817549423179461056531056102741963677007097061600281918678364910813585444151640384802648969082273001142879806475184857246441212406056540028447374033197873299250076862108042582790928405869475508762352345569281589853917902601519294573327847401601789315980414998055948162169170771240383220643819333682845459742335249254576151835966500230706707674854493184181354958093926469960861)
]

flag_enc = b'G$\xf5\x9e\xa9\xb1e\xb5\x86w\xdfz\xbeP\xecJ\xb8wT<<\x84\xc5v\xb4\x02Z\xa4\xed\x8fB\x00[\xc0\x02\xf9\xc0x\x16\xf9\xa4\x02\xb8\xbb'
nonce = b'\x8f\xa5z\xb4mZ\x97\xe9'

DEGREE = 128
SHARES_FOR_YOU = 8  # I (maple3142) am really stingy :)


def polyeval(poly, x):
    return sum([a * x**i for i, a in enumerate(poly)])


def recover_poly_from_shares(shares: list[tuple[int, int]]) -> list[int]:
    poly = [0] * (DEGREE+1)

    for i in range(DEGREE+1):
        crt_a = [0] * (len(shares))
        crt_b = [0] * (len(shares))
        for j, (x, y) in enumerate(shares):
            crt_b[j] = x
            crt_a[j] = (y) - (polyeval(poly, x))
            assert crt_a[j] % x**i == 0
            crt_a[j] //= x**i
            crt_a[j] %= crt_b[j]
        poly[i] = crt(crt_a, crt_b)
    return poly

poly = recover_poly_from_shares(shares)

secret = polyeval(poly, 0x48763)
key = sha256(str(secret).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)

flag = cipher.decrypt(flag_enc)
print(flag)