密碼學／加密貨幣原理

有啲好奇點解你會出post講

因為我覺得最有效既學習方法，就係講番一次出黎教人

agger

留名!

lm先

LM

強post, it 白痴留名

有個位諗唔通就係究竟點樣去交易少於1 個bitcoin 係咪之後會講?

50年前d 人點將5仙買個白飯?

要交易五仙首先要有五仙嘅幣存在

依家香港已經唔存在五仙幣所以我地最少都要交易一毫｡ bitcoin掘出嚟就係1蚊所以先問點樣去交易少於1 個bitcoin

事實上我都幾訝異會有咁嘅程度嘅回應

唔係想罵戰
但邊個話bitcoin 係"一蚊一蚊咁掘"?

再加上, digital 既野......要有返"5仙" 有難度?

我都唔想罵戰

無奈閣下個例子真係完全講唔到重點

咁你問點交易少於1 個既bitcoin

就等如而家有人問點交易少於1個菠蘿包

重點係bitcoin 最少單位唔係1
同埋bitcoin 唔係唯一交易工具

嗰陣讀咗好多number theory
費馬 chinese remainder theorem多到唔係好記得

自此就好憎number theory呢個topics

用數學既方法黎表示上面兩個特質：
x1, x2係input
y1, y2係output

Hiding:given y1, 好難好難好難搵到x1 such that SHA256(x1) = y1
collision resistance：好難好難好難搵到x1, x2 such that SHA256(x1) = SHA256(x2)

數學家發明既hash function有好多款
但就唔係款款hash function都符合到上面兩個要求
例如SHA family入面既SHA1(output length: 160 bit)
美國政府起1995年發表SHA1, 所有科技巨頭包括Apple Google Microsoft 當時都用左呢個cryptographic hash function
用暴力破解SHA1既話計2^80次先會搵到一對input導致collision
直到2005年，一個中國女數學家-王小雲 發現左個方法，只需要計2^63次就會搵到collision input
注意王小雲只係諗到個方法，但係果時佢都未真係搵到x1,x2 such that SHA1(x1)=SHA1(x2)
要再隔多12年，即係2017年既二月， Google先成功製造到兩份唔同既PDF file , 佢地既SHA1 output係一樣既
所以而家SHA1已經無資格做cryptographic hash function, 只能夠做一個普通hash function

如果大家有留意chrome既新聞，應該聽過chrome由v.56開始唔再支援SHA1生成既certificate
就係因為google知道chrome已經唔再安全，通過到SHA1認證都唔代表乜野
唔係話SHA完全無用，例如git而家仲用緊SHA1黎做file integrity check
只係大家已經唔可以倚靠呢個function黎保護系統

hash function仲有好多值得講既topic
例如birthday attack: 160bit output length既hash function點解只需要2^80步就可以暴力破解到collision,而唔係2^160步?
點為知好難好難好難搵到？有無單手游出公海咁難？

講左咁耐，究竟hash function同bitcoin有咩關係？
SHA256正正係所有礦工日計夜計既數：Find x such that SHA256(x) < target
而且成條blockchain之所以安全，之所以無可能被篡改，都係多得SHA2既collision resistance property
詳情就留番後面既chapter先講

點解 160個位但係暴力破解2^80就可以破？ 20^80係平均次數？

因為birthday attack
e.g. 20人有人同一日生日既機率係
1-(365/365)(364/365)...(346/365)
=1- prod(1-i/365) from i=0 to 19
generalise完會得到
搵到collision既機會大約係=n(n-1)/(2m)
n係試既次數, m係output size
當n=sqrt(m), 個機率大約係1/2
所以when m=2^160, n=2^80

2^80係平均數
我就咁話「破解到」可能係有少少misleading, 其實都係得50%機會
不過已經好犀利
就算要去到99%都唔洗好多（相對於2^160黎講）

用番Birthday problem黎講
假設唔係潤年，要100%肯定搵到collision就要搵366個人
如果我只係要50%機會搵到collision，咁要搵幾多個人？答案：23個
點計？

由base case開始睇
P(兩個人，而且發生collision)
=1-P(兩個人，而且無發生collision)
=1-(365/365 * 364/365)
第一個人邊一日生日都無所謂
第二個人只要同第一個人唔撞就得，所以第二個人有364個選擇

P(三個人，而且發生collision)
=1-P(三個人，而且無發生collision)
=1-(365/365 * 364/365 * 363/365)
第一個人邊一日生日都無所謂
第二個人只要同第一個人唔撞就得，所以第二個人有364個選擇
第三個人只要同第一／二個人唔撞就得，所以第三個人有363個選擇

general formula係
P(k個人，而且發生collision)
=1- (365/365 * 364/365 * ... * (365-k+1)/365)
=1- (365*364...*(365-k+1))/365^k

sub k=23去上面條式
就計到
P(23個人，而且發生collision) ＝ 50.7%

呢個結果都幾得意
原來facebook fd list只要有23個人，就有一半機會有一pair fd同一日生日

比多幾個數：
只需要70個人，已經有99.9%發生collision
100個人已經有99.99997%機會發生

數學野始終都係跳唔出probability 呢個框架

不如樓主唔好覆住 出咗下篇文先

聽晚12點前出chapter 2

用數學既方法黎表示上面兩個特質：
x1, x2係input
y1, y2係output

Hiding:given y1, 好難好難好難搵到x1 such that SHA256(x1) = y1
collision resistance：好難好難好難搵到x1, x2 such that SHA256(x1) = SHA256(x2)

數學家發明既hash function有好多款
但就唔係款款hash function都符合到上面兩個要求
例如SHA family入面既SHA1(output length: 160 bit)
美國政府起1995年發表SHA1, 所有科技巨頭包括Apple Google Microsoft 當時都用左呢個cryptographic hash function
用暴力破解SHA1既話計2^80次先會搵到一對input導致collision
直到2005年，一個中國女數學家-王小雲 發現左個方法，只需要計2^63次就會搵到collision input
注意王小雲只係諗到個方法，但係果時佢都未真係搵到x1,x2 such that SHA1(x1)=SHA1(x2)
要再隔多12年，即係2017年既二月， Google先成功製造到兩份唔同既PDF file , 佢地既SHA1 output係一樣既
所以而家SHA1已經無資格做cryptographic hash function, 只能夠做一個普通hash function

如果大家有留意chrome既新聞，應該聽過chrome由v.56開始唔再支援SHA1生成既certificate
就係因為google知道chrome已經唔再安全，通過到SHA1認證都唔代表乜野
唔係話SHA完全無用，例如git而家仲用緊SHA1黎做file integrity check
只係大家已經唔可以倚靠呢個function黎保護系統

hash function仲有好多值得講既topic
例如birthday attack: 160bit output length既hash function點解只需要2^80步就可以暴力破解到collision,而唔係2^160步?
點為知好難好難好難搵到？有無單手游出公海咁難？

講左咁耐，究竟hash function同bitcoin有咩關係？
SHA256正正係所有礦工日計夜計既數：Find x such that SHA256(x) < target
而且成條blockchain之所以安全，之所以無可能被篡改，都係多得SHA2既collision resistance property
詳情就留番後面既chapter先講

點解 160個位但係暴力破解2^80就可以破？ 20^80係平均次數？

因為birthday attack
e.g. 20人有人同一日生日既機率係
1-(365/365)(364/365)...(346/365)
=1- prod(1-i/365) from i=0 to 19
generalise完會得到
搵到collision既機會大約係=n(n-1)/(2m)
n係試既次數, m係output size
當n=sqrt(m), 個機率大約係1/2
所以when m=2^160, n=2^80

2^80係平均數
我就咁話「破解到」可能係有少少misleading, 其實都係得50%機會
不過已經好犀利
就算要去到99%都唔洗好多（相對於2^160黎講）

用番Birthday problem黎講
假設唔係潤年，要100%肯定搵到collision就要搵366個人
如果我只係要50%機會搵到collision，咁要搵幾多個人？答案：23個
點計？

由base case開始睇
P(兩個人，而且發生collision)
=1-P(兩個人，而且無發生collision)
=1-(365/365 * 364/365)
第一個人邊一日生日都無所謂
第二個人只要同第一個人唔撞就得，所以第二個人有364個選擇

P(三個人，而且發生collision)
=1-P(三個人，而且無發生collision)
=1-(365/365 * 364/365 * 363/365)
第一個人邊一日生日都無所謂
第二個人只要同第一個人唔撞就得，所以第二個人有364個選擇
第三個人只要同第一／二個人唔撞就得，所以第三個人有363個選擇

general formula係
P(k個人，而且發生collision)
=1- (365/365 * 364/365 * ... * (365-k+1)/365)
=1- (365*364...*(365-k+1))/365^k

sub k=23去上面條式
就計到
P(23個人，而且發生collision) ＝ 50.7%

呢個結果都幾得意
原來facebook fd list只要有23個人，就有一半機會有一pair fd同一日生日

比多幾個數：
只需要70個人，已經有99.9%發生collision
100個人已經有99.99997%機會發生

但係你講緊”暴力破解“， 就應該係講緊有一個特定既file 要撞開， 而唔係好似birthday question 咁隨便咪埋眼搵2個相同既hash出黎。咁既情況之下仍然係需要撞2^160次

"暴力破解" 唔係指"violence"果隻暴力

係指"有系統咁" "攻擊", 搵出弱點

你指既"violence" 係代表鳩試
即係有機會重覆"打返之後打過一個穴位"

而brutal force 既方法係每個穴位都打你一次
總會有個穴位會令你暈低

呢個係我對Brutal Force 既理解
即係有System咁trial and error

不如樓主唔好覆住 出咗下篇文先

聽晚12點前出chapter 2

ho ball

支持

Lm

出現了

追曬 好睇呀 我係個19社科生都覺得有趣

上面有好多人提到hashing同encryption
呢兩個concept好似有少少亂

簡而言之
無人可以將hashing 既output變番input出黎
就算有人真係搵得到個input, 佢都只係鳩撞出黎

而encryption就保證有decrypt辦法
問題只係你知唔知道個secret

講開又想講下hasing vs encryption 起媒體上係引起過一次混亂
2011年PSN比人hack既時候，Sony講左句"password is stored uncrypted"引起好大風波
果時大家諗住比人hack都算喇，如果密碼係encrypted，就算比人拎到手都無用
但係Sony竟然話"uncrypted", 嚇到全世界死咁濟，大家都以為uncrypted = plain text
而實際上Sony想講既係"password is stored in hashed format, not encrypted format"
大家唔係好分得到hashed / encrypted，所以起勢咁屌Sony有乜理由儲plaintext word
其實我覺得儲hashed password仲好過encrypted password
因為有encryption就有decryption, 就算個encryption algorithm 幾難都好
如果你可以收買到Sony入面既工程師，叫佢比少少hints你，就可以decrypted番轉頭
但係hashed password既話，就算有Sony有二五仔都好，佢最多只可以話比你知用左邊個hash function
逆向破解果一步就無人幫到你

不過我都唔敢講Sony個案例既密碼係咪即係有比人hack到出黎，因為最後Sony都係叫大家reset password

Chapter 2 Digital Signature
數碼簽名同紙張上既簽名一樣，目的係要簽紙果個人無得抵賴佢同意，發佈左一份文件。
例如我寫左份合約，「如果聽朝8點仲掛緊八號風球，我就切JJ」，仲起上面簽個名。
點知聽朝8點真係仲掛緊，你就可以拎住份合約黎，「拿上面你簽左名，無得抵懶啦，拎條J黎」

現實世界既簽名係有弱點：冒簽。
我可以反口話「尋日另一個人扮我簽名，我唔會認我賭過J架」
呢個時就口同鼻拗，又要搵筆跡專家鑑定，或者下次賭J既時候要簽指模先算數。

但係數碼簽名就唔同喇，除非竊漏左你既秘密，否則無人扮到你簽名。

個秘密係咩？係一條private key
顧名思義，private key係只有你可以知道，因為你唔想其他人冒認你既身份，用你條priavte key黎簽名。
同private key相對既另一條key叫做public key
public key就全世界都可以知道，係用黎比人判斷一個簽名係咪你簽既。
如果文件上面既簽名係用另一個人既private key整出黎，咁你用underpant&#039;s public key去驗証，就會失敗
如果文件上面有underpants&#039;s private key 製造出黎既簽名，你用underpant&#039;s public key黎驗証先會成功。
驗証成功左，咁我就無得賴啦。

用兩個function黎表達上面段字：
簽名＝sign(underpant's private key, 文件)
簽名有效＝verify(簽名, 文件, underpant's public key)

verify呢個function會return true or false, 視乎簽名／文件／public key三樣野夾唔夾。
例如
verify(sign(underpant's private key, 文件), 文件, underpant's public key) 會return true
verify(sign(腦魔's private key, 文件), 文件, underpant's public key) 會return false
verify(sign(underpant's private key, 文件1), 文件2, underpant's public key) 會return false

要做到一個成功既signature scheme，最緊要就係無可能冒簽到
如果我用左個廢既signature, 又有個IQ180既連登仔想扮我既簽名
佢可以先收集好多個我既簽名，例如
文件1:「聽朝仲有8號風球我就切J」，underpants 簽名1
文件2:「聽朝仲有3號風球我就切J」，underpants 簽名2
....
文件n:「I go to school by bus」，underpants 簽名n
然後佢可能分析到文件同簽名既關係，破解呢個scheme
咁佢就可以試下sign 文件n+1: 「I am your father」，睇下佢有無方法起無我條private key既情況下都計到簽名n+1出黎
如果簽得arm既話，呢個signature scheme就可以收皮

private key，public key，同埋用private製造出黎既簽名, 其實都只係一串數字
都係好大好大好大好大既數
一條public key只會有一條相對應既private key
因為public key係由private key經過好複雜既數學方法生成出黎
簽名都一樣，係由private key同文件，經過數學方法產生。

要留意，拎住private key可以計到條public key出黎
但係拎住public key係無可能計得番private key
如果計得番既話，呢個digital scheme就收得皮啦
因為public key係全世界都可以知既
如果全世界都可以計得番你條private key出黎，咁就個個都可以扮你簽名啦。

「好複雜既數學方法」都有幾款，例如RSA, elliptic curve cryptography (ECC)
下面會介紹ECC

------文字解說完畢------
------對無興趣學數學既讀者黎講睇到呢度已經夠-----

首先講下private key
問：ECC既private key係點搵出黎架呢？
答：由1至2^256 入面random 揀一個數出黎
就係咁簡單。

當然你點樣random gen一條key 出黎都有好多學問既
如果你話你揀2做你條private key既話
無話唔得既，2真係起1到2^256之間
但係呢D咁簡單既key好容易就會比人破解到
用黎做例子就無乜所謂

跟住講下ECC既public key

elliptic curve cryptography就梗係有條curve啦
下面呢幅好似lin頭既野就係elliptic curve


講點樣generate public key之前先講下定義
＋呢個operator起唔同group入面既做法都唔係好同
咁起呢條憜圓曲線上面，點樣做「點同點既加法」呢？
例如想計P點＋Q點，我地會先劃一條線連起PQ兩點
好似下面幅圖咁

呢條直線隨左經過P同Q，仲會起第三點cut過條curve
我地拎住第三點，水平反轉佢，得到R，就係P同Q相加既結果。

點解要咁加法？
因為起憜圓曲線上既加法既definition係：P+Q+R=0, where P/Q/R on the same straight line

可能你會問，如果P同Q其實係同一點咁點算呀？得一點我點樣define一條直線？
如果有學過limit既概諗，你可以想像下Q點沿住條curve向P點越行越近
take limit之後其實就係條tangent line

就用呢條tangent line, 佢照樣會cut中條curve既另一點
反轉番果點就係P＋P（或者Q＋Q）既結果喇

好，而家大家知道
1. private key
2. addition on elliptic curve
有呢兩樣野就可以計到條public key出黎

起個lin頭上面我地揀一點做Generator Point, 即係G點
呢個G點要話比所有同你一齊用同一套digital signature scheme既人知
因為無左G點就verify唔到人地個簽名
點解G點會叫G點呢？因為我地拎住G點就可以generate曬其他點出黎
呢個唔詳細講啦，總之你就當大家公認左條curve上面其中一點好重要

起ECC入面，public key其實係一組(x,y)座標
public key既公式如下：
public key = private key * G點
起我地個例子入面private key 係2
所以
public key = 2*G點 = G＋G

根住就可以套用剛剛學完既加法:
劃條tangent line on G, cut the curve at another point
反轉佢，做完！
用番上面幅圖，如果private key係2, G點既座標係(1, 開方2)
咁public key既座標就係(-2, -開方2)

實際上條private key唔會係2咁簡單，起碼都十萬九千七
所以你要計既可能係public key = 109700*G點＝G點+G點+G點+G點+G點+G點+G點+G點+G點+G點+G點+G點+G點+G點.....

-----前方有進階數學-----

如果用上面既方法黎生成 public key, 就死梗
識少少數學既話你一睇就知可以調番轉佢黎計
即係拎住public key可以derive番private key出黎
因為elliptic curve on real plane係唔cryptographic secure

bitcoin真係用既elliptic curve其實又唔憜圓又唔係曲線
而係一堆點，條式係
y^2 === (x^3 + 7) mod p, where p = 2^256-2^32-2^9-2^8-2^7-2^6-2^4-1, 係一個超級大既質數
mod既意思係同餘,例如38===14 (mod 12), 因為38除12餘數係2, 14除12餘數又係2
所以38同14係同餘over 12

plot呢堆點出黎好似一堆symmetric noise咁:
https://image.ibb.co/n9ftkQ/discrete_elliptic_curve.png
起呢一大堆點上面計P點＋Q點要點做呢？
淨係劃一條線連起P同Q點係唔夠既
要畫(ax+by+c) mod p === 0, 係一堆平行線
起呢堆平行線之間搵出第三點再水平翻轉（概念同curve既情況一樣）

因為加左mod operator, 而且係一個超級大既質數
要起上面reverse engineer番條private key係好難好難好難既事

即係
given public key, G點： find private key such that: public key = private key * G點
咁你可能會話好簡單者，private key = public key / G點
elliptic curve上面既除法，又叫做discrete logarithm
問題黎喇，某種條件下既discrete logarithm係難到連數學家都諗唔到快既方法做
discrete log既難度係直情超越左RSA (based on large integer factorization)
即係話唔洗用咁多既bit數都提供到同樣既安全程度

就係因為discrete log係咁難解
我地先可以好安全咁比人知我地個public key，咁放心比人睇我地個簽名
同時又唔擔心佢地會估得番條private key出黎

------前方高能，數學恐懼人員請從速徹離-----

有public key, private key，就可以做digital signature入面最重要既一步：簽名

起generate 簽名之前我地仲要計一對暫時性既private key and public key
而家define
k = 暫時性private key
r = 由k gen出黎既暫時性public key既x coordinate
s = k^-1 * (Hash(文件) + my private key * r) mod p
where p = 2^256-2^32-2^9-2^8-2^7-2^6-2^4-1
(s,r)呢組數就我簽比呢份文件既簽名

當對家要verify呢個簽名，佢就要計
s^-1 * Hash(文件) * G + s^-1 * r * my public key
呢個結果係一組coordinate
如果佢既x-coordinate係等於r, 咁呢個簽名就係有效既

留意起呢條verify function入面只有我既public key
無我既private key起度

如果睇到你都無比上面堆怪獸嚇窒，仲睇得明同識得問
「點解條式要咁寫？」
「點prove佢地？」
「點解要揀果個p?」
可以reply問下，睇下有無數學系既高手肯回
再講落去就要更加深入認識憜圓曲線
要講algebraic structure, finite fields, subgroup order....
開多幾個chapter講都唔知得唔得
所以，真係有興趣既話，自己Google啦，有些路只能一個人走

-----數學部份完畢-----

咁public key private key起bitcoin上有咩作為呢
每一次你要動用你既bitcoin，都要用private key簽個名作實
起真係過數之前，server會check下你個戶口既public key同你個簽名夾唔夾
夾既，先比你動用果筆資金，validate呢次transaction
如果比人偷到你條private key，就可以冒認你簽發交易
下個chapter會詳細講

-----課外知識1-----

之前提過ECC既private key係random揀個數出黎
簽名時候用既k, 即係暫時性既private key同樣係隨機揀個數出黎
但係呢個k要揀得好小心：用過一次既k唔可以再用
如果你真係咁環保
文件1同文件2都用左同一個k黎簽名
咁就大檸樂喇：hacker可以根據簽名1同簽名2 計番你條private key出黎
即係玩撚猿

點解咁特別提起呢個k?
因為歷史上真係有人試過用左同一個k而奶野：Sony

PS3一直以黎係唔玩得翻版碟
當中就係用左ECC digital signature
每隻正版碟都有Sony既簽名，文件就係隻game
而且部console就有Sony既public key, 可以驗證 Sony既簽名
如果你自己寫左game，擺落PS3度行，因為你無Sony 既簽名，通過唔到認證，就行唔到隻game
PS3就係用左ECC digital signature

2010年George Hotz唔知點樣發現，Sony generate PS3 Game既簽名果陣無用到隨機暫時性private key (即係k)
反而，所有簽名都用左同一個k
咁只要你肯比錢買多幾隻正版碟
就可以有好多
文件1, Sony 簽名1
文件2, Sony 簽名2
文件3, Sony 簽名3

就可以搵到Sony簽名用既private key
然後用Sony既private key黎幫你自己寫既game簽名
Digital Signature scheme係唔會知邊人用private key黎簽
verify果陣淨係認數字，所以一但公開左條key，就全世界都可以冒認Sony簽名
即係可以繞過Sony既認證檢查
簡單黎講：Jailbroken，可以玩翻版碟

George Hotz公開左條key之後，Sony嬲到爆炸
決定從法律途徑告George告到甩褲
呢個行為辣著左Anonymous, 因為Anonymous覺得而家係Sony柒左
有人免費幫你搵個loophole出黎你唔多謝佢不突止，仲要告佢？
Apple iOS都成日比人jailbreak啦，你有無見過Apple告人？
所以2011年4月Anonymous大規模攻擊Sony
傳說話佢地就係用private key 簽左一個自己寫既programme，所以登入到dev-PSN network...
繼而拎到曬所有PSN所有user既資料...
之後既事大家都應該知啦，PSN down左成個月咁濟...

lm

-----前方有進階數學-----

如果用上面既方法黎生成 public key, 就死梗
識少少數學既話你一睇就知可以調番轉佢黎計
即係拎住public key可以derive番private key出黎
因為elliptic curve on real plane係唔cryptographic secure

bitcoin真係用既elliptic curve其實又唔憜圓又唔係曲線
而係一堆點，條式係
y^2 === (x^3 + 7) mod p, where p = 2^256-2^32-2^9-2^8-2^7-2^6-2^4-1, 係一個超級大既質數
mod既意思係同餘,例如38===14 (mod 12), 因為38除12餘數係2, 14除12餘數又係2
所以38同14係同餘over 12

plot呢堆點出黎好似一堆symmetric noise咁:
https://image.ibb.co/n9ftkQ/discrete_elliptic_curve.png
起呢一大堆點上面計P點＋Q點要點做呢？
淨係劃一條線連起P同Q點係唔夠既
要畫(ax+by+c) mod p === 0, 係一堆平行線
起呢堆平行線之間搵出第三點再水平翻轉（概念同curve既情況一樣）

因為加左mod operator, 而且係一個超級大既質數
要起上面reverse engineer番條private key係好難好難好難既事

即係
given public key, G點： find private key such that: public key = private key * G點
咁你可能會話好簡單者，private key = public key / G點
elliptic curve上面既除法，又叫做discrete logarithm
問題黎喇，某種條件下既discrete logarithm係難到連數學家都諗唔到快既方法做
discrete log既難度係直情超越左RSA (based on large integer factorization)
即係話唔洗用咁多既bit數都提供到同樣既安全程度

就係因為discrete log係咁難解
我地先可以好安全咁比人知我地個public key，咁放心比人睇我地個簽名
同時又唔擔心佢地會估得番條private key出黎

上堂有聽過下DLP,
cap張有關Pohlig–Hellman algorithm既圖:
例如23^x = 9689 (mod 11251)要搵x