密码学系列文(4)--公钥密码

一、公钥密码概述

公钥密码体制的概念是在解决单钥密码体制中最难解决的密钥分配和数字签字问题时提出的：

• 对第一个要求，常常可用人工方式传送双方最初共享的密钥，这种方法成本很高，而且还完全依赖信使的可靠性。第二个要求则完全依赖于密钥分配中心的可靠性

• 第二个问题数字签字考虑的是如何为数字化的消息或文件提供一种类似于为书面文件手书签字的方法。

公钥密码算法的最大特点：用两个密钥将加密和解密分开。

• （1）其中一个密钥是公开的，称为公开密钥，简称公钥，用于加密；
•  （2）另一个密钥是为用户专用，因而是保密的，称为私钥，用于解密。

算法有以下重要特性：已知密码算法和加密密钥，求解密密钥在计算上是不可行的。

1.1 用于加解密

下图是公钥体制加密的框图：

• (1)接收者产生一对密钥，其中是公开密钥，是私有的密钥;
• (2)将加密密钥予以公开，则保密
• (3)要想向发送消息，则使用的公开密钥加密，表示为，其中是密文，是加密算法
• (4)B收到密文后，用自己私钥解密，表示为，其中是解密算法；
• 因为只有B知道，所有其他人无法对解密。

1.2 用于认证

公钥加密算法不仅能用于加、解密，还能用于对发方A发送的消息提供认证。

• 用户用自己的密钥对加密，表示为；
• 将发往。用的公钥对解密，表示为;
• 因为从得到是经过的密钥加密，只有才能做到。因此可当作对的数字签字；

另一方面，任何人只要得不到的秘钥就不能篡改，所以以上过程完成了对消息来源和消息完整性的认证；

缺点：在实际应用中，特别是用户数目很多时，以上认证方法需要很大的存储空间，因为每个文件都必须以明文形式存储以方便实际使用，同时还必须存储每个文件被加密后的密文形式即数字签字，以便在有争议时用来认证文件的来源和内容。

改进的方法:减小文件的数字签字的大小，将文件经过一个函数压缩成长度较小的比特串。或者采用下列方法。

1.3 用于加解密和认证

为了同时提供认证功能和保密性，可使用双重加、解密.

• 发方首先用自己的密钥对消息加密，用于提供数字签字；
• 再用收方的公钥第二次加密，表示为：
• 解密过程为：即收方先用自己的密钥再用发方的公钥对收到的密文两次解密。

1.4 公钥密码算法应满足的要求

公钥密码算法应满足以下要求：

• (1)接收方产生密钥对在计算上是容易的；
• (2)发送方用收方的公钥对消息加密产生密文，即在计算上是容易的；
• (3)收方用自己的密钥对解密，即在计算上是容易的；
• (4)敌手由的公钥求密钥在计算上是不可行的；
• (5)敌手由密文和的公钥恢复明文在计算上是不可行的；
• (6)加、解密次序可换，即;

以上要求的本质之处在于要求一个陷门单向函数。    

• 单向函数是两个集合之间的一个映射，使得中每一元素都有惟一的一个原像，且由易于计算它的像，由  计算它的原像  是不可行的。
• 称一个函数是陷门单向函数，是指该函数是易于计算的，但是求它的逆是不可行的，除非再已知某些附加信息。当附加信息给定后，求逆可在多项式时间完成。

1.5 对公钥密码体制的攻击

• 和单钥密码体制一样，如果密钥太短，公钥密码体制也易受到穷搜索攻击。因此密钥必须足够长才能抗击穷搜索攻击。密钥长度太大又会使得加解密运算太慢而不实用。
• 对公钥密码算法的第二种攻击法是寻找从公开钥计算秘密钥的方法。目前为止，对常用公钥算法还都未能够证明这种攻击是不可行的。
• 因此公钥密码体制目前主要用于密钥管理和数字签字。

二、RSA算法

2.1 算法描述

RSA算法是1978年由R. Rivest, A. Shamir和 L. Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。

2.1.1 密钥的产生

• (1)选两个保密的大素数和；
• (2)计算，其中是的欧拉函数值；
• (3)选一整数，满足，且
• (4)计算，满足;
• (5)以为公钥，为私钥

即是在模下的乘法逆元，因与互素，由模运算可知，它的乘法逆元一定存在；

2.1.2 加密

加密时首先将明文比特串分组，使得每个分组对应的十进制数小于，即分组长度小于。然后对每个明文分组，作加密运算：;

2.1.3 解密

对密文分组的解密运算为：

2.2 RSA的安全性

RSA的安全性是基于分解大整数的困难性假定，之所以为假定是因为至今还未能证明分解大整数就是 NP 问题，也许有尚未发现的多项式时间分解算法。

如果RSA的模数被成功地分解为，则立即获得，从而能够确定模的乘法逆元，即，因此攻击成功。

2.2.1 共模攻击

在实现RSA时，为方便，我们可能给每一用户相同的模数 ，虽然加解密密钥不同，然而这样做是不行的。例如：设两个用户的公开钥分别为  和   ，且  和  互素（一般情况都成立），明文消息是   ，密文分别是:

敌手截获和后，可如下恢复。用推广的Euclid算法求出满足得两个整数和，其中一个为负，设为。再次用推广的Euclid算法求出，由此得。

2.2.2 低指数攻击

假定将RSA算法同时用于多个用户(假定3个)，然而每个用户的加密指数(即公开钥)都很小。

设三个用户的模数分别为，当  时，，否则通过 有可能得出 和  的分解。设明文消息是 ，密文分别是 

由中国剩余定理可求出。由于，可直接由开立方根得到。

三、椭圆曲线密码体制

相比之下，椭圆曲线密码体制ECC（Elliptic Curve Cryptography）可用短得多的密钥获得同样的安全性，因此具有广泛的应用前景。ECC的另一个优势是可以定义群之间的双线性映射，双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。

在数学上，椭圆曲线为一代数曲线，被式子所定义，并要求判别式，即无奇点的；换句话说，其图形没有尖点或自相交，椭圆曲线的形状并不是椭圆，只是因为它能够被”椭圆函数“参数化；”椭圆曲线“则来源于求椭圆的周长；如图：

3.1 椭圆曲线

（1）实数域上的椭圆曲线

对于固定的和的值，满足形如方程、

的所有点的集合，外加一个无穷远点，其中是实数，和在实数域上取值。

（2）有限域上的椭圆曲线

对于固定的和的值，满足形如方程

的所有点的集合，外加一个零点或无穷远点，其中和均在有限域上取值，即在上取值。是素数。

（3）有限域上的椭圆曲线

对于固定的和的值，满足形如方程

的所有点的集合，外加一个零点或无穷远点。其中，上的点是位的比特串。

3.2 加法定律

3.2.1 加法定义

任意取椭圆曲线上两点(若重合，则作点的切线)作直线交于椭圆曲线上另一点，过作轴的平行线交于。则规定，如图所示：

如果对称(或重合于轴)，此时，连线于轴平行，显然与曲线没有第三个交点，规定，为它们的和，称为零点，表示此时连线在无穷远处与曲线相交，也称为无穷远点。

3.2.2 加法法则

在椭圆曲线上定义的加法实际上是点的一种运算，椭圆曲线上的点再加上零点，构成一个加法群。关于运算"+"有如下加法法则：

（1）与零元相加：对任意, 有

（2）逆元：对任意， 存在上一点，记为，使得。称为的逆元，它是椭圆曲线上点关于轴的对称点；

（3）加法交换律：对任意，有

（4）加法结合律：设，则

（5）两相异点相加：对任意，且，令,此时则有其中

（6）两相同点相加（倍乘运算）：对任意，且，令，此时，其中.

3.3 双线性对

在数学中，一个双线性映射是由两个矢量空间上的元素生成第三个矢量空间上一个元素的函数，并且该函数对每个参数都是线性的。

定义：设是由生成的循环加法群，其阶数为素数，是一个阶为的循环乘法群。双线性映射是指具有下列性质的映射：

• （1）双线性。
• 对所有的和，;
• （2）非退化。
• 存在一个，满足;
• （3）可计算。
• 对，存在一个有效的算法计算;
• 双线性映射可以由超奇异椭圆曲线中的Weil和Tate配对中得到。

3.4 椭圆曲线上的密码

在椭圆曲线构成的群上考虑方程，其中，则由和易求，但由求则是困难的，这就是椭圆曲线上的离散对数问题，可应用于公钥密码体制。

Diffie-Hellman密钥交换和ElGamal密码体制是基于有限域上离散对数问题的公钥体制，下面考虑如何用椭圆曲线来实现这两个例。

3.4.1 Diffie-Hellman密钥交换

3.4.2 ElGamal密码体制

四、SM2算法

SM2是中国国家密码管理局颁布的中国商用公钥密码标准算法，它是一组椭圆曲线密码算法，其中包含加解密算法、数字签名算法。

SM2算法与国际标准的ECC算法比较：

• (1)ECC算法通常采用NIST等国际机构建议的曲线及参数，而SM2算法的参数需要利用一定的算法产生。而由于算法中加入了用户特异性的曲线参数、基点、用户的公钥点信息，故使得SM2算法的安全性明显提高。
• (2) 在ECC算法中，用户可以选择MD5或SHA-1等国际通用的哈希算法。而SM2算法中则使用SM3哈希算法，SM3算法输出为256 比特，其安全性与SHA-256算法基本相当。

SM2算法分为基于素数域和基于二元扩域两种。本文仅介绍基于素数域的SM2算法。

4.1 密钥产生

4.2 加密算法

4.3 解密算法