密碼學／加密貨幣原理

強post, it 白痴留名

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

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

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

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

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

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

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

我都唔想罵戰

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

巴打可唔可以講解吓segwit

P=np

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

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係完全唔同曬

睇完呢段已經冇心機追落去

想問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既比喻，等我再諗諗

想問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 >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係平均次數？

算講得幾清楚

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

但想知hash function係公開既?

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

係公開既。 如果唔係點證明佢係安全。

而點解公開既都咁難reverse搵番input? 因為真係好難。 數學上有D operation 一邊做就很簡單， 調轉就好難， 例如 RSA 依賴既 prime factorization， 叫你乘埋兩個質數好容易， 俾個答案叫你拆翻開佢就好難。

想問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

多謝巴打 我終於明laaaa

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

用數學既方法黎表示上面兩個特質：
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個秘密都無分別， 都係要夾硬爆， 但係我記一句就易記好多， 要幾長都得

唔怪之得有時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個秘密都無分別， 都係要夾硬爆， 但係我記一句就易記好多， 要幾長都得

如果係爆password﹐記得以前有人寫過library﹐會優先試左用英文字 (source好似係字典有的字) 同number的combination先
所以真係想加難的，可以用外文拼音，冇咁易比人估中

唔怪之得有時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次

用數學既方法黎表示上面兩個特質：
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」
可能同你理解既「暴力破解」有少少分別

暴力破解係一種方法, 同9試差唔多
你可以用呢種方法解決各種問題
唔會話你用暴力破解就一定係解決緊某種問題
而
given x, hash(x), can't find x'=/=x such that hash(x')=hash(x)
係講緊second-preimage resistance, 係一個弱過collision resistance既property
即係做到collision resistance, 就一定做到second-preimage resistance

https://en.m.wikipedia.org/wiki/Preimage_attack

有啲好奇點解你會出post講

留名學野

leave name

LM

有啲好奇點解你會出post講

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

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