NS_107 CTF 當個礦工神
===
###### tags: `ns107` `HW4` `CTF` `WINKYFAC3`

> 請解釋一下原理！
> [name=Dange]
## 題目內容
礦工進得來，貨幣出得去，比特發大財！

nc eens.ee.ncku.edu.tw 2003

## 解題思路
一開始看到程式給的訊息，基本上是完全不懂這題是要幹嘛，不過直接把第二句話丟到Google搜尋一下，我們就能發現這題是跟區塊鏈系統中的Proof-of-Work機制有關。
### Proof-of-Work原理說明：
>工作量證明（Proof-of-Work，PoW）是一種對應服務與資源濫用、或是阻斷服務攻擊的經濟對策。一般是要求使用者進行一些耗時適當的複雜運算，並且答案能被服務方快速驗算，以此耗用的時間、裝置與能源做為擔保成本，以確保服務與資源是被真正的需求所使用。此一概念最早由Cynthia Dwork和Moni Naor於1993年的學術論文提出，而工作量證明一詞則是在1999年由Markus Jakobsson與Ari Juels.所發表。現時此一技術成為了加密貨幣的主流共識機制之一，如比特幣所採用的技術。
>[name=[wikipedia](https://zh.wikipedia.org/wiki/%E5%B7%A5%E4%BD%9C%E9%87%8F%E8%AD%89%E6%98%8E)]
>

因為hash不可逆的特性，當我們要找到能算出特定條件的hash值的字串(nonce)時，只能用窮舉的方式一一比較，計算上比較困難，然而要驗算時，只需要將該字串代回hash function再算一次即可。這樣的特性被應用在Bitcoin等虛擬貨幣上。

>由於加密貨幣多由區段鏈所建構，而區段鏈本來就要依賴雜湊函式來做為資料正確無誤的擔保，所以在加密貨幣上使用工作量證明，是非常簡明的設計。由分散在各處的電腦，競賽誰能最早找出，搭配原本要打包的資料的窮舉猜測值（nonce），誰就等同獲得該區段的打包權（記帳權）。此猜測值被找出後，與資料、雜湊值一起打包成塊後廣播，經多數節點確認與承認，打包者就能獲得打包該區段所提供的獎勵。一般採用工作量證明的加密貨幣，好比比特幣，會設定成隨著參與競賽的算力增減，而調整找尋猜測值的難度，以維持合理的運作速度。
>[name=[wikipedia](https://zh.wikipedia.org/wiki/%E5%B7%A5%E4%BD%9C%E9%87%8F%E8%AD%89%E6%98%8E)]
>
在Bitcoin中，proof-of-work的運作方式為：先有人在網路上發出一筆待處理的交易紀錄，並指定nonce值的條件(例如hash值的前N位為0)，網路上的礦工們就要設法找出一組字串"n"，接在一個base string "b"之後，並以SHA256演算法計算，使這個b+n字串的hash值的前N位皆為0，第一個找到正確nonce的礦工即可獲得記帳權(可以處理這筆交易紀錄)，並獲得Bitcoin獎勵；所謂的「挖礦」，就是指根據系統的要求，計算出正確的nonce值，取得記帳權，完成記帳工作後，獲得虛擬貨幣獎勵的過程，其中大部分的資源都是消耗在計算nonce值上。由於只有第一個算出nonce的人可以獲得記帳權，所以要靠挖礦來賺錢，不只要算的多，還要算的比別人快。

## 解題流程
根據以上資料，可以推測出這題的解法就是要以程式給出的那一串hash值為base string，找到一個nonce字串，使這兩個字串接在一起時能算出前N位為0的hash值。

以最上面的圖片為例，我們的base string為：

63097455c3b448f49646dfefc5a00b087b2957a178092b94626886affa331eda

並且我們的目標為找出nonce，使hash值的前3位為0，我們可以寫個Python程式來幫我們計算：

import hashlib

prefix_length = 3
base = '63097455c3b448f49646dfefc5a00b087b2957a178092b94626886affa331eda'
nonce = 0 # 為了方便計算，我們使用數字作為nonce字串

while True:
    hash_input = base + str(nonce) # 兩個字串接在一起
    hash_func = hashlib.sha256()
    hash_func.update(hash_input.encode('utf-8')) # 以SHA256計算hash值
    result = hash_func.hexdigest() # 將結果轉成16進位的字串
    
    if result[:prefix_length] == '0' * prefix_length: # 檢查結果是否符合條件
        print('Nonce:', nonce) # 最後的nonce值就是我們要的答案
        print('Result:', result)
        break
    else:
        nonce += 1 # 如果hash值不符合條件，將nonce+1再算一次

計算結果：

將結果輸入回程式，即可得到Flag

## References:
https://zh.wikipedia.org/wiki/%E5%B7%A5%E4%BD%9C%E9%87%8F%E8%AD%89%E6%98%8E
https://www.khanacademy.org/economics-finance-domain/core-finance/money-and-banking/bitcoin/v/bitcoin-proof-of-work
https://en.bitcoin.it/wiki/Proof_of_work
https://docs.python.org/3/library/hashlib.html