入门密码学④非对称加密

2022-03-18 本文已影响0人 _涼城

什么是公钥密码

公钥密码（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 加密的方法。

生成密钥对

求 N
首先需要通过伪随机数生成器生成两个很大的质数 p 和 q，准备好两个很大的质数后，将这两个质数相乘得到 N。
根据欧拉函数，可得 φ(N) = ()
求 E
E 是一个比 1大，比 L 小的数，此外，E 和 L 的最大公约数必须为 1。则 E 和 L 之前存在下列关系：
$1 < E < L gcd(E,L) = 1$
求 D
数 D 是由数 E 计算得到的，D、 E 和 L之前必须具备下列关系：
$1 < D < L E * D \bmod L = 1$

算法描述

任意选取两个不同的大素数 p 和 q，计算乘积 N
计算 N 的欧拉函数 φ(N)，则 : $φ(N) = φ(p)φ(q)$ ，由于 p 和 q 都为质数，则 $φ(N) = (p - 1)(q - 1)$ 。
随机选择一个整数 E，条件是 1< E < φ(N)，且 E 与 φ(N) 互质。
由于 E 与 φ(N)互质，根据模反元素求得 D
$E * D = 1(\bmod φ(N))$
将 N 和 E 封装成公钥，N 和 D 封装成私钥。
将明文M（M < N 是一个整数）加密成密文C，加密算法
$C = E(M) = M^E \bmod N$
将密文c解密为明文m，解密算法为
$M = D(C) = C^D \bmod N$