密码学03｜群和公钥加密

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，乘法情况下：aa^(-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* (4*5)) 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。

​ (33333)mod7=5，记为3⁵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αβ)

用会话密钥使用对称加密算法，对数据加密和解密
举例： 素数群，生成元，乘法群。
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αβ=245=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；

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

则Alice计算出与Adversary的会话密钥

Adversary计算出与Alice的会话密钥

则Bob计算出与Adversary的会话密钥

Adversary计算出与Bob的会话密钥

添加随机数不能解决中间人攻击

3.3 ElGamal加密

3.4 椭圆曲线群

3.5 零知识证明

3.6 ElGamal同态加密

3.6.1 密文同态运算原理

3.6.2 Sigma证明2个值相等

3.7 ElGamal 加密安全升级

3.8 ECIES加密