Cryptography

Table of Contents

1 密码学

密码学中,有两类密码体制:“对称密钥密码体制”和“公钥密码体制”。
对称密钥密码体制使用同一个密钥进行加密和解密。而公钥密码体制的加密密钥和解密密码是不同的。

2 对称密钥密码体制

对称密钥密码体制使用“同一个密钥”进行加密和解密。
Kerckhoff’s principle告诉我们,依赖于不公开算法进行加密解密的方法都不可靠。

Kerckhoff’s principle: All algorithms must be public; only the keys are secret.

用对称密钥密码体制进行加密和解密的过程如图 1 (图片摘自:https://technet.microsoft.com/en-us/library/cc962028.aspx) 所示。

cryptography_symmetric_key.gif

Figure 1: Encryption and Decryption with a Symmetric Key

一些常见的对称密钥算法如表 1 所示(摘自:Computer Networks, by A Tanenbaum, 5th, 8.2.4 Other Ciphers)。

Table 1: Encryption and Decryption with a Symmetric Key
Cipher Author Key length Comments
DES IBM 56 bits Too weak to use now
RC4 Ronald Rivest 1-2048 bits Caution: some keys are weak
RC5 Ronald Rivest 128-256 bits Good, but patented
AES (Rijndael) Daemen and Rijmen 128-256 bits Best choice
Serpent Anderson, Biham, Knudsen 128-256 bits Very strong
Triple DES IBM 168 bits Good, but getting old
Twofish Bruce Schneier 128-256 bits Very strong; widely used

3 公钥密码体制

对称密钥密码体制有一个重要的问题是:加密解密都需要这个密钥,所以不能把密钥藏起来,必须把密钥分发给系统中的所有人,这很难保证密钥的安全(密钥容易泄露给系统外的人)。

1976年Diffie和Hellman在他们的文章“New Directions in Cryptography”中提出了一个新想法:在发送端和接收端之间不传递密钥也可以完成解密,这对密码学产生了深远的影响。

Diffie和Hellman使人们意识到:加密密钥和解密密钥可以不同。1977年Rivest, Adi Shamir和Leonard Adleman提出了第一个公钥密码算法,即RSA算法

说明:Rivest, Adi Shamir和Leonard Adleman获得了2002年的图灵奖。(补充:Diffie和Hellman获得了2015年的图灵奖。)

在公钥密码体制中,每个参与者都有两个密钥:公钥和私钥。公钥是公开的,私钥则只有自己知道。用户B给用户A发送消息时,首先用户B使用用户A的公钥对消息进行加密,用户A收到密文后用自己的私钥对密文进行解密。利用公钥密码系统进行加密和解密的过程如图 2 (图片摘自https://technet.microsoft.com/en-us/library/cc962028.aspx) 所示。

cryptography_asymmetric_keys.gif

Figure 2: Encryption and Decryption with Asymmetric Keys

3.1 RSA算法

3.1.1 RSA算法描述(不证明)

RSA算法的描述分为两个部分:如何生成公钥和私钥,如何进行加密及解密。

RSA算法生成公钥和私钥的方法如下:
(1) 选择两个随机大素数 \(p\) 和 \(q\) ( \(p\) 和 \(q\) 是保密的,生成完公钥和私钥后就销毁)
(2) 计算大素数 \(p\) 和 \(q\) 的乘积 \(n=p \times q\) ( \(n\) 是公开的)
(3) 计算 \(z = (p-1) \times (q-1)\) ( \(z\) 是保密的,生成完公钥和私钥后就销毁)
(4) 随机选择整数 \(e\) ,满足 \(\text{gcd}(e, z) =1\) ,即 \(e,z\) 互素( \(e\) 是公开的)。
(5) 计算 \(d\) ,满足 \(d \times e = 1 (\bmod z)\) ( \(d\) 是保密的)
完成上面步骤后, \((e,n)\) 就是公钥,而 \((d,n)\) 是私钥。

RSA算法的加密及解密过程如下:
(1) 假设明文为 \(P\) ,则其对应的密文 \(C\) 的计算方法(使用公钥进行加密的过程)为: \(C = P^e (\bmod n)\)
(2) 假设密文为 \(C\) ,则其对应的明文 \(P\) 的计算方法(使用私钥进行解密的过程)为: \(P = C^d (\bmod n)\)

注意:
使用RSA算法时,明文 \(P\) 对应数字必须要小于模数 \(n\) ,否则解密会出错。用一个简单的例子来说明原因。假设 \(e=d=1\) ,则加密过程为 \(C=P (\bmod n)\) ,解密过程为 \(P' = C (\bmod n)\) ,当 \(P \ge n\) 时,容易验证 \(P'\) 和 \(P\) 不相同,解密失败,从而明文 \(P\) 对应数字必须小于模数 \(n\) 。

3.1.2 RSA算法实例

3 是用RSA算法对明文“SUZANNE”进行加密和解密的演示实例。
在这个例子中,选择素数 \(p=3,q=11\) ,从而 \(n=3 \times 11=33, z = 2 \times 10=20\) ,可以选择 \(e=3\) (因为3和20是互素的,所以满足要求),从方程 \(d \times 3 = 1 (\bmod 20)\) 中,求解得出 \(d=7\) 。所以,加密过程为 \(C=P^3 (\bmod 33)\) ,解密过程为 \(P = C^7 (\bmod 33)\)

cryptography_RSA_example.png

Figure 3: An example of the RSA algorithm

说明:在上面例子中,除了对单个字母进行分别加密外,还可以把“SUZANNE”作为整体转换为一个数字后,运行一次RSA算法进行加密(不过这时要求选择一个更大的 \(n\) ,因为RSA算法要求模数 \(n\) 必须大于明文)。

参考:Computer Networks, by A Tanenbaum, 5th, 8.3.1 RSA

3.2 其它公钥密码算法

除RSA外,还有其它一些公钥密码算法,如:EIGamalElliptic curve cryptography (ECC)

3.2.1 椭圆曲线密码学(ECC)

ECC (Elliptic Curves Cryptography)是另一种著名的公钥密码算法,它由1985年由Neal Koblitz和Victor S. Miller提出。

和RSA公钥密码算法相比,ECC具有下面优点:
1、在相同安全性级别下,ECC的public key的长度更短。For example, a 256-bit elliptic curve public key should provide comparable security to a 3072-bit RSA public key.
2、加解密速度更快,占用的CPU和内存资源更少。

参考:
ECC加密算法入门介绍:https://www.pediy.com/kssd/pediy06/pediy6014.htm
Elliptic Curve Cryptography (ECC) Certificates Performance Analysis

3.3 公钥的分配

假设用户Alice要和Bob进行加密通信,Alice怎么得到Bob的公钥呢?Bob可以把他的公钥放到他的网站主页上,Alice下载即可。但是,这是不可靠的。Alice访问Bob的主页时,黑客Trudy可能拦截Alice的请求,并把Bob的公钥(设为 \(E_B\) )替换为他自已的公钥(设为 \(E_T\) ),Alice得到的是Trudy的公钥(但她不知道)。

Alice发送消息给Bob时,用公钥(Trudy的公钥)加密后发送出去,被Trudy拦截,Trudy利用自已的私钥解密了消息(甚至解密后还可以修改消息),并用Bob的公钥重新加密发送给Bob。整个过程Alice和Bob是不知情的。具体过程如图 4 所示。

cryptography_subvert_public_key.png

Figure 4: A way for Trudy to subvert public-key encryption

所以,Bob把他的公钥放在他主页上让别人下载的做法是不安全的。

那怎么办呢?一个作法是把公钥放到一个安全的Key Distribution Center (KDC, 注:KDC常常用于“对称密钥算法”中密钥的分配)中,需要时就去下载,但是KDC必须24小时在线,而且可能成为瓶颈。

人们想到了另外的办法,克服Key Distribution Center需要随时24小时在线并可能成为瓶颈的缺点。这就是用证书(Certificates)证明公钥属于某个人或组织,请看下文介绍。

参考:Computer Networks, by A Tanenbaum, 5th, 8.5 Management of Public Keys

3.3.1 证书(Certificates)

证书(Certificates)可以证明公钥属于某个人或组织。能够证明公钥属于某个人或组织的机构称为CA (Certification Authority)。

还是以前面的场景作例子。Bob为了使别人知道和他通信是安全的,他首先把它的公钥提交给CA(很可能要交付一定的费用),CA给他颁发一个证书,证明这个公钥确实属于Bob。证书用CA的私钥进行了数字签名(后文将介绍数字签名),别人无法伪造。证书的大概内容如图 5 所示。

cryptography_certificate.png

Figure 5: A possible certificate and its signed hash

Alice想和Bob通信,首先从Bob主页上下载得到了Bob的公钥及公钥的证书。(如果这个过程被Trudy拦截,Trudy把Bob的公钥及公钥的证书换成了自己的公钥及自己公钥的证书,Alice打开证书时就可以发现证书中公显示公钥是Trudy的,而不是Bob的!证书有CA的签名,Trudy无法伪造证书。)

Alice确认Bob的公钥及其证书后,利用Bob的公钥进行消息加密,就可以向Bob发送加密信息了。

3.3.1.1 证书格式(X.509)

如果每个CA采用不同的证书格式,则管理起来比较麻烦。一般地,大家都使用 X.509 作为证书格式的标准。

Table 2: The basic fields of an X.509 certificate
Field Meaning
Version Which version of X.509
Serial number This number plus the CA’s name uniquely identifies the certificate
Signature algorithm The algorithm used to sign the certificate
Issuer X.500 name of the CA
Validity period The starting and ending times of the validity period
Subject name The entity whose key is being certified
Public key The subject’s public key and the ID of the algorithm using it
Issuer ID An optional ID uniquely identifying the certificate’s issuer
Subject ID An optional ID uniquely identifying the certificate’s subject
Extensions Many extensions have been defined
Signature The certificate’s signature (signed by the CA’s private key)
3.3.1.2 Public Key Infrastructures (PKI)

还有一些其它问题需要解决,如CA的一些操作规范,如何废止证书等等。这一系列其他问题都在公钥基础设施(Public Key Infrastructures, PKI)中有规范。

3.4 公钥密码体制 VS. 对称密钥密码体制

公钥密码算法一般比对称密钥密码算法慢好几个数量级。 一般公钥密码算法用于密钥(对称密钥算法所使用的key称为密钥)管理和数字签名等任务。公钥密码体制并没有取代对称密钥密码体制。它们将长期并存。

4 数字签名(Digital Signatures)

书信或文件可以根据亲笔签名或印章来证明其真实性。电子消息怎么实现这一点呢?这是“数字签名”所要完成的任务。
一般地,数字签名要满足下面三个要求:
(1) The receiver can verify the claimed identity of the sender.
(2) The sender cannot later repudiate the contents of the message.
(3) The receiver cannot possibly have concocted the message himself.

有两类主要的数字签名技术——RSA Digital Signature Process和Digital Signature Algorithm (DSA)。

4.1 RSA Digital Signature Process

用RSA算法进行数字签名的过程如图 6 (图片摘自:https://technet.microsoft.com/en-us/library/cc962021.aspx) 所示。

cryptography_RSA_digital_signature.gif

Figure 6: Basic RSA Data Security Digital Signature Process

说明1:图示中Originator用自己的私钥对消息摘要进行加密的过程就是“签名过程”。私钥怎么可以用来加密呢(前面介绍过的都是用别人公钥进行加密,用自己私钥进行解密)?RSA算法的加密操作步骤和解密操作步骤是一样的(只是使用的密钥不同),所以你不用关心到底叫“加密”还是“解密”,只需关心用“公钥”还是“私钥”处理数据。正常的加密解密过程是“先使用公钥操作数据,再使用私钥操作数据”(即D(E(P))=P)。RSA算法还有一个特性就是“先使用私钥操作数据,再使用公钥操作数据”也可以得到原始数据(E(D(P))=P),用RSA进行数字签名正是利用了RSA的这个特性。
说明2:图示中,对消息本身是没有加密的,如果有需求可以进行额外的加密操作。即有数字签名,又有加密过程的示意图如图 7 所示。

cryptography_digital_signature_public_key.png

Figure 7: Digital signatures using public-key cryptography(Alice用自已私钥处理数据的过程就是“签名”)

4.2 Digital Signature Algorithm (DSA)

Digital Signature Algorithm (DSA)是另一种广泛使用的数字签名技术(它并不是一个加密解密算法),这里不介绍它。

5 Secret Key Exchange(密钥交换)

目前,公钥密码算法的处理速度远远慢于对称密钥算法。当使用对称密钥算法用作网络通信时,一个重要的问题是如何传输或者约定一个密钥?这称为Secret Key Exchange。通常有两种方法:
(1) RSA key exchange process
(2) Diffie-Hellman Key Agreement algorithm

参考:https://technet.microsoft.com/en-us/library/cc962035.aspx

5.1 RSA Key Exchange Process

用RSA算法(当然使用其它公钥密码算法也行)传输密钥的过程如图 8(图片摘自:https://technet.microsoft.com/en-us/library/cc962035.aspx) 所示。

cryptography_RSA_key_exchange.gif

Figure 8: Basic RSA Key Exchange

5.2 Diffie-Hellman Key Agreement algorithm

Diffie–Hellman key exchange (D–H) 算法可以使通信双方通过一定方式生成一个相同密钥。其基本流程如图 9 (图片摘自:https://technet.microsoft.com/en-us/library/cc962035.aspx) 所示。

cryptography_Diffie_Hellman_key_agreement.gif

Figure 9: Diffie-Hellman Key Agreement

10 (图片摘自https://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange) 是Diffie-Hellman Key Agreement算法的另一个图示。

cryptography_Diffie_Hellman_Key_Exchange.png

Figure 10: Illustration of the Diffie–Hellman Key Exchange

说明: Diffie-Hellman Key Agreement algorithm并没有传输密钥本身,它是通过一定方式让通信双方生成一个相同密钥。

5.3 Secret Key Exchange应用

Secret Key Exchange相关算法在SSH1和SSH2中广泛使用。SSH2避免了RSA的专利问题(专利现在已经过时),采用Diffie-Hellman算法代替RSA来完成对称密钥的交换。
参考:http://docstore.mik.ua/orelly/networking_2ndEd/ssh/ch03_09.htm

For protocol 2, forward security is provided through a Diffie-Hellman key agreement. This key agreement results in a shared session key. The rest of the session is encrypted using a symmetric cipher, currently 128-bit AES, Blowfish, 3DES, CAST128, Arcfour, 192-bit AES, or 256-bit AES.

摘自: man sshd

6 Tips

6.1 RSA算法、Diffie-Hellman算法及DSA算法在应用上的比较

Table 3: RSA算法、Diffie-Hellman算法及DSA算法在应用上的比较
算法 加密或解密 数字签名 密钥交换
RSA Y Y Y
Diffie-Hellman N N Y
DSA N Y N

注:RSA算法用于加密或解密可参考图 3,用于数字签名可参考图 6,用于密钥交换可参考图 8


Author: cig01

Created: <2012-01-03 Tue 00:00>

Last updated: <2018-01-26 Fri 20:59>

Creator: Emacs 25.3.1 (Org mode 9.1.4)