公钥密码

公钥密码体制

一个系统中，n 个用户之间进行保密通信。为了确保安全性，两两用户之间的密钥不能一样。这种方式下，需要系统系统提供很多把共享密钥，密钥的数量大幅增加，随之而来的就是密钥的产生、存储、分配、管理的成本也就大幅增加，而使用公钥密码体质就可以大大减少密钥的数量，来降低密钥的管理难度。

公钥密码体制的公钥加密原理非常类似于信箱的工作原理。

公钥密码体制的公钥加密原理非常类似于信箱的工作原理。

一个信箱有两个开口，一个开头对所有人开放 就相当于公钥，寄信人通过开放的开口将信投入信箱，相当于应用公钥对信件进行加密。

邮递人员和工作人员拥有信箱的钥匙，就相当于私钥。

他们能够运用私钥打开信箱取出信件的过程相当于运用私钥进行解密。只有拥有信箱钥匙的人才能打开信箱，并取出信件，相当于只有拥有私钥的人才能解密数据。

公钥的分发不要求保密但要求真实可信，主要的公钥分发方法有：

• 公开发布：依赖于个人信誉保证公钥可信
• 公开可访问目录
• 公钥的授权
• 公钥证书

其中公开可访问目录、公钥授权、公钥证书这三种方法都依赖于第三方实体或组织保证公钥可信。

公钥密码算法的应用

• ① 密钥交换：用于通信双方交换会话密钥
• ② 加密：用于传输机密消息
• ③ 数字签名：用于身份或行为认证

公钥密码模型

加密模型

若图所示 假设，Alice 和 Bob 各拥有一对密钥 PKa，SKa，和 PKb，SKb。Bob 想发送机密消息 P 给 Alice，Bob 可以利用 Alice 的公钥 PKa 和公钥加密算法加密消息 P 得到密文 C 然后发送给 Alice。Alice 接收到密文 C 之后利用自己的私钥和相应的解密算法解密密文得到明文消息 P，如果明文 P 是 Bob 生成的私有的会话密钥，则公钥密码体制的加密模型可用于密钥交换。公钥密码的认证模型而可用于实现用户行为的认证，也就是行为的不可否认性，和身份鉴别的功能。

如图所示：

假设 Bob 想向 Alice 证明自己的身份或者行为。认证模型的整体思想被认证方通过一定的方式向认证方证明他拥有对应的私钥。而证明的方式就是 被认证方利用自己的私钥对认证的相关的消息或者摘要实行变换 S，该变换一般称为数字签名。然后认证方用被认证方的公钥进行签名验证。

混合密码模型

有一种非常广泛的对称密码和公钥密码混合使用的方法称为数字信封技术。该技术结合两种密码的优势利用对称密码比加密公钥密码效率高的特点，用对称密码加密长的数据而用公钥密码的加密模型作为安全信道向信息的目的方传递短的对称密钥。

假设消息放松方 Bob 要发送机密消息给 Alice，双发需要配置一对公钥。

其具体操作过程为：

• 1. Bob 产生临时的对称加密密钥 K，将明文消息利用对称密码算法和密钥 K 进行加密
• 2.应用非对称密码算法和 Alice 的公钥 PKa 加密密钥 K 形成数字信封，将数字信封和消息密文 E 一起发送给 Alice
• 3.Alice 收到信息后首先运用自己的私钥 SKa 解密数字信封得到对称密钥 K
• 4.利用密钥 K 解密数据得到消息明文

公钥密码算法

根据应用功能 典型公钥密码算法 如表所示

根据上表我们可以得出：

1.RSA 和 ElGamal 这两种算法可以用于所有的用途（所有是指上表中指出的三种应用）
2.Diffie-Hellman 密钥交换算法专门用于密钥交换
3.数字签名算法 DSA 和 Schnorr 算法专门用于数字签名

RSA 公钥密码算法

RSA 算法于 1977 年由 Rivest，Shamir，Adleman 一起提出，RSA 这个名字就是由这三位的名字的首字母组成的,RSA 算法也是公钥密码算法中最具代表性的算法。

RSA 是典型的非对称加密算法，该算法基于大素数分解，核心是模幂运算。

RSA 的算法分为三个部分

• 密钥生成
• 加密
• 解密

RSA 的密钥生成过程如下

① 独立的选取两个大的素数 p 和 q，计算 n=p×q 和欧拉函数 Φ(n)=(p-1)(q-1)

② 然后随机的选取整数 e，满足 1≤e＜Φ(n),gcd(Φ(n),e)=1

③ 解方程 ed ≡ 1 mod Φ(n),求 d

得出私钥 （d,n）,公钥（e,n）

RSA 的加密和解密算法非常简单。

加密：C≡m^e mod n 明文 m 的加密过程就是计算 m 的 e 次方 mod n

解密：C≡C^d mod n 计算密文 C 的 d 次方 mod n

0 < m < n

RSA 的安全性和性能

• 基于大合数的质因子分解的困难问题，如果能分解 n，则理解可得到欧拉函数 Φ(n)值，从而求出公钥 e 关于模 Φ(n)的逆元 d 也就是私钥。
• 应用中密钥长度是指整数 n 的长度，RSA-130 在 1996 年被成功分解，当前所选长度一般不低于 1024 比特，主流的选值为 1024、2048、3072、4096。。。
• 微软研究院 Svore 博士指出破解 RSA-2048（2048-bit）的密钥可能需要耗费 10 亿年的时间，而量子计算机只需要 1000 秒就可以完成。
• 对于密钥长度为 1024 比特（128 字节）的 RSA，其一次能加密的最大明文长度只有 117 字节，其中 11 字节为 padding。
• RSA 加密算法也可直接用于签名，用发送者私钥加密签名消息生成签名，接受者利用发送者公钥解密消息与原消息进行对比确认签名的正确性。
• RSA 的私钥加密计算时间长，实际对文件签名前，需要对消息做 Hash 变换，然后对输出的短的 hash 值进行签名。

Diffie-Hellman 密钥交换

• 基于有限域上的离散对数困难性；
• 有两个全局公开的参数，素数 P 和 P 的一个原根 g。

假设 Bob 想和 Alice 交换一个密钥，Bob 选定一个素数 P 和原根 g 并公开，也选定一个小于素数 P 的随机数 b，在 mod P 下计算 B=g 的 b 次方并公开。Alice 也选定一个小于素数 P 的随机数 a，在 mod p 下计算 A=g 的 a 次方并公开。离散对数困难性保证了攻击者不能根据公钥参数 A 和 B 计算出私钥 a 和 b。最后 Bob 和 Alice 各自在本地 mod P 下计算密钥 K=g 的 a 和 b。

• D-H 算法可以让通信双方在完全没有对方任何预先信息的条件下通过不安全信道创建起一个密钥

但是基本的 D-H 算法在安全性方面存在许多不足

① 没有对方发送的公钥参数和双方身份进行认证，容易受到中间人攻击；

② 它是计算密集型，容易遭受阻塞性攻击，即攻击者发起大量的密钥交换请求，浪费被攻击者的计算资源。

③ 不能抵抗重放攻击。（将子密钥交换过程中产生的消息可以重复发送）

D-H 算法的改进（Oakley 算法）

• IETF 研究出一种新的密钥交换算法 Oakley，对 D-H 密钥交换算法进行优化，克服 D-H 密钥交换算法的安全弱点：

① 加入鉴别机制抵抗中间人的攻击，支持数字签名、公钥加密和对称密钥加密三种鉴别机制，Oakley 协议可以支持 DNS 公钥，能对 IPv4，IPv6 地址和有效域名进行鉴别；

② 采用 cookie 程序机制来对抗阻塞攻击，cookie 程序是由源和目的地址、源和目的 UDP 端口以及一个本地生成的秘密值共同生成的哈希值；

③ 采用现时机制抵抗重放攻击，每次密钥交换过程双方都在本地生成一个伪随机数（现时 nonce）并加密用于应答中。因为每次每次的现时都不同，所以消息不能重用。

相对于 D-H 算法 Oakley 算法可能需要双发预先配置被认证的公钥。

如上图所示，Oakley 的秘钥交换过程中除了传递 D-H 算法的公钥参数以外，还需要传递双发的 cookie 生成 ID 以及用对方的公钥加密的现时。双发交换的身份 ID 也可以用临时的 D-H 秘钥即 a、b 次方进行加密。最后的共享秘钥的计算为 D-H 秘钥即 a、b 次方、双方现时和 cookie 合起来的一个伪随机函数值。该伪随机函数在秘钥交换过程中进行协商，比如 HMAC-MD5。

D-H 算法的其他改进

• 除了 Oakley，D-H 算法也被做不同的改进应用到不同的场景：

① 瞬时 D-H，用于创建临时密码，在交换 D-H 公钥参数时用发送者的私钥进行签名，来防止中间人攻击；

② 固定 D-H，D-H 的公钥参数包括在由签证机构颁发公钥证书中，可以多次使用。公钥证书起到鉴别用户身份防止中间人攻击的作用。

以上两种方法都被用于传输层协议 SSL 中。

D-H 算法组

根据不同的安全强度，D-H 被区分为不同的 D-H 组

• D-H 组确定了在秘钥交换过程中使用的秘钥的强度。组的编号越大安全性就越高，但是也就需要越多的时间来计算秘钥。

DH 组 1: 768 位
DH 组 2: 1024 位
DH 组 5: 1536 位

• 在实际应用中，通信双发需要事先协商所采用的 D-H 组。

ElGamal

• 1997 年 ElGamal 提出 ElGama 算法，与 D-H 算法密切相关，安全性基于有限域上的离散对数困难性。

其结构包括四个部分：

• 加密算法

① 系统初始化：系统选取公共参数包括大素数 p 以及一个本原根 g

② 秘钥生成：随机选取整数 x，1≤x≤p-2，计算 y=g 的 x 次方 (mod p),公钥为 y，私钥为 x；

③ 加密：对任意明文 m∈Z(Z 是一个整数集) ，随机选取一个秘密整数 k，1≤k≤p-2，计算 c1 = g 的 k 次方 (mod p), c2 = m 乘以 y 的 k 次方 (mod p), 密文 c = （c1,c2）;

④ 解密：计算 m=c2/(c1 的 x 次方) （mod p）

• 签名算法

EIGamal 用于签名的时候，为了提升效率，对签名算法进行了修改，系统参数的选取和秘钥的生成都没有变

① 系统初始化：系统选取公共参数包括大素数 p 以及一个本原根 g

② 秘钥生成：随机选取整数 x，1≤x≤p-2，计算 y=g 的 x 次方 (mod p),公钥为 y，私钥为 x；

③ 签名生成：对待签名的消息 m∈Z，随机选取一个秘密整数 k，1≤k≤p-2，且（k，p-1）= 1，计算 r=g 的 k 次方（mod p），s=(m- r x)/k (mod p-1) ,则（m，r，s）为对消息 m 的数字签名。

④ 签名验证：对方收到对消息 m 的数字签名（m‘，r’，s‘）后，利用签名者公开秘钥 y，g,p 可对签名进行以下验证：

如果上式成立，则接受该签名，否则拒绝该签名。

Schnorr 数字签名算法

• ElGamal 签名方案的变种，基于离散对数求解的困难性，将生成签名所需的消息计算量最小化

• 算法

① 系统公共参数选取：素数 p（一般 1024 位）和 q（一般 160 位），q 是 p-1 的素因子，选取整数 g，满足 gq ≡ 1 (mod p) ,公共参数为 （p，q，g）

② 密钥生成：选取随机整数 s，0 < s < q ，作为私钥；公钥为

③ 签名生成：选择随机整数 r，0 < r < q,计算 x=g 的 r 次方 （mod p），对待签名消息 m，计算 e=H（m||x），y=(r+se) (mod p),得到签名为（e，y）

④ 签名验证：收到签名（e’，y‘）之后，验证等式
是否成立

数字签名算法 DSA

• 1991 年 8 月 美国国家标准局（NIST）公布了数字签名标准（Digital Signature Standard，DSS），此标准采用的算法为数字签名算法（Digital Signature Algorithm,DSA）

• 它是 ElGamal 和 Schnorr 签名算法的变种，采用了 Schnorr 系统中，g 为非本原元的做法，以降低其签名文件的长度。

值得注意的是 DSA 和 Schnorr 算法的签名都针对消息的 hash 值，这使得签名同时具有消息完整性验证的功能。

椭圆曲线密码 ECC

• 椭圆曲线密码(Elliptic curve cryptography,ECC),在椭圆曲线上建立公钥密码算法，在 1985 年由 Neal Koblitz 和 Victor Miller 分别独立提出的；

• ECC 的主要优势是在同样的安全强度下，其可以比其他的方法使用更小的秘钥，如模数长度为 1024 位的 RSA 和 ElGamal 的安全强度约等于 160 位模数的 ECC

• ECC 的安全性都依赖于有限域上椭圆曲线离散对数困难问题

• 相比于公钥密钥算法 RSA、ElGamal 等定义在有限域乘法群上，ECC 则定义在有限域假发群上；（椭圆曲线上的加法对应乘法群的乘法，椭圆曲线的数乘对应乘法群的幂运算，一般认为有限域乘法群上的离散对数问题和椭圆曲线上的离散对数问题并不等价，椭圆曲线上的离散对数问题要困难的多）

• ECC 中最流行的有限域是以素数为模的整数域 GF(p)和特征为 2 的伽罗瓦域 GF（2^m）,前者通常在通用处理器上更有效，后者在专门的硬件实现上计算更为有效

• ECC 可用于密钥交换、加解密和数字签名。

中国的 ECC 标准

• 我国的密码标准 SM2 （GM/T 0003-2012）和 SM9 （GM/T 0044-2016）算法是椭圆曲线密码机制，其推荐了一条 256 位的曲线作为标准曲线。

• SM2 标准包括总则，数字签名算法，密钥交换协议，公钥加密算法四个部分。

• SM9 是基于双线性对的标识密码算法，也包含四个部分：总则，数字签名算法，密钥交换协议以及密钥封装机制和公钥加密算法。

• 可以实现基于身份的密码体制，可以将用户的身份标识如手机号码、邮件地址等作为公钥，不需要申请数字证书，适用互联网的各种新兴应用的安全保障。

密码服务
电子邮件安全
智能终端保护
物联网安全
云存储安全
...

• 2017 年 11 月，第 55 次 ISO/IDC 信息安全分技术委员会（SC27）会议上，我国 SM2 与 SM9 数字签名算法一致通过为国际标准。
• 这是我国商用密码标准首次正式进入 ISO/IEC 标准，极大地提升了我国在网络安全领域的国际标准化水平。

大纲生成的思维导图敬上