什么是公钥密码
公钥密码（Public-key cryptography）也称非对称式密码（Asymmetric cryptography）是密码学的一种算法，它需要两个密钥，一个是公开密钥，另一个是私有密钥；公钥用作加密，私钥则用作解密。使用公钥把明文加密后所得的密文，只能用相对应的私钥才能解密并得到原本的明文，最初用来加密的公钥不能用作解密。由于加密和解密需要两个不同的密钥，故被称为非对称加密；不同于加密和解密都使用同一个密钥的对称加密。公钥可以公开，可任意向外发布；私钥不可以公开。
security_asymmetric
公钥密码的历史
1976年以前，所有的加密方法都是同一种模式:加密和解密使用同样的规则。
1976年，由惠特菲尔德·迪菲（Bailey Whitfield Diffie）和马丁·赫尔曼（Martin Edward Hellman）在1976年首次发表 迪菲-赫尔曼密钥交换。
1977年，Ralph Merkle和Martin Hellman 共同设计了一种具体的公钥密码算法--Knapsack。
1978年，罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）共同发表了一种公钥密码算法--RSA。
RSA 可以说是现在公钥密码的事实标准。
什么是密钥配送问题
在对称密码中，由于加密和解密的密钥是相同的，因此必须向接收者配送密钥。由于解密的密钥必须被配送给接收者，在传输中的过程中存在着被窃听的问题，这一问题称为密钥配送问题。
解决密钥配送问题的方法有以下几种：
- 通过事先共享密钥来解决
- 通过密钥分配中心来解决
- 通过 迪菲赫尔曼（Diffle-Hellman ）密钥交换 来解决
- 通过 公钥密钥 来解决
公钥通信的流程
非对称加密解决密钥分发的问题
所示的安全消息交换具有以下步骤：
- Alice 使用其中一种公钥算法来生成一对加密密钥：他们保密的私钥和公钥。他们还准备发送给 Bob 的消息。
- Alice 将未加密的公钥发送给 Bob。因为他们的私钥不能从公钥中推导出来，所以这样做不会以任何方式损害他们的私钥。
- Alice 现在可以轻松地向 Bob 证明他们的身份（这个过程称为身份验证）。为此，他们使用他们的私钥加密他们的消息（或消息的任何部分）并将其发送给 Bob。
- Bob 使用 Alice 的公钥解密消息。这证明消息一定来自 Alice，因为只有他们拥有用于加密它的私钥。
- Bob 使用 Alice 的公钥加密他们的消息并将其发送给 Alice。消息是安全的，因为即使它被截获，除了 Alice 之外没有人拥有解密它所需的私钥。
Alice 用他们的私钥解密消息。
公钥密码的优缺点
优点
- 可以解决密钥配送问题，破解难度较大
缺点
- 处理速度只有对称密码的几百分之一
RSA
什么是 RSA
RSA 是世界第一个广泛使用的公钥算法，可以被用于公钥密码和数字签名。RSA公开密钥密码体制的原理是：根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。它的强度被认为与分解一个非常大的数字的难度有关。以现代数字计算机的当前和可预见的速度，在生成 RSA 密钥时选择足够长的素数应该使该算法无限期地安全。但是，这种信念尚未在数学上得到证明，并且可能有一种快速分解算法或一种完全不同的破解 RSA 加密的方法。
相关数学原理
-
互质关系
如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。
-
欧拉函数
在数论，对正整数n，欧拉函数是小于等于n的正整数中与n互质的数的数目，以
表示。
特殊地，如果 n 可以分解成两个互质的整数之积，则
-
费马小定理
假设 正整数 a 与质数 n 互质，因为质数 φ(n) = n - 1，则：
-
模反元素
如果两个正整数 a 和 n 互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说 ab 被 n 除的余数是 1。
这时，b 就叫做 a 的 模反元素 。
欧拉定理可以用来证明模反元素必然存在。
可以看到a^{φ(n) - 1} 就是 a 的模反元素
ab = 1
生成密钥对
-
求 N
首先需要通过伪随机数生成器生成两个很大的质数 p 和 q，准备好两个很大的质数后，将这两个质数相乘得到 N。 -
根据欧拉函数，可得 φ(N) = ()
-
求 E
E 是 一个比 1大，比 L 小的数，此外，E 和 L 的最大公约数必须为 1。则 E 和 L 之前存在下列关系：
-
求 D
数 D 是 由 数 E 计算得到的，D、 E 和 L之前必须具备下列关系：
算法描述
-
任意选取两个不同的大素数 p 和 q，计算乘积 N
-
计算 N 的欧拉函数 φ(N)，则 :
，由于 p 和 q 都为质数，则
。
-
随机选择一个整数 E，条件是 1< E < φ(N)，且 E 与 φ(N) 互质。
-
由于 E 与 φ(N)互质，根据模反元素求得 D
-
将 N 和 E 封装成公钥，N 和 D 封装成私钥。
-
将明文M（M < N 是一个整数）加密成密文C，加密算法
-
将密文c解密为明文m，解密算法为
然而只根据 N 和 E（注意：不是p和q）要计算出 d 是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道D）才可对密文解密。
RSA 的加解密
其他公钥算法
RSA 是现在最为普及的一种公钥密码算法，但是除了 RSA之外还有其他的公钥密码，基于与 RSA 等效复杂度的不同数学，包括 ElGamal 加密、Rabin 方式 和椭圆曲线加密。
ElGamal
在密码学中，ElGamal 加密算法是一个基于迪菲-赫尔曼密钥交换的非对称加密算法。它在1985年由塔希尔·盖莫尔（Taher ElGamal）提出。ElGamal加密算法利用了 求离散对数的困难数。
Rabin
Rabin 利用了 下平方根的困难度
椭圆曲线密码
椭圆曲线密码是通过将椭圆曲线上的特定点进行特殊的乘法运算实现，它利用了这种乘法运算的逆运算非常困难这一特性。它的特点是所需的密钥长度比 RSA 短。
网友评论