利用非对称密码技术加密数据

非对称密码算法又称为公开密钥算法，是在1976年由Diffie和Hellman在其《密码学的新方向》一文中提出的，该算法有效解决了对称密码算法存在的一系列问题。

【任务描述】

在非对称密码中，Alice使用Bob的公钥加密，Alice发送机密信息给Bob，Bob收到加密信息后，Bob使用自己的私钥解密，如图3-38所示。

图3-38　非对称密码加解密

雅鹿公司电商专员小王需要详细了解非对称密码的加解密原理。请帮助小王完成这一任务。

【任务分析】

此任务涉及非对称密码的加解密过程。非对称加密算法需要两个密钥进行加密和解密，一个密钥是公钥，另一个密钥是私钥。

【知识准备】

1.基本概念

1）公开密钥基础设施PKI

公开密钥基础设施PKI是一种遵循既定标准的密钥管理平台。它能够为所有网络应用提供加密和数字签名等服务及所必需的密钥和证书管理体系，为用户建立一个安全的网络运行环境。

2）数字信封

数字信封技术使用两层加密体系，结合了对称密码算法和非对称密码算法的优点，既利用了对称密码算法运算速度快的优点，又利用了非对称密码算法保密性高的优点。

数字信封的作用是分发对称密钥。在数字信封中，信息发送方采用对称密钥来加密信息内容，然后将此对称密钥用接收方的公开密钥加密之后，将它和加密后的信息一起发送给接收方，接收方先用相应的私钥打开数字信封，得到对称密钥，然后使用对称密钥解开加密信息。

数字信封具有一定的局限性，信息发送方和接收方必须确保密钥的安全传输，以保证数字信封的有效使用。

3）数字摘要

数字摘要是将任意长度的消息变成固定长度的短消息，它类似于一个自变量是消息的函数，也就是Hash函数。数字摘要就是采用单向Hash函数将需要加密的明文“摘要”成一串固定长度（128位）的密文，这一串密文又称为数字指纹。它有固定的长度，而且不同的明文“摘要”成密文，其结果总是不同的，而同样的明文其“摘要”结果必定一致。

4）数字签名

数字签名技术有效保证了信息的完整性、有效性、安全性和不可抵赖性。信息的发送方用私钥对数字摘要加密，从而形成发送方的数字签名。

2.非对称密码技术的常用算法

非对称密码系统是一种公开密钥的密码系统，要求密钥成对使用，即加密和解密分别由两个密钥来实现，每个用户都有一对密钥。其典型算法有RSA算法、SHA-1算法、MD5算法等。

1）SHA-1算法

SHA-1算法也属于单向散列算法，是一种生成信息摘要的算法。SHA-1算法可以从明文生成160位的信息摘要。

例如，给定明文“abcd”，生成的SHA-1摘要为

81FE8BFE87576C3ECB22426F8E57847382917ACF

SHA-1算法可以保证信息的完整性，因为单向散列算法不能够由信息摘要反推出原内容。

2）MD5算法

MD5算法也属于单向散列算法，能将任意大小的数据映射到一个较小的、固定长度的唯一值。加密值强的散列一定是不可逆的。散列同时也具备了防冲突的特性，MD5算法比SHA-1算法的运行速度大约快33%。

3.非对称密码学基础

对于传统对称密码而言，密文的安全性完全依赖于密钥的保密性，一旦密钥泄漏，将毫无保密性可言。由于传统对称密码体制出现了密钥管理的困难，如2 000个用户保密通信，每个人需要保存1 999个密钥[两两保密通信需要共（2 000×19 999）/2＝1×999 000个密钥，每人保管1 999个]，所以在密钥管理分配上有困难。

非对称密码解决了上述问题，即每个人有一对密钥（公钥和私钥），将公钥公开，私钥自己保管，这样每人只要保管好自己的私钥就可以了。在通信时，使用收信方的公钥进行加密，收信方使用自己的私钥进行解密。在身份认证时，签名者使用私钥签名，验证签名者使用签名者的公钥验签。

非对称密码（公钥密码）体制的特点如下：

（1）公钥的公开特性。在非对称密码体制中，公钥是公开的，只有私钥是需要保密的。

（2）私钥的保密特性。在非对称密码体制中，只要保障私钥是安全的，那么加密就是可信的。由公钥和密码算法推测出私钥，这在计算上是不可行的。

（3）公钥密码的非对称特性。在非对称密码体制中，可使用两个独立的密钥。

（4）公钥算法的安全性基于难解可计算问题。在非对称密码体制中，公钥算法是基于数学函数而不是基于代替和置换。在近代非对称密码系统的研究中，其安全性都是基于难解的可计算问题，如大数分解问题和计算有限域的离散对数问题等。

4.传统密码和公钥密码的区别

传统密码和公钥密码的区别如表3-6所示。

表3-6　传统密码和公钥密码的区别

对称加密与非对称加密的区别如表3-7所示。

表3-7　对称加密与非对称加密的区别

【任务实施】

1.了解RSA算法的原理

1）RSA算法的由来

1977年，罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出了RSA算法。当时他们三人都在麻省理工学院工作实习。RSA就是他们三人姓氏开头字母拼在一起组成。RSA能同时用于加密和数字签名的非对称密码算法，被ISO推荐为公钥数据加密标准。

2）RSA算法的理论基础

1987年7月，美国首次公布RSA算法，该算法的理论基础是大数分解和素数检测。RSA算法基于一个简单的数论事实：将两个大数相乘容易，但是想要对其乘积进行质因子分解却极其困难，因此可以将其乘积公开作为加密密钥。例如，计算7 817和7 333的乘积很容易，但反过来计算一个大数的质因子就很困难，例如，对于57 322 061这个大数来说，不能轻而易举地计算出它的两个质因子。

正是由于大数的质因子分解过程非常困难，这种特性被应用非对称密码技术。采用非对称加密机制，发送方发送的信息都采用两个质数的乘积进行加密，只有知道这两个质因子的人才有可能对已经加密的信息进行解密，那些中途窃取信息的人由于不知道用于加密的质因子，所以无法破解信息的内容。非对称密码技术正是通过这一过程来达到保护信息的目的的。

RSA算法的原理是找两个很大的质数，其中一个对外界公开，称为公钥，另一个称为私钥，用公钥加密的密文可以用私钥解密，反之亦然。RSA算法的优、缺点如表3-8所示。

表3-8　RSA算法的优、缺点

3）RSA算法的数学描述

RSA算法的数学描述如下：(www.xing528.com)

（1）选择一对不同的、足够大的质数p，q。

（2）计算n＝pq。

（3）计算f（n）＝（p-1）（q-1），同时对p，q严加保密，不让任何人知道。

（4）找一个与f（n）互质的数e，且1＜e＜f（n）。

（5）计算d，使得de≡1 mod f（n）。这个公式也可以表达为d≡e-1 mod f（n）。

说明：“≡”是数论中表示同余的符号。公式中，“≡”符号的左边必须和右边同余，也就是两边的模运算结果相同。显而易见，不管f（n）取什么值，符号右边1 mod f（n）的结果都等于1；符号的左边d与e的乘积作模运算后的结果也必须等于1。这就需要计算出d的值，让这个同余等式能够成立。

（6）公钥KU＝（e，n），私钥KR＝（d，n）。

（7）加密时，先将明文变换成0～n-1的一个整数M。若明文较长，可先分割成适当的组，然后再进行交换。设密文为C，则加密过程为C≡Me mod n，解密过程为：M≡Cd mod n。

注：如果知道加密算法，从加密密钥得到解密密钥在计算上是不可行的（单向函数的性质）。RSA算法的数学原理如表3-9所示。

表3-9　RSA算法的数学原理

4）RSA算法的安全性

RSA算法是目前最有影响力和最常用的公钥加密算法，它能够抵抗目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。

只要RSA密钥的长度足够长，使用RSA算法加密的信息很难被破解。RSA算法的安全性依赖于大数分解，取决于从公钥（e，n）计算出私钥（d，n）的困难程度。后者等同于从n找出它的两个质因子p和q。因此，n的值越大，其分解难度越大。

RSA实验室认为，512位的n已不够安全，在1997年或1998年后应停止使用，个人应用768位的n，企业应用1 024位的n，极其重要的场合应用2 048位的n。

假设一台计算机一次运算的时间需要1μs，则分解n所需要的时间如表3-10所示。

表3-10　大数质因子分解的运算次数和运算时间

由表3-10可知，随着模n位数的增加，RSA算法的安全性提高，但其加密解密所耗的时间也延长。因此，需根据所保护信息的敏感度、攻击者破解所需要花的代价值不值得系统所要求的反应时间，来综合考虑并决定密钥的长度。在分布式计算和量子计算理论日趋成熟的今天，RSA算法安全性受到了严峻挑战。

2.非对称密码体制的优、缺点

1）非对称密码体制的优点

（1）非对称密码技术与对称密码技术相比，其优势在于不需要共享通用的密钥。

（2）公钥在传递和发布过程中即使被截获，由于没有与公钥匹配的私钥，截获公钥对入侵者没有太大意义。

（3）密钥分配简单。

2）非对称密码体制的缺点

加密算法复杂，加密和解密的速度比较慢。

3.非对称密码的加解密过程

在非对称密码体系中，密钥被分解为一对，即公钥和私钥。这对密钥中的公钥（加密密钥）通过非保密方式向他人公开，而另一把作为私钥（解密密钥）加以保存。公钥用于加密，私钥用于解密。私钥只能由生成密钥的交换方掌握，公钥可广泛公布。非对称密码的加解密过程如图3-39所示。

图3-39　非对称密码的加解密过程

例3.6　在非对称密码体制中，单向函数的构造基于大数n质因子分解的困难，因此n的两个质因子p与q都应取大质数。为了便于理解，选取两个较小的质数来说明该体制。在RSA算法中，质数p＝7，q＝11，已知加密密钥e＝7，计算解密密钥d。

解：

N＝pq＝7×11＝77

φ(n)＝(p-1)(q-1)＝6×10＝60

根据公式d×e≡1mod（p-1）（q-1），又e＝7，所以7×d≡1mod 60，即7d mod 60＝1。7×43＝301

301除以6刚好余1，所以d＝43。

例3.7　在使用RSA算法加密时，已知明文M＝3，公钥是（e＝7，n＝20），私钥是（d＝3，n＝20），求解密文C。

解：

M＝3的加密，根据公式C＝me mod n。

37＝2 187≡7mod 20，求解得到密文C＝7。

【动手做一做】

（1）异或运算练习。

在加解密时，经常使用异或运算，异或（xor）是一个数学运算符，它应用于逻辑运算，数学符号为“⊕”，计算机符号为“xor”。

异或运算法则为：a⊕b＝（¬a∧b）∨（a∧¬b）

如果a、b值不相同，那么异或结果为1；如果a、b值相同，那么异或结果为0。

异或也叫半加运算，其运算法则相当于不带进位的二进制加法。在二进制下用1表示真，用0表示假，则异或运算法则为：0⊕0＝0，1⊕0＝1，0⊕1＝1，1⊕1＝0（同为0，异为1）。

这些法则与加法是相同的，只是不带进位。程序中有3种演算子：XOR、xor、⊕。

使用方法如下：

z＝x⊕y

z＝x xor y

（2）对字符'A'使用密钥7进行异或运算，结果是________。

解：

字符'A'的ASCII编码为65：00000000 01000001；

取整数7：00000000 00000000 00000000 00000111；

异或运算结果：00000000 00000000 00000000 01000110。