Hacker??Dōjō?Web3前沿技術(shù) workshop文稿

研究種類：密碼學-群與公鑰加密

資助金額：100 USDT

Bounty鏈接：https://dorahacks.io/zh/daobounty/139

Workshop回顧：https://b23.tv/wT55PzR

內(nèi)容貢獻者：密碼學專家?Lynndell

本項目由Hacker?Dōjō?資助，文章轉(zhuǎn)載請注明出處。

??學習量子計算、密碼學、Space等Web3前沿技術(shù)

??認領(lǐng)Bounty，賺取賞金

??參與Hackathon，獲得資助

更多Web3精彩技術(shù)分享盡在Dōjō??

WeChat: @HackerDojo0

密碼學專題一課程安排

第一課：對稱加密?（DES、AES、五種加密模式）

第二課：哈希函數(shù)?（SHA2、SHA3、MiMC、Rescue、Poseidon）

第三課：群與公鑰加密?（群，橢圓曲線群，Diffie-Hellman密鑰交換，ElGamal加密）

第四課：數(shù)字簽名?（BLS、Schnorr、EdDSA、ECDSA）

第五課：零知識證明?（Sigma零知識證明、Groth16、PLONK）

第三課：群與公鑰加密

3.1 群

符號說明：?a^b是指a的b次方；a_1 下劃線表示下標；a*b是指a乘以b。

介紹公鑰密碼算法之前先要介紹一個關(guān)鍵的數(shù)學工具：群。

群定義：?一個集合G?，滿足以下6個條件，則稱為群。

1.?非空集：?集合中至少有一個元素。

2.?二元運算：?集合中的元素能夠進行一種運算，例如加法運算、或乘法運算。

3.?封閉性：?集合中的元素進行運算后，得到的結(jié)果仍然是集合中的元素。

4.?結(jié)合律：?任意a,b,c屬于G，則(a+b)+c=a+(b+c)。

5.?單位元e?：?加法情況下a+e=e+a=a，乘法情況下：ae=ea=a。

6.?每個元素?都有逆元a^(-1)?：加法情況下a+ a^(-1)= a^(-1)+a=e，乘法情況下：a*a^(-1)= a^(-1)*a=e。

因此集合G稱為群。

對群的概念可以簡單理解為：具有封閉運算的集合稱為群。

舉例：?{0,1}集合，除法，則不滿足封閉性。1除以0等于無窮大。

這個概念有點復雜，有6個性質(zhì)，主要用到二元運算、封閉性、單位元、逆元這四個性質(zhì)。

而非空集和結(jié)合律很容易滿足。

概念1?：?如果一個群元素能夠通過有限次本身運算，表達出群內(nèi)其他所有元素，則稱為群的生成元。**生成元：**理解為用一個元素表達其他所有元素；例如：橢圓曲線上的離散對數(shù)點，是一個群。生成元G。

概念2?：?群內(nèi)元素個數(shù)稱為群的階。

例1?：?集合{0,1,2,3,4,5,6}模系數(shù)為7，就是一個加法群。

1.?非空集：?群內(nèi)有7個元素。

2.?二元運算:?加法。

3.?封閉性：?群內(nèi)任意兩個元素相加后模7后仍然是群中的元素，例如(5+6)mod7=4；

4.?結(jié)合律：?((3+4)+5) mod7=(3+(4+5)) mod7=5，結(jié)果相同。

5.?單位元為e=0?：?3+0=0+3=3。

6.?逆元：?1的逆元為6，因為(1+6)mod7=e，2的逆元為5，因為(2+5)mod7=e，同理3的逆元為4。0的逆元是0。

因此集合{0,1,2,3,4,5,6}模系數(shù)為7就是一個群。
7?是素數(shù)，這個素數(shù)群的性質(zhì)特別好。因為素數(shù)7?與群元素i?是互素的，所以每個非零元素都是群的生成元。?例如：群元素2能夠通過有限次運算，表達其他所有元素：

(2+2)mod7=4則表達群元素4，

(2+2+2)mod7=6則表達群元素6，

(2+2+2+2)mod7=1則表達群元素1，

(2+2+2+2+2)mod7=3則表達群元素3，

(2+2+2+2+2+2)mod7=5則表達群元素5，

(2+2+2+2+2+2+2)mod7=0則表達群元素0。

群元素3能夠通過有限次運算，表達其他所有元素：

(3)mod7=3

(3+3)mod7=6

(3+3+3)mod7=2

(3+3+3+3)mod7=5

(3+3+3+3+3)mod7=1

(3+3+3+3+3+3)mod7=4

(3+3+3+3+3+3+3)mod7=0

群元素4能夠通過有限次運算，表達其他所有元素：

(4)mod7=4

(4+4)mod7=1

(4+4+4)mod7=5

(4+4+4+4)mod7=2

(4+4+4+4+4)mod7=6

(4+4+4+4+4+4)mod7=3

(4+4+4+4+4+4+4)mod7=0

群元素5能夠通過有限次運算，表達其他所有元素：

(5)mod7=5

(5+5)mod7=3

(5+5+5)mod7=1

(5+5+5+5)mod7=6

(5+5+5+5+5)mod7=4

(5+5+5+5+5+5)mod7=2

(5+5+5+5+5+5+5)mod7=0

群元素6能夠通過有限次運算，表達其他所有元素：

(6)mod7=6

(6+6)mod7=5

(6+6+6)mod7=4

(6+6+6+6)mod7=3

(6+6+6+6+6)mod7=2

(6+6+6+6+6+6)mod7=1

(6+6+6+6+6+6+6)mod7=0

群元素1,2,3,4,5,6?均可以通過有限次運算表達其他群元素。

例2?：?集合{1,2,3,4,5,6}模系數(shù)為7，就是一個乘法群。

1.?非空集：?群內(nèi)有6個元素。

2.?二元運算:?乘法?。

3.?封閉性：?群內(nèi)任意兩個元素相乘后模7后仍然是群中的元素，例如(5*6)mod7=2；

4.?結(jié)合律：?((34)?5) mod7=(3?(45)) mod7=4，結(jié)果相同。

5.?單位元為1?：?1乘以任意元素等于任意元素;31=13=3。

6.?逆元：?1的逆元為1，因為(11)mod7=1;2的逆元為4，因為(24)mod7=e=1; 3的逆元為5，因為(35)mod7=1。6的逆元為6，因為(66)mod7=1。

因此集合{1,2,3,4,5,6}模系數(shù)為7就是一個乘法群。

(2)mod7=2

(2*2)mod7=4

(222)mod7=1

(222*2)mod7=2

(22222)mod7=4

(22222*2)mod7=1

(2222222)mod7=2

只能表達1,2,4?因此2不是生成元
(3)mod7=3，記為31mod7=3

(3*3)mod7=2，記為32mod7=2

(333)mod7=6，記為33mod7=6

(333*3)mod7=4，記為34mod7=4

(33333)mod7=5，記為35mod7=5

(33333*3)mod7=1，記為36mod7=1

所以3?是生成元

舉例：公鑰為6?，生成元是3?；如何計算私鑰？

已知公鑰計算私鑰，需要暴力搜索，短時間內(nèi)不可行，需要指數(shù)時間。

已知私鑰，計算公鑰，多項式時間內(nèi)可計算；

離散對數(shù)困難問題：
私鑰sk=x,公鑰pk=X，其中X=gx,PK=gX=gsk。已知g，X，不能在多項式時間內(nèi)計算出x。

? ? ? ? (3*3*3*3*3)mod7=5，記為3<sup>5</sup>mod7=5




3.2 Diffie-Hellman密鑰交換

Alice私鑰SK1= α，公鑰PK1=gα；

Bob私鑰SK2=β，公鑰PK2=gβ;

協(xié)議：?Alice發(fā)送其公鑰給Bob；

Bob發(fā)送其公鑰給Alice。

則Alice如下計算（PK2）SK1=(gβ)α=gαβ；Bob如下計算(PK1）SK2=(gα)β=gαβ公共密鑰。

因此Alice與Bob計算出相同的公共密鑰Key=gαβ，或Key=Hash(gαβ)

用會話密鑰使用對稱加密算法，對數(shù)據(jù)加密和解密
舉例：?素數(shù)群，生成元，乘法群。
Alice私鑰SK1= α=4,公鑰PK1=gα=24mod11=5;
Bob私鑰SK2= β=5,公鑰PK2=gβ=25mod11=10;
協(xié)議：?Alice發(fā)送其公鑰PK1=5給Bob；Bob發(fā)送其公鑰PK2=10給Alice。
則Alice如下計算(PK2)SK1=104mod11=1；Bob如下計算
(PK1)SK2=55mod11=1
等價于?Alice，計算Key=(25)4mod11=1，Bob計算(24)5mod11=1

因此Alice與Bob計算出相同的會話密鑰Key=gαβ=24*5=1，
或Key=Hash(gαβ)=SHA256(24x5mod11) =SHA 256(1)
但是，有?2?個缺點：

缺點?1?：公共密鑰永遠沒變化

改進：添加公開隨機數(shù)r
協(xié)議：?Alice發(fā)送其公鑰PK1和公開隨機數(shù)r1給Bob；Bob發(fā)送其公鑰PK2和公開隨機數(shù)r2給Alice
則Alice計算如下（PK2）SK1=(gβ)α=gαβ，令Key=Hash（gαβ，r1，r2）
Bob計算如下(PK1）SK2=(gα)β=gαβ，令Key=Hash（gαβ，r1，r2）
因此?Alice?與?Bob?計算出相同的會話密鑰?。會話密鑰每次都會發(fā)生變化?。。?/strong>

第一天：?m1， r1=100，r2=100

第一天：?m1，r1=200，r2=200

缺點?2?：中間人攻擊
Adversary私鑰SKA=ω，公鑰PKA=gω
理想情況：Alice發(fā)送其公鑰PK1給Bob；Bob發(fā)送其公鑰PK2給Alice；

實際情況：?Alice發(fā)送其公鑰PK1給Adversary，Adversary發(fā)送其公鑰PKA給Bob。

Bob發(fā)送其公鑰PK2給Adversary，Adversary發(fā)送其公鑰PKA給Alice

則Alice計算出與Adversary的會話密鑰

Adversary計算出與Alice的會話密鑰

則Bob計算出與Adversary的會話密鑰

Adversary計算出與Bob的會話密鑰

添加隨機數(shù)不能解決中間人攻擊

3.3 ElGamal加密

3.4 橢圓曲線群

3.5 零知識證明

3.6 ElGamal同態(tài)加密

3.6.1 密文同態(tài)運算原理

3.6.2 Sigma證明2個值相等

3.7 ElGamal 加密安全升級

3.8 ECIES加密

關(guān)于Hacker Dōjō?

Hacker Dōjō?是由Hacker共建的加密、Web3前沿技術(shù)開源知識社區(qū)。Dōjō?會以直播/音頻/文字等形式定期組織分享session, 分享主題主要覆蓋L1和L2的共識算法，架構(gòu)，GitHub repo相關(guān)內(nèi)容，包括不限于以下話題：Scroll / Polygon zkEVM、 Eigen的混合證明系統(tǒng)、Starkware、azTec、 Optimism、Zecrey、Aptos、 Move、密碼學(零知識證明、公鑰加密、哈希函數(shù)、格密碼) 、 分布式系統(tǒng)、 以太坊協(xié)議棧、 量子計算和量子信息、衛(wèi)星通信系統(tǒng)和航天器系統(tǒng)設(shè)計等。

?Bounty詳情及認領(lǐng)進度詳情：https://innovative-laser af4.notion.site/174922df15884848b6ac8b57cb4f2fae?v=612e13dc6b9d44dd8197f755abb9fe9c

?加入?Dōjō?中文社區(qū)微信聯(lián)系：@HackerDojo0

有關(guān)DoraHacks

DoraHacks 是一個全球范圍內(nèi)的極客運動，全球黑客馬拉松組織者，也是全球最活躍的多鏈 Web3 開發(fā)者平臺之一。DoraHacks.io平臺使得世界各地的Hacker和開源開發(fā)者可以參與黑客馬拉松、Bounty、Grant、Grant DAO，以及公共物品質(zhì)押等加密原生協(xié)議和基礎(chǔ)設(shè)施進行協(xié)作并獲得資助。到目前為止，DoraHacks 社區(qū)的 4000 多個項目已經(jīng)獲得了來自全球行業(yè)支持者超過 3000 萬美元的資助。大量開源社區(qū)、DAO 和 超過50個主要區(qū)塊鏈生態(tài)系統(tǒng)正在積極使用 Dora 的基礎(chǔ)設(shè)施（DoraHacks.io）進行開源融資和社區(qū)治理。

官網(wǎng)：https://dorahacks.io/

標簽：群密碼學公鑰HackerDōjō