Blockchain and cryptography （区块链与密码学）学习笔记3：群与公钥加密

Dora Dōjo
1

Hacker Dōjo Workshop：
研究种类：密码学，群与公钥加密
资助金额：100 usdt
Bounty链接：https://dorahacks.io/zh/daobounty/139
创作者：Lynndell
本项目由Hacker Dōjo资助，文章转载请联系
Telegram: @HackerDojo0
WeChat: @HackerDojo0
E-mail: hackerdojo0@gmail.com

3 群与公钥加密

3.1 群

符号说明： a^b是指a的b次方；a_1 下划线表示下标；a*b是指a乘以b。

介绍公钥密码算法之前先要介绍一个关键的数学工具：群。

群定义： 一个集合G ，满足以下6个条件，则称为群。

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

2. 二元运算： 集合中的元素能够进行一种运算，例如加法运算、或乘法运算。

3. 封闭性： 集合中的元素进行运算后，得到的结果仍然是集合中的元素。

4. 结合律： 任意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个性质，主要用到二元运算、封闭性、单位元、逆元这四个性质。

而非空集和结合律很容易满足。

概念1 ： 如果一个群元素能够通过有限次本身运算，表达出群内其他所有元素，则称为群的生成元。**生成元：**理解为用一个元素表达其他所有元素；例如：椭圆曲线上的离散对数点，是一个群。生成元G。

概念2 ： 群内元素个数称为群的阶。
例1 ： 集合{0,1,2,3,4,5,6}模系数为7，就是一个加法群。

1. 非空集： 群内有7个元素。

2. 二元运算: 加法。

3. 封闭性： 群内任意两个元素相加后模7后仍然是群中的元素，例如(5+6)mod7=4；

4. 结合律： ((3+4)+5) mod7=(3+(4+5)) mod7=5，结果相同。

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}模系数为7就是一个群。
7 是素数，这个素数群的性质特别好。因为素数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}模系数为7，就是一个乘法群。

1. 非空集： 群内有6个元素。

2. 二元运算: 乘法 。

3. 封闭性： 群内任意两个元素相乘后模7后仍然是群中的元素，例如(5*6)mod7=2；

4. 结合律： ((34) 5) mod7=(3 (45)) mod7=4，结果相同。

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}模系数为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 ；如何计算私钥？

已知公钥计算私钥，需要暴力搜索，短时间内不可行，需要指数时间。

已知私钥，计算公钥，多项式时间内可计算；

离散对数困难问题：
私钥sk=x,公钥pk=X，其中X=gx,PK=gX=gsk。已知g，X，不能在多项式时间内计算出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β;

协议： Alice发送其公钥给Bob；

Bob发送其公钥给Alice。

则Alice如下计算（PK2）SK1=(gβ)α=gαβ；Bob如下计算(PK1）SK2=(gα)β=gαβ公共密钥。

因此Alice与Bob计算出相同的公共密钥Key=gαβ，或Key=Hash(gαβ)

1
1638×761 9.95 KB

用会话密钥使用对称加密算法，对数据加密和解密
举例： 素数群，生成元，乘法群。
Alice私钥SK1= α=4,公钥PK1=gα=24mod11=5;
Bob私钥SK2= β=5,公钥PK2=gβ=25mod11=10;
协议： Alice发送其公钥PK1=5给Bob；Bob发送其公钥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 ：公共密钥永远没变化

改进：添加公开随机数r
协议： Alice发送其公钥PK1和公开随机数r1给Bob；Bob发送其公钥PK2和公开随机数r2给Alice
则Alice计算如下（PK2）SK1=(gβ)α=gαβ，令Key=Hash（gαβ，r1，r2）
Bob计算如下(PK1）SK2=(gα)β=gαβ，令Key=Hash（gαβ，r1，r2）
因此 Alice 与 Bob 计算出相同的会话密钥 。会话密钥每次都会发生变化！！！

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

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

缺点 2 ：中间人攻击
Adversary私钥SKA=ω，公钥PKA=gω
理想情况：Alice发送其公钥PK1给Bob；Bob发送其公钥PK2给Alice；

2
2692×295 4.97 KB

实际情况： Alice发送其公钥PK1给Adversary，Adversary发送其公钥PKA给Bob。
Bob发送其公钥PK2给Adversary，Adversary发送其公钥PKA给Alice

则Alice计算出与Adversary的会话密钥
3
Adversary计算出与Alice的会话密钥
4
则Bob计算出与Adversary的会话密钥
5
Adversary计算出与Bob的会话密钥
6
添加随机数不能解决中间人攻击
7

3.3 ElGamal加密

8

3.4 椭圆曲线群

9

10
10657×787 101 KB

11
11646×945 127 KB

12
12675×797 191 KB

3.5 零知识证明

13
13700×914 259 KB

14
14702×944 60.4 KB

15
15695×484 10.1 KB

3.6 ElGamal同态加密

3.6.1 密文同态运算原理

16

17
17683×903 23.3 KB

18

3.6.2 Sigma证明2个值相等

19
19610×545 12.7 KB

20
20620×936 23.8 KB

21
21631×958 22.5 KB

22
22597×610 13.7 KB

3.7 ElGamal 加密安全升级

23
23573×505 45.1 KB

3.8 ECIES加密

24

25
25561×712 228 KB

关于我们
:small_orange_diamond:Hacker Dōjo是由Hacker共建的加密、Web3前沿技术开源知识社区。Dōjo会以直播/音频/文字等形式定期组织分享session，内容包括Web3领域前沿技术论文解读、技术研讨、工作坊等。欢迎在Hacker Dōjo社区讨论、学习和交流。加入Dōjo的Hacker可以提出自己的学习期望，主动提案自己擅长的技术话题，由Dōjo组织分享。同时，Hacker Dōjo推出Web3前沿课题研究计划，定期选题，由hacker进行研究和讲解，并以bounty形式奖励研究贡献者。
合作事项
:small_orange_diamond:认领Bounty：DoraHacks
:small_orange_diamond:转载文章：请保留Hacker Dōjo Workshop介绍并联系我们hackerdojo0@gmail.com

2

笔记更新

3.3 ElGamal加密

1
2

3.4 椭圆曲线群

椭圆曲线群与第一节介绍的素数群，都是群。仅仅是底层表达不一样，计算速度不一样。相同的安全性，需要的私钥位宽更低。

椭圆曲线群下的ElGamal加密方案
3
乘法素数群下的ElGamal加密方案
4

关于Dorahacks
DoraHacks 是一个全球范围内的极客运动、全球黑客马拉松组织者，也是全球最活跃的多链 Web3 开发者平台之一。DoraHacks.io平台使得世界各地的Hacker和开源开发者可以参与黑客马拉松、Bounty、Grant、Grant DAO，以及公共物品质押等加密原生协议和基础设施进行协作并获得资助。到目前为止，DoraHacks 社区的 4000 多个项目已经获得了来自全球行业支持者超过 3000 万美元的资助。大量开源社区、DAO 和 超过50个主要区块链生态系统正在积极使用 Dora 的基础设施（DoraHacks.io）进行开源融资和社区治理。

关于Dorahacks DAO Bounty
Dorahacks DAO Bounty，为各类DAO和组织赋能！
Bounty计划为DAO和组织提供了一个强大的平台，通过社区激励的形式，发布问题，协调任务，鼓励用户积极参与。
作为Bounty发布者，您可以根据我们的指南，发布社区相关的悬赏任务，解决问题的同时，提升社区活跃度：How to publish a bounty and easily fund bounty hunters
作为赏金猎人，您可以在DAO Bounty计划中发挥自己的专长和能力，认领悬赏，解决问题，获得酬金：DAO Bounties | DoraHacks

关于Hacker Dōjō
Hacker Dōjō是由Hacker共建的加密、Web3前沿技术开源知识社区。Dōjō会以直播/音频/文字等形式定期组织分享session，内容包括Web3领域前沿技术论文解读、技术研讨、工作坊、技术领袖研讨会等。欢迎在Hacker Dōjo社区讨论、学习和交流：Dora Dōjo - Dora Community Forum

目前Hacker Dōjō已分享的主题有：

  • 密码学：基础专题（对称加密算法、哈希函数、群和公钥加密、数字签名和KZG承诺、零知识证明、非对称密码算法、分布式密码学）
  • 密码学：算法代码专题（Halo、Halo2、Plonk、Groth16、分布式密钥生成）
  • 密码学：抗量子计算破解算法专题
  • Layer1架构：Move系列、模块化公链、共识协议Bullshark、内存池协议Narwhal和共识协议Tusk、Aptos共识与交易并行执行
  • Layer2架构：zkSync研究、Layer2的支付通道扩容方法、Polygon Hermez、Optimism、StarkWare技术与生态梳理
  • IRS系列：Interest Rate Swap and DeFi Platforms、Interest Rate Swap and Perpetual Swap、The Future Dencentralized Interest Rate Swap
  • 量子计算系列：量子计算基础、Qiskit专题（Qiskit入门、Deutsch-Jozsa算法、Bernstein-Vazirani算法、Simon算法、量子卷积神经网络、量子傅里叶变换、量子相位）、Pennylane专题（利用变分量子电路拟合傅里叶级数）、实验法观测宏观量子叠加态
  • AIGC系列：ChatGPT比较语料评测、GPT-4论文解读

加入Dōjō的Hacker可以提出自己的学习期望，主动提案自己擅长的技术话题，由Dōjō组织分享。同时，Hacker Dōjō推出Web3前沿课题研究计划，定期选题，由Hacker进行研究和讲解，并以bounty形式奖励研究贡献者。欢迎各位Hacker认领Bounty：DAO Bounties | DoraHacks

联系我们：

Telegram: @DoraDojo0

WeChat: @HackerDojo0

E-mail: hackerdojo0@gmail.com

3

Good job! Very useful!