公钥密码

公钥密码体制

一个系统中，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标准，极大地提升了我国在网络安全领域的国际标准化水平。

大纲生成的思维导图敬上