Blockchain and cryptography (区块链与密码学)学习笔记3:群与公钥加密

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如下计算(PK2SK1=(gβ)α=gαβ;Bob如下计算(PK1SK2=(gα)β=gαβ公共密钥。

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


用会话密钥使用对称加密算法,对数据加密和解密
举例: 素数群,生成元,乘法群。
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计算如下(PK2SK1=(gβ)α=gαβ,令Key=Hash(gαβ,r1,r2
Bob计算如下(PK1SK2=(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;

实际情况: 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



3.5 零知识证明



3.6 ElGamal同态加密

3.6.1 密文同态运算原理

16


18

3.6.2 Sigma证明2个值相等




3.7 ElGamal 加密安全升级

3.8 ECIES加密

24


关于我们
: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

笔记更新

3.3 ElGamal加密

1
2

3.4 椭圆曲线群

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

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

Good job! Very useful!