《密码编码学与网络安全原理与实践》第九章 第十章 公钥密码学与密钥管理

第九章 公钥密码学与RSA

原则上不能说传统密码优于公钥密码，也不能说公钥密码优于传统密码

公钥密码学仅限于用在密钥管理和签名这类应用中

与密钥分配中心的会话过程既不比传统密码中的那些过程更简单，也不比之更有效

动机：简化密钥分配和管理、实现签名等功能

不对称性是公钥最为重要的性质，可以用来保证“真实”性，“不可否认”性

术语：

非对称密钥：两个密钥：公钥和私钥，用来实现互补运算，即加密和解密，或者生成签名与验证签名；

公钥证书：认证机构将用户的姓名和公钥绑定在一起，用户用自己的私钥对数字文件签名后，可以通过证书识别签名者，因为签名者是唯一拥有与证书上对应的私钥的用户

公钥密码算法：含有两个密钥：公钥和私钥。从公钥中推出私钥在计算上是不可行的

公钥基础设施：由一系列的协议、服务平台、软件和工作站组成，用于管理证书和公钥-私钥对，并产生、维护和废除公钥证书

公钥密码体制特点：

仅根据密码算法和加密密钥来确定解密密钥在计算上是不可行的；

两个密钥中的任何一个都可用来加密，另一个用来解密

公钥体制的应用：

加密/解密、数字签名、密钥交换

（先签名后加密）

对公钥密码的要求：

1）B产生一对密钥在计算上是容易的；

2）已知公钥和要加密的信息M，发送方A产生相应的密文在计算上是容易的；

3）接收方B使用其私钥对接收的密文解密以恢复明文在计算上是容易的；

4）已知公钥时，攻击者要确定私钥在计算上是不可行的；

5）已知公钥和密文，攻击者要恢复明文M在计算上是不可行的；

6）加密和解密函数的顺序可以交换；

数学问题

公钥算法是基于数学函数而不是基于替换和置换，公钥密码是非对称的（应基于单项陷门函数）

区分单向函数和单向Hash函数：
单向函数：每个函数值都存在唯一的逆，并且计算函数值是容易的，但是求逆却是不可行的；

单向Hash函数：输入可以是任意长度的数据，其输出是定长的，用于消息认证；

单向陷门函数：一个函数，若计算函数值很容易，并且在缺少一些附加信息时计算函数的逆是不可行的，但是已知这些附加信息时，可在多项式时间内计算出函数的逆，那么称这样的函数为单向陷门函数。

寻找合适的单向陷门函数是公钥密码体制应用的关键。

困难问题

困难问题具有客观性：P-问题、NP-问题、NP完备问题

离散对数问题(DLP)

设$p$是素数，$b\in N$（特别地b=2）

函数：$f(x)=bx\mathrm{mod}p$（离散指数函数）；逆函数：$y=lo{g}_{b}x$（离散对数函数）

求解算法：常规算法、Giant-Step-Baby-Step算法、Index Calculus算法

就目前计算机而言这是无法完成的

公钥密码分析

公钥密码易受穷举攻击，其解决方法也是使用长密钥，但为了方便密钥又必须足够短，所以公钥密码目前仅限于密钥管理和签名中。

公钥密码易受已知密钥长度的穷举消息攻击，解决方法是在发送的消息后附加一个随机数。

RSA密码体制

Diffie和Hellman开创性的论文为密码学提出了挑战，并指明新的方向

Rivest, Shamir和Adleman提出的RSA公钥算法则第一次将公钥密码由理想变为现实

该算法的数学基础是初等数论中的Euler定理，并建立在大整数分解的困难性之上。

RSA体系是一种分组密码，其明文和密文均是0至某n-1之间的整数。

RSA密码体制描述如下：

明文空间$M＝$密文空间 C = Z n = { 0 , 1 , … , n − 1 } C= Z_n =\{0,1,…,n-1\} C=Zn​={0,1,…,n−1}，即分组是$lo{g}_{2}n$ 比特

密钥的生成：选择不同的素数$p,q$，计算$n=pq,\phi (n)=(p-1)(q-1)$，

选择整数$e$使$gcd(\phi (n),e)=1$, 其中$1<e<\phi (n)$,计算$d$，使$d\equiv e^{-1}\mathrm{mod}\phi (n)$

公开参数：大模数$n$，公钥$e$

秘密参数：大素数$p,q$，私钥$d$

加密：$c=m^e\mathrm{mod}n$

解密：$m=c^d\mathrm{mod}n$

（可以用中国剩余定理加快解密的运算速度）

RSA密码分析

攻破RSA与分解n是多项式等价的。然而，这个猜想至今没有给出可信的证明

针对RSA的攻击非常丰富：数学攻击、物理攻击、基于运行错误的攻击、基于系统使用错误的攻击。。。。。。

p、q相似（参数选取不当）：

在选择$p，q$时，应注意：应该是随机素数并且不包含在素数表中、两个素数不应该太接近；

对于前两点：因为$n=p\ast q=(p+q{)}^2/4-(p-q{)}^2/4$，当$(p-q)/2$ 很小时，那么$(p+q)/2$ 只比$\surd n$稍大一点，那么逐个检查大于$\surd n$的整数$x$，直到找到一个使得$x^2-n$ 是一个平方数，记作$y^2$，那么就有$p=x+y$和$q=x-y$.

解决方法：选择$p$和$q$使其二进制位表示的长度有几比特不同。

共模攻击：

指通信系统中使用相同的$n$，且存在两个用户的公钥$e_1$和$e_2$是互素的，则可以由这两个用户对同一条明文的不同加密结果，恢复出原始明文

攻击方法：

设$c_1\equiv m^{e_1}\mathrm{mod}n,c_2\equiv m^{e_2}\mathrm{mod}n$，攻击者知道$e_1,e_2,n,c_1,c_2$

根据中国剩余定理推论：存在$s,t$使$t\times e_1+s\times e_2=1$ (注意是相等)，则$c_1^t\times c_2^s=m\mathrm{mod}n$

结论：不能用同一个n来生成密钥

小e攻击：（广播攻击）

指$e$很小时，若使用广播加密（即利用同一个$e$对同一个消息$m$加密再分发给多个人）下遭遇的攻击

设$e=3$，攻击方法如下：有三个成员的公钥$e$均为3,但他们彼此的$n$不同,记为$n_1，n_2，n_3$

$c_1\equiv m^3\mathrm{mod}{n}_1,c_2\equiv m^3\mathrm{mod}{n}_2,c_3\equiv m^3\mathrm{mod}{n}_3$

因为$n_1,n_2,n_3$一般是互素的 （否则。。），因此由中国剩余定理可得：

$C\equiv m^3\mathrm{mod}{n}_1\times n_2\times n_3$

又因为$m<n_1,n_2,n_3$；所以可得$m^3<n_1\times n_2\times n_3$，则m为C开三次方

解决方法：给每一个待加密的消息M填充一个唯一的伪随机位串可以阻止这种攻击；

计时攻击：

思想：利用指数中某一位为0或者为1时，硬件加密速度不同

解决方法：不变的幂运算时间：保证所有幂运算中返回结果前执行的时间相同、随机延时、隐蔽：在密文上乘以随机数

模数攻击

通过收集信息查看公钥是否存在复用问题

存在很多产生安全素数的方法

但在实际应用，常常使用没有新鲜信息的“低熵”种子，导致问题

例如：同一随机数发生器在第一次运行时总是输出同一个素数、第二次运行时输出不同的素数、出现公共素因子

可能可以解释深度为1的树的出现，不能解释其他情况

第十章 密钥管理和其他公钥密码体制

Diffie-Hellman密钥协商

算法的目的是使两个用户能安全地交换密钥

是公钥体制的思想来源，但其本身不是公钥加密算法,是基于公钥的密钥分配算法(不可以被用于加密、而是用于建立一对密钥、仅交互双方知道密钥)

密钥的值依赖于双方参与者的公开信息和私有信息

安全性依赖于离散对数问题的困难性

步骤

首先定义素数$p$的本原根（素数$p$的本原根是一个整数，且其幂可以产生$1$到$p-1$之间所有整数）

初始化：用户得到全局参数：大素数$p$、模$p$的原根$g$

各个用户生成各自的公私钥对，选择私钥：正整数 $x<p$，计算公钥：$y\equiv g^x\mathrm{mod}p$

各个用户公开自己的公钥，然后进行密钥交换：

适用于参与者为2个的情形（双方密钥交换），假设参与者为Alice和Bob

Alice用自己的私钥和Bob的公钥计算$K_A\equiv y_B^{x_A}\mathrm{mod}p$

Bob用自己的私钥和Alice的公钥计算$K_B\equiv y_A^{x_B}\mathrm{mod}p$

则有$K_A=(g^{x_A}{)}^{x_B}\mathrm{mod}p=K_B$

所得到的K作为Alice和Bob的会话密钥，用于私钥加密算法

除非Alice和Bob更新自己的公钥，则Alice和Bob的会话密钥保持不变

全局量存于某中心目录中，若该中心目录是可信的，则这种形式的通信既可以保证保密性由可以保证真实性。但不能抗重播攻击和中间人攻击。

最典型的攻击：中间人攻击（Man in the middle attack），因为没有身份认证

解决方法：数字签名/公钥证书

ElGamal公钥算法

由T. ElGamal提出，基于离散对数公开密钥体制

系统用户共同选择一个素数$q$，取$q$的原根$a$

用户A生成的密钥对如下：

随机生成$X_A$，使得$1<X_A<q-1$。计算$Y_A=a^{X_A}\mathrm{mod}p$。

A的私钥为$X_A$，公开密钥为$q,a,Y_A$。

任何用户B通过A的公开密钥可以加密信息：

将信息表示为一个整数$M$，其中$1\le M\le q-1$，以分组密码序列的方式来发送信息，其中每个分块的长度不小于整数$q$。选择任意整数$k$，使得$1\le k\le q-1$

计算一次密钥$K=Y_A^K\mathrm{mod}q$；将M加密成明文对$(C_1,C_2)$

其中，$C_1=a^k\mathrm{mod}q;C_2=KM\mathrm{mod}q$。

用户A恢复明文：

通过计算$K=C_1^{X_A}\mathrm{mod}q$恢复密钥，计算$M=C_2{K}^{-1}\mathrm{mod}q$。

椭圆曲线公钥算法

可以用较短的参数长度实现同样的安全级别，属于基于离散对数问题的公钥加密体制

动因：ElGamal类公钥基于循环群 ；需要一个与GF(q)差异较大的循环群，这样已知关于GF(q)的离散对数算法不适用

椭圆曲线(Elliptic Curve)：

代数几何曲线，满足：形如$E(x,y):y^2=x^3+ax+b$且$4a^3+27b^2\ne 0$，外加无穷远点$O$

可以证明$E(x,y)$结合所定义的加法构成一个“加群”

困难问题：给定点$P$，从倍点$kP$求$k$。

定义在$Z_p$上的素曲线（模$p$运算）$y^2\equiv x^3+ax+b$

（建议软件应用，$x,y,a,b$均在$Z_p$中取值）

$GF(2^m)$上的二元曲线$y^2+xy\equiv x^3+ax+b$

（$GF(2^m)$中运算，建议硬件应用，$x,y,a,b$均在$GF(2^m)$上取值)

设$a,b$为实数，方程$y^2=x^3+ax+b$的所有实数解(x，y)组成的集合E，加上一个无穷远点$O$，组成了一个椭圆曲线。此外，要求$4a^3+27b^2\ne 0$ ，确保方程的三个解是不同的，所得的椭圆曲线称为非奇异椭圆曲线。

实数域上的椭圆曲线

方程：$y^2=x^3+ax+b$外加无穷点或零点的元素$O$，曲线关于$y=0$对称

加法的几何描述：

参数需要满足条件：$4a^3+27b^2\ne 0$，则可基于集合$E(a,b)$定义一个群。

规则：若椭圆曲线上的三个点同在一条直线上，则它们的和为$O$；$O$是加法的单位元；点$P$的负元是具有相同$x$坐标和相反$y$坐标的点；$P+Q$为直线与曲线第三个交点的相对于$x$轴的镜像；求$2Q$需要画切线取另一交点；

加法的代数描述：

$P=(x_P,y_P),Q=(x_Q,y_Q)$，连接它们的曲线$l$的斜率$\Delta =(y_Q-y_P)/(x_Q,x_P)$

公式1：$P+Q=R=(x_R,y_R)=({\Delta }^2-x_P-x_Q,-y_P+\Delta (x_P-x_R))$

公式2：$P+P=2P=R=(x_R,y_R)=({\left(\frac{3x_p^2+a}{2y_P}\right)}^2-2x_P,\left(\frac{3x_P^2+a}{2y_P}\right)(x_p-x_R)-y_p)(y_P\ne 0)$

$GF(p)$上的椭圆曲线

与实数域一样，只是计算需要模p，点的个数是p个

计算并没有几何意义，代数运算与实数域一样

$GF(2^m)$ 上的椭圆曲线

方程：$y^2+xy=x^3+a{x}^2+b$，要$b$为$0$则可基于集合$E_{2^m}(a,b)$定义一个有限阿贝尔群。

规则：$P+O=P$；若$P=(x_p,y_P)$，则$P+(x_p,x_p+y_P)=O$。点$(x_P,x_P+y_P)$是P的负元;

公式1：若$P=(x_P,y_P);Q=(x_Q,y_Q)$，且$P\ne -Q;P\ne Q$，则$P+Q=R=(x_R,y_R)=({\lambda }^2+\lambda +x_P+x_Q+a,\lambda (x_P+x_R)+x_R+y_P)$，其中$\lambda =\frac{y_Q+y_P}{x_Q+x_P}$;

公式2：$P+P=2P=R=(x_R,y_R)=({\lambda }^2+\lambda +a,x_P^2+(\lambda +1)x_R)$其中$\lambda =x_P+\frac{y_P}{x_P}$。

椭圆曲线密钥交换

用椭圆曲线实现Diffie-Hellman密钥交换，基于有限域$GF(p)$

椭圆曲线加解密：

用椭圆曲线实现ElGamal加解密–ECC

必须将要发送的消息明文m编码为形为$(x,y)$的点$P_m$

参数选择：点$G$和曲线$E_q(a,b)$

A选取私钥$n_A$,公钥为$P_A=n_A\ast G$;相应的B选取私钥$n_B$,公钥为$P_B=n_B\ast G$;

A发送消息$P_m$之前要选取一个随机正整数$k$，计算密文$C_m=kG,P_m+k{P}_B$

B接受到密文之后已知$kG$和$(P_m+k{P}_B)$要求出$P_m=(P_m+k{P}_B)-n_B\ast (kG)$。

安全性分析

ECC的安全性是建立在由$kP$和$P$确定$k$的困难程度之上的，这个问题成为椭圆曲线对数问题。

Pollard rho方法是已知的求椭圆曲线对数的最快方法。

与RSA相比ECC使用的密钥更短，所需计算量更少。

密钥长度1024位的RSA安全性相当于密钥长度160位的ECC；

密钥长度2048位的RSA安全性相当于密钥长度224位的ECC；

基于非对称密码的伪随机数生成器

基于RSA的PRNG

除了RSA的参数选择外，$N=[lo{g}_{2}n]+1$(n的位长度)，选择r,k使得r+k=N;

种子需要选择位长度为r的随机种子；生成一个长为k*n的随机序列，输出$z_1||z_2||\dots \dots ||z_m$。

参数遵循要求：(除rsa相关)，$re\ge 2N$确保求幂运算是有取模过程；$r\ge 2$防止密码攻击；k,r是8的倍数，应用方便；$k\ge 8,r+k=N$所有位都有效。

基于ECC的PRNG

同等安全的条件下，相应密码体制的密钥长度比较

商密算法中的公钥密码

SM2、SM9
传送门

相关题目

答案仅供参考