信息安全概述-第三章-3.5公钥密码体制

信息安全工程师----第三章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-1mod3220=1019mod3220。公开e=79和n=3337，保密p=47，q=71，d=1019和φ(n)=3220。

设明文M=6882326879666683，进行分组，M1=688,M2=232，M3=687,M4=966,M5=668,M6=003。M1的密文C1=68879mod3337=1570，继续进行类似计算，可得最终密文

C=15702756209122762423158。

如若解密，计算M1=15701019mod3337=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算法如下：密钥产生

任选一个大素数p，使得p-1有大素因子，g是模p的一个本原根，公开p与g。

使用者任选一私钥x，x∈[0,p-1]

计算公钥y=gxmodp

公开公钥：y,p,g

保密私钥：x加密过程

对于明文m，选取一个r，r∈[0,p-1]

计算c1=grmodp

c2=m*yrmodp

则密文为{c1,c2}解密过程

先计算w=(c1x)-1mpdp

再计算出明文m=c2*wmodp签名过程

假设对消息m签名，任选一个随机数k，使k∈[0,p-1]

计算r=gkmodp

s=k-1(m-x_r)mod(p-1)

签名为{r,s}

(5)签名验证过程

yr_rs=gm(modp)

需要说明的是，为了避免选择密文攻击，ElGamal是对消息m的hash值进行签名，而不是对m签名与RSA方法比较，ElGamal方法具有以下优点：系统不需要保存秘密参数，所有的系统参数均可公开同一个明文在不同的时间由相同加密者加密会产生不同的密文，但ElGamal方法的计算复杂度比RSA方法要大。更为细致做法如下：随机地选择一个大素数p，且要求p-1有大素数因子。再选择一个模p的本原元α。将p和α公开。1.密钥生成

用户随机地选择一个整数d作为自己的秘密的解密钥，1≤d≤p-1，计算y=αdmodp，取y为自己的公开的加密钥。

由公开钥y计算秘密钥d，必须求解离散对数，而这是极困难的。2.加密

将明文消息M(0≤M≤p-1)加密成密文的过程如下：①随机地选取一个整数k，1≤k≤p-1。②计算U=ykmodp（2-46）C1=akmodp（2-47）C2=UMmodp（2-48）③取(C1，C2)作为的密文。3.解密

将密文(C1，C2)解密的过程如下：①计算V=C1dmodp（2-49）②计算M=C2V-1modp（2-50）解密的可还原性可证明如下：

因为，C2V-1modp=(UM)V-1modp=UM(C1d)-1modp=UM((αk)d)-1modp=UM((αd)k)-1modp=UM((y)k)-1modp=UM(U)-1modp=Mmodp故解密可还原。例2-3设p=2579，取α=2，秘密钥d=765，计算出公开钥y=2765mod2579=949。再取明文M=1299，随机数k=853，则C1=853mod2579=435，C2=1299x949835mod2579=2396，所以密文为(C1，C2)=(435，2396)。解密时计算

M=2396x(435765)-1mod2579=1299

从而还原出明文。椭圆曲线密码人们对椭圆曲线的研究已有100多年的历史，而椭圆曲线密码ECC(EllipticCurveCryptosysytem)是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的阶（nG=O∞），k为小于n的整数。则给定k和G，根据加法法则，计算K很容易但反过来，给定K和G，求k就非常困难。因为实际使用中的ECC原则上把p取得相当大，n也相当大，要把n个解点逐一算出来列成上表是不可能的。这就是椭圆曲线加密算法的数学依据。点G称为基点（basepoint）k(k<n)为私有密钥（privatekey）K为公开密钥（publickey)

下面是利用椭圆曲线进行加密通信的过程：1、用户A选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。

2、用户A选择一个私有密钥k，并生成公开密钥K=kG。

3、用户A将Ep(a