密碼學／加密貨幣原理 (1)

**********

Chapter 1 (Cryptographic) Hash function

大家平時download software既時候可能都見過checksum呢樣野。
checksum係用黎比你驗証download落黎既file係咪corrupt左。
例如download VLC Player既時候

佢SHA-256既checksum係9826a85aab0c6dca2361c70a97fa12d8f2aa140328bdc80e68b659f9228f22fd
download完之後你可以行command睇下個checksum夾唔夾

bash-3.2$ shasum -a 256 vlc-2.2.6.dmg
9826a85aab0c6dca2361c70a97fa12d8f2aa140328bdc80e68b659f9228f22fd vlc-2.2.6.dmg

SHA其實就係一款hash function, 全名係secure hash algorithms
SHA可以大致分為SHA-1, SHA-2, SHA-3
SHA-256係SHA-2既其中一種，佢叫做SHA-256係因為佢既output size係256bits
頭先個例子入面, 9826a85aab0c6dca2361c70a97fa12d8f2aa140328bdc80e68b659f9228f22fd其實係16進制
轉番做2進制黎表示既話：
1001100000100110101010000101101010101011000011000110110111001010001000110110000111000111000010101001011111111010000100101101100011110010101010100001010000000011001010001011110111001000000011100110100010110110010110011111100100100010100011110010001011111101
唔信你可以數下，上面有256個位。

hash function既input係一個file, 或者任何可以用數字黎表示既野
而output就係一串好長好長既數
比多幾個例子大家(output用16進制表示)
SHA256(“I am underpants”)=37225F6B3F4A62E6FA48BC1A00244EBCD371E752227C55A48100EFCBF2466BDE
SHA256(“I am underpants.”)=854E461F648B3317B4C9A47A611176F4775DC01B123978CB0AAB406CBF2BEA56
SHA256(“I am underpants1”)=66CC10677AA3C55C4F02E8D45B4DD5104F553C5072D681E28A194ED500F987A7
SHA256(“I am underpants2″)=11FAFDCEC29B4907ED5DAE61E0AD0BF19B64A56801689102A2980D781E35147E
留意input入面既”係無pass入去function, 只係用黎表示input係一條string
大家可以見到，條input string只係有一個字母唔同左，成個output係完全唔同曬

**********

咁要符合咩條件先可以叫做cryptographic hash function呢？

0. 要好快就計得到
當然唔係講緊人肉可以好快計到，而係電腦可以好快計到
一部家用電腦閒閒得一秒鐘可以計到2000萬次SHA256
如果用埋GPU行parallel processing仲可以一秒幾億次

1. 你估我唔到(hiding / pre-image resistance)

你比個hash function output我，我係無好快既方法估到你個input係乜。
換句話講呢個係1-way function. 所有有inverse既function 都唔係1-way function
例如sin, cos, tan就唔係1-way, 因為有時機都唔洗禁就知input係咩
sin(x) = 1
=> x = pi/2

如果果個係cryptographic hash function
SHA256(x)=7d1a54127b222502f5b79b5fb0803061152a44f92b37e23c6527baf665d4da9a
咁x=咩呢？？？
如果我唔開估既話，你係好難好難好難搵得到個x係”abcdefg”
因為SHA256既inverse function係無closed form, 甚至連approximation既close form都無
如果真係要估，唯一方法就即係暴力破解，由0開始逐個逐個慢慢試。

2. 防撞（collision resistance)
就算好似連登仔咁高智商，都搵唔到兩個唔同input，經過hash function計算後得出同一個output
留意我係話「連登仔都搵唔到」，唔係話呢D inputs唔存在。
事實上呢D inputs一定存在。

用一個簡單既例子(Birthday Problem): 你有無可能起你既facebook friend list入面搵到兩個人係同一日出世？一定有可能。
一年最多得365日（唔計潤年），假設你有365個朋友，可能真係咁「橋」你366個朋友都係唔同日子出世。
但係如果你有366個朋友，咁就肯肯定，至少有其中兩個人既生日日期一樣。

同樣道理
SHA256既output係256bits, 即係話佢既可能既output數只有2^256個。
(每個bit只可以係1或者0 兩個可能性, 有256個位，所以係2^256)
只要你有恆心試下2^256+1咁多個input, 就肯定搵到其中兩個inputs會得出同一個output

因為好重要，所以要重覆多一次：導致SHA256 output一樣既inputs一定存在，問題係搵唔搵得到／有無快既方法搵得到。
SHA256面世到而家都未有人搵到唔同input但係一樣output既case
因為output數量實在太多
2^256大約等於10^77, 而呢個世界上見得到既atom數都只不過係10^80

你想挑戰一下既話，可以去http://passwordsgenerator.net/sha256-hash-generator
試下入唔同既string，睇下SHA256既output
如果你真係咁犀利搵到兩條唔同string ，得出黎既SHA256 output係一樣，請通知一聲，呢個發現夠你揚名立萬

**********

用數學既方法黎表示上面兩個特質：
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先講

**********

隨非大家有SHA既問題….如果唔係第1個chapter就到呢度為止…
要等幾日先會出到chapter 2啦

**********

算講得幾清楚

起碼一個有數理背景既人都應該睇得明

但想知hash function係公開既?

如果係公開既話, 係咩原因令佢咁難reverse搵番input?

係公開既
你上wiki都搵得到條式

點解咁難…
我唔係好識解SHA256點解咁難，不過都試下㗕啦
bitwise operation reverse可以有好多個結果
例如我話A同B都係1-bit
A or B = 1, 咁A同B＝？
呢度已經有三個possibilities
照道理只要我sub番落條式度試下就得

但係SHA256入面有十九幾萬個steps
其中一D steps例如bit shift係會造成information loss
例如00010111 left shift 變成00101110, 最左果個bit既你係估唔番
每一round都會做同樣既bitwise operation
每一round都少左D information
所以行左64 rounds之後已經無曬原本既information

所以而家學術界研究破解方法既時候
係嘗試破解低round數既SHA256先
例如而家已經有人搵到28 round SHA256 快過brute-force而且現實上可行既破解方法

用bitwise operation黎解釋可能有D難明
下面呢個例子同SHA256無乜關係，但係同好多其他cryptographic function (例如RSA public key cryptography)有關，就係integer factorization
比一個數你
3571082522473766674484304975778527401895200115726120795842576355509746402614775567 （10進制）
要你做factorization
簡單到連小學生都識做既數 偏偏就係最難解決

答案係
170,141,183,460,469,231,731,687,303,715,884,105,727
同
20,988,936,657,440,586,486,151,264,256,610,222,593,863,921
兩個都係超級大既質數

但係如果掉番轉，我比兩個好大既質數你，要你乘出黎
好快就做完

呢類semiprime factorization係數學界入面都未搵到有咩快方法做得到
注意：係未搵到有咩快方法
by nature呢D數學問題就係咁難解決
btw 數學家都未証明到快方法唔存在，所以各位爸打都可以研究下

**********

用一個簡單既例子(Birthday Problem): 你有無可能起你既facebook friend list入面搵到兩個人係同一日出世？一定有可能。
一年最多得365日（唔計潤年），假設你有365個朋友，可能真係咁「橋」你366個朋友都係唔同日子出世。
但係如果你有366個朋友，咁就肯肯定，至少有其中兩個人既生日日期一樣。

應該係365

多謝爸打指正

**********

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

呢度可唔可以再解釋下

sin(pi/2) = sin (5pi/2) = 1
呢個就係sin function collision
pi/2 同5pi/2係唔同既數，但係sin出黎都係1

但係放入SHA256既case度，你搵唔搵到兩個唔同既input, 擺入SHA256之後
出黎個input係一樣？

**********

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

呢度可唔可以再解釋下

sin(pi/2) = sin (5pi/2) = 1
呢個就係sin function collision
pi/2 同5pi/2係唔同既數，但係sin出黎都係1

但係放入SHA256既case度，你搵唔搵到兩個唔同既input, 擺入SHA256之後
出黎個input係一樣？

**********

請教一下
小弟以前睇過 Tom Scott (Computerphile) 講過Hash algorithm會因為電腦越黎越快而慢慢失效
隨住電腦運算速度越黎越快，SHA-2終有一日會被破解，而呢個時間好有可能早過2100年（掘唔到bitcoin之前），到時會唔會對bitcoin有影響？

另外想問Bitcoin本身一但唔見咗（例如整唔見實體錢包USB之類）就好似冇方法補充，bitcoin數量長期黎講只會有減無增，咁現時有冇第二啲cryptocurrency可以解決呢個問題？

第一個問題
（我估）hardfork而家條blockchain
switch 去另一種cryptographic hash function, 例如SHA512

第二個問題
無

第三個問題
ethereum已經係inflationary 啦

**********

巴打睇緊邊本書? 我都想買返本睇下

bitcoin and cryptocurrency technology
mastering bitcoin

Thanks

如果想學埋數學，就唔係睇cryptocurrency既書啦
要睇Forouzan既Cryptography and Network Security

**********

強post, it 白痴留名

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

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

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

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

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

bitcoin掘出黎都唔係一個個
最初最初一掘就掘到50個出黎
早兩年變左做一掘掘到25個出黎
遲D會變做掘到12.5個

起電腦既世界其實你填幾多個小數位落去都得架啦
理論上你填幾多個小數位電腦都handle到
中本聰limit佢做8個小數位係為左限制一個transaction既file size
慳番D network transmission time同storage space

**********

有無預告ch2 係講咩

會講digital signature, 即係public key private key

**********

竟然有咁多爸打有興趣  
竟然一日就有咁多個reply    
我開頭仲驚個post會沉底

上面有太多回覆
如果我睇漏左唔記得覆既話請唔好屌得咁大力

夜少少番到屋企之後會盡量覆

**********

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

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

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

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

bitcoin掘出黎都唔係一個個
最初最初一掘就掘到50個出黎
早兩年變左做一掘掘到25個出黎
遲D會變做掘到12.5個

起電腦既世界其實你填幾多個小數位落去都得架啦
理論上你填幾多個小數位電腦都handle到
中本聰limit佢做8個小數位係為左限制一個transaction既file size
慳番D network transmission time同storage space

謝解惑｡

所以係會有個地方(say server) 記住我目前擁有幾多bitcoin(去到小數點8位照你講) ? 而我同人交易時係會整一個如上面有張圖所講加咗我條public & private key再encrypt變成一個transaction file再俾人﹐而個人就會放個file上server去處理而完成交易?

差唔多

嚴格黎講bitcoin node無記得一個人／一個account有幾多錢
而係有一個transaction既output未有人用過
過多幾個chapter會詳細講

**********

請教一下
小弟以前睇過 Tom Scott (Computerphile) 講過Hash algorithm會因為電腦越黎越快而慢慢失效
隨住電腦運算速度越黎越快，SHA-2終有一日會被破解，而呢個時間好有可能早過2100年（掘唔到bitcoin之前），到時會唔會對bitcoin有影響？

另外想問Bitcoin本身一但唔見咗（例如整唔見實體錢包USB之類）就好似冇方法補充，bitcoin數量長期黎講只會有減無增，咁現時有冇第二啲cryptocurrency可以解決呢個問題？

bitcoin掘新coin係靠搵 partial collision (用brute force 逐個試)
如果只係運算能力提高, 即brute force更快, 咁會自動提高難度
e.g.由搵頭5個位係0, 變搵頭10個位係0
而個難度係根據上一個partial collision幾快比人搵到而調節, 所以掘coin既人升得愈快, 或者電腦運算速度升得愈快, 個難度就升得愈快
如果講到破解, 就要視乎破解法幾有效, 不過一般唔會即時影響安全性
然後正常會有update轉用新既hash algorithm, 確保新transaction係安全
舊record點處理就視情況而訂

bitcoin現時設左上限, 將來有需要既話取消都唔奇
同埋唔係所有cryptocurrency都有設上限

其實我最唔明嘅係點解撞中左個transaction 就會有錢分？

簡單咁講 係比特幣創造人整出黎嘅獎勵 鼓勵更多人去mine(撞個hash) 因為愈多人就愈難比人改到當中既資料

搵partial collision係出新coin既唯一方法
具體黎講係搵x令到Hash(x,y)<z
x係brute force搵出黎既數
y係(hash of) past records
z係一個數, 決定搵x既難度
掘coin者要先verify y, 即先前既record係岩
如果y錯, 咁搵到x都冇用
呢個做法可以令人幫手verify交易記錄

另一方面, 你搵到k=Hash(x,y), 而且成功拎到coin
k亦會成為past record既一部分
新既hash input 亦會包埋k, 如此類推
新hash係由舊hash加新野得出黎
呢個步驟run得愈多次(愈多block, 條chain愈長), 舊hash/record就愈可靠
因為只有係最長個條chain既record先至有效, e.g.
A chain: a || hash(a, ·)
B chain: a || hash(a, *) || hash(hash(a, *),*)|| hash(hash(a, *),*)
只有B chain既record先會被認同
因為搵hash需時, B比A長愈多, A就愈難追上B, 除非你有極大運算能力

y係(hash of) past records
唔係好明y係咩

y係hash function既input既一部份
係固定既，miner都改變唔到既input（或者話大部份情況下都唔會改變）
x就係miner可以改變既input
x同y夾埋要hash得出一個數細過target miner先算成功

過多幾個chapter會詳細講

**********

MD5同SHA係咪類似嘅嘢嚟？

係
都係hash algorithm
設計SHA-1果陣直情有參考過MD5

**********

想問hard fork 同Segwit 係咩 同埋咩情況先需要咁做?

hardfork即係改變左block既rules
可能尋日呢個block仲係合法既，但係hardfork完呢個block就唔合法
例如有一日舊登班高撚起義，立法矮過180上舊登係犯法

咁矮過180班高人唔同意呢個規舉
佢地有兩個選擇
一係食增高丸等自己高過180入舊登
一係自己另起爐灶，開新登，而且唔限制身高。
另起爐灶呢個動作就叫做fork

點分硬fork同軟fork?

如果新登係不論身高無任歡迎，咁就係softfork, 因為舊登仔無論幾高都可以上新登

如果新登走向另一個極端，只受矮過180既人玩，咁舊登仔會可能因為高過180上唔到
為之hardfork

segwit個問題就係…而家blockchain入面每個block都有size limit
唔可以超過1MB
因為呢個寛制，搞到bitcoin 每秒處理到既交易得6-7單
呢個問題越黎越嚴重，因為搞到每單交易都要等好耐先確認到
所以就有人建議放寛個限制到2MB (segwit)
有人覺得2MB都唔夠，應該比blocksize自由浮動（segwit對家）
今年年頭呢兩班人傾唔掂數，如果實行左2MB限制，segwit對家話會hardfork條chain
咁佢果邊就會有D block >2MB which 而家條chain就算更新左都唔會接受
最近呢兩班人又傾掂數，接受左2MB限制

hardfork左既chain以後都唔可能merge番一齊
所以會變左兩種currency咁
ethereum 就出現過呢個問題
所以而家起交易所會見到兩款ethereum: ethereum vs ethereum classic

**********

想問hard fork 同Segwit 係咩 同埋咩情況先需要咁做?

hardfork即係改變左block既rules
可能尋日呢個block仲係合法既，但係hardfork完呢個block就唔合法
例如有一日舊登班高撚起義，立法矮過180上舊登係犯法

咁矮過180班高人唔同意呢個規舉
佢地有兩個選擇
一係食增高丸等自己高過180入舊登
一係自己另起爐灶，開新登，而且唔限制身高。
另起爐灶呢個動作就叫做fork

點分硬fork同軟fork?

如果新登係不論身高無任歡迎，咁就係softfork, 因為舊登仔無論幾高都可以上新登

如果新登走向另一個極端，只受矮過180既人玩，咁舊登仔會可能因為高過180上唔到
為之hardfork

segwit個問題就係…而家blockchain入面每個block都有size limit
唔可以超過1MB
因為呢個寛制，搞到bitcoin 每秒處理到既交易得6-7單
呢個問題越黎越嚴重，因為搞到每單交易都要等好耐先確認到
所以就有人建議放寛個限制到2MB (segwit)
有人覺得2MB都唔夠，應該比blocksize自由浮動（segwit對家）
今年年頭呢兩班人傾唔掂數，如果實行左2MB限制，segwit對家話會hardfork條chain
咁佢果邊就會有D block >2MB which 而家條chain就算更新左都唔會接受
最近呢兩班人又傾掂數，接受左2MB限制

hardfork左既chain以後都唔可能merge番一齊
所以會變左兩種currency咁
ethereum 就出現過呢個問題
所以而家起交易所會見到兩款ethereum: ethereum vs ethereum classic

sorry上面講錯左softfork同hardfork既比喻，等我再諗諗

hardfork即係改變左block既rules
可能尋日呢個block仲係合法既，但係hardfork完呢個block就唔合法
例如有一日舊登班高撚起義，立法矮過180上舊登係犯法
矮過180班人唔同意呢個規舉
高撚一怒之下決定另立新登，並且規定高過180先可以上新登，呢個動作叫做fork
呢個例子係softfork, 因為高撚起新舊登都可以自由出入，只不過以前合法既野而家變左犯法
“A softfork is a change to the bitcoin protocol wherein only previously valid blocks/transactions are made invalid.”

另一個例子，舊登公認：五毛上舊登係犯法既
但係如果有一日五毛多得濟，多到佢地由舊登fork左個五毛登出去
五毛上舊登係犯法
五毛上五毛登係合法
呢個就係hardfork, 因為以前犯法既野而家竟然變左合法
“A hardfork is a change to the bitcoin protocol that makes previously invalid blocks/transactions valid,”

segwit個問題就係…而家blockchain入面每個block都有size limit
唔可以超過1MB
因為呢個寛制，搞到bitcoin 每秒處理到既交易得6-7單
呢個問題越黎越嚴重，因為搞到每單交易都要等好耐先確認到
所以就有人建議放寛個限制到2MB (segwit)
有人覺得2MB都唔夠，應該比blocksize自由浮動（segwit對家）
今年年頭呢兩班人傾唔掂數，如果實行左2MB限制，segwit對家話會hardfork條chain
咁佢果邊就會有D block &gt;2MB which 而家條chain就算更新左都唔會接受
大過2MB既block就好似班五毛，舊chain入面大過2MB係犯法，但係起佢地自立出黎既新chain係合法

最近呢兩班人又傾掂數，接受左2MB限制，所以變番softfork

hardfork左既chain以後都唔可能merge番一齊
所以會變左兩種currency咁
ethereum 就出現過呢個問題
所以而家起交易所會見到兩款ethereum: ethereum vs ethereum classic

**********

用數學既方法黎表示上面兩個特質：
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%機會發生

**********

唔怪之得有時d 密碼要at least 6個字
係防止太短容易比人硬解

至於點解要又大階又細階, 又要符號?

一樣原理姐
a-z 26個
A-Z 又多26個
符號又幾個

個combination 就差好遠

6個數字就10＾6 組合
大細階英文+數字就有(10+26+26)＾6組合

咁又係
但反而有d 濕鳩網/App 要咁多限制

反而gmail 果d 唔洗

點解呢

risk base control姐 你都做過audit狗嫁咩

google 有unusual attempt 你鳩撞唔知幾多次 佢封你ip
你用第二部手機入gmail 都立即收到email alert
有其他compensate control
password config control咪可以廢d lo 

咁又係

不過其實邊種方法secure d ?
(考慮cost, maintainence….etc)

purely 用複雜密碼去提高暴力破解所需既時間

定係google 咁做多層risk control

最 secure 就係用句子做密碼。 電腦黎講， KHGIindso498544 同 “you bloody mother fecker” 2個秘密都無分別， 都係要夾硬爆， 但係我記一句就易記好多， 要幾長都得

你係假設左對方用brute-force 攻擊你
但現實上更加多人用dictionary attack
會用字典＋生日日期＋你名＋老婆名＋仔女名＋寵物名＋常用字 generate possible password
用英文句子既話好快收皮

詳情可以睇下Mr. Robot 係點樣hack人
頭兩集已經講佢點樣hack心理學家同同事既facebook password

**********

用數學既方法黎表示上面兩個特質：
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次

我理解「暴力破解」既意思係有系統地，逐個逐個可能咁撞，直到搵到答案

問題係咩種類／要搵乜野出黎唔係重點
個問題可以係「撞個password出黎」「撞對collision input出黎such that hash output一樣」「撞對質數such that product is a certain number」
可能同你理解既「暴力破解」有少少分別

**********

上面有好多人提到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's public key去驗証，就會失敗
如果文件上面有underpants's private key 製造出黎既簽名，你用underpant'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點…..

*********