信息安全工程师----第三章 3.5公钥密码体制

第三章 3.5公钥密码体制

公钥密码体制的概念

在公钥密码体制中

公钥密码体制中，加密和解密采用两把不同的钥匙，分别为公钥和私钥 ，公钥可以公开 ，而私钥需要严格保密 ，这种密码系统需要使用单向陷门函数来构造。

单向函数y=f（x ）满足下面两个条件：

• 已知x ，要计算y很容易
• 已知y，要计算x很难
  常见的单向函数有SM3、SHA-1、MD5。单向函数的加密效率高 但加密后不能还原

单向陷门函数y=f（x ） 满足下面三个条件：

• 函数f具有陷门。比如，陆逊受困于诸葛亮的八阵图 ，他只有在诸葛亮老丈人带着走了生门后才捡回一命 ，这里的生门就是陷门。
• 已知x，要计算y很容易
• 已知y， 如果不知道陷门，要计算出x很难； 如果知道陷门， 则计算出x很容易。
  目前暂时还不能证明单向函数一定存在 ，所以应用中只要求实用即可。目前单向性足够的函数有：
• 因子分解问题 ：计算素数乘积容易 而计算因子分解困难
• 离散对数问题 ：计算素数幂乘容易，而计算对数困难
  加密秘钥和解密密钥不相同的算法，称为非对称加密算法， 这种方法又称为公钥密， 公钥密码体制解决了对称秘钥算法的秘钥分配与发送的问题。 在非对称加密算法中， 私钥用于解密和签名 ，公钥用于加密和认证。

公钥密码体制的特点如下 ：

明文M通过加密算法E和加密密钥Ke变成密文C的方法，用公式表达如下

C=E（M，Ke）

密文C通过解密算法D和解密秘钥Kd还原为明文M的方法，用公式表示如下

M=D（C，Kd）

计算上不能由Ke求出Kd。

加密算法E和解密算法D都是高效的 。

RSA密码

RSA算法是1977年由Rivest、Shamir、Adleman提出的非常著名的公钥密码算法

它是基于大合数的质因子分解问题的困难性

RSA的缺点是加密、解密速度太慢，因此很少用于数据加密，而多用于数字签名、密钥管理和认证等方面

RSA算法是一种分组密码，明文和密文是0到n-1之间的整数，通常n的大小为1024位二进制数或309位十进制数.

基本的RSA密码体制：参数、加密算法、解密算法

①随机地选择两个大素数p和q，而且保密；
②计算n=pq，将n公开；
③计算φ(n)=(p-1)(q-1)，对φ(n)保密；
④随机地选取一个正整数e ， 1，而保密的解密钥Kd=。

说明：算法中的φ(n)是一个数论函数，称为欧拉(Euler)函数。φ(n)表示在比n小的正整数中与n互素的数的个数。例如，φ(6)=2，因为在1,2, 3, 4, 5中与6互素的数只有1和5两个数。若p和q为素数，且n=pq，则φ(n)=(p-1)(q-1) 。

例2-2  令p=47，q=71，n=47x71=3337，φ(n)=φ(3337)=46×70=3220 。选取e=79，计算d=e-1 mod 3220 =1019 mod 3220。公开e=79和n=3337 ，保密p=47，q=71，d=1019和φ(n)=3220 。
设明文M=688 232 687 966 668 3，进行分组，M1=688 , M2=232， M3=687,M4=966,M5=668,M6=003。M1的密文C1=68879 mod 3337=1570 ，继续进行类似计算，可得最终密文
C=1570 2756 2091 22762423 158。
如若解密，计算M1=15701019 mod 3337=688，类似地可解密还原出其他明文。

Diffie-Hellman密钥交换体制

Diffie-Hellman密钥交换是W.Diffie和M.Hellman于1976年提出的第一个公开密钥算法，已在很多商业产品中得以应用。

算法的惟一目的是使得两个用户能够安全地交换密钥，得到一个共享的会话密钥
算法本身不能用于加、解密

该算法的安全性基于求离散对数的困难性。

假定p是一个素数，α是其本原根，将p和α公开。假设A和B之间希望交换会话钥。

–用户A：

–用户B：

Diffie-Hellman密钥交换协议很容易受到中间人攻击。

一个主动的窃听者C可能截取A发给B的消息以及B发给A的消息，他用自己的消息替换这些消息

并分别与A和B完成一个Diffie-Hellman密钥交换

密钥交换协议完毕后，A实际上和C建立了一个会话密钥，B和C建立了一个会话密钥

当A加密一个消息发送给B时，C能解密它而B不能。类似地，当B加密一个消息发送给A时，C能解密它而A不能

防止Diffie-Hellman密钥交换协议中间人攻击的一个方法是让A和B分别对消息签名。

ElGamal体制

ElGamal是1985年由T. EIGamal提出的一个著名的公钥密码算法，是基于离散对数问题上的公开密钥体制。

该算法既能用于数据加密也能用于数字签名。

ElGamal算法如下：

1. 密钥产生
   任选一个大素数p，使得p-1有大素因子，g是模p的一个本原根，公开p与g。
   使用者任选一私钥x，x∈[0, p-1]
   计算公钥 y=gx mod p
   公开公钥： y, p, g
   保密私钥： x
2. 加密过程
   对于明文m，选取一个r，r∈[0, p-1]
   计算 c1=gr mod p
   c2=m*yr mod p
   则密文为 {c1,c2}
3. 解密过程
   先计算 w=(c1x)-1 mpd p
   再计算出明文 m=c2*wmod p
4. 签名过程
   假设对消息m签名，任选一个随机数k，使k∈[0, p-1]
   计算 r=gk modp
   s=k-1(m-x_r)mod(p-1)
   签名为{r,s}
   (5) 签名验证过程
   yr_rs=gm(mod p)
   需要说明的是，为了避免选择密文攻击，ElGamal是对消息m的hash值进行签名，而不是对m签名
   与RSA方法比较，ElGamal方法具有以下优点：

• 系统不需要保存秘密参数，所有的系统参数均可公开
• 同一个明文在不同的时间由相同加密者加密会产生不同的密文，但ElGamal方法的计算复杂度比RSA方法要大。
  更为细致做法如下：

随机地选择一个大素数p，且要求p-1有大素数因子。再选择一个模p的本原元α。将p和α公开。

1.密钥生成
用户随机地选择一个整数d作为自己的秘密的解密钥，1≤d≤p-1，计算y=αd mod p，取y为自己的公开的加密钥。
由公开钥y计算秘密钥d，必须求解离散对数，而这是极困难的。

2.加密
将明文消息M(0≤M≤p-1)加密成密文的过程如下：

①随机地选取一个整数k，1≤k≤p-1。

②计算 U=yk mod p （2-46）

C1=ak mod p （2-47）

C2=UM mod p （2-48）

③取(C1，C2) 作为的密文。

3.解密
将密文(C1，C2)解密的过程如下：

①计算V=C1d mod p （2-49）

②计算M=C2 V-1 mod p （2-50）

解密的可还原性可证明如下：
因为，

C2 V-1 mod p=(UM)V-1 mod p

=UM(C1d) -1 mod p

=UM ((αk) d)-1 mod p

=UM ((αd) k)-1 mod p

=UM ((y)k)-1mod p

=UM (U)-1 mod p

=M mod p

故解密可还原。

例2-3设p=2579，取α=2，秘密钥d=765，计算出公开钥y=2765 mod 2579=949。再取明文M=1299，随机数k=853，则C1=853 mod 2579=435，C2=1299x949 835 mod2579=2396，所以密文为(C1，C2) =(435，2396) 。解密时计算
M=2396x(435765 )-1 mod 2579=1299
从而还原出明文。

椭圆曲线密码

人们对椭圆曲线的研究已有100多年的历史，而椭圆曲线密码ECC(Elliptic Curve Cryptosysytem) 是Koblitz和Miller于20世纪80年代提出的。ELGamal密码是建立在有限域GF§之上的，其中p是一个大素数，这是因为有限域GF§的乘法群中的离散对数问题是难解的。受此启发，在其他任何离散对数问题难解的群中，同样可以构成ELGamal密码。于是人们开始寻找其他离散问题难解的群。研究发现，有限域上的椭圆曲线上的一些点构成交换群，而且离散对数问题是难解的。于是可在此群上定义ELGamal密码，并称为椭圆曲线密码。

椭圆曲线计算比RSA复杂得多，所以椭圆曲线密钥比RSA短，一般认为160位长的椭圆曲线密码相当于1024位RSA密码的安全性。我国第二代居民身份证使用的是256位的椭圆曲线密码。

SM2算法是国家密码管理局发布的椭圆曲线公钥密码算法，用于在我国商用密码体系中替换RSA算法

2018年11月，ISO/IEC14888-3：2018《信息安全技术带附录的数字签名第3部分：基于离散对数的机制》正式纳入SM2/SM9数字签名算法。其中，SM9(标识密码算法)是基于双线性对的标识密码算法，SM9不需要申请数字证书，利用用户身份标识生成公、私密钥对，可用于数据加密、数字签名、密钥交换以及身份认证等。

椭圆曲线加密过程

考虑K = kG ，其中K、G为椭圆曲线Ep(a,b)上的点，n为G的阶（n G = O ∞），k为小于n的整数。则给定k和G，根据加法法则，计算K很容易但反过来，给定K和G，求k就非常困难。因为实际使用中的ECC原则上把p取得相当大，n也相当大，要把n个解点逐一算出来列成上表是不可能的。这就是椭圆曲线加密算法的数学依据 。

• 点G称为基点（base point）
• k ( k < n )为私有密钥（private key）

• K为公开密钥（public key)
  下面是利用椭圆曲线进行加密通信的过程：

  1、用户A选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。
  2、用户A选择一个私有密钥k，并生成公开密钥K=kG。
  3、用户A将Ep(a,b)和点K，G传给用户B。
  4、用户B接到信息后 ，将待传输的明文编码到Ep(a,b)上一点M（编码方法很多，这里不作讨论），并产生一个随机整数r （r<n）。
  5、用户B计算点C1=M+rK和C2 = rG
  6、用户B将C1 、C2 传给用户A。
  7、用户A接到信息后，计算C1 − kC2，结果就是点M。再对点M进行解码就可以得到明文。
  因为C1 −kC2 = M+rK-k(rG)=M+rkG-krG=M