浅谈非对称加密方式及其应用

李 彬

（湖北第二师范学院 湖北 武汉 430000）

1 非对称加密的概述

1.1 背景

非对称加密是美国学者Dime 和Henman 在1976 年提出的一种新的密钥交换协议，用于解决信息公开传送和密钥管理问题。

1.2 核心原理

非对称加密加、解密信息的过程需使用一组密钥对，称为公钥和私钥。若使用公钥加密信息，则只能使用私钥进行解密，若使用私钥进行加密，则只能使用公钥进行解密。要求公钥公开给其他人，私钥必须由用户保存且保密。并且不能轻易通过公钥推出私钥[1]。

1.3 与对称加密的不同点

对称加密时只有一个密钥，加密和解密的过程都由同一个密钥来完成。这样带来的问题就是：如果将一段信息用密钥加密，那么别人解密这个信息也需要这个密钥。如何将这个密钥在网络上完整地，不泄露地传给对方很难做到。

而非对称加密使用一对密钥，可以将公钥公布给所有人，只需要把私钥保存好就行。若A 要向B 发送信息，那么A 只需要使用B 已经公开的公钥信息，B 收到信息后用自己的私钥就能解开信息。

2 非对称加密的原理

（1）生成密钥对使用的算法一般使用RSA 算法生成密钥对，一般基于下面两个数论上的事实：

i.已有确定一个整数是不是质数的快速概率算法。

ii.尚未找到确定一个非常大的合数的质因数的快速算法。

目前，虽然还未找到高效的素性检测方法，但是已经有了一些随机算法能够用于素性检测以及因数分解[2]。以下描述的MillerRabin 算法就是这样的一种方法：

（2）Miller-Rabin 算法：

引理1（费马定理）设p 是素数，a 为整数，且（a,p）=1，则ap-1 ≡1（modp）。

证明：考虑1,2,3……（p-1）这p-1 个数字，给它们同时乘上a，得到a,2a,3a……（p-1）a。

∵a ≠b（modp）,（c,p）=1

∴ac ≠bc（modp）

∴1x2x3……（p-1）≡a.2a.3a……（p-1）a（modp）

∴（p-1）!≡（p-1）!ap-1（modp）

∵（（p-1）!,p）=1

∴ap-1 ≡1（modp）

引理2（二次探测定理）如果p 是一个素数，且0[x[p,则方程χ2≡1（modp）的解为χ=1，p-1。

证明：易知χ2≡0（modp）

∴（χ+1）（χ-1）≡0（modp）

∴p|（χ-1）（χ+1）

∵p 为质数

∴χ=1 或者χ=p-1

总之，若n 是素数，则a^m ≡1（modn）,或存在0 ≤r ≤q-1，使a^（2r·m）≡n-1（modn）。

由上面的分析可知，素数一定通过Miller 测试。所以，如果n 不能通过Miller 测试，则n 一定是合数；如果n能通过Miller 测试，则n 很可能是素数。这就是Miller-Rabin 算法。

可以证明Miller-Rabin 算法给出的错误结果的概率小于等于1/4。若反复测试k次，则错误概率可降低至（1/4）^k。这仅仅只是一个大概的保守估计，在实际操作过程中效果会更加突出，更加高效。

（3）生成密钥对的过程：

1）首先，使用Miller-Rabin 算法生成两个大的素数p，q，且p，q 是保密的。

2）计算n=pq 和ψ（n）=（p-1）（q-1）,其中ψ（n）是保密的。

3）选择一个随机数e（0 ＜e ＜ψ（n）），使得（e，ψ（n））=1，即e 和ψ 互素。

4）计算得到d，使得dxemodψ（n）=1，即在与n 互素的数中选取与ψ（n）互素的数。

5）其中私钥是d，公钥是（e，n）。

3 非对称加密的应用

若A 用户想要向B 用户发送一个邮件，那么他需要先用邮件内容生成一个MD5 值，然后再将时间戳和MD5 值和其他某些标记一起用私钥加密成数字签名。

假设C 用户将邮件内容篡改，那么B 用户通过对比邮件内容MD5 以及用A 用户公钥解密的数字签名内的MD5 值就能发现内容被篡改过。即满足i 特性。

若该消息可以通过A 用户的公钥解密数字签名，那么该数字签名一定是由A 的私钥加密，若A 的私钥没有泄漏，且MD5 值相同，那么就可以证明该消息一定是A 发出的。即满足ii 和iii 特性。

若将A 文件的数字签名放到B 文件上，则可以通过对比MD5 值来判断签名和文件是否是对应的。

（1）发送邮件的完整过程：若A 用户想要向B 用户发送一个邮件，那么他需要先用邮件内容生成一个MD5 值，然后再将时间戳和MD5 值和其他某些标记一起用私钥加密成数字签名。然后将邮件内容和数字签名一起用B 的公钥加密成密文发送给B。B 收到消息后，先用自己的私钥解密成邮件内容和数字签名，再用A 的公钥解密数字签名得到MD5。通过对比邮件内容的MD5 和数字签名的MD5 是否相同可以检测出邮件内容有没有被篡改[3]。

（2）发送公开声明的完整过程：若A 想发送一个公开声明，那么他需要先用声明内容生成一个MD5 值，然后再将时间戳和MD5 值和其他某些标记一起用私钥加密成数字签名，然后加在声明的后面发送出去。其他用户收到这份声明，可以用A 用户的公钥验证数字签名的MD5 值和声明内容的MD5 值是否相等来判断这份声明是否是A 发出的。